36 歲捧走圖靈碗！80 歲演算法大師高德納要在 105 歲完結《計算機程序設計藝術》
【CSDN 編者按】號稱計算機領域經典必讀的著作你都讀過哪些，例如《計算機程序設計藝術》系列？近日，這套書的作者高德納（Donald Knuth）在接受紐約時報採訪時，談到了自己對於這部已投入五十載心血作品的反思。
自幼便顯露非凡智力的演算法大師高德納，是美國著名計算機科學家、斯坦福大學電腦系榮譽教授，36 歲便憑藉未完的《計算機程序設計藝術》捧走圖靈碗，曾是最年輕的圖靈獎獲得者。他被譽為現代計算機科學的鼻祖、演算法領域的精神導師，在計算機科學及數學領域發表了多部影響力深遠的論文和著作，同時還是TeX 和 Metafont 排版系統的發明人，更與 Edsger Wybe Dijkstra 並稱為我們這個時代最偉大的計算機科學家。除了寫書，高德納同時還是一位音樂家、作曲家、管風琴設計師……
作為一個不折不扣的完美主義者，高德納近乎偏執地對自己提出了嚴苛的要求——精益求精的作品、嚴密的時間安排，乃至文學層面的追求，甚至曾以排版工具太差破作品之美為由宣布歇筆。這也導致《計算機程序設計藝術》的下一冊遲遲「難產」，已然拖過了原定計劃中的「聖誕」之期。關於完結，更是預留了未來二十五年。如今已是 80 高齡的他，繼續玩技術、玩音樂、玩遊戲、寫小說——做一切「快樂」的事。
最後，套用一句高德納自傳開頭的話：「Donald Knuth 真的僅僅是一個人嗎？」
作者 | Siobhan Roberts
譯者 |彎月
責編 | 仲培藝
出品 | CSDN（ID：CSDNnews）
以下為譯文：
近乎偏執的完美主義者
半個世紀以來，斯坦福大學的計算機科學家 Donald Knuth 已然成為演算法領域的精神領袖。說起他的外貌，倒是與星球大戰中的尤達頗有幾分相似，只不過他身高 6 英尺 4 英寸（約 1.93 米），還戴了副眼鏡。
Donald Knuth 在加利福尼亞州斯坦福的家中 | 圖片來源：紐約時報Brian Flaherty
他是個眾所周知的極端完美主義者，甚至願意為任何指出他的書中錯誤的人支付報酬。
他是《The Art of Computer Programming》（中譯本《計算機程序設計藝術》）一書的作者，該書共有四卷，也是他一生的傑作。第一卷首發於 1968 年，2013 年該合集（售價約為 250 美元）被《美國科學家（American Scientist）》雜誌評選為 20 世紀最重要的科學類專著，一起被入選該書單的還包括《The Autobiography of Charles Darwin》（達爾文自傳）的特別版、湯姆·沃爾夫的《太空英雄》（The Right Stuff）、雷切爾卡遜的《寂靜的春天》（Silent Spring）以及阿爾伯特·愛因斯坦、約翰·馮·諾伊曼和理查德·費曼的專著。
《計算機程序設計藝術》出版了一百多萬冊，是計算機領域的聖經。Google 的研究主管 Peter Norvig 曾評論稱：「這本書就像一本真正的聖經，內容很長而且很全面，其他書籍都無法比擬。」該書的第一卷一共有 652 頁，書的後封面上還印有比爾·蓋茨的推薦語：「如果你能夠看懂這本書的所有內容，那麼歡迎給我發來簡歷。」
《計算機程序設計藝術》1-4 卷 | 圖片來源：紐約時報 CreditBrian Flaherty
第一卷開頭有一段摘錄自《McCall"s Cookbook》的話：
你們寫了幾千封信要求我們出版的那本書來啦。我們花了很多年的時間反覆檢查書中這不計其數的食譜，只為給您帶來最好、最有趣又完美的內容。
這本書講的是數字時代的基石——演算法，儘管 Knuth 博士認為演算法早在 3800 年前就誕生於巴比倫的石板上。Knuth 是一位受人尊敬的演算法專家，他的名字與該領域一些最重要的發展息息相關，例如 Knuth-Morris-Pratt 字元串搜索演算法。該演算法設計於 1970 年，它可以在文本中查找所有給定的單詞或任何字母組合——例如，在你按下 Command F 的時候來查找文檔中的關鍵字時，採用的就是這種演算法。
如今，Knuth 博士已然 80 歲高齡了，但工作時的他每每穿得像個年輕的極客：長袖 T 恤外套一件短袖 T 恤，再配上條牛仔褲，每年這個時候他都是這種打扮。早些年，他總是和機器打交道，寫一些原始的二進位代碼。
Norvig 博士說：「Knuth 證明了，整個計算機系統，一直到機器代碼級別的所有內容都是可理解的。」當然，隨著現在演算法越來越深入日常的方方面面，普通程序員不再有時間去「擺弄」那些二進位的東西，而是整天與各種抽象的層次結構和一層又一層的代碼打交道，經常要把從各個代碼庫中拿來的代碼串在一起。但是，真正優秀的工程師偶爾還是會深入研究底層代碼。
在加利福尼亞州山景城舉行的 Google Trips 團隊會議上，Norvig 博士說：「在 Google，有時我們只是把東西整合在一起，但是更多時候，如果你為數十億用戶提供服務，那麼效率就很重要了。效率提高 10% 就可以創造數十億美元的價值，為了獲得足夠高的效率，你必須了解底層的工作原理。」
Knuth 博士在加州理工學院
他於 1963 年獲得了該校的博士學位，圖片來源：Jill Knuth
Andrei Broder 是 Google 傑出的科學家，也曾是 Knuth 博士的研究生，他在會議期間表示：「我們希望為我們正在做的事情提供一些理論基礎依據。我們不希望我們的演算法變得輕浮、草率或二流。我們不希望其他演算法主義者說，『你們這些傢伙是白痴』」。
Google Trips 是一款創建於 2016 年的應用，它採用了「定向演算法」，用於繪製一天的推薦旅遊活動。該團隊正致力於「最大限度地提高某一次旅行活動的質量」（https://ai.google/research/pubs/pub46479），例如避免僅僅因為景點不同就將用戶反覆送到同一地區。他們從瑞士數學家萊昂哈德·歐拉（Leonhard Euler） 300 年前提出的演算法中汲取靈感。歐拉希望繪製一條穿越普魯士城市柯尼斯堡的路線，並保證這條路線只穿過科尼斯堡的七座橋各一次。Knuth 博士在其論文的第一卷中論述了歐拉的經典問題。 （他曾經將歐拉方法編寫了一套用於控制縫紉機的計算機程序）。
遵循 Knuth 博士的學說有助於避免代碼的堆砌。眾所周知，他引入了「文學編程（literate programming）」的概念，強調編寫人類和計算機皆可閱讀的代碼的重要性， 儘管如今這個概念看起來似乎有點過於感性。Knuth 博士甚至認為，有些計算機程序就像伊麗莎白·畢曉普的詩歌和菲利普·羅斯的《美國牧歌》一樣，其可讀性可以與普利策文學獎作品相媲美。
同時，Knuth 博士也是一位不折不扣的完美主義者。xkcd 漫畫家、《萬物解釋者》（Thing Explainer）的作者Randall Munroe 第一次聽說 Knuth 博士，還是聽其他計算機科學人士提及 Knuth 博士願意給那些從他的書中發現錯誤的人支付獎金。Munroe 回憶道，「人們看這筆獎金就像看計算機科學界的諾貝爾獎一樣。」
Knuth 博士嚴格的標準以及在文學等方面的追求，也恰恰說明了為什麼他傾注畢生心血的這一作品的完成依然遙遙無期。他曾與 Google 聯合創始人謝爾蓋·布林（廣義上來講布林也是他之前的學生）打賭，看布林是否可以在 Knuth 博士完成他的作品之前獲得博士學位。
演算法的曙光
19 歲時，Knuth 博士在《瘋狂》雜誌上發表了他的第一篇技術論文《The Potrzebie System of Weights and Measures》。他在計算機科學這門學科存在之前就成為了一名計算機科學家，當時他在克利夫蘭的一所學校學習數學，這所學校就是如今的 Case Western Reserve University。他看到了學校的 IBM 650 大型機（一台十進位計算機）上的示常式序，並注意到一些不足之處，於是他重寫了軟體以及課堂上使用的教科書。他的一個業餘項目是編寫計算機程序來執行統計數據，幫助籃球隊贏得聯賽冠軍，因此 Walter Cronkite 還稱他為「電子教練」。
1981 年，Knuth 博士正在讀 1957 年出版的《瘋狂》雜誌，裡面有他發表的第一篇技術論文，發表這篇論文時他年僅 19 歲。圖片來源：Jill Knuth
Knuth 博士利用暑假期間編寫編譯器賺的錢比當教授一年掙的還多。編譯器就像一個翻譯器，將高級編程語言（類似於代數）轉換為低級編程語言（有時是神秘的二進位），在理想情況下還可以在此過程中對程序本身進行改進。在計算機科學中，「優化」是一門藝術，這一點可以從另一句 Knuth 式的名言中看出來：「過早優化乃萬惡之源。」
最終，Knuth 博士自己成為了「編譯器」——他在無意中開闢了一個新的領域，並稱之為「演算法分析」。有一位出版商聘請他寫一本關於編譯器的書，但最後這本書收錄了他所知道的關於計算機編程的方法合集，成為了一本關於演算法的書。
談及「演算法」一詞，Knuth 博士表示：「文藝復興時期，人們開始懷疑演算法這個詞的起源。早期的語言學家試圖猜測這個詞的起源，認為它是從 algiros [痛苦] arithmos [數字] 派生出來的辭彙。事實上，這個名詞起源於九世紀的教科書作者，波斯人 Abū 『Abd Allāh Muhammad ibn Mūsā al-Khwārizmī（拉丁語名字是 Algorithmi）」。1979 年，不達目的誓不罷休的 Knuth 博士更是專程前往烏茲別克，到 al-Khwārizmī』s 的故鄉朝聖。
Knuth 博士剛開始寫這本書的時候，並沒打算寫得這麼複雜。但不久之後，計算機科學經歷了大爆炸，所以他重新構思了這部作品並重鑄成了七卷。現在他把各卷分冊，接下來是第 4 卷第 5 冊，其中包括「backtracing」和「dancing links」等演算法，原計划出版的時間為聖誕節，但被推遲到了明年四月出版，因為 Knuth 博士不斷發現越來越多有意思的問題，他想把這些問題都寫進書中。
為了儘早完成這本書，Knuth 博士一直惜時如金。自 55 歲退休後，他就很少參加公眾活動，並停止使用電子郵件。Andrei Broder 回憶說，即使在 20 世紀 80 年代早期，Knuth 對時間的管理也非常嚴格。
Knuth 博士通常在周五上午約見學生，但後來他把會見時間改到了晚上，因為他可以利用這漫漫長夜在人工智慧學科創始人 John McCarthy 的實驗室中使用空閑的計算機。隨著數字出版業務的推行，Knuth 博士對其心血的最終呈現效果甚是不滿，轉而創立 TeX 計算機排版系統，直到現在，該系統仍然是所有科學出版物的黃金標準。有人認為這是 Knuth 博士對世界的最大貢獻，也是自古騰堡（Gutenberg，德國活版印刷發明人）以來人類對印刷術貢獻最大的人。
這項任務花了他十年的時間，彼時還處於用戶共享計算機的時代，而在大多數人都在睡覺的夜晚，計算機跑得更快。因此，Knuth 博士改成了夜間工作，將日程安排調整了 12 個小時，開始了日夜顛倒的生活，並將與學生的約見改為周五晚上 8 點到午夜。Broder 博士回憶稱：「當我告訴我的女朋友周五晚上我沒空，因為周五晚上 10 點我必須和我的導師見面時，她接連感嘆『不可思議、難以理解』。」
然而，當 Knuth 出現時，他一定會百分之百的投入。微軟研究院的一名總監 Jennifer Chayes 說：「和他在一起你會很愉快。他是社區中的佼佼者，你可曾幻想過如果優化功能（optimization function）也可以兼具溫暖和深度該多好。那麼 Knuth 就是讓這一設想成真的人。」
Knuth 與字體設計師 Hermann Zapf 討論字體。許多人認為 Knuth 博士在 TeX 電腦排版系統上的工作是自古騰堡以來人類對印刷術最大的貢獻。圖片來源：Getty Images/ Bettmann
周日拜訪小記
Knuth 博士住在斯坦福，他同意我們在周日拜訪他。他為此花費了一整天的時間，這很不尋常——通常他的空閑時間只有下午 1 點到 4 點的「modulo nap time」時段，就像他每天的神聖儀式一樣。周末他會很早就起床，去 往 Palo Alto 的第一路德教堂，並在這裡上一節課，課上擠滿了站立的人群。在開車回家的途中，他會對數學進行一些哲學上的思考。
1999 年，Knuth 博士在家辦公 | 圖片來源：Jill Knuth
「我永遠不可能知道一切，」他說，「但如果我對問題的答案一無所知，或者我什麼都知道，那麼我的生活將會更糟。」然後他帶我們參觀了他加州現代風格的房子，這所房子是他和他的妻子 Jill 於 1970 年建造的，Jill是一名平面設計師。他的辦公室里亂七八糟地堆放著成堆的 USB 線，還裝飾著 Jill 設計的情人節心形藝術品。最令人印象深刻的是音樂廳，環繞著他定製的 812 管風琴。在這天的最後，我們開了一場拼圖派對，還喝了點啤酒。
一些筆記 | 圖片來源：紐約時報Brian Flaherty
拼圖和遊戲、寫一本關於超實數的小說、創作一部 90 分鐘的多媒體音樂白日夢《幻想曲啟示錄》等——這些都是他真正感興趣的東西。他的書有一部分名為「謎題與真實世界」。他通過電子郵件將摘錄發送給了藝術家 Martin Demaine 和計算機科學家 Erik Demaine（他倆是父子，都在麻省理工學院），因為 Knuth 博士用到了他們的「演算法解謎字體」（algorithmic puzzle fonts）。
對此，Erik Demaine 表示：「我很激動，能出現在這本書中是一種榮幸。」他提到了 Knuth 的另一句名言（這句鼓舞人心的話是兩年一度的「演算法的樂趣」會議的座右銘）：「快樂也許是一直以來的主要目標。」
但Demaine 博士還表示，「這個領域追求實際應用。工程師、科學家和藝術家正在聯手解決現實問題，比如蛋白質摺疊、機器人技術、安全氣囊等，他們使用 Demaines 的數學摺紙設計方法來將紙片和連桿摺疊成不同的形狀。」
當然，所有演算法的繁瑣性都會導致現實問題。人類編寫的演算法雖然可以解決越來越難的問題，但也產生了帶有 bug 和偏見的代碼，這些已經夠麻煩了。更令人擔憂的也許是並非人類編寫的演算法，而是機器通過學習後編寫的演算法。
程序員仍在訓練機器，而且關鍵在於過程中向機器輸入的數據（數據是偏見和bug的新領域，而且該領域中的 bug 和偏見更難被發現和修正）。然而，正如麻省理工學院媒體實驗室研究員 Kevin Slavin 所言：「我們現在正在編寫一些連自己都看不懂的演算法。這是一個獨一無二的時代，因為我們受到一系列物理學的思想、行動和努力的影響，這些物理學源於人類，但人類卻無法理解。」正如 Slavin 常說的那樣，」如果你是一個演算法，那你將擁有光明的未來（It"s a bright future, if you"re an algorithm.）。「
「如果你是一個精通 Knuth 演算法的人，那麼你的未來將更加光明。」Norvig 博士補充道，「如今，程序員使用 Knuth 和其他人已經完成的內容作為他們演算法的組成部分，然後把這些內容與他們需要的其他內容相結合。」
「AI 也是一樣，只是這些組合將會基於數據自動完成，而不是由程序員來完成。你希望 AI 能夠根據數據將之前的內容組合起來，並得到良好的結果。但是你必須決定這些內容是什麼。可能所有內容都出自 Knuth 作品的某一頁或某一章節，因為這是完成某些任務的最佳方式。」
幸運的是，Knuth 博士仍在堅持不懈地努力。他覺得還需要25年時間才能完成《計算機程序設計藝術》，儘管自 1980 年以來他就一直在做這件事。那麼會不會有一章，或者有一頁會討論到會寫演算法的演算法？Knuth博士對於這一點的答案是：「肯定不會！」
他解釋道：「我擔心演算法變得太過重要。最初計算機科學家擔心沒有人聽我們說話。但現在，我擔心聽我們話的人太多了。 」
原文：https://www.nytimes.com/2018/12/17/science/donald-knuth-computers-algorithms-programming.html
作者：Siobhan Roberts，紐約時報記者。
本文為 CSDN 翻譯，如需轉載，請註明來源出處。
【完】
熱 文推 薦
TAG:CSDN |