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