概述

李開復(fù)曾說，練內(nèi)功，不要僅僅花功夫?qū)W習(xí)各種流行的編程語言和工具，以及一些公司招聘廣告上要求的科目。要把數(shù)據(jù)結(jié)構(gòu)、算法、數(shù)據(jù)庫、操作系統(tǒng)原理、計算機體系結(jié)構(gòu)、計算機網(wǎng)絡(luò)，離散數(shù)學(xué)等基礎(chǔ)課程學(xué)好。最好還是試試Donald Knuth的Art of Computer Programming里的題目，假設(shè)你可以解決當(dāng)中的大部分題目，就說明你在算法方面的功力不錯了。

Donald Knuth

Donald Knuth自傳的開頭這樣寫道：“Donald Knuth真的僅僅是一個人么？”作為世界頂級計算機科學(xué)家之中的一個。Knuth教授已經(jīng)完畢了編譯程序、屬性文法和運算法則的前沿研究。并編著完畢了已在程序設(shè)計領(lǐng)域中具有權(quán)威標(biāo)準(zhǔn)和參考價值的書目的前三卷。在完畢該項工作之余。Knuth還用了十年時間發(fā)明了兩個數(shù)字排版系統(tǒng)。并編寫了六本著作對其做了詳盡的解釋說明。如今,這兩個系統(tǒng)已經(jīng)被廣泛地運用于全世界的數(shù)學(xué)刊物的排版中。隨后。Knuth又發(fā)明了文件程序設(shè)計的兩種語言，以及“文章性程式語言”相關(guān)的方法論。

到眼下為止，Knuth已經(jīng)出版發(fā)行了17部書籍，一百五十余篇論文，包含了巴比倫算法、圣經(jīng)、字母“s”的歷史等多方面的內(nèi)容。作為一名數(shù)學(xué)家。Knuth曾開創(chuàng)了幾門新的課程，為純計算數(shù)學(xué)做出了非常大貢獻。他所獲得的獎項和榮譽數(shù)不勝數(shù)，當(dāng)中最值得注目的有1974年美國計算機協(xié)會圖靈獎(ACM Turing Award)。1979年美國前總統(tǒng)卡特授予的科學(xué)金獎(Medal of Science)以及1996年11月因為發(fā)明先進技術(shù)榮獲的極受尊重的京都獎(Kyoto Prize)。在不多的業(yè)余時間里。Knuth不僅寫小說，還是一個音樂家、作曲家、管風(fēng)琴設(shè)計師。

早期經(jīng)歷

Knuth，1938年1月10日生于美國威斯康星州密爾沃基市。他在模式方面辨別和熟練操作的能力在八年級的時候開始顯現(xiàn)出來。當(dāng)時。當(dāng)?shù)氐囊患姨枪圃焐膛e辦了一項比賽。比賽要求選手用其品牌“Ziegler's Giant Bar”中的字母組成新的單詞，規(guī)定時間內(nèi)組成單詞數(shù)量最多者獲勝。Knuth參加了比賽，并以單詞總數(shù)4500余個遠(yuǎn)遠(yuǎn)超過了裁判的2500個的標(biāo)準(zhǔn)。輕松贏得頭獎。賽后，Knuth說道，假設(shè)自己當(dāng)初想到回答時用些省略符號的話。還能寫出很多其它。

Knuth多產(chǎn)的出版事業(yè)開始于他的高中時代，當(dāng)時他的科技設(shè)計被Westinghouse Science Talent Search 光榮提及。他的“Potzebie System of Weights and Measures ”的基礎(chǔ)章節(jié)被登在“Mad”雜志第26號。“Mad”的編輯認(rèn)識到了年輕的Donald著作的重要性，以25美元買下了他的文章，并刊登在了其1957年6月的期刊上。

高中的時候，Knuth對數(shù)學(xué)并沒多大興趣，而是把主要精力放在主修的課程：聽音樂和作曲上。他在高中的樂隊里吹薩克斯、大號時，曾把Dragnet、 Howdy Doody Time 和 Brylcream的主題曲聯(lián)成一段新的音樂。

1956年?？伺匾愿骺破骄?7．5的創(chuàng)記錄的高分從密爾沃基路德蘭高級中學(xué)畢業(yè)。進入俄亥俄州克利夫蘭的開思理工學(xué)院(Case Institute of Technology)攻讀物理。這一年，他在中學(xué)時就創(chuàng)作的一篇出色的科學(xué)幻想小說“普茨比度量衡體系”(The Potrzebie System of Weights and Measures)在美國著名的《瘋狂》(Mad)雜志上發(fā)表，克努特獲得了他的第一筆稿費25美元，并因而獲得西屋科學(xué)天才的提名獎。

在這篇小說中，克努特風(fēng)趣而富于幻想地提出了替代公制的一種新的計量制度，比方以一本流行雜志的厚度為長度單位。盡管滑稽可笑，卻設(shè)計得嚴(yán)密周到。天衣無縫。當(dāng)中甚至還包含一種新的歷法。文章刊出后大受歡迎，多次重印，1991年還重印過一次，其時作者克努特即將退休。

盡管 Knuth的等級平均分是學(xué)校歷史上最高的，可是他和他的指導(dǎo)老師還是對他是否能成功學(xué)習(xí)大學(xué)數(shù)學(xué)持懷疑態(tài)度。

Knuth說在他高中階段和大學(xué)早期一直有一種自卑感，這個問題一度是他的一個障礙。作為一個大學(xué)新生，Knuth沒有對于失敗的恐懼。他花了很多時間攻克額外的數(shù)學(xué)難題。幾個月后。他在這方面的能力已經(jīng)遠(yuǎn)遠(yuǎn)超過了其它同學(xué)。

高等教育和早期的計算機工作

當(dāng)Knuth在Case科學(xué)院獲得物理獎學(xué)金時，夢想成為一個音樂家的計劃改變了。Knuth回去繼續(xù)研究數(shù)學(xué)是在大二，當(dāng)時一個愛出難題的教授提出了一個特殊的問題，并說哪個學(xué)生能解決問題就立馬記成績“A”。Knuth跟大多數(shù)同學(xué)一樣，也覺得那是道解不出來的題目。直到有一天。他錯過了公共汽車，僅僅能步行去看一個演出，Knuth利用路上這點空暇時間決定嘗試一下。那陣子他運氣真的是非常好，不僅問題非?？炀徒忾_了。得到了“A”。還成功地常常逃課。盡管 Knuth也承認(rèn)，逃課讓他有負(fù)罪感，可是非常明顯，他全然有能力補上落下的功課，接下來的一學(xué)年，他的離散數(shù)學(xué)就又得了個“A”，并且還獲得了給自己不能參加的課程評定論文等級的工作機會。

1956年，作為Case的新生，一年級結(jié)束以后的暑假，克努特在學(xué)校打工，負(fù)責(zé)把統(tǒng)計數(shù)字畫成圖表。碰巧他工作室的隔壁就是計算機房，新到了一臺IBM650。

當(dāng)時的計算機體積都非常龐大，有供輸入和調(diào)試的控制臺，上面排列著一排排的開關(guān)和指示燈，計算機工作時指示燈高速閃爍變化出不同的圖案，這引起克努特極大的好奇與興趣，他接連好幾天徹夜不眠地呆在機房，觀察它的工作。鉆研使用手冊，探究計算機的奧秘。一年以后，他最終改學(xué)數(shù)學(xué)，與計算機結(jié)緣。這段經(jīng)歷對于克努特是如此重要和關(guān)鍵，以致他在《計算機程序設(shè)計的藝術(shù)》第一卷的卷首，不像別的作者那樣一般寫上“獻給自己的父母”或“獻給自己的妻子”。而是寫著“獻給以前安裝在開思理工學(xué)院的650型計算機，以紀(jì)念那些愉快的夜晚”。

天天與計算機為伍，Knuth說直到一年后，女孩才進入了他的生活。這又是計算機科學(xué)界一直以來虧欠科學(xué)家們的一個事例之中的一個。

Knuth 熬夜讀IBM 650的說明手冊，自學(xué)主要的程序設(shè)計。那時，在高等計算機語言發(fā)明之前。程序編寫僅僅能用第二代或是匯編語言。

這個工作既耗時又困難。由于指令必須依據(jù)每臺機器特定的構(gòu)造編寫，而實際上指令僅僅須一步就可從二進制0、1系列轉(zhuǎn)存到計算機硬盤上。Knuth說，有了第一次使用650的經(jīng)歷，他便肯定自己能編寫出比說明手冊上介紹的更好的程序。

Knuth非?？毂汩_始“閑逛”，編寫能夠運行數(shù)學(xué)函數(shù)的程序。

他的第一個程序是把數(shù)字轉(zhuǎn)化為素數(shù)。第三個是做井字游戲（或者說是讓計算機在改正每次輸?shù)腻e誤的過程來學(xué)會玩井字游戲）。

他的第一個計算機應(yīng)用程序也是在650計算機上實現(xiàn)的：他為他所在的?；@球隊(克努特人高馬大，也喜愛運動,娛樂)設(shè)計了一個復(fù)雜的公式，依據(jù)球員在每場比賽中的得分、助攻、搶斷、籃板球、蓋帽等多項統(tǒng)計數(shù)字對球員進行綜合評估。球隊教練依據(jù)克努特的程序挑選和使用球員，使開思理工學(xué)院在1960年贏得了聯(lián)賽冠軍，克努特的“奇妙的公式和程序”也被當(dāng)?shù)貓蠹埡蛷V播傳為美談。

作為學(xué)校籃球隊的經(jīng)理，Knuth編寫了一個依據(jù)不同成績標(biāo)準(zhǔn)評定每個運動員對球隊貢獻等級的程序。他的努力贏來了那些覺得這樣做有助于球隊贏得同盟冠軍的教練的好評（盡管，無庸質(zhì)疑，不是每個運動員都這樣覺得）。

Knuth的成就成了新聞周刊的標(biāo)志，他和教練、計算機的照片也被刊登在IBM650后來的說明手冊上，當(dāng)然這也是Knuth的第一個計算機應(yīng)用程序。

1960年，Knuth從 Case畢業(yè)時享有著最高榮譽。在由全體教員參加的選舉上，他因其公認(rèn)的出眾成就不但被授予學(xué)士學(xué)位，還被破例同一時候授予碩士學(xué)位。之后他進入加州理工學(xué)院研究生院。1963年獲得博士學(xué)位，留校工作至1968年。然后轉(zhuǎn)入斯坦福大學(xué)任教。其間1972—1973年以前在奧斯陸大學(xué)當(dāng)客座教授。

1963年，Knuth回到加利福尼亞理工學(xué)院攻取了數(shù)學(xué)博士學(xué)位。之后成為了該院的數(shù)學(xué)教授。

在加利福尼亞理工學(xué)院任教期間，Knuth作為Burroughs 公司的顧問繼續(xù)從事軟件開發(fā)工作。

1968年。他增加了斯坦福大學(xué)，九年后坐上了該校計算機科學(xué)學(xué)科的第一把交椅。1993年，Knuth成為斯坦福大學(xué) “the Art of Computer Programming”（計算機程序設(shè)計藝術(shù)）的榮譽退休教授。

計算機程序設(shè)計藝術(shù)

1962年，Knuth還是個研究生的時候就開始了他計算機程序的工作。

那時，他已經(jīng)開始了個人咨詢，為不同的機器編寫編譯程序。編譯程序是一種翻譯原始或高級語言和對象或二進制機器語言的中間語言。在不知道眾多軟件公司正高額尋求成百上千的編輯者的情況下，Knuth編寫了一個程序，賺得5000美元。他的名字立馬響譽了整個行業(yè)。在伯克利畢業(yè)的前一年，世界上一流的出版社Addison-Wesley艾迪生-韋斯利出版社約初露頭角的高德納寫一本編譯器和程序設(shè)計方面的書，這件原本平常的事終于成就了計算機科學(xué)史上的一個奇觀。出版社1962年約稿，可直到1966年還動靜全無，編輯忍不住去電催促，說都過去4年了，書寫到啥程度了啊？高答才3000來頁。編輯驚呼那干嘛還不交稿？答曰還沒進入正題呢。編輯崩潰地說，那僅僅能出多卷本了……

當(dāng)Knuth的出版商計算出他的那3000頁的筆跡打印成文章大約須要2000頁時。大家才發(fā)現(xiàn)這實際上是一項多么大的project。在3000頁的手寫設(shè)計草圖中。Knuth發(fā)明了一種綜合方法，用于分析或決定結(jié)構(gòu)翻譯所客觀須要的文法規(guī)則。近期。關(guān)于他的那第一部著作，Knuth自己這樣評述：“用三年半的時間寫第一章可并非件好事?！盞nuth決定將它詳述，成為一部更大的關(guān)于程序設(shè)計科學(xué)的縱覽。共分為七個部分。一部巨著就這樣——誕生了?！队嬎銠C程序設(shè)計藝術(shù)》。至今仍是各程序類圖書書架上標(biāo)志性的書籍

把一件尋常的事做到人間極致。這就是高納德。他不是故弄玄虛，他的心里攢著一股勁兒。要寫一部與牛頓的《自然哲學(xué)的數(shù)學(xué)原理》相媲美的巨著。 1968年，《計算機程序設(shè)計藝術(shù)》(TAOCP)的第一卷正式出版了。這一卷的標(biāo)題叫《基本算法》。但難度卻并不低。。

微軟首席運行官比爾蓋茨在1995年接受一次採訪時說。“假設(shè)你覺得你是一名真正優(yōu)秀的程序猿，就去讀第一卷。確定能夠解決當(dāng)中全部的問題?！敝档米⒁獾氖?，蓋茨本人讀這本書時用去了幾個月的時間。并同一時候進行了難以置信的訓(xùn)練。蓋茨還說：“假設(shè)你能讀懂整套書的話，請給我發(fā)一份你的簡歷。

”高納德本人的說法更犀利：要是看不懂，就別當(dāng) 程序猿。

同年，高納德跳槽到斯坦福大學(xué)。并當(dāng)上了教授。

一年后，TAOCP第二卷正式出版。1973年，這本書出到了第三卷。

這三卷書被計算機界驚為“ 神作”，在最初的幾年內(nèi)就賣出去100多萬套。

依照計劃，這套書一共是七卷?？墒侨缃駝倓倢懲耆?，就已是震古爍今。

震到什么程度呢。連圖靈獎頒獎委員都 坐不住了。依照慣例。圖靈獎的獲獎?wù)叨际浅删偷壬?。要?jīng)過時代的檢驗。但此時，美國計算機協(xié)會便決定馬上為其頒發(fā)圖靈獎。

這對高納德來說，無疑是個殊榮。 這一年他僅僅有36歲。至今。他仍保持著圖靈獎最年輕獲獎?wù)叩募o(jì)錄。

高納德在獲此殊榮之后。再一次令世界大跌眼鏡：他宣布從此歇筆了，由于排版工具太差。破壞了這套書的美。這一動作讓外界十分震驚。有人說。高德納江郎才盡，見好就收；有人說。圖靈獎對前三卷的評價過高了。高納德僅僅好找理由撤了。

Tex文字排版系統(tǒng)

可高納德在輟筆的10年間竟然創(chuàng)造了三個重要的成果：字體設(shè)計系統(tǒng)METAFONT、文學(xué)化編程(Literate Programming)。以及當(dāng)中影響最大的排版系統(tǒng)TEX。

在Word系統(tǒng)中寫科學(xué)論文是一件非常辛苦的事，你須要調(diào)整格式，也非常難表現(xiàn)數(shù)學(xué)式。

可是在TEX中，這些麻煩差點兒全然不存在。僅僅要加載樣式文件，排版就自己主動完畢了。

TEX是一場出版界的革命，直到如今仍是全球?qū)W術(shù)排版的不二規(guī)范。

TEX作為一個軟件產(chǎn)品，也令人嘆為觀止。它的版本號號不是自然數(shù)列，也不是年份。而是從3開始，不斷逼近圓周率(眼下最新版本號是 3.1415926)。

高納德再一次用行動宣告，這個東西趨近完美，不可能再有什么大的改進了。他還設(shè)立了獎金：誰發(fā)現(xiàn)TEX的一個錯誤。就付他2.56 美元，第二個錯誤5.12美元，第三個10.24美元……以此類推。結(jié)果直到今天。他也沒有為此付出多少錢，可見TEX經(jīng)過了如何的千錘百煉。他設(shè)置的另 一個獎項是找出其著作中錯誤的人能得到2.56美元。由于“256美分剛好是十六進制的一美元”。據(jù)說，獲獎?wù)邔⒂兴灻闹币暈檎鋵殻⒉粌冬F(xiàn)。

為什么是2.56美元？Knuth 教授的答案是：

從1981年夏至1996年7月1日，Knuth 教授給指出錯誤的人回信250多封，當(dāng)中一半以上裝有獎勵支票。

從獎勵支票清單來看，有一位名叫 Axel B?ttcher 的人，曾先后5次得到兩塊五毛六的支票，3次得到五塊一毛二的支票，真可謂牛人背后有牛人。

受麥粒與棋盤的故事影響。Knuth 教授宣布。每發(fā)現(xiàn)一個 TeX 程序或 METAFONT 程序中的錯誤，獎勵從2.56美元開始，每年翻倍。最高為327.68美元。

1995年有兩人領(lǐng)取了這項獎金。此后至今，還無人可以認(rèn)領(lǐng)！

依Knuth本人所講，《計算機程序設(shè)計藝術(shù)》是他畢生最重要的事業(yè)，其目的是“組織和總結(jié)所知道的計算機方法的相關(guān)知識。并打下堅實的數(shù)學(xué)、歷史基礎(chǔ)”。Knuth撰寫的前三卷被翻譯成多種語言，到1976年為止，已賣出超過一百萬冊。

他眼下正目不轉(zhuǎn)睛地編寫第四卷，他期望第四卷的篇幅約為2000頁，并分為三個獨立的章節(jié)。

為了完畢叢書的其余部分，Knuth如今進入了一種引退的狀態(tài)，全身心地投入這項工作。Knuth說，一般說來，他更喜歡在一段時間內(nèi)集中精神完畢一項工作。正像他自己在書中提出的：按“一批”的模式。

Knuth從他基本的工作計劃中拿出了十年，即從1976年起，致力于對數(shù)字排版的研究，設(shè)計了著名的文件準(zhǔn)備TeX系統(tǒng)，字體生成程序METAFONT。這項工作帶來的值得注意的副產(chǎn)品是用于結(jié)構(gòu)文件和“文章性程式語言”附隨方法論的WEB和CWEB語言。

如今，Knuth和他的妻子Jill，兩個孩子John 和Jennifer一起。住在斯坦福大學(xué)校園里。他繼續(xù)著《計算機程序設(shè)計藝術(shù)》第四卷的編寫工作。盡管說Knuth是全身心的投入這一項工作，但他還是能擠出時間研究MMIX的設(shè)計。那是一臺64位RISC（精簡指令集計算機）。

而他的業(yè)余愛好仍然是音樂，還一直邀請那些可以即興演奏四手聯(lián)彈鋼琴曲的人們給他留下便條。以便安排一些活動。