這套書他寫了 50 年,程式史上最重要神作《電腦程式設計藝術》第四卷 B 新章節預覽釋出

作者 | 發布日期 2017 年 01 月 25 日 5:08 | 分類 名人堂 , 數位內容 , 科技教育 follow us in feedly

或許你不知道高德納(Donald Ervin Knuth)是誰,甚至可能沒有讀過他的著作,但是事實上任何資工科系的學生,現在學校裡所念的課本,內容多少都是他的著作翻譯以及翻譯的再翻譯;甚至可以說,整個電腦史如果沒有他,可能現在的演算法走向就會完全不一樣。



高德納,史丹佛大學的電腦系榮譽退休教授,是現代電腦科學及現代數學的大師級人物,尤其在演算法領域可說為後人奠定了基礎。現代學習演算法中有一個字串搜尋演算法「Knuth–Morris–Pratt」,就是他與學生的合作發明。

他早在 1962 年還是研究生時就已經從事程式設計,而他攻讀博士學位的時候,就有人找他撰寫程式設計相關的書籍,但當時他課業繁忙,一直到 1968 年,才開始出版著作,也就是至今被程式設計史上列為經典的《電腦程式設計藝術》(The Art of Computer Programming)。

《TAOCP》被美國科學家期刊列為與相對論、博奕論、量子力學等重量級學術作品並駕齊驅的科學史上最重要著作,李開復也說過,要把資料結構、演算法、資料庫、作業系統原理、離散數學等基礎課程學好,就去練習 TAOCP 裡的題目。甚至比爾‧蓋茲 1995 年的時候還建議新鮮人「如果你能讀懂整套書,請發給我你的履歷。」

《TAOCP》一書的出版過程也是電腦書籍出版史上的一個傳奇,前面說在 1962 年就有出版社跟他約稿,當時他回答課業繁忙,4 年之後出版社問他書寫得怎麼樣,他回答「才寫了三千多頁……」讓編輯大吃一驚,他們只想要出一本電腦基礎書,但是高納德把這本書的規格提高到前所未有的高度。

而這三千多頁的內容,僅僅只是整套《TAOCP》的一章。

而從 1968 年到 1973 年,這本書出到了第三部,在這期間他已經是史丹佛大學的教授,而這三部書也被電腦界視為經典之作。1974 年他才 36 歲,就以這套書獲得美國電腦界最高成就的圖靈獎,為至今最年輕的獲獎者。不過,就在這時候,他宣布要暫時停筆,不寫了。理由是當時的「排版工具太爛,無法表現書中的演算法之美」。

於是,接下來的 10 年,他花時間設計了一套論文排版系統 TEX,這個系統專門針對適合學術寫作和數學式的排版設計;並且設計了一個字體設計系統 METAFONT。值得一提的是,高納德的想法處處與眾不同,TEX 的版本開發並不像一般 Windows 2.0、3.0 這樣一路往上累進,而是使用圓周率來當版本開發的代號,TEX3、TEX3.1、TEX3.14……這樣一路往下,不斷逼近圓周率以趨近完美。

到了 1992 年,高德納宣布從史丹佛大學退休,並且從此不收 Email,理由是希望專心完成整套《TAOCP》。整套《TAOCP》預計共有七冊,每冊主題如下:

  • 第一冊  基礎演算法(Fundamental Algorithms)

第一章  基本觀念(Basic concepts)

第二章  資訊結構(Information structures)

  • 第二冊  半數值演算法(Seminumerical Algorithms)

第三章  隨機數(Random numbers)

第四章  算數(Arithmetic)

  • 第三冊  排序與搜尋(Sorting and Searching)

第五章  排序(Sorting)

第六章  搜尋(Searching)

  • 第四冊  組合演算法(Combinatorial Algorithms),準備中(至 2009 年 4 月已出版 5 個分冊),測試版本已上載到 Knuth’s 的網站)

第 4A 卷  列舉與回溯(Enumeration and Backtracking)

第七章  組合的搜尋(Combinatorial searching)

第 4B 卷  圖形與網路演算法(Graph and Network Algorithms)

第七章  續(continued)

第 4C 及 4D(可能)卷  最佳化與遞迴(Optimization and Recursion)

第七章  續(continued)

第八章  遞歸(Recursion)

  • 第五冊  造句演算法(Syntactic Algorithms),計劃中(預計 2020 年完成)

第九章  語句掃瞄(Lexical scanning)

第十章  剖析技術(Parsing techniques)

  • 第六冊  與上下文無關語言理論(Theory of Context-Free Languages),計劃中
  • 第七冊  編譯器技術(Compiler Techniques),計劃中

就跟許多不按牌理出牌的大師一樣,高德納的興趣很廣,從音樂到小說藝術都有。但他最愛的還是程式設計的藝術,以及「做到完美」的信念。

最近高德納在他的網站上發表了他最近的寫作進度,並且披露了最近寫到 4B 的部分內容,提供了 52 頁的預覽版

T客邦配圖

在這部分他主要是延伸了第一卷中第一章以及第二章的數學基礎,並且加入了他表示在 1960 年代當時的他還不知道的內容。他表示與過去一樣,任何首先發現錯誤以及提出有價值意見的人,他都會寄出獎勵。高納德的獎勵是:每指出一個錯誤,就能得到 2.56 美元,因為 256 美分為 16 進制的 1 美元。這就是高納德有名的「16 進制獎勵」。

此外,高德納最近還很高興地宣布,2016 年他在史丹佛的一場講課,可能是美國大學史上第一場首次用 3D VR LIVE 直播的講課。

你可以在這段影片中看出,他本人也非常幽默。一開始他就說,這可能是史丹佛有史以來第一場 VR 3D Live 直播講課,所以他個人覺得應該邀請一些舞者來開場,他也跟在看影片的觀眾說,如果你想要感受 3D 有多 Cool,或是確認你看的是不是 VR 3D,請你把頭低下來。影片截圖 T克邦配圖

(Source:影片截圖)

你會看到他在 360 度相機下,為大家準備了幾本課本。影片截圖

(Source:影片截圖)

雖然畫面不是很清楚,不過看起來左邊兩本是《TAOCP》的日文版、第三本是《TAOCP》英文版,至於第四本……可能是與拼圖有關的書,實在看不清楚。

根據高德納的規劃,從他 1992 年退休至今,他實際上只出了第四冊 A(而第四冊還分成 A、B、C、D 四部!)現在還在努力跟第四冊 B 搏鬥中。而他希望在 2020 年可以完成第五冊,看來這個時間表真的拖得有點長。希望今年已 79 歲高齡的大師真的要好好照顧身體,把整套書完成啊!

(本文由 T客邦 授權轉載) 

發表迴響