数学史 · 中文镜像

数学家传记

迪杰斯特拉Edsger W. Dijkstra

出生
1930年5月11日 荷兰鹿特丹
逝世
2002年8月6日 荷兰纽南

迪杰斯特拉是一位荷兰数学家和计算机科学家,以图论中的最短路径算法最为著名。

完整传记

迪杰斯特拉的父母是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基金会的:-

……表彰他通过在基础软件理论、算法理论、结构化编程和信号量方面的创造性研究,为建立计算机软件的科学基础所做的开创性贡献。

参考文献

正文里的方括号编号指向这里,悬停即可直接看到条目。书目保留原文——译了书名反而查不到文献。

延伸资源

原站列出的延伸阅读与外部数据库,照原样保留,目标多为英文页面。