算法和数据结构的先驱者 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 年后，第四卷在高粉的千呼万唤中终于面世，此际的高德纳已然是满头白发。对计算机科学的倾心热爱，使他为这部作品耗费了毕生心血：从及冠之年直至古稀老人。