計算機界最大“追書坑”，82歲大神高德納仍在寫《計算機程序設(shè)計藝術(shù)》4B卷

曉查 2020-05-16 10:10:04 來源：量子位

曉查 編譯整理
量子位 報道 | 公眾號 QbitAI

Donald Knuth，中文名高德納，是他創(chuàng)造了“算法分析”這一新的計算機科學研究領(lǐng)域。

對于他，我們已無需太多贅述。他發(fā)明的TeX已成為科學界通用的排版工具，每個計算機專業(yè)學生應(yīng)該都拜讀過他的教材《計算機程序設(shè)計藝術(shù)》。

這本書原本是他在1962年讀研期間開始編寫，至今尚未完成，第1卷第1版于1968年出版，到今天已經(jīng)更新到第42版。

為了讓自己能專心寫書，他1993年從斯坦福大學的計算機科學教授職位上退休，按照他的規(guī)劃這套書的總共有7卷。

現(xiàn)年82歲的他還在努力完成第4卷的B分冊，他預(yù)計這本書至少包含A到F部分。

Donald Knuth的中文名“高德納”是1977年訪問中國前，姚期智夫人儲楓所取。姓高是因為他身材高大，德納是Donald的音譯。

高德納從13歲開始就較真。當時一家糖果公司舉辦了一場比賽：用Ziegler’s Giant Bar里的字母組成單詞，最多者獲勝。

為了解決這個問題，高德納翻閱了2000頁的字典，而且還騙父母說自己病了，在家不上學，用2周的時間潛心研究并贏得了比賽。

最后他找到了4700個單詞，而活動主辦方以為最多只能找到2000多個單詞。他因此獲得了巧克力的獎勵，而這只是他人生的第一個獎項。

1974年，高德納獲得了美國計算機學會的圖靈獎；1995年，他又獲得了馮·諾依曼獎。

今年2月，高德納接受了美國科技網(wǎng)站Quanta Magazine的采訪，談到了他創(chuàng)立算法分析的過程，以及《計算機程序設(shè)計藝術(shù)》4B卷的最新狀態(tài)。

我們將采訪的內(nèi)容整理如下：

QM：您一直對寫作感興趣嗎？

小時候，我發(fā)覺現(xiàn)實世界對我來說太難了。我沒想到會發(fā)現(xiàn)任何新東西，但是我喜歡用寫作來表達自己對思想的享受。

六年級的時候，我和幾個朋友在一臺復(fù)印機上寫了兩頁紙的文章。上高中的時候，作為報紙編輯，每周一晚上，我要熬一整夜才把報紙出版。

我在大學里第一次看到過我的打印稿，是作為學生論文的復(fù)印編輯。在大三和大四時，我們開始進行工程和科學評審。

例如，我寫過“Th5E4CH3EmIC2Al2Ca3P4Er” ，每個詞都是化學式。

（注：高德納在大學的時候?qū)戇^一篇短篇小說，其中每個詞都是化學式。是不是有《絕命毒師》片頭的感覺？）

QM：是這個原因?qū)е履銓憰膯?？或者還是有另外一個故事？

《計算機程序設(shè)計藝術(shù)》是一個宣言。這本書描述了我喜歡的做數(shù)學的方式，我希望有人用這種方式來教我。從第1頁，我就開始講述算法的故事。

當時大多數(shù)教科書都沒有探索發(fā)現(xiàn)的人文一面。他們只是說，“這就是化學的樣子”或者“這就是物理的樣子”。

我還講了一個技術(shù)故事。我說：“這是行不通的，這里有一種方法可以解決這個問題?！?/p>

所以我不只是陳述事實，而是加入了戲劇性成分。如果你知道發(fā)現(xiàn)的先后順序，那么學習科學就容易得多。另外，我無法抗拒一個好的故事。

我不認為自己是一個先驅(qū)，而是一名記者。

QM：那么，除了故事之外，《計算機程序設(shè)計藝術(shù)》這本書是關(guān)于什么的？

寫了兩年書之后，我意識到這本書的新穎之處應(yīng)該是在定量上決定程序的質(zhì)量。我不只是想說一個程序比另一個更好，我想說的是一個程序比另一個要好13.8％，并說明如何比較它們。

作者A談?wù)撍惴ˋ，作者B談?wù)撍母偁幩惴˙。作者A從來沒有寫算法B，作者B也從來沒有寫算法A。而且，作者A和B使用不同的計算機。

作為中立的記者，我要從一個角度解釋了這兩種算法。問“算法到底有多好” 是一個有趣的問題，而那就是算法分析。

QM：“算法分析”只是“計算機程序設(shè)計藝術(shù)”的另一種說法嗎？

1967年，在一次工業(yè)與應(yīng)用數(shù)學協(xié)會的會議上，當時有人問我做什么。

那時，計算機科學被劃分為數(shù)值分析、人工智能和編程語言。就這樣，我意識到我需要為自己的工作起個名字。

我的書創(chuàng)新在于，它對算法的好壞程度進行了嚴格研究。所以我決定，下次有人再問我這個問題時，我會說我做的是“算法分析”。

我對算法分析的定義是：如果我對這個內(nèi)容感興趣，那它就是算法分析。這不是一個很好的定義。

后來，我決定證明這一點。我認為算法分析是對算法性能的定量研究。我將其分為兩部分：其中一部分考慮了某個問題的所有可能算法；另一部分考慮了某個特定問題的特定算法。

算法分析將是我一生的工作。

我告訴出版商把我的書名改成《算法分析》，出版商說：“那（這本書）就永遠賣不出去了?！?/p>

他們做出了正確的決定。不過，讓我非常高興的是，這本書出版40年后，有五六個版本里算法分析（作為副標題）出現(xiàn)了。

QM：但是對于您來說，編程不僅僅是功能性的。例如在設(shè)計TeX時，您想要找到連接某些點的“最令人愉悅的曲線”。您是在嘗試為美麗編程嗎？

我的程序必須以某種方式把點連接起來，對優(yōu)秀書法家的工作進行逆向工程。

字母“S”的曲率從正變到負，也許它會在中間穩(wěn)定一段距離。字母的設(shè)計者遵循一些邏輯將線條做成字母形狀。

我不僅想獲取設(shè)計的結(jié)果，還想獲取它背后的智慧。這就像編寫計算機程序。

△?1980年，高德納與字體設(shè)計師Herman Zapf合作

我與設(shè)計師交談，了解他們想要達到的目標。數(shù)學是以定量的方式獲取設(shè)計。

通過數(shù)學，我在每樣東西上都放了小刻度盤。我可以說字母“A”有這個點、這個寬度、這個角度、在那里變細、底部有確定的襯線長度。

我從未打算取代設(shè)計師，我只想為下一代人精確獲取我們現(xiàn)在正在做的事情。有了TeX，設(shè)計就可以重現(xiàn)。

QM：您有沒有預(yù)料到TeX在全世界被接受？

TeX最初只是給我的秘書和我自己使用。Phyllis是一位出色的秘書，她可以讀懂我的筆跡并使它更漂亮。

由于經(jīng)驗的方法變得過于昂貴，因此印刷技術(shù)日漸式微。

1970年代發(fā)表的幾乎所有數(shù)學著作都看起來都很糟糕。比如在《美國數(shù)學月刊》中，下標的字體與主線文本不同。

我知道計算機編程可以使書本看起來不錯。

1978年4月，我完成了TeX的試用版調(diào)試。5月有10個用戶，6月有100個用戶，7月份有1000個用戶……每個新的團隊都會說：“你必須有這個功能?！?/p>

五年后，我發(fā)布了我們現(xiàn)在擁有的TeX。Tex最初為美國人設(shè)計的，然后歐洲人也開始使用它。到了1980年代，世界上各種語言的人都在使用它。

QM：聽起來探索發(fā)現(xiàn)一直是您人生進程的一部分，到今天仍然適用嗎？

我每周平均寫五個新程序。詩人必須寫詩，而我必須寫計算機程序。

理解某件事的終極測試是能否向計算機解釋。我可以對你說些什么，你會點頭，但我不確定我解釋得很好。

但是計算機沒有點頭，它重復(fù)了我所說的。在生活中大多數(shù)時候，您可以欺騙，但是對計算機不行。

QM：您花時間寫作，但您還有其他興趣，您每天是如何處理的？

杰克·倫敦（注：美國現(xiàn)實主義小說家）每天在與別人交談之前都要寫1000字。他完全就像這樣：“讓我一個人靜一靜，直到我有千言萬語！”然后他會在一天的剩余時間里喝酒或校對。

我不是，我的日程安排原則是，在待辦事項清單上先做自己最討厭的事情。到周末，我就會很開心。

QM：真的嗎？做討厭的事情怎么能讓自己快樂？

對我來說，說“哦，讓我成為一個天才，永遠不要打掃廁所”，這是很容易的。即便你還是要去打掃廁所。

我妻子的吉爾和我買了一套409清潔套裝，然后就可以到處噴噴，心情愉悅地去打掃廁所！

一個人的成功是由高的下限決定的，而不是高的上限。如果你能把某件事做得很好，但還有其他事情你失敗了，而后者會讓你退縮。

但是如果你所做的每件事都成了，那么你就有了美好的生活。所以我努力學習如何讓自己去做不喜歡的事情。

QM：您也有許多與計算機科學無關(guān)的項目，例如您的音樂作品《幻想曲世界》，您甚至在兩層高的管風琴周圍建造房子。這些事情是否也使您感到快樂？

我寫了幾本書，包括《計算機科學家很少談?wù)摰氖虑椤罚═hings a Computer Scientist Rarely Talks About），這些書是關(guān)于神學的，它不像數(shù)學或者的計算機科學，你無法證明。

如果只剩下機械的東西，我的生活就不會完整。我不了解的神秘事物讓我謙遜，有些事情超出了我的理解。

在數(shù)學中，我知道定理是否正確，我喜歡這樣。但是如果一切都可行的話，我就不會有太多的生活樂趣。這些知識不會使我失望，相反，它讓我不會墨守成規(guī)。

QM：完成《計算機程序設(shè)計藝術(shù)》是否重要？

計算機科學將繼續(xù)發(fā)展。一種情況是，每個人都將不再使用我們現(xiàn)有的那種計算機，他們都會去做機器學習并使用量子計算機。

然后我就可以結(jié)束非量子計算機的故事。當我可以說“這就是故事的結(jié)局”的時候，我會更開心。

那是我想象的完成這本書的最簡單方法，但是我沒有回答你的問題。

你知道“項狄”的故事嗎？勞倫斯·斯特恩（注：英國傷感主義小說家）在18世紀后期撰寫了一本自傳體小說《項狄傳》，以分冊方式出版。

主人公的故事大概只有100頁。作者希望主角人生故事完整，但是他沒有做到。斯特恩一直在寫項狄傳，直到去世。

我想以我所知的最佳方式繼續(xù)去寫出好的內(nèi)容，并涵蓋我獨創(chuàng)性的部分。我會盡我所能，而不是說我必須在某個截止日期之前完成。

我一直非常幸運，在適合我的特別的時候出生。

除了《計算機程序設(shè)計藝術(shù)》，我現(xiàn)在已經(jīng)實現(xiàn)了我一生的所有目標。我將繼續(xù)講述我找到的故事并持續(xù)下去。