1956年,克努特以各科平均97.5的创记录的高分从密尔沃基路德兰高级中学毕业,进入俄亥俄州克利夫兰的开思理工学院(Case Institute of Technology)攻读物理。这一年,他在中学时就创作的一篇出色的科学幻想小说“普茨比度量衡体系”(The Potrzebie System of Weights and Measures)在美国著名的《疯狂》(Mad)杂志上发表,克努特获得了他的第一笔稿费25美元,并因而获得西屋科学天才的提名奖。在这篇小说中,克努特风趣而富于幻想地提出了替代公制的一种新的计量制度,比如以一本流行杂志的厚度为长度单位,虽然滑稽可笑,却设计得严密周到,天衣无缝,其中甚至还包括一种新的历法。文章刊出后大受欢迎,多次重印,1991年还重印过一次,其时作者克努特即将退休。
克努特至今进行了两大工程,一个已经完成,一个尚未完成。第一个大工程就是《计算机程序设计的艺术》系列,开始于他念博士期间,计划出七卷,第一卷《基本算法》于1968年出版,第二卷《半数字化算法》于1969年出版,第三卷《排序与搜索》于1973年出版,第四卷《组合算法》尚在写作之中。这个工程为什么前紧后松,长期停顿呢?原来,前三卷书出版以后,克努特根据自己在校对清样时的感受,决心对排版技术进行彻底改造,因此中止了第一个工程,而开始其第二个工程。这个工程花费了克努特整整9年的时间和精力,结果就是对整个西文印刷行业带来了革命性变革的TEX排版软件和METAFONT字型设计软件。这两个软件为克努特赢得了ACM的另一个奖项:1986年度的软件系统奖(Software System Award)。但是这两个软件并没有为克努特和斯坦福大学赚过一分钱:克努特把它们作为自由软件无偿提供给用户。这比理查德·斯托尔曼(Richard Stallman,1990年ACM Hopper奖获得者)在1984年发动自由软件运动早了约5-6年。克努特说:“我写这两个程序是出于对书籍的热爱,也想给这个领域以必要的推动。我已经有些名气了,我的书卖得也不错。所以我不需要为我出于热爱而做的事保留专卖权。此外,数学家通常是不为他们发现的定理获取报酬的”。1979年,克努特还创建了TEX用户集团,这个集团10年前的成员数就超过3 000。细心的读者也许会注意到,许多西文书版权页的下部注明“本书用TEX系统排版”。
克努特的两大工程(虽然其中之一尚未最后完成)都是取得很大成功的。《计算机程序设计的艺术》一书以其内容的丰富和深刻喻为经典,有人甚至称之为“计算机的圣经”,被译为俄、日、西、葡、匈牙利、罗马尼亚等多种文字在世界各国广泛流传,其发行量创造了计算机类图书的最高记录,直至20世纪80年代中期,都一直保持着月销售量每卷达2 000册的势头,成为Addison-Wesley出版社成立以来销路最好的图书。在我国也有译本(可惜书名译为《计算机程序设计技巧》,这是不符合克努特的本意的)。此外,克努特还有许多“小创造”。计算机科学技术中两个最基本的概念:“算法”(Algorithm)和“数据结构”(Data Structure)就是克努特于29岁时提出来的。1973年他首创双向链表。在编译器设计方面,著名的LR(A)文法也是克努特在对自左至右、自底向上的移进一归约分析进行了深刻剖析的基础上,经过高度概括和集中以后发明的,它表示具有从左(L)到右(R)的分析而向前看A个符号,以确定所要进行的归约和应用何种语法解释。LR(A)文法的识别效率高,在从左至右扫描输入串时,就能发现其中的语法错误,并能准确地指出出错位置,因此被广泛应用。此外,利用LR(A)文法还能正确区分像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)。
这个片段是采用标准的插入排序算法对一个数组中的元素进行排序。片段中的@符号是系统约定,用以引入作文式程序设计中的各种特征。符号$则通知系统交叉引用某段文本作为代码而非注解。片段中有一个“宏”(macro),就是{Insert $ v $ in the array)。宏允许缩写,上述宏就可缩写为{Insert...),因此是很方便和精炼的。上述片段经过处理以后获得的程序代码如下所示。
for i:=2 tO N do
begin v:=a[i];j:=i;
while a[j-1]> v do
begin a[j]:=a[j-1];
j:=j-1 end;
a[j]:=v
而处理以后获得的可供印刷的文档则如下所示。
31.Insertion sort.This is the standard inseaion son algorithm.Assumes a sentinel at O[0].
克努特的著作很多,除了已由Addison-Wesley出版社出版的三卷The Art of Computer Programming(由管纪文、苏运霖等译成中文,国防工业出版社出版),介绍TEX和METAFONT的五卷《计算机与排版》(Computers and Typesetting)早已流传于世外,还有以下一些主要著作:
超现实数》(Surreal Numbers,Addison-Wesley,1974)
《实用数学:计算机科学的基础》(Concrete Mathematics :A Foundation for Computer Science,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 GraphBase:a Platform for Combinatorial Computing,ACM Pr.,1993)
克努特于1992年在斯坦福大学退休。但实际上他“退而不休”,继续辛勤耕耘,做了大量工作。首先是对《计算机程序设计的艺术》前3卷进行了修订充实,其中第一卷在1997年出了第三版,第二卷和第三卷在1998年出了第二版。其次对他过去设计的虚拟机MIX(用在《计算机程序设计的艺术》中)进行了扩充和完善,发展成为面向64bit计算的、具有十分丰富和灵活的指令集的MMIX,并为MMIX开发了一系列软件,使得用MMIX指令编写的程序能在几乎现有的各种计算机上都能高效地运行。此外,MMIX全部采用克努特所倡导的作文式程序设计方法。他的这一成果反映在他1999年出版的专著《MMIXware:用于下一个千年的RISC计算机》一书中(MMIXware:a RISC Computer for the Third Millennium,Springer Verlag)。书名反映了克努特对自己这一工作所追求的目标和期望。惟一的不足是:它缺乏图形用户界面。克努特在本书的前言中坦言自己缺乏足够的时间来完成这一任务,希望能有读者帮助他解决这一缺陷。如同克努特的其他软件成果一样,MMIXware也是免费的自由软件,感兴趣的读者可通过下列网址下载: