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

2017.01.25 by
T客邦
T客邦 查看更多文章

《T客邦》是由台灣最大的電腦出版集團「PC home電腦家庭」所經營,每日提供專業、詳實、高品質的科技資訊,成為許多電腦族群愛好的科技網站。

這套書他寫了50年,程式史上最重要神作「電腦程式設計藝術」第四卷B新的章節預覽釋出
T客邦
史丹佛大學的電腦係榮譽退休教授高德納,從1968年開始出版他的「電腦程式設計藝術」,被程式設計史列為經典,與相對論、博奕論、量子力學等重量級學術作品並駕齊驅,而近日他宣布第四卷B即將出版。

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

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

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

T客邦

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

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

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

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

於是,接下來的十年,他花了時間去設計了一套論文排版系統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月已出版五個分冊),測試版本已上載到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客邦

你會看到他在360像機底下,為大家準備了幾本課本。

T客邦

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

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

延伸閱讀:向史上最棒的電子電路學課本致敬

其實講到國外的經典課本,除了這套TAOCP之外,過去我們也介紹過,在電子電路學方面,還有另外一本經典課本是由Forrest Mims III所著作的「電子學入門」(Getting Started in Electronics)

T客邦

這本書用的不是冰冷的印刷字體,也不是冷冰冰的電路圖,整本書就像是一個工程師的筆記本,採用手寫字搭配手繪電路圖,深入淺出的幫大家解說電路學的原理。也是值得一看的奇書。

相關報導:向史上最棒的電子電路學課本致敬,自己親手打造出「經典電路」

本文授權轉載自:T客邦

每日精選科技圈重要消息