算法和数据结构的先驱者 Donald E.Knuth

Donald E. Knuth,这位“现代计算机科学的鼻祖”是计算机界的传奇人物。高德纳是他的中文名,是 1977 年他访问中国之前所取的,命名者是姚储枫(姚期智的夫人,夫妇都是计算机科学家)。

高德纳曾在自传的开头幽默地发问:“Donald Knuth 真的只是一个人么?”作为现代计算机科学的鼻祖,他完成了编译程序、属性文法和运算法则等领域的前沿研究,出版专著 17 部,发表论文 150 余篇(涉及巴比伦算法、圣经、字母“s”的历史等诸多内容),写出两个数字排版系统,同时在纯计算数学领域也有独特贡献。他获得的奖项难以胜数,其中包括 ACM Turing Award 颁发的图灵奖(1974),美国国家科学奖(1979),日本 KYOTO 奖(1996),瑞典科学院的 Adelskold 奖及冯诺伊曼奖。而他对荣誉从不经意,据说那只代表至高荣誉的图灵碗被用来盛放水果。

1938 年 1 月 10 日,高德纳出生于美国密尔沃基。他的超凡智力在 8 岁时就显示出来了。当时,一家糖果商在孩子们当中举办了一项有趣的比赛,要求用 “Ziegler’s GiantBar”里面的字母,写出尽可能多的单词。裁判事先准备了一份 2500 个单词的列表,可小高德纳令人惊讶地写出了 4500 多个单词。他为学校赢 得一台电视机,还为每个同学赢得一根棒棒糖。他的赛后感言是,我还能写出更多。

高德纳就读的大学是凯斯理工学院。1956 年,他在这里第一次使用了 IBM650,并开始学习编程。不久之后,高德纳就对编程有了许多体 会。当时高德纳还兼职管理学校的篮球队,于是他编写了一个程序,能够自动评估每名球员的价值,令球队的教练非常欣赏,还引来了 CBS 电视台。1960 年,高德纳以公认出色的成就,打破了学校的惯例,同时获得了学士和硕士两个学位。

随后,高德纳进入伯克利攻读数学博士学位。在此期间,他的编程生涯也正式开始了。他当时所写的程序中最值得一提的,是对 ALGOL60 编 译器提出的测试方法。ALGOL60 经常会因为编译器不成熟而出故障。高纳德编写了一段非常简单的测试程序,江湖人称“Man or boytest”。

高德纳最为人知的事迹是,他是《计算机程序设计艺术》(The Art of Computer Programming)的作者。此书是计算机科学界最受高度敬重的参考书籍之一。他创造了算法分析的领域,在数个理论计算机科学的分支做出初步贡献,此外还是排版软件 TeX 和字体设计系统 Metafont 的发明人。

《美国科学家》(American Scientist)杂志曾将《计算机程序设计艺术》与爱因斯坦的《相对论》、狄拉克的《量子力学》、理查·费曼的《量子电动力学》等书并列为 20 世纪最重要的 12 本物理科学类专论书之一。

高德纳还有许多“小创造”。计算机科学技术中两个最基本的概念:“算法”(Algorithm)和“数据结构”(Data Structure)就是高德纳于 29 岁时提出来的。1973 年他首创双向链表。在编译器设计方面,著名的 LR(k)文法也是高德纳在对自左至右、自底向上的移进一归约分析进行了深刻剖析的基础上,经过高度概括和集中以后发明的,它表示具有从左(L)到右(R)的分析而向前看 k 个符号,以确定所要进行的归约和应用何种语法解释。

在算法方面,有他和他的学生共同设计的诸如 Knuth-Bendix 算法和 Knuth-Morris-Pratt 算法,前者是为了考察数学公理及其推论是否“完全”而构造标准重写规则集(rewriting rule set)的算法,曾成功地用它解决了群论中的等式的证明问题,是定理机器证明的一个范例。后者是在文本中查找字符串的简单而高效的算法。此外,高德纳还设计与实现过最早的随机数发生器(random number generator)。

1992 年,高德纳为潜心写作 TAOCP 从斯坦福提前退休,同时停用电子邮箱(他自1975年就开始玩电邮)。2008 年,TAOCP 前三卷出版 30 年后,第四卷在高粉的千呼万唤中终于面世,此际的高德纳已然是满头白发。对计算机科学的倾心热爱,使他为这部作品耗费了毕生心血:从及冠之年直至古稀老人。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180116B10GBI00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券