office_tools 版 (精华区)
发信人: hitwdh (一潭死水※痛并快乐着), 信区: office_tools
标 题: 高德纳的二十年计划 (zz)(转载)
发信站: 哈工大紫丁香 (2004年04月14日20:19:24 星期三), 站内信件
【 以下文字转载自 AI 讨论区 】
【 原文由 hitwdh 所发表 】
高德纳已经五十八岁了。 他打算再花二十年的时间继续他的著作，The Art of Comput
er Programming. 大家知道 Donald E. Knuth 是资讯科学界公认的大宗师， 知道他以
他的重量级著作 The Art of Computer Programming(以下简称TAOCP)[2,3,4] 闻名于世
，原计划要出七册，但目前只完成了三册。但也许并没有很多人知道他还有个中文名字
："高德纳"。
TAOCP 这套书的名气这么大，敢去碰它的人反倒不多。寒假我因为一些原因，读了高德
纳的另一本书 "The Stanford GraphBase"[1]。大师的书到底是什么样子呢？
高德纳在序言里说了写这本书的原因：在写 TAOCP 的第四册前， 他想要用一个叫做 l
adders 的游戏当作贯穿全书的例子。 于是写了不少相关的程式和庞大的测试雷柿希?br
> 后集结成了一个程式／资料库。 他想这套 GraphBase 可以作为大家测试 graph 演算法
的基础，让那些 "街上混的程式员们 (programmers-on-the-street)" 知道电脑科学家
们也会做实际的事。另外，这套程式库全部用他鼓吹的 literate programming 方式写
成，也可以当成一个活生生的例子。最后一个，但却是最重要的原因是，"to have fun
"."的确，快乐是这一路上最主要的原因，但我不敢承认。电脑科学家们总是得装出一副
咬牙工作的样子，让别人心甘情愿付给他们高薪水。但迟早这个社会得承认， 有些工作
仍然值得尊敬 --- 即使它们比任何事情都要来
得有趣。"
我不禁笑了。高德纳在办正事的途中岔出去做别的事情，一做就是好几年已经不是第一
次。TeX 这个现在大家都在用的排版系统不就是他嫌 TAOCP 被排得不好看， 因此自己
卷起袖子研究电脑排版的产物吗？Tex 耗去了他十年的光阴，而这本 Stanford GraphB
ase 则可以追溯到二十年前。高德纳好像永远不怕老？
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" 果然常出现，比出现("occu
r") 还要常出现。
看来高德纳真的是玩得不亦乐乎呢。"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 的拿手技巧是钜细靡遗地用 forma
l 方法推导、检验程式， 这和工业界不断产生数以 mega 计的软体， 但使用者却无时
不负担著 bug 的风险的实际情况显然有段差距。高德纳则认为自己位于两种极端的中间
。一方面他赞同 formal 方法提供的可靠性，但他也知道在大系统中这种方式的极限。
他尽力维持他的软体的品质，因此他愿意提供赏金给在 TeX 中找到新 bug 的人。
由于高德纳已经不用 email 了，他有一个 Web page[6]，http://www-cs-faculty.Sta
nford.EDU/~knuth/ 里头还有个 FAQ, 可以看到他中文名字的图章。大家劈头要问的当
然是：第四册什么时候出来呀？
他说，TAOCP的第四册将会分成三部份，4A : Enumeration and Backtracking, 4B : G
raph and Network Algorithms 和 4C : Optimization and Recursion. 从 1997 年开
始，他会以大约每 128 页为一个单位（高德纳好像很喜欢用 2 的乘幂做单位，他付给
找出 TAOCP中错误的赏金也是 $65536 分）把第四册的部份散发给大家，听取各方的意
见。如果一切顺利，第四册将在2003 年正式完成。第五册的完成时间则定在 2009 年。
第五册告一段落后，他会重新整理 TAOCP的一到三册，更新内容。再下一步，他将把一
到五册的重要内容全部浓缩在一本书里。之后才著手进行六和七册。所以，高德纳至少
得活到 2020 年啰....
为了完成 TAOCP, 高德纳已经退休，过著半隐士的生活。 他不用 e-mail, 不怎么会见
访客， 取消大部分的演讲和旅行。 他说，他得用 batch 方式工作，而不能把事情 sw
ap 来 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
[14] Selected Papers on Fun and Games, to be published
--
“我们的情感来自我们的思想。
如果你能控制自己的思想，
你就有能力控制自己的全部生活
其中包括你的情感和你的行动……”
……
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.237.9]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: 202.118.237.9]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：4.652毫秒