1974年的图灵奖得主唐纳德·克努特(Donald Ervin Knuth),因其在计算机程序设计理论、算法分析与相关领域的开创性工作而获得这一计算机科学界的最高荣誉。他是《计算机程序设计的艺术》(The Art of Computer Programming)系列著作的作者,该系列书籍是计算机科学领域内极具权威和影响力的经典之作。此外,他还开发了TEX排版系统以及METAFONT字体设计系统,对计算机排版技术产生了革命性的影响。克努特被誉为“计算机科学的艺术家”和“算法分析之父”,他的研究成果奠定了现代计算机科学尤其是程序设计基础理论的重要基石。
高德纳(Donald Ervin Knuth)是算法和程序设计技术的先驱者,计算机排版系统TeX和字型设计系统Metafont的发明者,他因这些成就和大量创造性的影响深远的著作而誉满全球。
数百万言的多卷本《计算机程序设计的艺术》(The Art of Computer Programming)堪称计算机科学理论与技术的经典巨著,有评论认为其作用与地位可与数学史上欧几里得的《几何原本》相比。本书作者高德纳(Donald Ervin Knuth)因而荣获1974年度的图灵奖。
排版软件TeX和字型设计系统METAFONT发明人,所著描述基本算法与数据结构的巨作《计算机程序设计的艺术》被《美国科学家》杂志列为20世纪最重要的12本物理科学类专著之一,与爱因斯坦《相对论》、狄拉克《量子力学》、理查·费曼《量子电动力学》等经典比肩而立。
唐纳德高德纳1938年1月10日生于威斯康辛州密歇根湖畔的密尔沃基(Milwaukee)。这是一个山灵水秀、人才辈出的地方,“人工智能之父”、诺贝尔奖获得者西蒙(H.A.Simon)也是在这里出生的,获诺贝尔奖次年获图灵奖。但高德纳比西蒙小整整22岁,是一个“小字辈”。高德纳的父亲是一个多才多艺的人,有研究生学历,当过小学和中学教师,星期天在教堂演奏风琴,还在自家地下室办了一个小印刷厂。受父亲影响,高德纳从小喜欢学习和音乐,并表现出与众不同的才能。高德纳上8年级时,当地的Ziegler糖果厂为了促销其称为Giant Bar的一种棒棒糖,在学校中搞了一个比赛,看谁能用Ziegler’s Giant Bar中的字母排列组合出最多的单词。高德纳假装胃疼,在家里呆了两个星期,利用一部大字典,得出了4500个单词,比裁判掌握的2000个单词多出一倍多,一举为他所在的班夺得冠军,赢得一台电视机和每人一块Giant Bar,而高德纳本人则赢得一副雪撬。
1956年,高德纳以各科平均97.5的创记录的高分从密尔沃基路德兰高级中学毕业,进入俄亥俄州克利夫兰的开思理工学院(Case Institute of Technology)攻读物理。这一年,他在中学时就创作的一篇出色的科学幻想小说《普茨比度量衡体系》(The Potrzebie System of Weights and Measures)在美国著名的《疯狂》(Mad)杂志上发表,高德纳获得了他的第一笔稿费25美元,并因而获得西屋科学天才的提名奖。在这篇小说中,高德纳风趣而富于幻想地提出了替代公制的一种新的计量制度,比如以一本流行杂志的厚度为长度单位,虽然滑稽可笑,却设计得严密周到,天衣无缝,其中甚至还包括一种新的历法。文章刊出后大受欢迎,多次重印,1991年还重印过一次,其时作者高德纳即将退休。
大学一年级结束以后的暑假,高德纳在学校打工,负责把统计数字画成图表。碰巧他工作室的隔壁就是计算机房,新到了一台IBM650。当时的计算机体积都很庞大,有供输入和调试的控制台,上面排列着一排排的开关和指示灯,计算机工作时指示灯快速闪烁变化出不同的图案,这引起高德纳极大的好奇与兴趣,他接连好几天彻夜不眠地呆在机房,观察它的工作,钻研使用手册,探究计算机的奥秘。一年以后,他终于改学数学,与计算机结缘。这段经历对于高德纳是如此重要和关键,以致他在《计算机程序设计的艺术》第一卷的卷首,不像别的作者那样一般写上“献给自己的父母”或“献给自己的妻子”,而是写着“献给曾经安装在开思理工学院的650型计算机,以纪念那些愉快的夜晚”。他的第一个计算机应用程序也是在650计算机上实现的:他为他所在的校篮球队(高德纳人高马大,也喜爱运动,娱乐)设计了一个复杂的公式,根据球员在每场比赛中的得分、助攻、抢断、篮板球、盖帽等多项统计数字对球员进行综合评估。球队教练根据高德纳的程序挑选和使用球员,使开思理工学院在1960年赢得了联赛冠军,高德纳的“神奇的公式和程序”也被当地报纸和广播传为美谈。
1960年,高德纳在开思理工学院毕业,不但被授予学士学位,还被破例同时授予硕士学位。之后他进入加州理工学院研究生院,1963年获得博士学位,留校工作至1968年,然后转入斯坦福大学任教,其间1972—1973年曾经在奥斯陆大学当客座教授。
高德纳进行了两大工程,一个已经完成,一个尚未完成。第一个大工程就是《计算机程序设计的艺术》系列,开始于他念博士期间,计划出七卷,第一卷《基本算法》于1968年出版,第二卷《半数字化算法》于1969年出版,第三卷《排序与搜索》于1973年出版,第四卷A《组合算法》已于2011年出版。这个工程为什么前紧后松,长期停顿呢?
高德纳暂停了写作,理由是现有的计算机排版软件效果太差,破坏了这套书的美。这不免引发作者是否江郎才尽,见好就收的猜测与怀疑——不料辍笔10年的高德纳以三个重量级创造性成果:字体设计系统METAFONT(其价值一言以蔽之:对整个西文印刷行业带来了革命性变革)、文学化编程(充分展示程序设计的艺术性:清晰,美感,诗意),尤其是最具革命性的排版系统TeX(仍是全球学术排版的不二之选)给出了强力回应。尽管如此,仍有人说高写完三卷TAOCP就去研究TeX,其实是害怕写第四卷——不过他对这类风言风语根本不以为意:一个人要把事情做的完美,只有跟上帝的意图保持和谐,现在上帝要我去写第四卷了。
搁置手头的重要工作,费时10年专研排版美学打造TeX系统,原因其实很简单:数理图文排版以前一直使用金属活字,70年代以降始有激光照排,然而当时的计算机虽能替代人工排出普通的报纸杂志,但对处理复杂的数理公式却力不从心。高德纳试图为计算机写一个小玩艺儿解决上述问题,TeX的前半部分由此产生。编写过程中,他想参考J·伯克霍夫的Aesthetic Measures(《美学标准》)一书,在哈佛的图书馆几经查阅也未能如愿,之后好不容易在麻省理工学院找到。参考的结果是在TeX里加入一个变量badness,用以衡量一行文字的美感,变量越小文字就越美。
20世纪70年代中期,高德纳和其他一些计算机科学家曾经设想在未来10年中将产生一种比现有程序设计语言更加强大,更加优美的新型语言,并预先命名它为“乌托邦84”(Utopia 84)语言。
1992年,高为潜心写作TAOCP从斯坦福提前退休,同时停用电子邮箱(他自1975年就开始玩电邮)。2008年,TAOCP前三卷出版30年后,第四卷在高粉的千呼万唤中终于面世,此际的高德纳已然是满头白发。对计算机科学的倾心热爱,使他为这部作品耗费了毕生心血:从及冠之年直至古稀老人。
高德纳获得的荣誉与奖励极多。ACM除了授予他图灵奖和软件系统奖外,还在1971年授予过他以COBOL的发明人、女计算机科学家霍泼(Grace Murray Hopper)命名的奖项,这个奖项是专门奖励30岁以下的优秀青年计算机科学家的。这样,高德纳一人就先后获得ACM的三个奖项,在1999年以前,这是计算机科学家中仅有的一位(1999年,布鲁克斯获得图灵奖,从而也拥有ACM三个奖项,平了高德纳的记录)。无独有偶,美国数学会也先后授予高德纳三个奖项,即Lester R.Ford奖(1975)、J.B.Priestley奖(1981)和Steele奖(1986)。1979年,当时的美国总统卡特向他颁发了全国科学奖章。IEEE授过他两个奖:McDowell奖(1980)和计算机先驱奖(1982)。1994年,瑞典科学院授予高德纳Adelskold奖。1995年他获得冯·诺伊曼奖和Harvey奖。1996年他获得日本INAMORI基金会设立的KYOTO奖,这个奖是专门奖励在高科技领域作出贡献的科学家的。面对这么多荣誉,高德纳都以平常心对待,据说,纪念他获得图灵奖的碗只是被他用来盛放水果。
ACM于1974年11月11日在南加利福尼亚濒临太平洋的海港城市圣迭戈举行的年会上向高德纳颁发图灵奖。高德纳发表了题为“作为一种艺术的计算机程序设计”(Computer Programming as an Art)的演说。在演说中,一如我们在阅读他的著作时所感受的那样,高德纳旁征博引,有根有据,人情人理,娓娓道来,把“科学”与“艺术”的不可分割的关系说得清清楚楚,令人心服口服。演说刊于Communications of ACM,1975年12月,667—673页,或见《前20年的ACM图灵奖演说集》(ACM Turing Award Lectures——The First 20Years:1966--1985,ACM h.),33—46页。
高德纳《计算机程序设计的艺术》系列,开始于他念博士期间,计划出七卷,第一卷《基本算法》于1968年出版,第二卷《半数字化算法》于1969年出版,第三卷《排序与搜索》于1973年出版,第四卷《组合算法》于2008年出版。《计算机程序设计的艺术》一书以其内容的丰富和深刻喻为经典,有人甚至称之为“计算机的圣经”,被译为俄、日、西、葡、匈牙利、罗马尼亚等多种文字在世界各国广泛流传,其发行量创造了计算机类图书的最高记录,直至20世纪80年代中期,都一直保持着月销售量每卷达2000册的势头,成为Addison-Wesley出版社成立以来销路最好的图书。我国也由苏运霖翻译并出版了《计算机程序设计艺术》一书。
此外,高德纳还有许多“小创造”。计算机科学技术中两个最基本的概念:“算法”(Algorithm)和“数据结构”(Data Structure)就是高德纳于29岁时提出来的。1973年他首创双向链表。在编译器设计方面,著名的LR(k)文法也是高德纳在对自左至右、自底向上的移进一归约分析进行了深刻剖析的基础上,经过高度概括和集中以后发明的,它表示具有从左(L)到右(R)的分析而向前看k个符号,以确定所要进行的归约和应用何种语法解释。LR(k)文法的识别效率高,在从左至右扫描输入串时,就能发现其中的语法错误,并能准确地指出出错位置,因此被广泛应用。此外,利用LR(众)文法还能正确区分像Flying planes is fun和Flying planes can crash这类句子(前一个句子“开飞机很有趣”中flying是动名词,而后一个句子“飞行中的飞机可能出事”中flying是现在分词当形容词)。以著名的巴克斯—诺尔范式为基础的“属性文法”(attribute grammar)也是高德纳首先提出来的。属性文法在普通的上下文无关文法(context-free grammar)的基础上,对每一个终结点或非终结点加上一些属性,和对这些属性进行估值的语义规则集,从而形成一种新的、有更强表达与描述能力的文法。其中属性是由的有序偶对组成的。属性的内容则可包括模式标识符表等。
在算法方面,有他和他的学生共同设计的诸如Knuth-Bendix算法和Knuth-Morris-Pratt算法,前者是为了考察数学公理及其推论是否“完全”而构造标准重写规则集(rewriting rule set)的算法,曾成功地用它解决了群论中的等式的证明问题,是定理机器证明的一个范例。后者是在文本中查找字符串的简单而高效的算法。此外,高德纳还设计与实现过最早的随机数发生器(random number generator)。
高德纳的著作很多,除了已由Addison-Wesley出版社出版的三卷The Art of Computer Programming,由管纪文、苏运霖等译成中文,国防工业出版社出版,介绍TeX和METAFONT的五卷《计算机与排版》(Computers and Typesetting)早已流传于世外,还有以下一些主要著作:
《研究之美》(Surreal Numbers,Addison-Wesley,1974)
《具体数学》(Concrete Mathematics,Addison-Wesley,1989)
《数学论著集》(Mathematical Writings,MAA,1989)
《用于算法分析的数学》(Mathematics for the Analysis of Algorithms,Birkhauser,1990,第三版)
《作文式程序设计》(Literate Programming,CSLI,1992)
《公理与外壳》(Axioms and Hulls,Springer,1992)
《斯坦福的GraphBase:组合计算用的平台》(The Stanford Graph Base:a Platform for Combinatorial Computing,ACMh·,1993)
其中,《研究之美》(Surreal Numbers)一书介绍了剑桥大学的康韦(J.H.Conway)所发明的一种新的数制,是高德纳听了康韦向他作的介绍后,用了一周时间写成的小说体裁的作品。有评论家指出,这是历史上第一次一个重大的数学发现以小说的形式向公众进行介绍。由此可见,高德纳的艺术才华同样是非凡的,要不是计算机深深吸引了他,高德纳很可能会成为出色的小说家或音乐家(前面说过他喜欢音乐,会自己制作管风琴,会创作不错的乐曲呢)。
文明上网,理性发言,共同做网络文明传播者