概述

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

Donald Knuth

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

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

早期經(jīng)歷

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

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

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

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

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

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

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

高等教育和早期的計(jì)算機(jī)工作

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

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

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

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

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

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

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

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

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

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

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

1960年，Knuth從 Case畢業(yè)時(shí)享有著最高榮譽(yù)。在由全體教員參加的選舉上，他因其公認(rèn)的出眾成就不但被授予學(xué)士學(xué)位，還被破例同一時(shí)候授予碩士學(xué)位。之后他進(jìn)入加州理工學(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é)，九年后坐上了該校計(jì)算機(jī)科學(xué)學(xué)科的第一把交椅。1993年，Knuth成為斯坦福大學(xué) “the Art of Computer Programming”（計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)）的榮譽(yù)退休教授。

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

1962年，Knuth還是個(gè)研究生的時(shí)候就開始了他計(jì)算機(jī)程序的工作。

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

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

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

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

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

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

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

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

依照計(jì)劃，這套書一共是七卷。可是如今剛剛寫完三卷，就已是震古爍今。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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