数学家传记
迪杰斯特拉是一位荷兰数学家和计算机科学家,以图论中的最短路径算法最为著名。
迪杰斯特拉的父母是Douwe Wybe迪杰斯特拉和Brechtje Cornelia Kluijver(或Kluyver);他是他们四个孩子中的第三个。他的父亲在鹿特丹的高中教化学,而他的母亲虽然从未有过正式职位,却受过数学家的训练。迪杰斯特拉后来写到母亲对他的数学影响[9]:-
……她在处理公式方面极为敏捷,并且有一种发现非常优雅解法的奇妙天赋。
他在鹿特丹上高中,在学校的最后几年里,他决定要学习法律。他的抱负是在联合国代表荷兰,并觉得法律学位是迈向这一目标的第一步。他于1948年参加了学校毕业考试,在数学、物理、化学和生物方面都取得了最高分。此时,鉴于他在理科科目上的出色表现,他的父母和老师都试图说服他从事科学事业。他随后决定学习理论物理,作为迈向这一目标的第一步,他前往莱顿大学修读数学和物理课程。他的打算是,在这些科目上打下良好基础之后,再转向理论物理。
1951年,迪杰斯特拉的父亲看到一则广告,内容是当年9月将在英国剑桥大学开设为期三周的计算机编程课程。他觉得能够给计算机编程对理论物理学家来说是一项很好的技能,于是报名参加了这门课程[5]:-
那是一次令人恐惧的经历:那是我第一次离开荷兰,第一次不得不听懂说英语的人,而且立刻就只有我一个人,努力跟上一门关于全新主题的课程。但我非常喜欢它。
阿德·范·维恩加登,时任阿姆斯特丹数学中心计算部主任,前一年在剑桥也修了同样的课程。当他得知迪杰斯特拉已完成该课程时,便向他提供了一个数学中心程序员职位。迪杰斯特拉从1952年3月起接受了这一职位,但仅作为兼职,因为他仍在莱顿大学注册为理论物理学生。他说[5]:-
……在55年,经过三年的编程工作,当时我仍是学生,我得出结论,编程的智力挑战大于理论物理的智力挑战,因此我选择了编程……我与范·维恩加登交谈……并解释了我的困境,即如果成为程序员,我就得离开科学。……他说他同意计算机编程中不存在明确的科学成分,但我很可能正是被召唤使其成为科学的人之一。
做出决定后,迪杰斯特拉完成了他在大学的理论物理学业,于1956年毕业。同样在1956年,数学中心建成了一台新计算机,并希望进行公开演示[5]:-
……为了向非计算人员演示,你必须有一个非数学家也能理解的问题陈述,甚至他们必须能理解答案。因此,我设计了一个程序,能在荷兰的两个城市之间找到最短路线,使用了一个稍微简化的荷兰地图,在上面我选择了64个城市(这样在编码中,6位就足以识别一个城市)。
他发表了这种最短距离算法,连同他非常高效的最短生成树算法,发表在两页论文A Note on Two Problems in Connexion with Graphs(1959年)中。同样在1959年,他因论文Communication with an Automatic Computer获得了阿姆斯特丹大学的博士学位。
1957年,他与玛丽亚·C·德贝茨结婚;他们有两个儿子和一个女儿。然而,他在婚礼上遇到了一个问题,因为治安法官不接受“程序员”作为职业记录,所以他不得不在表格上填写“理论物理学家”。
计算机语言ALGOL-60由一个国际团队设计,该团队于1958年12月开始工作。迪杰斯特拉是该团队成员,做出了几项重大贡献:递归的明确引入归功于他,在处理递归时,他引入了“栈”的概念,这个词归功于迪杰斯特拉,现在完全是标准术语。迪杰斯特拉与他在数学中心的一位同事一起,编写了ALGOL-60的第一个编译器,于1960年8月完成。迪杰斯特拉回顾时,认为ALGOL-60[5]:-
……作为计算科学的开端;如果我们想标记我们思考计算方式上的一个断裂,那就是ALGOL 60的出现。……例如,它使这一主题在学术上体面起来。
1962年,迪杰斯特拉被任命为埃因霍温理工大学数学教授。当时埃因霍温没有计算机科学系,其他大学当然也没有。他在数学系内组建了一支计算机科学家团队,尽管一些同事有所保留,他还是设法做到了。正是在这个时候,他开发了“THE”操作系统。它以Technische Hogeschool te Eindhoven命名,这是当时埃因霍温理工大学的名称。这个操作系统的许多特性已成为所有未来操作系统的标准特性。
1972年,迪杰斯特拉获得了ACM 艾伦·图灵奖,这被认为是计算机科学中最负盛名的奖项。在接受该奖项时,他发表了The humble programmer 演讲,其中包含了对该学科未来的一系列非凡思考,现在,有了后见之明,我们可以看出这些思考绝对正确。1973年8月,迪杰斯特拉加入宝来公司担任研究员,并被任命为埃因霍温的特别教授[9]:-
他[在宝来]的职责包括每年几次访问公司的一些研究中心,并进行自己的研究,他是在最小的宝来研究设施中进行的,即他在Nuenen家中二楼的书房。那时他已经非常有名,收到了大量在世界各地讲学的邀请。他利用这些访问与其他计算机科学家互动,指导年轻科学家,并提高自己作为英语演讲者的技能。
迪杰斯特拉从1970年代末开始访问位于德克萨斯州奥斯汀的宝来研究中心,在这些访问期间,他逐渐熟悉了德克萨斯大学的计算机科学系。1984年,他获得了奥斯汀的斯伦贝谢百年计算机科学讲席,并欣然接受。他一直在奥斯汀,直到1999年退休。
现在让我们看看迪杰斯特拉出版的一些书。首先我们看Structured programming,这本书包含三篇专著,其中迪杰斯特拉写的是Notes on structured programming (1973年)。C A Ellis和James Reid在评论这本书时写道:-
本书基于并支持这样一个前提:编程是一种智力活动,需要高水平的知识和创造力。这种态度与当前许多从业者的态度形成对比。
在迪杰斯特拉的专著中,他们写道:-
迪杰斯特拉的《结构化编程笔记》以给自己写信的形式写成,为结构化编程进行了雄辩而有力的论证。
迪杰斯特拉 A discipline of programming(1976年)的书中包含C A R Hoare撰写的序言,他写道:-
这本书以作者一贯的优雅风格,阐述了他对计算机编程本质的激进新见解。从这些见解中,他发展出了一系列新的编程方法和符号工具,并在大量优雅而高效的示例中展示和检验。这必将被公认为计算机编程这一智力学科发展中的杰出成就之一。
H Kilov在评论中写道:-
你怀着极大的兴趣看着这本最新的迪杰斯特拉著作。你知道他对编程产生了巨大影响,因此你非常想看到一本阐述一般编程概念的专著(或者我可以称之为教科书?)。你的期望没有落空。
1982年,迪杰斯特拉的Selected writings on computing: a personal perspective出版,收集了他1968年至1979年间撰写的66篇论文,其中大部分此前未曾发表。与卡雷尔·S·斯霍尔滕合著的Predicate calculus and program semantics于1990年出版。弗瑞兹·约翰·C·米切尔写道:-
正如引言中明确指出的,本书有两个主要关注点。一是通过著名的谓词转换器方法研究编程语言语义学。二是特定的形式化表述与证明展开风格。
Van Vlissingen的个人回忆[11]中包含以下内容,它很能说明迪杰斯特拉的性格:-
从更深层的意义上说,迪杰斯特拉的一生都在追求让人思考。让人在动笔之前先思考问题。他很受欢迎,但学生有时既不喜欢他,又——人们会认为是不情愿地——尊敬他,因为他坚持手写论文,不接受文字处理器的输出。他的理由是:通过修改的次数,他可以看出这个人在写之前是否在思考,而他认为这是编程的一项基本技能。因此他身体力行自己所教的,并让学生也这样做。
最后,让我们看看为表彰迪杰斯特拉的杰出贡献而授予他的众多荣誉中的一些。我们在上文提到了1972年颁发的ACM 艾伦·图灵奖。部分引文如下:-
这个艾伦·图灵奖所承认的珍贵礼物是迪杰斯特拉的风格:他将编程视为一项崇高的智力挑战;他雄辩地坚持并实际证明程序应当被正确地构造,而不仅仅是调试到正确;以及他对程序设计基础问题的启发性洞察。
迪杰斯特拉获得的其他奖项和荣誉包括:当选荷兰皇家艺术与科学院会士(1971年);当选英国计算机学会杰出会士(1971年),获得AFIPS哈里·古德纪念奖(1974年),被选为美国艺术与科学院外籍名誉会员(1975年);被贝尔法斯特女王大学授予荣誉理学博士学位(1976年);获得IEEE计算机学会颁发的计算机先驱奖(1982年);获得ACM/SIGCSE计算机科学教育杰出贡献奖(1989年);当选ACM会士(1994年),被希腊雅典大学授予荣誉博士学位(2001年);因其论文Self-stabilizing systems in spite of distributed control获得ACM影响力论文奖(2002年)。他的最后一个奖项是2002年来自日本C&C基金会的:-
……表彰他通过在基础软件理论、算法理论、结构化编程和信号量方面的创造性研究,为建立计算机软件的科学基础所做的开创性贡献。
Edsger Dijkstra's parents were Douwe Wybe Dijkstra and Brechtje Cornelia Kluijver (or Kluyver); he was the third of their four children. His father taught chemistry at the high school in Rotterdam while his mother was trained as a mathematician although she never had a formal position. Dijkstra wrote later of his mother's mathematical influence on him [9]:-
... she had a great agility in manipulating formulae and a wonderful gift for finding very elegant solutions.
He attended High School in Rotterdam and in his final years at school he decided he wanted to study law. His ambition was to represent the Netherlands at the United Nations and felt that a law degree was the first step towards this. He took his final school examinations in 1948, scoring the highest possible marks in mathematics, physics, chemistry, and biology. At this point his parents and his teachers all tried to persuade him to follow a career in science, given his outstanding performance in science subjects. He then decided to study theoretical physics and as a first step towards this he went to the University of Leyden to take courses in mathematics and physics. His intention was, after getting a good grounding in these topics, he would move towards theoretical physics.
In 1951 Dijkstra's father saw an advertisement for a three-week course in computer programming to be given at the University of Cambridge in England in September of that year. Feeling that being able to programme a computer was a good skill for a theoretical physicist to have so he registered for the course [5]:-
It was a frightening experience: it was the first time that I left the Netherlands, the first time I ever had to understand people speaking English and immediately I was all by myself, trying to follow a course on a totally new topic. But I liked it very much.
Aad van Wijngaarden, who was the director of the Computation Department of the Mathematical Centre in Amsterdam, had taken the same course in Cambridge in the previous year and when he learnt that Dijkstra had completed it, he offered him a position as a programmer of the Mathematical Centre. Dijkstra accepted the position from March 1952 but it only as a part-time position for he was still registered as a student of theoretical physics at the University of Leyden. He said [5]:-
... in '55 after three years of programming, while I was still a student, I concluded that the intellectual challenge of programming was greater than the intellectual challenge of theoretical physics, and as a result I chose programming ... I spoke with van Wijngaarden ..., and explained my dilemma that I had to take leave from science if I became a programmer. ... he said he agreed that there was no such thing as a clear scientific component in computer programming, but that I might very well be one of the people called to make it a science.
Having taken the decision, Dijkstra completed his studies in theoretical physics at the university, graduating in 1956. Also in 1956 the Mathematical Centre competed building a new computer and wanted to give a public demonstration [5]:-
... for a demonstration for non-computing people you have to have a problem statement that non-mathematicians can understand, even they have to understand the answer. So I designed a program that would find the shortest route between two cities in the Netherlands, using a somewhat reduced roadmap of the Netherlands, on which I had selected, 64 cities (so that in the coding, 6 bits would suffice to identify a city).
He published this shortest distance algorithm, together with his very efficient algorithm for the shortest spanning tree, were published in the two page paper A Note on Two Problems in Connexion with Graphs (1959). Also in 1959 he was awarded his Ph.D. from the University of Amsterdam for his thesis Communication with an Automatic Computer.
In 1957 he had married Maria C Debets; they had two sons and a daughter. However, he had a problem at his wedding for the Justice of the Peace would not accept 'programmer' as profession for the records, so he had to give 'theoretical physicist' on the form.
The computer language ALGOL-60 was designed by an international team which began work in December 1958. Dijkstra, who was a member of the team, made several major contributions: due to him was the explicit introduction of recursion and in handling recursion he introduced the notion of a 'stack', a word due to Dijkstra which is now totally standard terminology. Dijkstra, together with one of his colleagues at the Mathematical Centre, wrote the first compiler for ALGOL-60 which was completed by August 1960. Dijkstra, in retrospect, regarded ALGOL-60 [5]:-
... as the beginning of computing science; if we wish to mark a discontinuity in the way in which we thought about computing, then that is the emergence of ALGOL 60. ... it has made, for instance, the topic academically respectable.
In 1962 Dijkstra was appointed Professor of Mathematics at the Eindhoven University of Technology. At this time Eindhoven had no Computer Science Department, nor of course did other universities. He built a team of computer scientist within the Mathematics department which he managed to do despite reservations by some colleagues. It was at this time that he developed the 'THE' operating system. It was named after Technische Hogeschool te Eindhoven, the name by which the Eindhoven University of Technology was known at this time. Many features of this operating system have become standard features in all future operating systems.
In 1972 Dijkstra won the ACM Turing Award which is considered the most prestigious award in Computer Science. In accepting the award he gave the address The humble programmer which contains a remarkable collection of thoughts on the future of the subject which now, with the advantage of hindsight, we can now see were absolutely correct. In August 1973 Dijkstra joined Burroughs Corporation as a Research Fellow and was made Professor Extraordinarius at Eindhoven [9]:-
His duties [at Burroughs] consisted of visiting some of the company's research centers a few times a year and carrying on his own research, which he did in the smallest Burroughs research facility, namely, his study on the second floor of his house in Nuenen. He was already very famous by that time, and he received a large number of invitations to lecture throughout the world. He used these visits to interact with other computer scientists, mentor younger scientists, and sharpen his skills as an English speaker.
Dijkstra visited the Burroughs Research Center in Austin, Texas, from the late 1970s and while on these visits he came to know well the Computer Science Department at the University of Texas. In 1984 he was offered the Schlumberger Centennial Chair in Computer Science at Austin and happily accepted. He remained at Austin until he retired in 1999.
Let us now look at some of the books which Dijkstra published. First we look at Structured programming, a book which contains three monographs, the one written by Dijkstra being Notes on structured programming (1973). C A Ellis and James Reid write in a review of the book:-
This book is based upon and supports the premise that programming is an intellectual activity requiring a high level of knowledge and creativity. This attitude is in contrast to that of many current practitioners.
Of the monograph by Dijkstra they write:-
Written in the form of letters to himself, Dijkstra's 'Notes on structured programming' make eloquent and forceful arguments for structured programming.
The book by Dijkstra A discipline of programming (1976) contains a Preface by C A R Hoare who writes:-
The book expounds, in its author's usual cultured style, his radical new insights into the nature of computer programming. From these insights, he had developed a new range of programming methods and notational tools, which are displayed and tested in a host of elegant and efficient examples. This will surely be recognized as one of the outstanding achievements in the development of the intellectual discipline of computer programming.
H Kilov writes in a review:-
You look at this latest Dijkstra book with great interest. You know about his enormous influence on programming, and therefore you are very interested to see a monograph (or may I call it a textbook?) presenting general programming concepts. You are not disappointed in your expectations.
In 1982 Selected writings on computing: a personal perspective by Dijkstra was published which collected together 66 of his papers written between 1968 and 1979, most of which had not previously been published. A joint work with Carel S Scholten, Predicate calculus and program semantics, was published in 1990. John C Mitchell writes:-
As stated clearly in the introduction, this book has two main concerns. One is programming language semantics via the well-known method of predicate transformers. The second is a particular formal style of presentation and proof development.
Van Vlissingen's personal reflection [11] contains the following which says much about Dijkstra character:-
Dijkstra's life in the deeper sense was spent in the pursuit of making people think. Making people think through a problem before they put pen to paper. He was popular, but his students sometimes disliked him as much as they - grudgingly one would think - respected him, because he insisted on handwritten papers and would not accept output from a word processor. His reasoning: by the number of corrections he could see if the person was thinking before they wrote, something he considered an essential skill in programming. So he lived what he taught, and made his students do the same.
Finally let us look at some of the many honours which have been given to Dijkstra in recognition to his outstanding contributions. We have mentioned above the ACM Turing Award made in 1972. Part of the citation reads:-
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.
Other awards and honours to Dijkstra include his election to the Royal Netherlands Academy of Arts and Sciences (1971); elected Distinguished Fellow of the British Computer Society (1971), received the AFIPS Harry Goode Memorial Award (1974), made a Foreign Honorary member of the American Academy of Arts and Sciences (1975); awarded an honorary Doctorate of Science by Queen's University of Belfast (1976); given the Computer Pioneer Award from the IEEE Computer Society (1982); given the ACM/SIGCSE Award for outstanding contributions to computer science education (1989); elected an ACM Fellow(1994), awarded an honorary doctorate by Athens University, Greece (2001); given the ACM Influential Paper Award for his paper Self-stabilizing systems in spite of distributed control (2002). His final award was in 2002 from the C&C Foundation of Japan:-
... 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.
正文里的方括号编号指向这里,悬停即可直接看到条目。书目保留原文——译了书名反而查不到文献。
原站列出的延伸阅读与外部数据库,照原样保留,目标多为英文页面。