??
字號(hào):
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0047)http://www.csdn.net/develop/article/7/7070.shtm -->
<HTML><HEAD><TITLE>高 德 納 的 二 十 年 計(jì) 畫 (轉(zhuǎn) 載）</TITLE>
<META content="text/html; charset=gb2312" http-equiv=Content-Type>
<META content=0 http-equiv=Expires><LINK
href="高 德 納 的 二 十 年 計(jì) 畫 (轉(zhuǎn) 載）.files/news.css" rel=stylesheet>
<STYLE type=text/css>.fst {
BACKGROUND: #eeeecc; BORDER-LEFT: #000000 1px solid; BORDER-RIGHT: #000000 1px solid; PADDING-BOTTOM: 0px; PADDING-LEFT: 15px; PADDING-RIGHT: 15px; PADDING-TOP: 0px; WIDTH: 770px
}
.fstdiv3 IMG {
BORDER-BOTTOM: 0px; BORDER-LEFT: 0px; BORDER-RIGHT: #eeeecc 8px solid; BORDER-TOP: #eeeecc 6px solid
}
</STYLE>
<META content="MSHTML 5.00.2920.0" name=GENERATOR></HEAD>
<BODY aLink=#990000 bgColor=#ffffff bottomMargin=0 leftMargin=0 rightMargin=0
topMargin=0 marginheight="0" marginwidth="0">
<CENTER><LINK href="news.css" rel=stylesheet>
<TABLE border=0 cellPadding=0 cellSpacing=0 width=770>
<TBODY>
<TR>
<TD bgColor=#001880 height=5 width=2></TD>
<TD height=5 width=768></TD></TR></TBODY></TABLE>
<TABLE align=center bgColor=#eeeecc border=1 cellPadding=1 cellSpacing=0
width=770>
<TBODY> </TBODY>
</TABLE>
<DIV align=center>
<DIV align=left class=fst>
<DIV class=fstdiv3
id=print2><BR><BR>
高 德 納 的 二 十 年 計(jì) 畫
<BR><BR><BR>
8123033 穆信成<BR><BR><BR>高德納已經(jīng)五十八歲了。 他打算再花二十年的時(shí)間繼續(xù)他的著作， <BR>The Art of
Computer Programming. 大家知道 Donald E. Knuth
<BR>是資訊科學(xué)界公認(rèn)的大宗師， 知道他以他的重量級(jí)著作 The Art <BR>of Computer
Programming(以下簡(jiǎn)稱TAOCP)[2,3,4]
聞名於世，原計(jì)<BR>畫要出七冊(cè)，但目前只完成了三冊(cè)。但也許並沒(méi)有很多人知道他還有<BR>個(gè)中文名字：「高德納」。<BR><BR> * *
*<BR><BR><BR>TAOCP 這套書的名氣這麼大，敢去碰它的人反倒不多。寒假我因?yàn)橐?lt;BR>些原因，讀了高德納的另一本書 "The Stanford
GraphBase"[1]。大<BR>師的書到底是什麼樣子呢？ <BR><BR>高德納在序言裡說(shuō)了寫這本書的原因：在寫 TAOCP 的第四冊(cè)前，
他<BR>想要用一個(gè)叫做 ladders 的遊戲當(dāng)作貫穿全書的例子。 於是寫了不<BR>少相關(guān)的程式和龐大的測(cè)試資料，最後集結(jié)成了一個(gè)程式／資料庫(kù)。
<BR>他想這套 GraphBase 可以作為大家測(cè)試 graph 演算法的基礎(chǔ)，讓那<BR>些 「街上混的程式員們
(programmers-on-the-street)」 知道電腦<BR>科學(xué)家們也會(huì)做實(shí)際的事。另外，這套程式庫(kù)全部用他鼓吹的 liter-<BR>ate
programming 方式寫成，也可以當(dāng)成一個(gè)活生生的例子。<BR><BR>最後一個(gè)，但卻是最重要的原因是，"to have
fun".「的確，快樂(lè)是<BR>這一路上最主要的原因，但我不敢承認(rèn)。電腦科學(xué)家們總是得裝出一<BR>副咬牙工作的樣子，讓別人心甘情願(yuàn)付給他們高薪水。但遲早這個(gè)社<BR>會(huì)得承認(rèn)，
有些工作仍然值得尊敬 ---
即使它們比任何事情都要來(lái)<BR>得有趣。」<BR><BR>我不禁笑了。高德納在辦正事的途中岔出去做別的事情，一做就是好<BR>幾年已經(jīng)不是第一次。TeX
這個(gè)現(xiàn)在大家都在用的排版系統(tǒng)不就是他<BR>嫌 TAOCP 被排得不好看， 因此自己捲起袖子研究電腦排版的產(chǎn)物嗎？<BR>Tex 耗去了他十年的光陰，而這本
Stanford GraphBase 則可以追溯<BR>到二十年前。高德納好像永遠(yuǎn)不怕老？<BR><BR>Ladders
這個(gè)遊戲是這樣的：挑兩個(gè)五個(gè)字母的英文單字，試試看一<BR>次一個(gè)字母，把一個(gè)字變成另外一個(gè)。但是在過(guò)程中它必須仍然是一<BR>個(gè)英文單字。比如說(shuō)把 black
變成 white 的方法是這樣的：<BR><BR> black -> brack -> brace ->
trace -> trice -> trite <BR> -> write ->
white<BR><BR>大家看得出來(lái)，如果把每個(gè)單字當(dāng)作一個(gè) node, 兩個(gè)單字如果只差<BR>一個(gè)字母，就連一條 edge,
那麼這個(gè)遊戲可以想成在兩個(gè) node 中<BR>找一條 path . <BR><BR>但 GraphBase 有趣的地方卻是資料。 高德納收集了一個(gè)含 5757
個(gè)<BR>單字的資料庫(kù)。他參考了 1971 年以前 Beeler
為了這個(gè)遊戲?qū)ｉT編<BR>的一部字典，刪去老的字，加入新的單字。高德納花了很大篇幅解說(shuō)<BR>他選字的標(biāo)準(zhǔn)：姓名不選，所以 Knuth 就沒(méi)有了；但是
gauss 已經(jīng)<BR>是一個(gè)電磁學(xué)單位，所以受錄了進(jìn)去。他很耐心的等到 e-mail 終於<BR>被大家寫成 email,
以便把他收集到資料庫(kù)中。<BR><BR>接下來(lái)就開(kāi)始玩這個(gè)資料庫(kù)囉。高德納發(fā)現(xiàn) 5757 個(gè)單字中，有 774<BR>個(gè) degree 是 1
的（只有一根接出去的 edge），位居第一。Degree<BR>= 2 的也有 727 個(gè)。株連最廣的單字是 "bares" 和 "cores" ，
de-<BR>gree = 25，而 "cores" 的 25 個(gè)鄰居都是 degree 大於 9 的。 De-<BR>gree = 1 的單字中有 103
組根本就是孤零零的兩兩成對(duì)，如 alpha-<BR>aloha, gonad-monad. 跑一個(gè)找 connected component
的演算法，<BR>發(fā)現(xiàn)大部分的單字都在同一個(gè)有 4493 個(gè)單字的大 component
裡面。<BR><BR>高德納自己定了一個(gè)方法橫量單字在文章中的出現(xiàn)頻率。 在這 5757 <BR>個(gè)單字中， "which" 是最常出現(xiàn)的， 其次是
"there" 和 "their"。<BR>"often" 果然常出現(xiàn)，比出現(xiàn)("occur")
還要常出現(xiàn)。<BR><BR>看來(lái)高德納真的是玩得不亦樂(lè)乎呢。"to have fun",
於是我們可以<BR>想像高德納出這本書的真正原因，是他自己建了這些資料後，發(fā)現(xiàn)越<BR>玩越有趣，終於忍不住想出書了。<BR><BR>玩過(guò)了單字，想知道美國(guó)大學(xué)足球隊(duì)誰(shuí)比較強(qiáng)嗎？高德納已經(jīng)把
120<BR>支隊(duì)伍的 638 場(chǎng)比賽建成 graph 了。 他又參考資料， 找出美國(guó)的<BR>128
個(gè)城市之間的最短距離，並且在發(fā)現(xiàn)前人的資料明顯錯(cuò)誤後自己<BR>寫程式來(lái)修正。把蒙娜麗莎的微笑掃描起來(lái)後，高德納示範(fàn)了如何運(yùn)<BR>用 bipartite
graph matching 的技巧，用骨牌重新拼出這幅名畫。<BR><BR>高德納的文筆親切而幽默。CWeb 是他大力推廣的 literate
program-<BR>ming 系統(tǒng)，他認(rèn)為每個(gè)人都應(yīng)該有一套。 「但是今天已經(jīng)沒(méi)什麼人<BR>能永遠(yuǎn)跟上新軟體的發(fā)行，所以如果你沒(méi)有
CWeb,也不用覺(jué)得太有罪<BR>惡感。」 接下來(lái)他解釋如何安裝 Stanford GraphBase, 這一段的
<BR>makefile 可以給想學(xué) make 的同學(xué)們做很好的參考。
如果裝不起來(lái)<BR>呢？高德納問(wèn)，你有沒(méi)有好好祈禱呀？最後，他希望大家能像他一樣，<BR>多用這些程式庫(kù)和資料檔做些實(shí)驗(yàn)，「也許有天你也會(huì)迫不及待地想<BR>出本這樣的書呢！」<BR><BR>瀏覽了全書，我想：高德納到底是太閒，還是有用不完的精力？將近<BR>六十歲的他，仍舊充滿著旺盛的活力和赤子般的好奇心，而這一切又<BR>以他深厚的功力做為基礎(chǔ)。<BR><BR>*
* *<BR><BR>四月號(hào)的 Dr. Dobb's Journal 做了一篇高德納的專訪[5]。 為什麼<BR>寫書寫到一半， 卻花了十年的時(shí)間在 Tex
上？ 他說(shuō)， Niklaus <BR>Wirth （Pascal, Modular-2 和 Oberon
的設(shè)計(jì)者）一直想設(shè)計(jì)飛機(jī)，<BR>但他發(fā)現(xiàn)他需要夠好的工具，於是他設(shè)計(jì)了一個(gè)個(gè)的電腦語(yǔ)言，造了<BR>自己的電腦。高德納也希望他的書能夠不因科技的進(jìn)步而被淘汰，希<BR>望即使製書的科技進(jìn)步，他的書仍舊是用領(lǐng)先的方式製作的。<BR><BR>談到另一位大師
Edsgar Dijkstra, 他說(shuō) Dijkstra 的力量來(lái)自於他<BR>不妥協(xié)的拗脾氣。「光是想像用 C++
寫程式就會(huì)讓他病倒！」Dijk-<BR>stra 的拿手技巧是鉅細(xì)靡遺地用 formal 方法推導(dǎo)、檢驗(yàn)程式， 這<BR>和工業(yè)界不斷產(chǎn)生數(shù)以 mega
計(jì)的軟體， 但使用者卻無(wú)時(shí)不負(fù)擔(dān)著 <BR>bug 的風(fēng)險(xiǎn)的實(shí)際情況顯然有段差距。高德納則認(rèn)為自己位於兩種極<BR>端的中間。一方面他贊同
formal 方法提供的可靠性，但他也知道在<BR>大系統(tǒng)中這種方式的極限。他盡力維持他的軟體的品質(zhì)，因此他願(yuàn)意<BR>提供賞金給在 TeX 中找到新 bug
的人。<BR><BR>* * *<BR><BR>由於高德納已經(jīng)不用 email 了，他有一個(gè) Web page[6]，
<BR><BR>
http://www-cs-faculty.Stanford.EDU/~knuth/<BR><BR>裡頭還有個(gè) FAQ,
可以看到他中文名字的圖章。大家劈頭要問(wèn)的當(dāng)然<BR>是：第四冊(cè)什麼時(shí)候出來(lái)呀？<BR><BR>他說(shuō)，TAOCP的第四冊(cè)將會(huì)分成三部份，4A :
Enumeration and Back-<BR>tracking, 4B : Graph and Network Algorithms 和 4C :
Optimiza-<BR>tion and Recursion. 從 1997 年開(kāi)始，他會(huì)以大約每 128 頁(yè)為一<BR>個(gè)單位（
高德納好像很喜歡用 2 的乘冪做單位，他付給找出 TAOCP <BR>中錯(cuò)誤的賞金也是 $65536
分）把第四冊(cè)的部份散發(fā)給大家，聽(tīng)取各<BR>方的意見(jiàn)。如果一切順利，第四冊(cè)將在 2003 年正式完成。第五冊(cè)的<BR>完成時(shí)間則定在 2009
年。第五冊(cè)告一段落後，他會(huì)重新整理
TAOCP<BR>的一到三冊(cè)，更新內(nèi)容。再下一步，他將把一到五冊(cè)的重要內(nèi)容全部<BR>濃縮在一本書裡。之後才著手進(jìn)行六和七冊(cè)。<BR><BR>所以，高德納至少得活到
2020 年囉....<BR><BR>為了完成 TAOCP, 高德納已經(jīng)退休，過(guò)著半隱士的生活。 他不用 e-<BR>mail, 不怎麼會(huì)見(jiàn)訪客，
取消大部分的演講和旅行。 他說(shuō)，他得用 <BR>batch 方式工作，而不能把事情 swap 來(lái) swap
去的。他託人在家裡<BR>造了一座管風(fēng)琴，空閒的時(shí)間裡，他就會(huì)彈彈琴自?shī)省Ｈ绻銜?huì)彈琴，<BR>他很願(yuàn)意和你見(jiàn)個(gè)面，來(lái)個(gè)四手聯(lián)彈。<BR><BR>為什麼那麼賣力呢？
在DDJ的專訪裡， 當(dāng)被問(wèn)到他是否能從 Tex 和<BR>Metafont 圖利時(shí)，
他說(shuō)，一旦一個(gè)人能夠餵飽自己，能夠有個(gè)安身<BR>之所，剩下的就是他能為別人做些什麼，如何能為群體做出一些貢獻(xiàn)<BR>了。<BR><BR>因此他很希望程式創(chuàng)作者們不要把演算法當(dāng)作自己的私產(chǎn)。程式應(yīng)該<BR>容易閱讀和了解，因?yàn)樵蕉嗳四軌蛄私馑拍軌虬l(fā)揮越大的影響<BR>力。<BR><BR>也許他也是基於這個(gè)想法繼續(xù)
TAOCP 的寫作吧？ 在他的 web page
<BR>中，對(duì)於他的這件「此生的大事」，他下了這樣的註腳：「我嘗試著<BR>盡我所能的去學(xué)習(xí)電腦科學(xué)裡的一些領(lǐng)域，然後把這些知識(shí)摘要成大<BR>家比較容易了解的方式，讓沒(méi)有那麼多時(shí)間做這種學(xué)習(xí)的人也能夠吸<BR>收他們」。<BR><BR>為了這個(gè)目的，他必須閱讀超過(guò)二十萬(wàn)頁(yè)的文件，然後把它們濃縮到<BR>兩千頁(yè)裡頭。他寫的東西並不是最流行的，但他希望他能從日新月異<BR>的新技術(shù)中，萃取出值得存活到下個(gè)世紀(jì)的東西。<BR><BR>不禁想起前陣子同學(xué)討論到的話題：專家是訓(xùn)練有素的狗嗎？我們?cè)?lt;BR>不該成為專家？高德納毫無(wú)疑問(wèn)地是個(gè)專家，但他的大師學(xué)養(yǎng)和風(fēng)範(fàn)<BR>也許能給我們不少啟發(fā)。<BR><BR>Reference<BR><BR><BR>[1]
Donald E. Knuth, The Stanford GraphBase : A Platform for Combinatorial
<BR> Computing, Addison-Wesley, 1993<BR><BR>[2] Donald
E. Knuth, The Art of Computer Programming, Vol 1 :
Fundamental<BR> Algorithms, Addison-Wesley,
1973<BR><BR>[3] Donald E. Knuth, The Art of Computer Programming, Vol 2 :
Seminumerical <BR> Algorithms, Addison-Wesley,
1973<BR><BR>[4] Donald E. Knuth, The Art of Computer Programming, Vol 3 :
Sorting and <BR> searching, Addison-Wesley,
1973<BR><BR> The Art of Computer Programming
有日文，俄文，西班牙文等許多國(guó)的版本。<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 <BR> 1996, p16-p22<BR><BR>[6]
Donald E Knuth's WWW Page :
http://www-cs-faculty.Stanford.EDU/~knuth/<BR>
http://www.geekchic.com/repliq6.htm
也有一篇小小的訪問(wèn)。高德納最喜歡的<BR> 語(yǔ)言是 CWeb,
最喜歡的運(yùn)動(dòng)是棒球，認(rèn)為有許多人是他值得崇敬的。<BR><BR>
高德納將在最近將他的論文以更淺顯的方式整理過(guò)後，重新集結(jié)出版。<BR>
這套書的預(yù)定讀者並不是電腦科學(xué)的專家，似乎很值得一讀。這套書<BR>
將有八本，前兩冊(cè)已經(jīng)出版：<BR> <BR>[7]
Literate Programming, Stanford, California: Center for the Study of
<BR> Language and Information,
1992<BR> <BR>[8] Selected Papers on Computer Science,
Stanford's Center for the Study<BR> of Linguistics
and Information and Cambridge University Press, spring,
<BR> 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><BR></DIV></DIV></DIV><BR><BR>
<BR>
<TABLE align=center bgColor=#ffffff border=0 cellPadding=2 cellSpacing=1
width=770>
<TBODY>
<TR>
<TD> </TD>
</TR>
</TBODY>
</TABLE>
</CENTER></BODY></HTML>
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -