Edsger Wybe Dijkstra
1 提出“goto有害论”;
2 提出信号量和PV原语;
3 解决了有趣的“哲学家聚餐”问题;
4 最短路径算法(SPF)的创造者;
5 第一个Algol 60编译器的设计者和实现者;
6 THE操作系统的设计者和开发者;
与D. E. Knuth并称为我们这个时代最伟大的计算机科学家的人。
在与癌症进行了多年的斗争之后，伟大的荷兰计算机科学家Edsger Wybe Dijkstra已经于2002年8月6日在荷兰Nuenen自己的家中与世长辞！享年72岁。
中文介绍：
Edsger Wybe Dijkstra介绍
本文转载自“http://emilmatthew.51.net/computerScience/scientist/dijkstra/index1.htm“ Edsger Wybe Dijkstra是计算机先驱之一，他开发了程序设计的框架结构。 他的早年经历 Edsger Wybe Dijkstra于1930年5月11日生于Rotterdam，他的父亲，Douwe Wybe Dijkstra是一位化学家，他的母亲，Brechtje Cornelia Kruyper是一位数学家，这种充满科学气息的家庭背景对于他的职业生涯乃至他的整个人生都有着深刻的影响。Edsger Wybe Dijkstra在当地的Gymnasium Erasmianum读高中，1948年，他考入了Leyden大学。他在联合国从事法律方面的工作时却在怀念在Erasmianum的日子，现在，他选择了数学和物理。 首次体验程序设计 Edsger Wybe Dijkstra在三年之内取得了学士学位，这令他的父亲非常高兴，并在1951年9月同意他去英国参加一个夏季的课程，那是一个由剑桥大学开设的，学习电子计算装置程序设计的课程，讲师是著名的M. V. Wilkes。Edsger Wybe Dijkstra的导师让他给Amsterdam数学中心计算部门的主管Aad van Wijngaarden写一封信，以确定他的基础知识是否足够他去完成该学业。 在那一年前，Van Wijngaarden曾在剑桥学习过，他很快便回复了，信的内容有两点，一是肯定Dijkstra现有的知识已经足够了，而是请他来Amsterdam作为一名程序设计人员为自己工作。 对于Dijkstra来说，当时还是一名学生，而他在1951年夏季Wilkes所授的学业成为了他日后职业生涯的基础。 在数学中心的“自由阶段” 在没有任何相关知识的情况下，Dijkstra的程序设计生涯开始于改写突变程序和输入Van Wijngaarden已经写好的程序。Van Wijngaarden允许他这样做，这些程序是为MC第一台计算机ARRA I开发的，由C.S. Scholten和J. Loopstra设计完成。 MC计算部门夜以继日的工作，去解决有关那些在Netherland开发的大的方案中为数众多的难题。例如关于Zeeland州安全问题的DELTA计划。 另外一个较大的工程是Fokker友谊飞机的开发，其机翼振动的计算结果需要MC尽最大的能量。 1953年Gerrit Blaauw加入了MC的队伍。第一台ARRA II 构造完成，由于这台机器的可靠性，Fokker飞机公司又订了一台类似的计算机，叫做FERTA。FERTA的速度是ARRA II 的两倍，而且用一套不同类型的代码。Dijkstra为这些机器都研制开发了软件，也包括其后1956年的ARMAC，那也是为MC开发的最后一台计算机。 在完成了FERTA之后，Gerrit Blaauw去往美国为IBM工作，在那里，他从事IBM7030“Stretch”的开发工作，并最终设计和建造了IBM 360系统。 新的挑战：Electrologica 由于巨大、精于计算的机器的开发以走上正轨，Dijkstra, Scholten 和Loopstra又以完成了下一台计算机的准备工作，1956年，MCmanagement和人寿保险公司Nillmij决定成立一个独立的公司：Electrologica，来经营商业电脑。 因此，Electrologica立即开始研发其第一台品牌机器：the Electrologica X1。 崭新的计算机语言：ALGOL 1952至1956年间，程序设计经历了一个演变的过程，这部分是由于系统分组的复杂性要求一个更具结构性的操作系统，部分是由于科学、数学上的关于程序设计的态度都提出了一个清楚的关于如何提高工作效率的观点。Dijkstra的Shortest Path Algorithm是在这方面取得的突出进展，因为这种演变是全球性的，所以，在全世界的推动下，一个科学的计算机语言基础：ALGOL，不久就诞生了。 1958年，Edsger Dijkstra代表Dutch MC出席了11月在Mainz召开的会议，那是一个定义ALGOL详述的准备会议。1959年12月，Dijkstra给ALGOL60下了这样的定义：“一个奇迹就被这样简单的创造了。”最后，1962年的4月，罗马公约同意了其大部分的详述，同年8月，IFIP，国际程序设计语言联盟复查并批准了该报告。 1960年的1月，在ALGOL60被定义之后，数学中心首先在荷兰开设了ALGOL60程序设计语言的课程，接着，1961年在英国的Brighton。这是MC一个新的开端：程序设计教育。 TH Eindhoven：机会与欺骗 1962年，Edsger Dijkstra在TH Eindhoven任全职教授，虽然在国外已经被认为是计算机科学的主席，但Dijkstra强烈反对这个方法，这主要是由于在专业科学知识上的缺乏。他的位置实际上是一个数学教授，他的学生接受了至少三年彻底的数学教育，经过这样一个时期，他们都能作为信息学方面的专家了。那些数学训练是以应用数学原理为基础的。由此，信息学有了适合其学科本身的数学方法。 1967年，Dijkstra陷入了情绪上的危机，他第一个学生的论文被他在Eindhoven数学上的同事拒收了，而这些同事对于计算机科学一直是带有偏见的。对于他和他的妻子来说，那段不景气的日子是他们一生中最困难的时期。但是他很快有恢复了，并开始投入编写：结构化编程笔记。 而Dijkstra在Eindhoven的同事对此不是保持沉默，就是完全消极的反应，但Dijkstra选择了正确的还击方式：他给欧洲和美国的同事们复印了20多份稿件。 Burroughs和彻底的自由 1973年，Dijkstra成为了Burroughs的研究员，他减少了在Eindhoven TH的工作。这个决定使他能够去写科学报告，他为Burroughs写了500多篇，还可以如愿的出国旅行。他成了一个自由人，而且拥有该公司最小的实验室：他的书房。 Austin：新纪元的起点 Dijkstra在旅行途中多次有机会参观在Austin的得克萨斯州立大学，在那里他还做过几次讲座。1984年，他有了一个担任那里计算机科学学院的全职教授的机会，他觉得他在那里会感到像家一样，于是他和他的妻子搬到美国居住。这便开始了他15年的教学生活：编写、讨论程序设计技术。除此以外，整个美国的好客给他和他的妻子都留下了深刻的印象。 得克萨斯州立大学：超型计算机 1999年，Dijkstra在他69岁的时候，结束了作为教授的职业生涯。回顾47年的艰苦工作，为了一个更好、更简单、更准确的编程方法而不停地努力奋斗，使“符号、说明清楚”。Dijkstra认为最具价值的是他对学生的教导，而且能够向人们展示这项工作可以做的比他们所知或所想象的更加出色。能够做到吸引他人，已经成为了他最有收获的活动。 “对于我来说，计算机科学上的第一个挑战是如何把命令维持在有限个内，然而巨大的、分立的宇宙是复杂地缠绕着的。第二个也是同样重要的挑战是如何传授解决那第一个问题的方法：只培养你个人的才智（那会随你进入坟墓的东西）是不够的，你必须教会其他人如何去发挥他们的才智。你越关注这两个挑战，你越会清楚的看到它们只不过是同一枚硬币的两个面：自学是去发现什么东西是可以被教会的。” （"My hopes to Computer Science") Edsger Wybe Dijkstra因患癌症于2002年8月6日在Nuenen, The Netherlands逝世 。
英文介绍：
E. W. Dijkstra -第七届(1972年)图灵奖得主
1972 – E. W. Dijkstra
Background
The working vocabulary of programmers everywhere is studded with words originated or forcefully promulgated by E.W. Dijkstra - display, deadly embrace, semaphore, got-to-less programming, structured programming. But his influence on programming is more pervasive than any glossary cna possibly indicate. The precious gift that this Turing Award acknowledges is Dijkstra's style: his approach to programming as a high, intellectual challenge; his eloquent insistence and practical demonstration that programs should be composed correctly, not just debugged into correctness; and his illuminating perception of problems at the foundations of program design. He has published about a dozen papers, both technical and reflective, among which are especially to be noted his philosophical address at IFIP, his already classic papers on cooperating sequential processes, and his memorable indictment of the go-to statement. An influential series of letters by Dijkstra have recently surfaced as a polished monograph on the art of composing programs. We have come to value good programs in much the same way as we value good literature. And at the center of this movement, creating and reflecting patters no less beautiful than useful, stands E.W. Dijkstra.
[Extract from the Turing award Citation ready by M.D. McIlroy, chairman of the ACM Turing Award Committee, at the presentatiion of his lecture on August 14, 1972, at the ACM Annual Conference in Boston.]
Biographical Information
Edsger Wybe Dijkstra (Rotterdam, May 11, 1930 – Nuenen, August 6, 2002) was a Dutch computer scientist.
Dijkstra studied theoretical physics at the University of Leiden. He worked as a research fellow for Burroughs Corporation in the early 1970s. He worked at the Eindhoven University of Technology in the Netherlands and later held the Schlumberger Centennial Chair in Computer Sciences at the University of Texas at Austin, in the United States. He retired in 2000.
Among his contributions to computer science are the shortest path-algorithm, also known as Dijkstra's algorithm. He received the Turing Award in 1972.
He was also known for his low opinion of the GOTO statement in computer programming, culminating in the 1968 article Go To Statement Considered Harmful (http://www.acm.org/classics/oct95/), regarded as a major step towards the widespread deprecation of the GOTO statement and its effective replacement by control structures such as the while loop. The paper's famous title was not the work of Dijkstra, but of Niklaus Wirth, then editor of Communications of the ACM. Dijkstra was known to be a fan of ALGOL 60, and worked on the team that implemented the first compiler for that language. Dijkstra and Jaap Zonneveld, who collaborated on the compiler, agreed not to shave until the project was completed. Zonneveld eventually shaved off his beard, Dijkstra had kept his ever since.
Since the 1970s, Dijkstra's chief interest was formal verification. The prevailing opinion at the time was that one should first write a program and then provide a mathematical proof of correctness. Dijkstra objected that the resulting proofs are long and cumbersome, and that the proof gives no insight as to how the program was developed. An alternative method is program derivation, to "develop proof and program hand in hand." One starts with a mathematical specification of what a program is supposed to do and applies mathematical transformations to the specification until it is turned into a program that can be executed. The resulting program is then known to be correct by construction. Much of Dijkstra's later work concerns ways to streamline mathematical argument.
Dijkstra was known for his forthright opinions on programming, and for his habit of carefully composing manuscrīpts with his fountain pen. Many of his notes have since been scanned and are available online.
He died on August 6, 2002 after a long struggle with cancer.
【附】Grady Booch对Dijkstra的介绍
> Professor Edsger Wybe Dijkstra, a noted pioneer of the science and
> industry of computing, died after a long struggle with cancer on 6
> August 2002 at his home in Nuenen, the Netherlands.
>
> Dijkstra was born in 1930 in Rotterdam, The Netherlands, the son of a
> chemist father and a mathematician mother. He graduated from the
> Gymnasium Erasmianum in Rotterdam and obtained degrees in mathematics
> and theoretical physics from the University of Leyden and a Ph.D. in
> computing science from the University of Amsterdam. He worked as a
> programmer at the Mathematisch Centrum, Amsterdam, 1952-62; was
> professor of mathematics, Eindhoven University of Technology,
> 1962-1984; and was a Burroughs Corporation research fellow, 1973-1984.
> He held the Schlumberger Centennial Chair in Computing Sciences at the
> University of Texas at Austin, 1984-1999, and retired as Professor
> Emeritus in 1999.
>
> Dijkstra is survived by his wife of over forty years, Maria (Ria) C.
> Dijkstra Debets, by three children, Marcus J., Femke E., and computer
> scientist Rutger M. Dijkstra, and by two grandchildren.
>
> Dijkstra was the 1972 recipient of the ACM Turing Award, often viewed
> as the Nobel Prize for computing. He was a member of the Netherlands
> Royal Academy of Arts and Sciences, a member of the American Academy
> of Arts and Sciences, and a Distinguished Fellow of the British
> Computer Society. He received the 1974 AFIPS Harry Goode Award, the
> 1982 IEEE Computer Pioneer Award, and the 1989 ACM SIGCSE Award for
> Outstanding Contributions to Computer Science Education. Athens
> University of Economics awarded him an honorary doctorate in 2001. In
> 2002, the C&C Foundation of Japan recognized Dijkstra "for his
> pioneering contributions to the establishment of the scientific basis
> for computer software through creative research in basic software
> theory, algorithm theory, structured programming, and semaphores".
>
> Dijkstra is renowned for the insight that mathematical logic is and
> must be the basis for sensible computer program construction and for
> his contributions to mathematical methodology. He is responsible for
> the idea of building operating systems as explicitly synchronized
> sequential processes, for the formal development of computer programs,
> and for the intellectual foundations for the disciplined control of
> nondeterminacy. He is well known for his amazingly efficient shortest
> path algorithm and for having designed and coded the first Algol 60
> compiler. He was famously the leader in the abolition of the GOTO
> statement from programming.
>
> Dijkstra was a prodigious writer. His entire collection of over
> thirteen hundred written works was digitally scanned and is accessible
> at http://www.cs.utexas.edu/users/EWD. He also corresponded regularly
> with hundreds of friends and colleagues over the years --not by email
> but by conventional post. He strenuously preferred the fountain pen to
> the computer in producing his scholarly output and letters.
>
> Dijkstra was notorious for his wit, eloquence, and way with words,
> such as in his remark "The question of whether computers can think is
> like the question of whether submarines can swim"; his advice to a
> promising researcher, who asked how to select a topic for research:
> "Do only what only you can do"; and his remark in his Turing Award
> lecture "In their capacity as a tool, computers will be but a ripple
> on the surface of our culture. In their capacity as intellectual
> challenge, they are without precedent in the cultural history of
> mankind."
>
> Dijkstra enriched the language of computing with many concepts and
> phrases, such as structured programming, separation of concerns,
> synchronization, deadly embrace, dining philosophers, weakest
> precondition, guarded command, the excluded miracle, and the famous
> "semaphores" for controlling computer processes. The Oxford English
> Dictionary cites his use of the words "vector" and "stack" in a
> computing context.
>
> Dijkstra enjoyed playing Mozart for his friends on his Boesendorfer
> piano. He and his wife had a fondness for exploring state and national
> parks in their Volkswagen bus, dubbed the Touring Machine, in which he
> wrote many technical papers.
>
> Throughout his scientific career, Dijkstra formulated and pursued the
> highest academic ideals of scientific rigour untainted by commercial,
> managerial, or political considerations. Simplicity, beauty, and
> eloquence were his hallmarks, and his uncompromising insistence on
> elegance in programming and mathematics was an inspiration to
> thousands. He judged his own work by the highest standards and set a
> continuing challenge to his many friends to do the same. For the rest,
> he willingly undertook the role of Socrates, that of a gadfly to
> society, repeatedly goading his native and his adoptive country by
> remarking on the mistakes inherent in fashionable ideas and the
> dangers of time-serving compromises. Like Socrates, his most
> significant legacy is to those who engaged with him in small group
> discussions or scientific correspondence about half-formulated ideas
> and emerging discoveries. Particularly privileged are those who
> attended his reading groups in Eindhoven and Austin, known as the
> "Tuesday Afternoon Clubs".
>
> At Dijkstra's passage, let us recall Phaedo's parting remark about
> Socrates: "we may truly say that of all the men of his time whom we
> have known, he was the wisest and justest and best."
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
艾兹格·W·迪科斯彻 （Edsger Wybe Dijkstra，1930年5月11日~2002年8月6日） 荷兰计算机科学家，毕业就职于荷兰Leiden大学，早年钻研物理及数学，而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖，之后，他还获得过1974年AFIPS Harry Goode Memorial Award、1989年ACM SIGCSE计算机科学教育教学杰出贡献奖、以及2002年ACM PODC最具影响力论文奖。
曾经提出“goto有害论”信号量和PV原语，解决了有趣的“哲学家聚餐”问题。于2002年8月6日在荷兰Nuenen自己的家中与世长辞。终年72岁。
艾兹格·W·迪科斯彻在离散数学中的贡献包括：
提出了目前离散数学应用广泛的最短路径算法(Dijkstra's Shortest Path First Algorithm)
迪克斯加（Dijkstra）算法(最短路径算法)是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中任意两个顶点之间的最短路径问题。
举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。 迪科斯彻算法可以用来找到两个城市之间的最短路径。
迪科斯彻算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 我们以E所有边的集合，而边的权重则由权重函数w: E → [0, ∞]定义。 因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径
这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，源点s的路径长度值被赋为0（d[s]=0）， 同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]= ∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到v的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到u的路径。这条路径的长度是d+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d达到它最终的值的时候每条边(u,v)都只被拓展一次。
算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。
