高 德 納 的 二 十 年 計 畫 (转 载） (转)[@more@] 高 德 納 的 二 十 年 計 畫
8123033 穆信成
高德納已經五十八歲了。 他打算再花二十年的時間繼續他的著作，
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)」 知道電腦
科學家們也會做實際的事。另外，這套程式庫全部用他鼓吹的 liter-
ate 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- 終於
被大家寫成 , 以便把他收集到資料庫中。
接下來就開始玩這個資料庫囉。高德納發現 5757 個單字中，有 774
個 degree 是 1 的（只有一根接出去的 edge），位居第一。Degree
= 2 的也有 727 個。株連最廣的單字是 "bares" 和 "cores" ， de-
gree = 25，而 "cores" 的 25 個鄰居都是 degree 大於 9 的。 De-
gree = 1 的單字中有 103 組根本就是孤零零的兩兩成對，如 alpha-
aloha, gonad-monad. 跑一個找 connected component 的演算法，
發現大部分的單字都在同一個有 4493 個單字的大 component 裡面。
高德納自己定了一個方法橫量單字在文章中的出現頻率。 在這 5757
個單字中， "which" 是最常出現的， 其次是 "there" 和 "their"。
"often" 果然常出現，比出現("occur") 還要常出現。
看來高德納真的是玩得不亦樂乎呢。"to have fun", 於是我們可以
想像高德納出這本書的真正原因，是他自己建了這些資料後，發現越
玩越有趣，終於忍不住想出書了。
玩過了單字，想知道美國大學足球隊誰比較強嗎？高德納已經把 120
支隊伍的 638 場比賽建成 graph 了。 他又參考資料， 找出美國的
128 個城市之間的最短距離，並且在發現前人的資料明顯錯誤後自己
寫程式來修正。把蒙娜麗莎的微笑掃描起來後，高德納示範了如何
来自 “ ITPUB博客 ” ，链接：http://blog.itpub.net/10748419/viewspace-1004874/，如需转载，请注明出处，否则将追究法律责任。