求真百科歡迎當事人提供第一手真實資料,洗刷冤屈,終結網路霸凌。

唐納德·克努特檢視原始碼討論檢視歷史

事實揭露 揭密真相
前往: 導覽搜尋
唐納德·克努特
原文名 Donald Ervin Knuth
出生 (1938-01-10) 1938年1月10日(86歲)
密爾沃基
國籍 美國
職業 計算機科學家,教授

唐納德·克努特

高德納是算法和程序設計技術的先驅者,計算機排版系統TEX和METAFONT的發明者,他因這些成就和大量創造性的影響深遠的著作而譽滿全球。被譽為「人工智能之父」。[1]

簡介

高德納(Donald Ervin Knuth)——經典巨著《計算機程序設計的藝術》的年輕作者。

洋洋數百萬言的多卷本《計算機程序設計的藝術》(The Art of Computer Programming)堪稱計算機科學理論與技術的經典巨著,有評論認為其作用與地位可與數學史上歐幾里得的《幾何原本》相比。本書作者高德納(Donald Ervin Knuth)因而榮獲1974年度的圖靈獎。

排版軟件TeX和字型設計系統Metafont發明人,所著描述基本算法與數據結構的巨作《計算機程序設計的藝術》被《美國科學家》雜誌列為20世紀最重要的12本物理科學類專著之一,與愛因斯坦《相對論》、狄拉克《量子力學》、理查·費曼《量子電動力學》等經典比肩而立。

個人生平

高德納1938年1月10日生於威斯康辛州密歇根湖畔的密爾沃基(Milwaukee)。這是一個山靈水秀、人才輩出的地方,「人工智能之父」、諾貝爾獎獲得者西蒙(H.A.Simon)也是在這裡出生的,獲諾貝爾獎次年獲圖靈獎。但高德納比西蒙小整整22歲,是一個「小字輩」。高德納的父親是一個多才多藝的人,有研究生學歷,當過小學和中學教師,星期天在教堂演奏風琴,還在自家地下室辦了一個小印刷廠。受父親影響,高德納從小喜歡學習和音樂,並表現出與眾不同的才能。高德納上8年級時,當地的Ziegler糖果廠為了促銷其稱為Giant Bar的一種棒棒糖,在學校中搞了一個比賽,看誰能用Ziegler’s Giant Bar中的字母排列組合出最多的單詞。高德納假裝胃疼,在家裡呆了兩個星期,利用一部大字典,得出了4500個單詞,比裁判掌握的2 000個單詞多出一倍多,一舉為他所在的班奪得冠軍,贏得一台電視機和每人一塊Giant Bar,而高德納本人則贏得一付雪撬。

1956年,高德納以各科平均97.5的創記錄的高分從密爾沃基路德蘭高級中學畢業,進入俄亥俄州克利夫蘭的開思理工學院(Case Institute of Technology)攻讀物理。這一年,他在中學時就創作的一篇出色的科學幻想小說「普茨比度量衡體系」(The Potrzebie System of Weights and Measures)在美國著名的《瘋狂》(Mad)雜誌上發表,高德納獲得了他的第一筆稿費25美元,並因而獲得西屋科學天才的提名獎。在這篇小說中,高德納風趣而富於幻想地提出了替代公制的一種新的計量制度,比如以一本流行雜誌的厚度為長度單位,雖然滑稽可笑,卻設計得嚴密周到,天衣無縫,其中甚至還包括一種新的曆法。文章刊出後大受歡迎,多次重印,1991年還重印過一次,其時作者高德納即將退休。

大學一年級結束以後的暑假,高德納在學校打工,負責把統計數字畫成圖表。碰巧他工作室的隔壁就是計算機房,新到了一台IBM650。當時的計算機體積都很龐大,有供輸入和調試的控制台,上面排列着一排排的開關和指示燈,計算機工作時指示燈快速閃爍變化出不同的圖案,這引起高德納極大的好奇與興趣,他接連好幾天徹夜不眠地呆在機房,觀察它的工作,鑽研使用手冊,探究計算機的奧秘。一年以後,他終於改學數學,與計算機結緣。這段經歷對於高德納是如此重要和關鍵,以致他在《計算機程序設計的藝術》第一卷的卷首,不像別的作者那樣一般寫上「獻給自己的父母」或「獻給自己的妻子」,而是寫着「獻給曾經安裝在開思理工學院的650型計算機,以紀念那些愉快的夜晚」。他的第一個計算機應用程序也是在650計算機上實現的:他為他所在的校籃球隊(高德納人高馬大,也喜愛運動,娛樂)設計了一個複雜的公式,根據球員在每場比賽中的得分、助攻、搶斷、籃板球、蓋帽等多項統計數字對球員進行綜合評估。球隊教練根據高德納的程序挑選和使用球員,使開思理工學院在1960年贏得了聯賽冠軍,高德納的「神奇的公式和程序」也被當地報紙和廣播傳為美談。

1960年,高德納在開思理工學院畢業,不但被授予學士學位,還被破例同時授予碩士學位。之後他進入加州理工學院研究生院,1963年獲得博士學位,留校工作至1968年,然後轉入斯坦福大學任教,其間1972—1973年曾經在奧斯陸大學當客座教授。

高德納至今進行了兩大工程,一個已經完成,一個尚未完成。第一個大工程就是《計算機程序設計的藝術》系列,開始於他念博士期間,計劃出七卷,第一卷《基本算法》於1968年出版,第二卷《半數字化算法》於1969年出版,第三卷《排序與搜索》於1973年出版,第四卷A《組合算法》已於2011年出版。這個工程為什麼前緊後松,長期停頓呢?

高德納暫停了寫作,理由是現有的計算機排版軟件效果太差,破壞了這套書的美。這不免引發作者是否江郎才盡,見好就收的猜測與懷疑——不料輟筆10年的高德納以三個重量級創造性成果:字體設計系統METAFONT(其價值一言以蔽之:對整個西文印刷行業帶來了革命性變革)、文學化編程(充分展示程序設計的藝術性:清晰,美感,詩意),尤其是最具革命性的排版系統TEX(至今仍是全球學術排版的不二之選)給出了強力回應。儘管如此,仍有人說高寫完三卷 TAOCP就去研究TeX,其實是害怕寫第四卷——不過他對這類風言風語根本不以為意:「一個人要把事情做的完美,只有跟上帝的意圖保持和諧,現在上帝要我去寫第四卷了。」

擱置手頭的重要工作,費時10年專研排版美學打造TEX系統,原因其實很簡單:數理圖文排版以前一直使用金屬活字,70年代以降始有激光照排,然而當時的計算機雖能替代人工排出普通的報紙雜誌,但對處理複雜的數理公式卻力不從心。高德納試圖為計算機寫一個小玩藝兒解決上述問題,TeX的前半部分由此產生。編寫過程中,他想參考J·伯克霍夫的Aesthetic Measures(《美學標準》)一書,在哈佛的圖書館幾經查閱也未能如願,之後好不容易在麻省理工學院找到。參考的結果是在TeX里加入一個變量badness,用以衡量一行文字的美感,變量越小文字就越美。

20世紀70年代中期,高德納和其他一些計算機科學家曾經設想在未來10年中將產生一種比現有程序設計語言更加強大,更加優美的新型語言,並預先命名它為「烏托邦84'』(Utopia 84)語言。[2]

1992年,高為潛心寫作TAOCP從斯坦福提前退休,同時停用電子郵箱(他自1975年就開始玩電郵)。2008年,TAOCP前三卷出版30年後,第四卷在高粉的千呼萬喚中終於面世,此際的高德納已然是滿頭白髮。對計算機科學的傾心熱愛,使他為這部作品耗費了畢生心血:從及冠之年直至古稀老人。

所獲榮譽

高德納獲得的榮譽與獎勵極多。ACM除了授予他圖靈獎和軟件系統獎外,還在1971年授予過他以COBOL的發明人、女計算機科學家霍潑(Grace Murray Hopper)命名的獎項,這個獎項是專門獎勵30歲以下的優秀青年計算機科學家的。這樣,高德納一人就先後獲得ACM的三個獎項,在1999年以前,這是計算機科學家中僅有的一位(1999年,布魯克斯獲得圖靈獎,從而也擁有ACM三個獎項,平了高德納的記錄)。無獨有偶,美國數學會也先後授予高德納三個獎項,即Lester R.Ford獎(1975)、J.B.Priestley獎(1981)和Steele獎(1986)。1979年,當時的美國總統卡特向他頒發了全國科學獎章。IEEE授過他兩個獎:McDowell獎(1980)和計算機先驅獎(1982)。1994年,瑞典科學院授予高德納Adelskold獎。1995年他獲得馮·諾伊曼獎和Harvey獎。1996年他獲得日本INAMORI基金會設立的KYOTO獎,這個獎是專門獎勵在高科技領域作出貢獻的科學家的。面對這麼多榮譽,高德納都以平常心對待,據說,紀念他獲得圖靈獎的碗現在只是被他用來盛放水果。

ACM於1974年11月11日在南加利福尼亞瀕臨太平洋的海港城市聖迭戈舉行的年會上向高德納頒發圖靈獎。高德納發表了題為「作為一種藝術的計算機程序設計」(Computer Programming as an Art)的演說。在演說中,一如我們在閱讀他的著作時所感受的那樣,高德納旁徵博引,有根有據,人情人理,娓娓道來,把「科學」與「藝術」的不可分割的關係說得清清楚楚,令人心服口服。演說刊於Communications of ACM,1975年12月,667—673頁,或見《前20年的ACM圖靈獎演說集》(ACM Turing Award Lectures——The First 20Years:1966--1985,ACM h.),33—46頁。

主要貢獻

《計算機程序設計的藝術》系列,開始於他念博士期間,計劃出七卷,第一卷《基本算法》於1968年出版,第二卷《半數字化算法》於1969年出版,第三卷《排序與搜索》於1973年出版,第四卷《組合算法》於2008年出版。《計算機程序設計的藝術》一書以其內容的豐富和深刻喻為經典,有人甚至稱之為「計算機的聖經」,被譯為俄、日、西、葡、匈牙利羅馬尼亞等多種文字在世界各國廣泛流傳,其發行量創造了計算機類圖書的最高記錄,直至20世紀80年代中期,都一直保持着月銷售量每卷達2000冊的勢頭,成為Addison-Wesley出版社成立以來銷路最好的圖書。我國也由蘇運霖翻譯並出版了《計算機程序設計藝術》一書。

其它貢獻

此外,高德納還有許多「小創造」。計算機科學技術中兩個最基本的概念:「算法」(Algorithm)和「數據結構」(Data Structure)就是高德納於29歲時提出來的。1973年他首創雙向鍊表。在編譯器設計方面,著名的LR(k)文法也是高德納在對自左至右、自底向上的移進一歸約分析進行了深刻剖析的基礎上,經過高度概括和集中以後發明的,它表示具有從左(L)到右(R)的分析而向前看k個符號,以確定所要進行的歸約和應用何種語法解釋。LR(k)文法的識別效率高,在從左至右掃描輸入串時,就能發現其中的語法錯誤,並能準確地指出出錯位置,因此被廣泛應用。此外,利用LR(眾)文法還能正確區分像Flying planes is fun和Flying planes can crash這類句子(前一個句子「開飛機很有趣」中flying是動名詞,而後一個句子「飛行中的飛機可能出事」中Flying是現在分詞當形容詞)。以著名的巴克斯—諾爾範式為基礎的「屬性文法」(attribute grammar)也是高德納首先提出來的。屬性文法在普通的上下文無關文法(context-free grammar)的基礎上,對每一個終結點或非終結點加上一些屬性,和對這些屬性進行估值的語義規則集,從而形成一種新的、有更強表達與描述能力的文法。其中屬性是由的有序偶對組成的。屬性的內容則可包括模式標識符表等。

在算法方面,有他和他的學生共同設計的諸如Knuth-Bendix算法和Knuth-Morris-Pratt算法,前者是為了考察數學公理及其推論是否「完全」而構造標準重寫規則集(rewriting rule set)的算法,曾成功地用它解決了群論中的等式的證明問題,是定理機器證明的一個範例。後者是在文本中查找字符串的簡單而高效的算法。此外,高德納還設計與實現過最早的隨機數發生器(random number generator)。

主要著作

高德納的著作很多,除了已由Addison-Wesley出版社出版的三卷The Art of Computer Programming(由管紀文、蘇運霖等譯成中文,國防工業出版社出版,介紹TEX和METAFONT的五卷《計算機與排版》(Computers and Typesetting)早已流傳於世外,還有以下一些主要著作:

《研究之美》(Surreal Numbers,Addison-Wesley,1974)

《具體數學》(Concrete Mathematics,Addison-Wesley,1989)

《數學論著集》(Mathematical Writings,MAA,1989)

《用於算法分析的數學》(Mathematics for the Analysis of Algorithms,Birkhauser,1990,第三版)

《作文式程序設計》(Literate Programming,CSLI,1992)

《公理與外殼》(Axioms and Hulls,Springer,1992)

《斯坦福的GraphBase:組合計算用的平台》(The Stanford Graph Base:a Platform for Combinatorial Computing,ACMh·,1993)

其中,《研究之美》(Surreal Numbers)一書介紹了劍橋大學的康韋(J.H.Conway)所發明的一種新的數制,是高德納聽了康韋向他作的介紹後,用了一周時間寫成的小說體裁的作品。有評論家指出,這是歷史上第一次一個重大的數學發現以小說的形式向公眾進行介紹。由此可見,高德納的藝術才華同樣是非凡的,要不是計算機深深吸引了他,高德納很可能會成為出色的小說家或音樂家(前面說過他喜歡音樂,會自己製作管風琴,會創作不錯的樂曲呢)。

軟件

高德納花了整整9年的時間和精力,完成了對整個西文印刷行業帶來了革命性變革的TEX排版軟件和METAFONT字型設計軟件。這兩個軟件為高德納贏得了ACM的另一個獎項:1986年度的軟件系統獎(Software System Award)。但是這兩個軟件並沒有為高德納和斯坦福大學賺過一分錢:高德納把它們作為自由軟件無償提供給用戶。這比理查德·斯托爾曼(Richard Stall man,1990年ACM Hopper獎獲得者)在1984年發動自由軟件運動早了約5—6年。高德納說:「我寫這兩個程序是出於對書籍的熱愛,也想給這個領域以必要的推動。我已經有些名氣了,我的書賣得也不錯。所以我不需要為我出於熱愛而做的事保留專賣權。此外,數學家通常是不為他們發現的定理獲取報酬的」。1979年,高德納還創建了TEX用戶集團,這個集團10年前的成員數就超過3000。細心的讀者也許會注意到,許多西文書版權頁的下部註明「本書用TEX系統排版」。

作為開源代碼運動最早的倡導者之一,高德納將Tex 和Metafont無償貢獻給了世界,自己沒有從中獲取任何報酬。他的想法是,一個人一旦能夠餵飽自己並有個安身之所,剩下的就是為別人做點什麼了。「我嘗試盡我所能的去熟悉電腦科學裡的一些領域,然後把這些知識摘要成大家比較容易了解的方式,讓沒有那麼多時間做這種學習的人也能夠吸收它們」。為此他常常需要閱讀超過20萬頁的文獻,然後將之濃縮為兩千頁——他無意追趕最流行的內容,而是希望從日新月異的信息中萃取出能夠存活到下個世紀的精華。

TEX的版本號不是自然數列,也不是年份,而是從3開始,不斷地逼近圓周率 (3.14,3.141…目前最新版本是3.1415926)。高德納再一次用行動宣告,我這個東西,不可能再有什麼大的改進了,最多只能小修小補,使其 趨近完美。他還專門設立了獎金: [2] 誰發現TEX的一個錯誤,就付他2.56美元,第二個錯誤5.12美元,第三個10.24美元…以此類推。我們都知道,傳 說某個國王就因為這種指數遊戲失去了江山,高德納作為算法大師,更清楚指數增長的可怕性。然而他卻敢立此重賞,結果直到今天,他也沒有為此付出多少錢,高的另一懸賞是向發現其著作中錯誤的人發獎,數額依舊是2.56美元始,因為「256美分剛好是十六進制的一美元」。不過寥寥幾位獲獎者都將有他簽名的支票當作文物珍藏,並未打算去銀行兌現。可見TEX經過了怎樣的千錘百鍊。這個耗費十年打造的玩具,讓當初質疑圖靈獎發錯了的人們全部閉嘴了,他們甚至改口說:哦,為了這個TEX,不妨再給高德納一個圖靈碗吧。

烏托邦

20世紀70年代中期,高德納和其他一些計算機科學家曾經設想在未來10年中將產生一種比現有程序設計語言更加強大,更加優美的新型語言,並預先命名它為「烏托邦84'』(Utopia 84)語言。烏托邦原是托馬斯所著Utopia一書中所描述的人間理想王國,高德納借用過來代表一種未來的理想語言,希望它有更好的數據結構和控制結構,更符合結構化程序設計的思想,等等。高德納提出Utopia 84已經過去20多年了,雖然程序設計語言在不斷地發展與完善之中,但「理想語言」並未出現,可能永遠也不會出現。但新一代人會不斷進取。高德納在20世紀80年代所倡導的「作文式程序設計」(literate programming,國內有人將它譯為「文化程序設計」)就是這一努力的又一體現和成果。我們從上小學起不就學做作文嗎?作文首先要構思好故事,把事情的來龍去脈交代清楚,這相當於編程時先要把程序邏輯弄好。其次要圍繞故事情節儘可能把有關的人物、環境等細節描寫得清清楚楚,生動活潑,這相當於在程序中加入必要的注釋和說明,以便閱讀和理解。所謂作文式程序設計就是要像寫作文那樣進行編程,從完成的「源程序」中既可提煉出可執行的程序代碼,又可生成程序文檔,「畢其功於一役」。作文還有一個要點是分段,一篇作文要分成若干段落,以便層次分明,鋪陳有序。作文式程序設計也是這樣,一個複雜的程序是由若干較簡單的片段構成的,較大的片段還可分為更簡單的一些小片段。1983年,高德納推出了第一個這樣的程序設計系統WEB。WEB包括兩個子系統,一個子系統從WEB程序中自動地抽出描述算法的部分,並且加工成PASCAL編譯器所能接受的形式,然後據此得到可在計算機上執行的代碼。另一個子系統則把WEB程序加工為TEX系統所能接受的形式,並據此得到具有高度可讀性的完整的程序文檔。顯然,WEB就是一個完成"PASCAL作文」的工具。繼WEB之後,提姆勃萊比(H.W.Thimbleby)開發出CWEB,和WEB類似,但是是一個完成「C作文」的工具。WEB和CWEB都是自由軟件,可從因特網上下載。

整個WEB程序還將自動產生目錄和索引。大家都知道或有過親自體驗,在軟件開發中,文檔編寫在整個過程中占着相當大的比重,是一種十分重要而又非常煩人的工作。作文式程序設計將大大減輕這方面的負擔,並提高文檔質量。因此,像我們從小學起就要學習寫作文那樣,學習並掌握用作文式程序設計進行編程實在是一件非常有意義、非常重要的事。

奇聞異事

高德納曾在自傳的開頭幽默地發問:「Donald Knuth真的只是一個人麼?」作為現代計算機科學的鼻祖,他完成了編譯程序、屬性文法和運算法則等領域的前沿研究,出版專著17部,發表論文150餘篇(涉及巴比倫算法、聖經、字母「s」的歷史等諸多內容),寫出兩個數字排版系統,同時在純計算數學領域也有獨特貢獻。他獲得的獎項難以勝數,其中包括ACM Turing Award頒發的圖靈獎(1974),美國國家科學獎(1979),日本KYOTO獎(1996),瑞典科學院的Adelskold獎及馮諾伊曼獎。而他對榮譽從不經意,據說那隻代表至高榮譽的圖靈碗被用來盛放水果。——回首過往,幾十年時光如白駒過隙,大約是他自己對做出的成果如此之多也感到吃驚,所以才有以上一問。

八歲時的高德納即顯出超凡智力:當時某糖果商以小學生為參與對象舉辦了一項益智趣味比賽,要求用「Ziegler’s Giant Bar」(分別為糖果廠名和出產的棒棒糖名)里的字母寫出儘可能多的單詞。高假裝胃疼宅家兩周,依靠一部大字典列出了4500個單詞(超出裁判掌握的2000個單詞一倍多),不僅使所在班級奪冠(獎品為一台電視機和每人一塊Giant Bar),本人也贏得一付雪撬。其賽後感言曰:我還能寫出更多。

在數學上,高德納也很早就表現出天才。高中一年級時,他發明了一種方法,利用這種方法,對任意畫出的2條相交直線,他能立即給出相應的方程。

在高中第一學年,高德納並未對數學發生太大興趣,他更喜歡聽音樂與作曲,一度考慮過報考音樂專業。這個愛好深度影響到他後來的生活及研究——他將寫作喻為演奏管風琴,其書房裡的確也擺放有一台特製的84管管風琴,此外他還會薩克斯和大號等樂器。所著《娛樂和遊戲論文集》一書有四個章節內容涉及到高的「主要副業」——音樂;進入90年代,當連續工作幾天需要放鬆一下時,他會着手譜寫管風琴樂曲。

1956年以科均97.5的分數高中畢業進入凱斯理工學院物理專業後,高德納中學時創作的科幻小說《普茨比度量衡體系》發表於著名的《瘋狂》(Mad)雜誌,掙得平生第一筆稿費25美元及西屋「科學天才」提名獎。這個作品曾多次再版,直到作者即將退休的1991年還重印過一次。

大學一年級留校打工,毗鄰的計算機房新到了一台IBM650——這個指示燈閃爍不定的龐然大物讓高德納生出莫大興趣。當獲准在晚上操作那台計算機後,他幾天不眠不休地觀察探究,並且改動了說明手冊上的程序使之更加好用。一年後,高改入數學系,自此終生同計算機結緣。當時兼職學校籃球隊的他用IBM650寫了一個程序,用於對球員在每場比賽中得分、助攻、搶斷、籃板球、蓋帽等一攬子數據的分析評估,球隊教練據此挑選球員,使凱斯理工學院贏得了1960年的聯賽冠軍。這個「神奇的公式和程序」引來了當地媒體乃至CBS電視台的大肆報道,高所在球隊和IBM650的合影被IBM印到了產品宣傳冊上。這段經歷的重要性不言而明,以至高德納在巨著《計算機程序設計的藝術》第一卷卷首寫下「獻給曾經安裝在開思理工學院的650型計算機,以紀念那些愉快的夜晚」的題辭。

上大二那年,某教授在課堂上給出一個刁鑽的題目,宣稱誰能破解就可記成績「A」。高跟大多數同學都以為那是道無解的題,直到某日他未趕上公共汽車,只能步行去看一個演出時,方決定利用路上的閒暇碰下運氣。不曾想問題很快便獲得解決,成功地得到了「A」。在接下來的那個學年裡,他的離散數學成績又一次被老師評為「A」。

高德納1960年畢業於開思理工學院,因學業特別出色,被破例同時授予學士和碩士學位。之後在伯克利攻讀數學博士期間,ALGOL60經常因為編譯器不成熟出現故障,他為此編寫了一個簡單的測試程序,人稱「Man or boy test」(男人或男孩測試),可以譯成「是男人就得-67」。高解釋,用ALGOL60來編譯這段程序,只要運行結果等於-67,就說明這個編譯器沒有問題了,是純爺們兒。

習慣用鉛筆而非鍵盤寫初稿,高將原因歸咎於打字速度遠高于思考速度(每分鐘 80 個單詞以上),而這會導致思考出現太多停頓,用鉛筆可以讓思考與輸入速度保持一致——「我打字的速度比我思考的速度更快,這樣當我試圖用鍵盤創作重要內容時,就會產生同步問題。速度通常不會是最重要的標準。科學一般都難以迅速解釋或迅速領會……我通常的工作方式是用鉛筆和紙先把所有東西都寫下來,然後在旁邊放一個大廢紙簍。然後使用Emacs將所有文本鍵入到機器中……特定的Emacs快捷鍵使得寫書的過程有點兒像演奏風琴……」

「我戴着一頂計算機科學家的帽子,而不是一頂數學家的帽子。」這似乎暗示了身為加州理工學院數學博士的高對數學家的某種成見——在他看來後者只知道「What is it(這是什麼)」,而前者還知道「How to do it(如何做到這一點)」這可能是他心目中的數學與計算機科學的區別。

斯坦福大學曾讓高德納為自己選擇一個頭銜,他確定的是「計算機程序設計藝術名譽教授」。高認為「計算機科學」不是科學(他很訝異人們為何如此喜歡科學),而是一門藝術。它們的區別在於:藝術是人創造的,而科學不是;藝術是可以無止境提高的,而科學不能;藝術創造需要天賦,而科學不需要。

傳聞高改作業通常是隨機翻到一頁認真批閱,有了一個初步印象後,對剩下的內容就只大概看看了。閱讀大致也照此辦理:遇上大部頭先讀第316頁,如果書比較薄就看第100頁;隨後就可以作出判斷了,據說準確率還八九不離十。如果追隨他的人很多,以後著書就要注意了:寫到第316頁或100頁時一定要停下來多推敲下。這或許是高德納推崇隨機算法的結果。

「文學編程(Literate Programming)」是高寫的又一程序,他自稱寫這個程序的動機有二:A.讓一個程序員(或許就是他自己)在某一日拿到普利策獎;B.讓那些提出「結構化程序」的傢伙在寫「非文學程序」時,就像他當年寫「非結構化程序」時一樣懷有罪惡感——娃哈哈。有關「文學編程」設想的文字最先發表於英國的《計算機學報》,有人問為何不在美國發表,高答曰:美國人沒文化,他們理解不了啊。

《美國數學月刊》刊載過高德納一篇名為「衛生紙問題」 的論文,研究如何合理使用廁紙的算法,小節標題中使用了大量的「糞便學」詞彙。編輯警告他,過度調侃的文風在我們這裡是危險的,請三思!高替換了小標題里的某些詞,但不想動文章標題,遂在給編輯的回信里寫道:我用這個題目做過兩次演講,主題早已被廣泛採用和討論……云云。編輯無奈之下只好表示:「你的廁紙被接受了!」(斯坦福大學計算機科學系樓內的廁紙架可並放兩筒廁紙,供如廁者取用。捲筒大小不等時,喜歡從大筒拿紙的叫big-chooser【大的選擇器】,喜歡從小筒拿紙的則稱little-chooser【小的選擇器】;若兩筒大小接近,一般人的選擇可能是離手最近的。廁紙平時由janitor【看門人】負責更換,用完一筒換掉一筒;不過要是同時用完,恐怕就會有人遇上麻煩了……高研究的似是兩筒紙同時用完的窘境出現的概率)

在伯克利畢業的前一年,著名的艾迪生-韋斯利出版社約初露頭角的高德納寫一本編譯器和程序設計方面的書,這件原本尋常的事最終成就了計算機科學史上的一個奇觀。出版社1962年約稿,可直到1966年還動靜全無,編輯忍不住去電催促,說都過去4年了,書寫到啥程度了啊?高答才3000來頁。編輯驚呼那幹嘛還不交稿?答曰還沒進入正題呢。編輯崩潰地說,那只能出多卷本了……

高做過大受歡迎的「信仰與科學的關係」系列講座,對訪者問及的寫作和信仰之間的關係,他回答說:「計算機科學是既壯觀又優美的,我嘗試儘自己所能,以最恰當的方式來解釋我所了解的某些片斷……我相信,總有一些神秘的東西是超越人類的理解而存在的……我認為,上帝希望我能創造某些成果,而這些東西能夠啟發其他人去創造別的成果。」

高德納這個中文名來自姚儲楓教授(香港城大計算機科學系主任,華裔圖靈獎得主姚期智的夫人)。以「高」為姓,據Knuth自述是因其個頭高大,且輔音G和K讀音接近;「德納」則與「Donald」相諧,且在中文裡含體面高貴之義。其時(1977年)高德納攜夫人及兒女John和與Jen正準備訪問中國大陸——姚儲楓給孩子也分別起了「高小強」、「高小珍」的名字,他們全家還同中國孩子在公園玩過無須語言交流的遊戲。

有人視高為文藝復興時期式的天才人物,因其不僅博學,更難得的是具超一流的動手能力——在分工日益細化,專業領域愈來愈狹窄的現代社會,這種博而專,基礎與應用兼能,理論和操作並行的人才類型尤為罕見。如同一個人獨力設計製造一架飛機,除了需要精通空氣動力學理論,還須考慮機身上每一顆螺絲釘的固定方式,這確實不免讓人想到歐洲文藝復興時期列奧納多·達·芬奇那樣的全能巨人。

《計算機程序設計藝術》第一卷於1968年推出,可真正能讀完讀懂的人為數並不多(傳比爾·蓋茨費時幾個月才讀完這一卷,然後說,如果你想成為一個優秀的程序員,那就去讀這個《基本算法》吧)。高對此解釋道:「我知道我的書是不容易讀,不過要知道的是,如果不是我精雕細琢地寫的話,它們會比現在難讀一百倍。」1973年,這部剛出到第三卷的書(計劃寫七卷)已被計算機界視為「神作」,最初幾年就賣出100多萬套;譯為俄、日、西、葡、匈牙利、羅馬尼亞等多種文字後,更創造了計算機類圖書的銷售紀錄。美國計算機協會(ACM)也不淡定了,1974年就將國際計算機界的至高榮譽「圖靈獎」授予了他——此時的高德納年方36歲,他迄今還是這項最年輕圖靈獎獲得者紀錄的保持者。

視頻

Donald Knuth - Two final major research projects (83_87)

參考文獻