小言_互联网的博客

Edsger W. Dijkstra -- 巨人的肩膀

335人阅读  评论(0)

  本文为原创,可能有一些不太严肃的胡说,请勿转载

Dijkstra:宗师、巨星,计算机学科的奠基人之一

  
  牛顿有句名言:“如果我看得比别人更远些,那是因为我站在巨人们的肩膀上1

  Edsger W. Dijkstra(狄克斯特拉)是计算机学科的巨人,是计算机软件和理论的奠基人之一。他创造了很多现在常用的计算机概念和术语,制订了很多编程技术的指导性原则,例如堆栈(stack)、显示(display)、信号量(semaphore)、死锁(deadlock)、互斥(mutual exclusion)、结构化编程(structured programming)等等。
  Dijkstra获得无数荣誉,其中最有名的是ACM图灵奖。Dijkstra得知自己获图灵奖时,十分惊讶,因为这个美国ACM协会设置的奖很少颁给非美国人。
  在1966-2000年间,共有43人获ACM图灵奖,其中:“美国出生+美国求学+美国工作”27人;“非美国出生+美国求学+美国工作”8人;其他6人,这6人中有4个英国人,1个荷兰人(1972年Dijkstra),1个以色列人(1996年的Amir Pnueli)。
  2001-2019年间,非美国获奖者多了起来。共30名获奖者,其中“美国出生+美国求学+美国工作”18人,“非美国出生+美国求学+美国工作”3人,其他9人。

  Dijkstra简历:
  1952–1962:荷兰阿姆斯特丹计算机部,程序员
  1962–1973:莱顿大学数学系,教授
  1973–1984:美国Burroughs Corporation公司,研究员
  1984–2000:美国德克萨斯大学奥斯汀分校,教授

1、引子
  图论中有两个著名的算法:Dijkstra最短路径算法和Prim最小生成树算法2。两个算法的思想基本一样,都是基于贪心法来扩展结点,执行步骤十分相似,代码只有微小差别。两个算法简单而高效,现在仍广泛应用在图问题中。

  这两个算法虽然以发明者的名字“Dijkstra”、“Prim”命名,但其实有好几位科学家独立发明过,其中一人是Dijkstra,他26岁做兼职程序员时曾在一篇论文中同时提出了这两个算法。这篇只有3页的小论文“A note on two problems in connection with graphs3”,第一部分现在一般被称为“Prim最小生成树算法”,第二部分现在一般被称为“Dijkstra最短路径算法”。

  Dijkstra算法维护两个集合:一个是已经计算出最短路径的结点集合A,另一个是这些点向外扩散的邻居结点集合B。算法的执行步骤是:扩展A的直连邻居,放到B中;每次从B中取出距离起点最短的结点,放到A中;当B为空时计算结束。

图1 Dijkstra原始论文中的集合A和集合B

  不过,论文中没有提到一个关键问题:如何高效地从B中选出距离起点最短的那个点?这个问题的解决决定了算法的复杂度,决定了代码的效率有多好。现在参加算法竞赛的学生都知道,编程时一般用优先队列(效率极高,n个数只需要计算logn次就能找到最小的数)来实现。但是在Dijkstra的论文中,并没有提到如何实现,也许他认为这是一个需要扩展的问题,也可能那时候还没有这些数据结构的概念吧。
  Dijkstra在1956年发明了这个算法,但那时还没有自动计算方面的专业期刊,直到1959年才找到合适的刊物发表。这篇论文是1945-2000年间Web of Science数据库中的一篇经典引文。在一次关于Dijkstra算法的通信中,Douglas McIlroy教授谈到了Dijkstra算法表达的现代性,指出“它在当时显然是不寻常的。后来的上千次引用也不能对它有所改进。”
  Dijkstra对计算机学科的发展有很多奠基性的贡献,最短路径算法只是他年轻时走过的一个小脚印。Dijkstra于1956年提出最短路径算法,时年26岁,是他作为一个计算机科学家的开端。之后的30年,他发展了现在众所周知的、成为常识的多种计算机概念和技术,他那“巨人的肩膀,扛起了计算机科学4”。

2、生平
  简单地概况Dijkstra的成功人生:书香门第、天资聪颖、勤学好思、抓住机遇、工作努力、交游广泛。
  1930年,Dijkstra出生于荷兰城市鹿特丹(Rotterdam),是四个孩子中的老三。他有个好家庭。他父亲是中学化学老师和中学校长,但不是一个普通的化学老师,而是一个化学家、荷兰化学学界的名人,当过荷兰化学协会的主席,博学多才。他母亲是数学家,不过没工作而是家庭妇女(那个年代的女性都这样),她非常聪明,是个天才,Dijkstra说他从母亲那里学到了如何简洁优雅地解决问题。
  Dijkstra又聪明又勤学,学习成绩非常好。中学毕业后,他原本想去学法律,但是长辈们都建议他不要浪费自己的聪明才智,应该去从事科学事业。1948年,他到离家不远的莱顿大学(University of Leiden)读物理学,他说他的大学生涯“很穷很累很快乐5”。这不奇怪,那时正是二战后的欧洲重建时期。

  大学的头三年,Dijkstra老老实实学物理和数学,1951年通过中期考试,比其他同学都早。然而Dijkstra一直到1956年才拿到大学学位,一共读了8年大学。读了这么久,不是因为去游戏人生了,而是因为他对物理的兴趣衰退了,中间去兼职工作当了一名程序员。
  1951年,一件事改变了Dijkstra的命运。计算机科学的一颗星星开始升起,这将是一颗星等为一等的亮星。
  这一年,他那热爱科学并积极关注科学发展的父亲,看到剑桥大学的一个编程课广告,一门三星期的短课,学习EDSAC计算机编程。EDSAC是世界第一台存储程序式电子计算机,采用了冯诺依曼结构。作为对Dijkstra提前通过中期考试的奖励,父亲资助他去英国学编程,可能真实目的是让他去剑桥大学见见世面,顺便路过伦敦逛逛吧。好学的Dijkstra觉得用计算机来帮助做数值计算,有利于物理研究,于是高兴地去了。
  Dijkstra在编程课上偶遇阿姆斯特丹数学中心的负责人。负责人对他说计算机刚起步,有光明的发展前景,注定成为一门显学,“小伙子你会成为计算机宗师的”。然后热情邀请他到数学中心做编程工作,而且宜早不宜迟,机会不等人。Dijkstra面临一个重大选择,是继续读物理,还是去搞编程?他决定一起做。
  从1952年开始,Dijkstra大部分时间都在数学中心兼职搞编程,物理学业差不多荒废了,导致他到1956年才从大学毕业。毕业后,他在数学中心全职工作,一直到1962年。
  他在自传中戏称自己是“第一个靠编程赚钱的荷兰人6”,在图灵奖获奖感言中也说自己是荷兰的第一个程序员。

  看到这里,我们发现Dijkstra当初其实是被数学中心负责人忽悠了。荷兰那时几乎没有人会编程,连一个只学了3周编程的Dijkstra也成了稀缺人才。数学中心的负责人之所以向Dijkstra伸出橄榄枝,根本原因是没有选择,只能找他。
  在数学中心当程序员,听起来不错:敲着键盘,喝着咖啡,工作之余还能打打游戏…这都是做梦,那时还没有电脑键盘,输入靠穿孔纸带,输出靠电传打字机,电脑屏幕自然也没有。至于编程嘛,高级语言还没有出现,汇编语言也没有,因为电脑还没有编译编程语言的能力,只能直接用机器码编程,就是0和1。现在编程语言教科书上的知识,当时几乎都没有。Dijkstra在剑桥学的就是这种编程,怪不得只要3周,因为也没什么好学的。Dijkstra没有被这种枯燥的工作吓倒,反而产生了浓厚的兴趣,数学中心负责人肯定高兴坏了。
  Dijkstra在数学中心的十年编程工作颇有成效,最短路径算法就是这个期间发明的,这是Dijkstra设计的第一个著名算法,并以他的名字命名。Dijkstra为此感到很得意,他在1993年的自传中回忆这一美妙时光:“最短路径算法以我的名字命名,让我出了名。当初我设计这个算法的时候,并没有拿着纸和笔冥思苦想。那是在阿姆斯特丹的一个露天咖啡馆,我和妻子(当时在谈恋爱,一年后的1957年结婚)晒着阳光喝着咖啡,然后我灵机一动想到了这个算法。”

图2 Dijkstra在自传中提到最短路径算法

  1960年,Dijkstra和同事一起编写ALGOL 60编译器,这是世界上第一个ALGOL 60编译器。开发过程中解决了很多关键问题,例如1960年Dijkstra在一篇论文“Recursive Programming”中,提出了术语“堆栈(stack)”。多年以后,他得知这篇小论文让他在美国计算机学界出了名。

图3 Dijkstra在自传中提到stack

  因为在数学中心的工作,Dijkstra于1959年获得了阿姆斯特丹大学的博士学位,博士论文题目是“Communication with an Automatic Computer”,研究实时中断问题。
  Dijkstra在数学中心工作到1962年,这期间的工作让他成为一位有名的计算机科学家,他这颗星星开始在天空眨眼。
  1962年,他被聘为荷兰埃因霍芬理工大学(Eindhoven University of Technology)数学系的教授。不过,他说自己其实是第3个候选人,只是因为前2人拒绝了聘请,才轮到他。学校给他安排的工作是上《数值分析》课,课余他组织了一个计算机研究小组,开发“THE Multiprogramming System”。“THE”系统创造了历史,是世界第一个松耦合、显式同步、协操作串行处理的操作系统,在大学的计算中心运行了10年。信号量(semaphore)、死锁(deadlock)等新概念就是在这个系统上提出的。他很为这个系统自豪,他到英国、美国交流这个系统的设计,获得了同行的高度认可,使他在计算机学界声名鹊起。
  Dijkstra最广为人知的事情,是他对GO TO语句的批评。当时人们在编程时,经常使用GO TO语句,随意跳转到程序的任意位置。这个语句极为暴力,让程序的流程变得支离破碎。敏锐的Dijkstra第一个认识到这个语句对程序逻辑、计算资源的的破坏性。1968年他给 Communications of the ACM写了一篇2页纸的通讯,信件原标题是“反对GO TO语句(A case against the GO TO statement7)”,因为过于露骨,被编辑改名为较为温和的“Go To Statement Considered Harmful”后发表,引起了广泛的争论。当然,现在大家都知道他赢了,几乎没有人在编程的时候使用GO TO语句。这封信影响如此之大,以至于“X considered harmful”成了一个标题模板,经常被用于咆哮和指责的文章中。

  1969年,他为了平复自己郁闷的心情(后文说明了原因:他不受自己工作的大学的待见,他的研究小组被解散),花大气力写了一篇80多页的报告“Notes on Structured Programming8”,即“结构化编程”。结构化编程现在是计算机程序默认的基本原则,不过那时还是一个全新的概念。他复制了20份,寄给外国的朋友,因为他觉得这只是一篇普通的报告,让大家看看就好了。然而出乎他的意料,这篇报告获得了巨大的成功,“像野火一样传播(spread like wildfire)”,辗转复印了很多轮,Dijkstra自己就认识一个住在偏远角落的人珍藏着这篇报告的第5、6代复印稿。“洛阳纸贵”,一时间人人都在看这篇伟大的报告,深深为Dijkstra充满哲人的洞见而折服。Dijkstra后来分析为什么受到欢迎:“这是第一篇严肃讨论编程挑战的文章。” 这份报告终于奠定了他计算机科学巨星的地位。

  Dijkstra声誉日隆。1972年他接到一个美国电话,被告知获得了第七届ACM图灵奖。Dijkstra非常震惊,没想到自己能得这个奖,因为前6个图灵奖获得者都是美国人或英国人。Dijkstra的震惊是可以理解的,如果他晚一些年获得图灵奖,他会更加震惊,因为一直到1996年,才有第2个非英美的获奖者。姚期智2000年获得图灵奖,是图灵奖唯一的华裔学者,当时他是美国国籍。姚期智于2016年放弃美籍,成为中国公民。
  然而,Dijkstra在学校的地位却越来越尴尬。就在获得ACM图灵奖之后不久,他就从大学离职了。大环境是计算机学科在1960年代中期才在英美的一些大学出现,而Dijkstra所在的大学那时还没有。他所在的数学学院的领导并不太理解和支持他的计算机工作,觉得他不务正业。他搞的计算机研究,和学院其他老师做的数学研究似乎毫不搭边。另外,Dijkstra在自传中用忧郁的语气回忆自己当时“穿拖鞋、留胡子、态度傲慢”,这不修边幅的样子和现代程序员的邋遢风格一样,一点儿都不像个教授,Dijkstra的人缘似乎不太好。他成了他所在大学的一个异类,学校甚至解散了他的研究小组,他成了一个孤家寡人。甚至1972年获得图灵奖,这个荣誉也没有让他在学校的地位有所好转。院长大人似乎不知道什么是图灵奖,当Dijkstra兴奋地第一时间跑去告诉他自己得了图灵奖,院长脱口而出说了一句伤人的话:“计算机的奖是不是太多了(In the world of computing, they are rather lavish with prizes, aren’t they?)?” 年轻的科学巨星、计算机宗师被说得如此不堪,Dijkstra记了一辈子。
  1973年,他从大学离职,找了个新工作,新东家是当时著名的美国计算机制造商Burroughs Corporation公司,办公地点就在他荷兰的家里。这是一份美妙的工作,他没有具体任务,而是“自由研究”,只需要每年去美国总部汇报几次就好了。在做“自由研究员”的那些年,他跑遍了世界各国,参加各种学术会议,在计算机的世界中自由飞翔。
  然而,美妙时光不会永远持续。1984年,他从Burroughs Corporation公司离职,因为“Burroughs的学术视野正在缩小,而我的视野正在扩大。” Burroughs Corporation公司在走下坡路,开始节流了。
  美国的好客和学术环境吸引着Dijkstra。他终于在54岁的年龄离开了荷兰,到美国德克萨斯大学奥斯汀分校做计算机教授。1999年退休,2002年查出癌症,回到荷兰后不久去世。
  Dijkstra一生著述极多。他做事非常有条理,用自己名字的缩写“EWD”对这些文件进行命名和编号,一共有1318篇,德克萨斯大学把这1318篇作品整理成档案在网上公开。有趣的是,他是一位计算机科学家,却几乎不用电脑打字,而习惯于用钢笔书写。这1318篇作品,除了早期的一部分已经找不到手稿,后期的手稿都在,字迹工工整整,几乎没有涂改的痕迹。这些手稿的笔迹,数十年完全一致,显然出自同一人的手笔,不是别人誊抄的。有的手稿长达几十页,是很不容易的。
  他的最后一篇“EWD1318”,写于2002年4月,当时已经回到荷兰,4个月后去世。绚烂的生命之花,在日暮时分凋落。

图4 最后的手稿:EWD1318

  
  本文参考了以下原始资料:
[1]Dijkstra自传:https://www.cs.utexas.edu/users/EWD/ewd11xx/EWD1166.PDF
[2]Dijkstra档案:https://www.cs.utexas.edu/users/EWD/
[3]ACM图灵奖介绍:https://amturing.acm.org/award_winners/dijkstra_1053701.cfm


  1. https://www.phrases.org.uk/meanings/268025.html ↩︎

  2. R. C. Prim, “Shortest Connection Networks and some Generalizations,” Bell System Technical Journal, Vol. 36, 1957, pp. 1389-1401. ↩︎

  3. Edsger W. Dijkstra, “A note on two problems in connection with graphs,” Numerische Mathematik 1, 1959, pp. 269–271. 下载:http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf ↩︎

  4. The Man Who Carried Computer Science on His Shoulders
    https://inference-review.com/article/the-man-who-carried-computer-science-on-his-shoulders ↩︎

  5. Dijkstra自传:“We were very poor, …, but life was incredibly exciting.” ↩︎

  6. Dijkstra自传:“the first Dutchman with the qualification ‘programmer’ on the payroll.” ↩︎

  7. A case against the GO TO statement https://www.cs.utexas.edu/users/EWD/ewd02xx/EWD215.PDF ↩︎

  8. “Notes on Structured Programming”: https://www.cs.utexas.edu/users/EWD/ewd02xx/EWD249.PDF ↩︎


转载:https://blog.csdn.net/weixin_43914593/article/details/114755499
查看评论
* 以上用户言论只代表其个人观点,不代表本网站的观点或立场