紐約時(shí)報(bào)長(zhǎng)文：硅谷的尤達(dá)—算法大師Donald Knuth
日期 ： 2022年01月06日
正文共 ：4619字
Donald Knuth 在加利福尼亞州斯坦福的家中。他是個(gè)臭名昭著的完美主義者，愿意對(duì)任何在他的書中發(fā)現(xiàn)錯(cuò)誤的人給予獎(jiǎng)勵(lì)。
斯坦福大學(xué)的計(jì)算機(jī)科學(xué)家 Donald Knuth 與《星球大戰(zhàn)》中的尤達(dá)略有相似，半個(gè)世紀(jì)以來(lái)，他一直是算法領(lǐng)域的精神導(dǎo)師——盡管他身高 6 尺 4 英寸（約 1 米93），戴著眼鏡。
他是《The Art of Computer Programming》一書的作者，這部作品是他的終生工作，共有四卷。第一卷于 1968 年出版，這卷書籍（盒裝出售，售價(jià)約 250 美元）2013 年被 American Scientist 雜志評(píng)選為塑造上世紀(jì)科學(xué)的書籍，一起被列入的書籍包括《The Autobiography of Charles Darwin》特別版、Tom Wolfe 的《The Right Stuff》、Rachel Carson 的《Silent Spring》以及 Albert Einstein、John von Neumann 和 Richard Feynman 的專著。
《The Art of Computer Programming》出版了一百多萬(wàn)冊(cè)，是計(jì)算機(jī)領(lǐng)域的圣經(jīng)。谷歌研究主管 Peter Norvig 曾說(shuō)過(guò)：“這本書就像一本真正的圣經(jīng)，它很長(zhǎng)，也很全面，沒(méi)有一本書能像它那樣全面?！狈^(guò) 652 頁(yè)，第一卷結(jié)束，可以看到后封面上比爾·蓋茨的推薦語(yǔ)：“如果你能讀懂全部?jī)?nèi)容，一定要給我發(fā)份簡(jiǎn)歷?！?/span>
本書開(kāi)頭摘錄自《McCall’s Cookbook》：
你們寫了上千封信要求我們出版的那本書來(lái)啦。我們花了很多年的時(shí)間反復(fù)檢查書里面那些數(shù)不盡的食譜，只為給您帶來(lái)最好的、有趣的、完美的內(nèi)容。
這本書主要講算法，盡管 Knuth 博士指出，在 3800 年前的巴比倫刻寫板上也能找到算法，但這本書能滿足數(shù)字時(shí)代的需求。Knuth 是一位受人尊敬的算法專家；他的名字與該領(lǐng)域一些最重要的方法關(guān)聯(lián)在一起，例如 Knuth-Morris-Pratt 字符串搜索算法。這個(gè)算法是在 1970 年設(shè)計(jì)的，它可以在文本中查找給定單詞或字母的所有匹配內(nèi)容——例如，當(dāng)你點(diǎn)擊 Command + F 在文檔中搜索關(guān)鍵字時(shí)采用的就是這種算法。
工作時(shí)，現(xiàn)年 80 歲的 Knuth 博士通常穿得像個(gè)年輕的極客：上身長(zhǎng)袖T恤，外面套件短袖T恤，下身牛仔褲，他在每年這個(gè)時(shí)候都是這種打扮。在早些年，他總是和機(jī)器打交道，寫一些原始的二進(jìn)制編碼。
Norvig 博士說(shuō)：“Knuth 證明了計(jì)算機(jī)系統(tǒng)實(shí)際上可以一直被理解到二進(jìn)制編碼級(jí)別?！钡缃瘢S著算法對(duì)二進(jìn)制編碼的主宰（和破壞），普通程序員不再有時(shí)間去處理那些二進(jìn)制“垃圾”，而是使用抽象的層次結(jié)構(gòu)和一層又一層的代碼，并且還經(jīng)常使用從代碼庫(kù)找來(lái)的一連串代碼。但是精英階層的工程師偶爾還是會(huì)深入研究底層代碼。
Norvig 博士在加利福尼亞州山景城的一次 Google 旅行小組會(huì)議上說(shuō)：“在 Google，有時(shí)我們只是把東西整合在一起，但是更多時(shí)候，比如你正在為數(shù)十億用戶提供服務(wù)，高效很重要。效率提高 10% 就可以創(chuàng)造數(shù)十億美元的價(jià)值，為了獲得足夠高的效率，你必須明白到底發(fā)生了什么?！?
1963年，加利福尼亞理工學(xué)院，在這里Knuth獲得博士學(xué)位
或許正如 Google 著名科學(xué)家 Andrei Broder 和 Knuth 博士以前的一個(gè)研究生在會(huì)議中所說(shuō)的那樣：“我們想為我們正在做的事情提供一些理論基礎(chǔ)。我們不需要輕浮的、草率的或二流的算法。我們不希望其他的算法工程師說(shuō)，‘你們這些家伙是白癡’”。
Google Trips 應(yīng)用程序創(chuàng)建于 2016 年，采用了“定向運(yùn)動(dòng)算法”，用于繪制一天的推薦旅游活動(dòng)。該團(tuán)隊(duì)正在致力于“最大限度地讓一天看起來(lái)不那么糟糕”，例如，避免將用戶反復(fù)送到同一地區(qū)，只是因?yàn)榭吹木包c(diǎn)不同。他們從 300 年前的瑞士數(shù)學(xué)家萊昂哈德.歐拉的算法中得到靈感，歐拉想繪制一條穿越普魯士城市科尼斯堡的路線，這條路線只穿過(guò)科尼斯堡的七座橋各一次。Knuth 博士在他的書的第一卷中闡述了歐拉的經(jīng)典問(wèn)題（他曾經(jīng)將歐拉方法用于控制縫紉機(jī)的計(jì)算機(jī)編碼）。
遵循 Knuth 博士的教義有助于避免代碼的堆砌。眾所周知，他引入了“編碼可讀性”的概念，強(qiáng)調(diào)代碼對(duì)于人類和計(jì)算機(jī)都具有好的可讀性的重要性，如今這個(gè)概念已經(jīng)成為了共識(shí)。Knuth 博士甚至認(rèn)為，一些計(jì)算機(jī)程序就像伊麗莎白·畢曉普的詩(shī)歌和菲利普·羅斯的《美國(guó)牧歌》一樣，可讀性和普利策文學(xué)獎(jiǎng)作品并無(wú)二致。
他也是一位臭名昭著的完美主義者。xkcd 漫畫家、《事物解釋者》的作者 Randall Munroe 第一次聽(tīng)說(shuō) Knuth 博士，還是別人提到 Knuth 博士會(huì)提供獎(jiǎng)金給任何在他的書中發(fā)現(xiàn)錯(cuò)誤的人。Knuth 回憶道，“他們說(shuō)得到 Knuth 博士的獎(jiǎng)金就像獲得計(jì)算機(jī)科學(xué)界的諾貝爾獎(jiǎng)?！?/span>
Knuth 博士具有對(duì)自己要求嚴(yán)格、博學(xué)等諸多特質(zhì)，這些特質(zhì)也解釋了為什么他這本書的完成遙遙無(wú)期。他和 Google 的聯(lián)合創(chuàng)始人謝爾蓋·布林打賭，布林是否會(huì)在他結(jié)束自己的作品之前獲得博士學(xué)位。
算法的曙光
19 歲時(shí)，Knuth 博士在《瘋狂》雜志上發(fā)表了他的第一篇技術(shù)論文《The Potrzebie System of Weights and Measures》。在計(jì)算機(jī)科學(xué)這門學(xué)科存在之前，他就成為了一名計(jì)算機(jī)科學(xué)家，在克利夫蘭的一所學(xué)校學(xué)習(xí)數(shù)學(xué)，這所學(xué)校就是如今的 Case Western Reserve University。他看了學(xué)校的 IBM 650 大型機(jī)（一臺(tái)十進(jìn)制計(jì)算機(jī)）的示例程序，發(fā)現(xiàn)了一些不足之處，就重寫了該軟件和在課堂上使用的教科書。作為一項(xiàng)輔助項(xiàng)目，他編寫計(jì)算機(jī)程序來(lái)執(zhí)行統(tǒng)計(jì)數(shù)據(jù)，幫助籃球隊(duì)贏得聯(lián)賽冠軍。
在暑假期間，Knuth 博士編寫編譯器賺的錢比當(dāng)教授一年掙的還多。編譯器就像一個(gè)翻譯器，將高級(jí)編程語(yǔ)言（類似于代數(shù)）轉(zhuǎn)換為低級(jí)編程語(yǔ)言（有時(shí)是神秘的二進(jìn)制），并在轉(zhuǎn)換過(guò)程中對(duì)其改進(jìn)。在計(jì)算機(jī)科學(xué)中，“優(yōu)化”確實(shí)是一門藝術(shù)，Knuthian 有一句名言：“過(guò)早的優(yōu)化是萬(wàn)惡之源?！?
最終，Knuth 博士自己成為了“編譯器”，他無(wú)意中開(kāi)辟了一個(gè)新的領(lǐng)域，并稱之為“算法分析”，有個(gè)出版商委托他寫一本關(guān)于編譯器的書，這本書最后成為一本他所知道的所有計(jì)算機(jī)編程方法的集合，成為了一本關(guān)于算法的書。
攝于 1981 年，Knuth 正在看 1957 年出版的《瘋狂》雜志，這本雜志里有他發(fā)表的第一篇技術(shù)論文，發(fā)表這篇論文的時(shí)候他才 19 歲。
《The Art of Computer Programming》1-4卷。比爾·蓋茨在推薦語(yǔ)中寫道：“如果你能讀懂全部?jī)?nèi)容，一定要給我發(fā)份簡(jiǎn)歷。”
“文藝復(fù)興時(shí)期，人們開(kāi)始懷疑算法這個(gè)詞的起源?！?Knuth 博士說(shuō)道，“早期的語(yǔ)言學(xué)家試圖通過(guò)組合像 algiros [痛苦] + arithmos [數(shù)字] 這些詞來(lái)猜測(cè)它的起源?！薄笆聦?shí)上，”，Knuth 博士繼續(xù)說(shuō)，“在 9 世紀(jì)波斯教科書作者 Abū ‘Abd Allāh Muhammad ibn Mūsā al-Khwārizmī 的書中就有這個(gè)詞的拉丁語(yǔ)。”。1979 年，Knuth 博士去了烏茲別克斯坦，到 al-Khwārizmī’s 的故鄉(xiāng)朝圣。
當(dāng) Knuth 博士剛開(kāi)始寫作時(shí)，他沒(méi)打算寫得這么復(fù)雜。不久之后，計(jì)算機(jī)科學(xué)經(jīng)歷大爆炸，所以他重新構(gòu)思了這部作品并重鑄成七卷。現(xiàn)在，他開(kāi)始分冊(cè)，把它們分成一系列叢書。接下來(lái)要寫的是系列 5 的第 4 卷，包含 “backtracking” 和 “dancing links” 算法，原計(jì)劃出版的時(shí)間為圣誕節(jié)，但它被推遲到第二年四月出版，因?yàn)?Knuth 博士不斷發(fā)現(xiàn)越來(lái)越多有意思的問(wèn)題，他想把這些問(wèn)題寫進(jìn)書中。
為了盡早完成這本書，Knuth 博士一直惜時(shí)如金。他 55 歲退休，極少參加公眾活動(dòng)，并停止使用電子郵件（至少停止了因公電子郵件）。Andrei Broder 回憶說(shuō)，即使是在 20 世紀(jì) 80 年代早期，Knuth 對(duì)時(shí)間也管理得非常嚴(yán)格。
Knuth 博士通常在周五上午約見(jiàn)學(xué)生，在這之后他便在人工智能學(xué)科創(chuàng)始人 John McCarthy 的實(shí)驗(yàn)室度過(guò)夜晚，在這里他可以使用空閑的計(jì)算機(jī)。隨著數(shù)字出版的出現(xiàn)，Knuth 博士對(duì)他心愛(ài)的書在書頁(yè)上的樣子感到不滿，他承擔(dān)了創(chuàng)建 TeX 計(jì)算機(jī)排版系統(tǒng)的任務(wù)，現(xiàn)在這一系統(tǒng)仍然是所有科學(xué)出版物的形式的黃金標(biāo)準(zhǔn)。有些人認(rèn)為這是 Knuth 博士對(duì)世界最大的貢獻(xiàn)，也是自 Gutenberg 以來(lái)人類對(duì)印刷術(shù)最大的貢獻(xiàn)。
這條長(zhǎng)達(dá)十年的迂回之路發(fā)生在用戶之間共享計(jì)算機(jī)的時(shí)代，那時(shí)，在大多數(shù)人都睡覺(jué)的晚上，計(jì)算機(jī)跑得更快。因此，Knuth 博士的作息開(kāi)始日夜顛倒，他把作息時(shí)間調(diào)整了 12 個(gè)小時(shí)，并將約見(jiàn)學(xué)生的時(shí)間改為周五晚上 8 點(diǎn)到午夜。Broder 博士回憶說(shuō)：“當(dāng)我告訴我的女朋友周五晚上不能做任何事情，因?yàn)橹芪逋砩?10 點(diǎn)，我必須和我的導(dǎo)師見(jiàn)面時(shí)，她想，‘這件事太愚蠢了，真的是太愚蠢?！?/span>
當(dāng) Knuth 出現(xiàn)時(shí)，他一定會(huì) 100% 投入到當(dāng)前的事情中。微軟研究院董事總經(jīng)理Jennifer Chayes 說(shuō)：“和他在一起你會(huì)很高興?！薄八谏鐓^(qū)里是最棒的。如果說(shuō)有個(gè)人在某種程度上既溫暖又有深度，那這個(gè)人就是 Don。”
Knuth 與字體設(shè)計(jì)師 Hermann Zapf 討論字樣。許多人認(rèn)為 Knuth 博士在 TeX 電腦排版系統(tǒng)上的工作，是自 Gutenberg.CreditBettmann的Getty Images 以來(lái)對(duì)排版最大的貢獻(xiàn)。
拜訪 Knuth 的星期天
Knuth 住在斯坦福，允許周日來(lái)訪。他這一天的時(shí)間很獨(dú)特，通常他的空閑時(shí)間是從下午 1 點(diǎn)到到 4 點(diǎn)（稱為 “modulo nap time” ），他會(huì)進(jìn)行一場(chǎng)神圣的每日儀式。他很早就起床，去帕洛阿爾托的第一路德教堂，在這里他給人們上一門“Sunday” 學(xué)校課程。在開(kāi)車回家時(shí)，他會(huì)對(duì)數(shù)學(xué)進(jìn)行一些哲學(xué)上的思考。
“我永遠(yuǎn)不可能全都知道，”他說(shuō)，“如果我對(duì)問(wèn)題的答案一無(wú)所知，或者我什么都知道，生活將會(huì)糟糕得多?！比缓笏麕覀儏⒂^了他加州現(xiàn)代風(fēng)格的房子，這所房子是他和他的妻子 Jill 在 1970 年建造的，Jill 是一名平面設(shè)計(jì)師。他的辦公室里亂七八糟地堆放著成堆的 USB 線，還裝飾著 Jill 設(shè)計(jì)的情人節(jié)心形藝術(shù)品。最令人印象深刻的是音樂(lè)廳，環(huán)繞著他定制的 812 管風(fēng)琴。在這天的最后，我們開(kāi)了一場(chǎng)益智派對(duì)，并喝了啤酒。
拼圖和游戲，寫一本關(guān)于超現(xiàn)實(shí)數(shù)的中篇小說(shuō)，寫一部 90 分鐘的多媒體音樂(lè)白日夢(mèng)——“幻想啟示錄”，這些都是他真正感興趣的東西。他的書有一部分名為“謎題與真實(shí)世界”。他把這里的一段發(fā)給了藝術(shù)家 Martin Demaine 和計(jì)算機(jī)科學(xué)家 Erik Demaine，因?yàn)樗玫搅怂麄兊摹癮lgorithmic puzzle fonts”。他們是倆父子，都在麻省理工學(xué)院。
“我很激動(dòng)，”Erik Demaine 說(shuō)?！澳艹霈F(xiàn)在這本書里面真是榮幸?！彼岬搅?Knuth的另一句名言，這句鼓舞人心的話是兩年一度的 “FUN with Algorithms” 會(huì)議的座右銘：“快樂(lè)也許是一直以來(lái)的主要目標(biāo)。”
“但是后來(lái)，” Demaine 博士說(shuō)，“這個(gè)領(lǐng)域崛起并且追求實(shí)際應(yīng)用?！惫こ處?、科學(xué)家和藝術(shù)家們正在聯(lián)合起來(lái)解決現(xiàn)實(shí)世界的問(wèn)題，如蛋白質(zhì)折疊、機(jī)器人技術(shù)、安全氣囊等問(wèn)題，他們使用 Demaine 父子的數(shù)學(xué)折紙?jiān)O(shè)計(jì)方法來(lái)將紙片和連桿折疊成不同的形狀。
當(dāng)然，算法繁瑣性會(huì)導(dǎo)致現(xiàn)實(shí)問(wèn)題。人類編寫的算法正解決著越來(lái)越難的問(wèn)題，但是會(huì)出現(xiàn)存在錯(cuò)誤和偏見(jiàn)的代碼，這些已經(jīng)足夠麻煩了。更令人擔(dān)憂的也許是那些不是由人類編寫的算法，即機(jī)器通過(guò)學(xué)習(xí)后編寫的算法。
程序員仍然訓(xùn)練機(jī)器，關(guān)鍵是，他們會(huì)給機(jī)器輸入數(shù)據(jù)。（數(shù)據(jù)是偏見(jiàn)和錯(cuò)誤的新領(lǐng)域，并且這里的錯(cuò)誤和偏見(jiàn)更難被發(fā)現(xiàn)和修正）。然而，正如麻省理工學(xué)院媒體實(shí)驗(yàn)室研究員 Kevin Slavin 所說(shuō)：“我們現(xiàn)在正在編一些自己看不懂的算法。這是一個(gè)獨(dú)一無(wú)二的時(shí)代，我們受制于那些源于我們，但是我們并不理解的思想、行動(dòng)所支配?！闭?Slavin在TED 中提到的那句話，“如果你是一個(gè)算法，那你將有光明的未來(lái)。（“It’s a bright future, if you’re an algorithm.”）”
1999 年，Knuth 博士在家辦公
一些筆記
“如果你是一個(gè)精通 Knuth 所述知識(shí)的算法，那未來(lái)將更加光明。”Google 的 Norvig 博士表示，“今天，程序員使用 Knuth 和其他人已經(jīng)完成的內(nèi)容作為他們算法的組成部分，然后他們把這些內(nèi)容與他們需要的其他內(nèi)容相結(jié)合?！?/span>
“AI 也是一樣，只是這些組合將會(huì)基于數(shù)據(jù)自動(dòng)完成，而不是由程序員來(lái)完成。你希望 AI 能夠基于數(shù)據(jù)，將之前的內(nèi)容組合起來(lái)，得到好的結(jié)果。但是你必須決定這些內(nèi)容是什么?？赡芩袃?nèi)容都出自 Knuth 作品的某個(gè)頁(yè)面或章節(jié)，因?yàn)檫@是完成某些任務(wù)的最佳方式?！?
Knuth 一直在堅(jiān)持完成他的作品，他估計(jì)還需要 25 年才能完成《The Art of Computer Programming》，盡管自 1980 年他就已經(jīng)在做這件事情。“會(huì)不會(huì)有一章，或者有一頁(yè)談到會(huì)寫算法的算法？”“當(dāng)然不會(huì)！”Knuth 表示。
“我擔(dān)心算法變得太過(guò)重要?！彼a(bǔ)充道，“一開(kāi)始，我們這些計(jì)算機(jī)科學(xué)家擔(dān)心沒(méi)有人聽(tīng)我們的，但現(xiàn)在，聽(tīng)我們的人太多了。”
— THE END —
<b id="afajh"><abbr id="afajh"></abbr></b>