作 者: LotusWensa
标 题: 高德纳(Donald E. Knuth)的二十年计划
时 间: Tue Jun 10 13:17:38 2003
点 击: 129
[收藏注：有谁不知道Donald E. Knuth吗，不知道的话，唔，怎么办呢？去看别的网页吧。
这篇文章可能写的比较早，如果看到一些信息与现时不符，请不要张大你的嘴巴。:)]
高德纳已经五十八岁了。 他打算再花二十年的时间继续他的著作，The Art of Computer
Programming. 大家知道 Donald E. Knuth 是资讯科学界公认的大宗师， 知道他以他的重
量级著作 The Art of Computer Programming(以下简称TAOCP)[2,3,4] 闻名于世，原计划
要出七册，但目前只完成了三册。但也许并没有很多人知道他还有个中文名字：“高德
纳”。
TAOCP 这套书的名气这么大，敢去碰它的人反倒不多。寒假我因为一些原因，读了高德纳的
另一本书 "The Stanford GraphBase"[1]。大师的书到底是什么样子呢？
高德纳在序言里说了写这本书的原因：在写 TAOCP 的第四册前， 他想要用一个叫做
ladders 的游戏当作贯穿全书的例子。 于是写了不少相关的程式和庞大的测试资料，最后
集结成了一个程式／资料库。 他想这套 GraphBase 可以作为大家测试 graph 演算法的基
础，让那些 “街上混的程式员们 (programmers-on-the-street)” 知道电脑科学家们也会
做实际的事。另外，这套程式库全部用他鼓吹的 literate programming 方式写成，也可以
当成一个活生生的例子。最后一个，但却是最重要的原因是，"to have fun".“的确，快乐
是这一路上最主要的原因，但我不敢承认。电脑科学家们总是得装出一副咬牙工作的样子，
让别人心甘情愿付给他们高薪水。但迟早这个社会得承认， 有些工作仍然值得尊敬 --- 即
使它们比任何事情都要来得有趣。”
我不禁笑了。高德纳在办正事的途中岔出去做别的事情，一做就是好几年已经不是第一次。
TeX 这个现在大家都在用的排版系统不就是他嫌 TAOCP 被排得不好看， 因此自己卷起袖子
研究电脑排版的产物吗？Tex 耗去了他十年的光阴，而这本 Stanford GraphBase 则可以追
溯到二十年前。高德纳好像永远不怕老？
Ladders 这个游戏是这样的：挑两个五个字母的英文单字，试试看一次一个字母，把一个字
变成另外一个。但是在过程中它必须仍然是一个英文单字。比如说把 black 变成 white 的
方法是这样的：
black -> brack -> brace -> trace -> trice -> trite -> write -> white
大家看得出来，如果把每个单字当作一个 node, 两个单字如果只差一个字母，就连一条
edge, 那么这个游戏可以想成在两个 node 中找一条 path 。
但 GraphBase 有趣的地方却是资料。 高德纳收集了一个含 5757 个单字的资料库。他参考
了 1971 年以前 Beeler 为了这个游戏专门编的一部字典，删去老的字，加入新的单字。高
德纳花了很大篇幅解说他选字的标准：姓名不选，所以 Knuth 就没有了；但是 gauss 已经
是一个电磁学单位，所以受录了进去。他很耐心的等到 e-mail 终于被大家写成 email, 以
便把他收集到资料库中。
接下来就开始玩这个资料库啰。高德纳发现 5757 个单字中，有 774个 degree 是 1 的
（只有一根接出去的 edge），位居第一。Degree= 2 的也有 727 个。株连最广的单字
是 "bares" 和 "cores" ， degree = 25，而 "cores" 的 25 个邻居都是 degree 大于 9
的。 Degree = 1 的单字中有 103 组根本就是孤零零的两两成对，如 alpha-aloha,
gonad-monad. 跑一个找 connected component 的演算法，发现大部分的单字都在同一个
有 4493 个单字的大 component 里面。
高德纳自己定了一个方法横量单字在文章中的出现频率。 在这 5757个单字中，"which" 是
最常出现的， 其次是 "there" 和 "their"。"often" 果然常出现，比出现("occur") 还要
常出现。
看来高德纳真的是玩得不亦乐乎呢。"to have fun", 于是我们可以想像高德纳出这本书的
真正原因，是他自己建了这些资料后，发现越玩越有趣，终于忍不住想出书了。
玩过了单字，想知道美国大学足球队谁比较强吗？高德纳已经把 120支队伍的 638 场比赛
建成 graph 了。 他又参考资料， 找出美国的128 个城市之间的最短距离，并且在发现前
人的资料明显错误后自己写程式来修正。把蒙娜丽莎的微笑扫描起来后，高德纳示范了如何
运用 bipartite graph matching 的技巧，用骨牌重新拼出这幅名画。
高德纳的文笔亲切而幽默。CWeb 是他大力推广的 literate programming 系统，他认为每
个人都应该有一套。 “但是今天已经没什么人能永远跟上新软体的发行，所以如果你没有
CWeb,也不用觉得太有罪恶感。” 接下来他解释如何安装 Stanford GraphBase, 这一段的
makefile 可以给想学 make 的同学们做很好的参考。 如果装不起来呢？高德纳问，你有没
有好好祈祷呀？最后，他希望大家能像他一样，多用这些程式库和资料档做些实验，“也许
有天你也会迫不及待地想出本这样的书呢！”
浏览了全书，我想：高德纳到底是太闲，还是有用不完的精力？将近六十岁的他，仍旧充满
著旺盛的活力和赤子般的好奇心，而这一切又以他深厚的功力做为基础。
四月号的 Dr. Dobb's Journal 做了一篇高德纳的专访[5]。 为什么写书写到一半， 却花
了十年的时间在 Tex 上？ 他说， Niklaus Wirth （Pascal, Modular-2 和 Oberon 的设
计者）一直想设计飞机，但他发现他需要够好的工具，于是他设计了一个个的电脑语言，造
了自己的电脑。高德纳也希望他的书能够不因科技的进步而被淘汰，希望即使制书的科技进
步，他的书仍旧是用领先的方式制作的。
谈到另一位大师 Edsgar Dijkstra, 他说 Dijkstra 的力量来自于他不妥协的拗脾气。“光
是想像用 C++ 写程式就会让他病倒！”Dijkstra 的拿手技巧是钜细靡遗地用 formal 方法
推导、检验程式， 这和工业界不断产生数以 mega 计的软体， 但使用者却无时不负担著
bug 的风险的实际情况显然有段差距。高德纳则认为自己位于两种极端的中间。一方面他赞
同 formal 方法提供的可靠性，但他也知道在大系统中这种方式的极限。他尽力维持他的软
体的品质，因此他愿意提供赏金给在 TeX 中找到新 bug 的人。
由于高德纳已经不用 email 了，他有一个 Web page[6]，
http://www-cs-faculty.Stanford.EDU/~knuth/ 里头还有个 FAQ, 可以看到他中文名字的图章。
大家劈头要问的当然是：第四册什么时候出来呀？
他说，TAOCP的第四册将会分成三部份，4A : Enumeration and Backtracking, 4B :
Graph and Network Algorithms 和 4C : Optimization and Recursion. 从 1997 年开
始，他会以大约每 128 页为一个单位（高德纳好像很喜欢用 2 的乘幂做单位，他付给找
出 TAOCP中错误的赏金也是 $65536 分）把第四册的部份散发给大家，听取各方的意见。如
果一切顺利，第四册将在2003 年正式完成。第五册的完成时间则定在 2009 年。第五册告
一段落后，他会重新整理 TAOCP的一到三册，更新内容。再下一步，他将把一到五册的重要
内容全部浓缩在一本书里。之后才著手进行六和七册。所以，高德纳至少得活到 2020 年
啰....
为了完成 TAOCP, 高德纳已经退休，过著半隐士的生活。 他不用 e-mail, 不怎么会见访
客， 取消大部分的演讲和旅行。 他说，他得用 batch 方式工作，而不能把事情 swap 来
swap 去的。他托人在家里造了一座管风琴，空闲的时间里，他就会弹弹琴自娱。如果你会
弹琴，他很愿意和你见个面，来个四手联弹。
为什么那么卖力呢？ 在DDJ的专访里， 当被问到他是否能从 Tex 和 Metafont 图利时，
他说，一旦一个人能够喂饱自己，能够有个安身之所，剩下的就是他能为别人做些什么，如
何能为群体做出一些贡献了。
因此他很希望程式创作者们不要把演算法当作自己的私产。程式应该容易阅读和了解，因为
越多人能够了解它，它才能够发挥越大的影响力。
也许他也是基于这个想法继续 TAOCP 的写作吧？ 在他的 web page 中，对于他的这件“此
生的大事”，他下了这样的注脚：“我尝试著尽我所能的去学习电脑科学里的一些领域，然
后把这些知识摘要成大家比较容易了解的方式，让没有那么多时间做这种学习的人也能够吸
收他们”。
为了这个目的，他必须阅读超过二十万页的文件，然后把它们浓缩到两千页里头。他写的东
西并不是最流行的，但他希望他能从日新月异的新技术中，萃取出值得存活到下个世纪的东
西。
不禁想起前阵子同学讨论到的话题：专家是训练有素的狗吗？我们该不该成为专家？高德纳
毫无疑问地是个专家，但他的大师学养和风范也许能给我们不少启发。
Reference
[1] Donald E. Knuth, The Stanford GraphBase : A Platform for Combinatorial
Computing, Addison-Wesley, 1993
[2] Donald E. Knuth, The Art of Computer Programming, Vol 1 : Fundamental
Algorithms, Addison-Wesley, 1973
[3] Donald E. Knuth, The Art of Computer Programming, Vol 2 : Seminumerical
Algorithms, Addison-Wesley, 1973
[4] Donald E. Knuth, The Art of Computer Programming, Vol 3 : Sorting and
searching, Addison-Wesley, 1973
The Art of Computer Programming 有日文，俄文，西班牙文等许多国的版本。
其中，中文版资料如下
Chinese translation by Guan JiWen and Su YunLin, Pei Xue He Cha Zhao,
Beijing: Defense Industry Publishing Co., 1985
[5] Jack Woehr, An interview with Donald Knuth, Dr. Dobb's Journal, April 1996,
p16-p22
[6] Donald E Knuth's WWW Page :
http://www-cs-faculty.Stanford.EDU/~knuth/http://www.geekchic.com/repliq6.htm也有一篇小小的访问。高德纳最喜欢的语言是
CWeb, 最喜欢的运动是棒球，认为有许多人是他值得崇敬的。高德纳将在最近将他的论文以
更浅显的方式整理过后，重新集结出版。这套书的预定读者并不是电脑科学的专家，似乎很
值得一读。这套书将有八本，前两册已经出版：
[7] Literate Programming, Stanford, California: Center for the Study of
Language and Information, 1992
[8] Selected Papers on Computer Science, Stanford's Center for the Study of
Linguistics and Information and Cambridge University Press, spring, 1996
[9] Selected Papers on Analysis of Algorithms, to be published
[10] Selected Papers on Computer Languages, to be published
[11] Selected Papers on Design of Algorithms, to be published
[12] Selected Papers on Digital Typography, to be published
[13] Selected Papers on Discrete Mathematics, to be published
[14] Selected Papers on Fun and Games, to be published
