高德納:演算法分析之父(二)-科學人雜誌
機器思維

高德納:演算法分析之父(二)

2023-09-01 林一平
演算法的分析是他一生的工作,用以進行「演算法有多好」的定量研究。
▲ 圖源:Addison-Wesley, Public domain, via Wikimedia Commons

當所有人都期待高德納的下一本新書時,身為現代計算機科學大師的他卻宣佈停筆,理由是「排版工具太爛,無法表現書中的演算法之美」。

當高德納在1969年收到出版商寄來《電腦程式的藝術》(TAOCP )第二冊的校樣時,他對頁面上數學符號和文字的外觀頗不滿意。不幸的是,能達到他排版要求的機器又太昂貴。因此高德納他開始發展一種計算機語言,讓使用者能夠以數位方式排版數學公式。接下來高德納花十年工夫,設計了一套論文排版系統TeX,並以圓周率的小數位數來為版本進行編號,由TeX3開始,現在的版本編號是TeX 3.141592653。

高德納在1978年4月完成了TeX的試用版。5月份有10位使用者、6月份有100位、7月份有1000位。每當使用者增多時,總會有人提出新需求:「TeX必須有這種功能。」五年後,高德納發佈了為美國人設計的TeX版本。然後歐洲人開始使用。到1980年代,TeX已經擴大到全世界。

1992年,高德納從美國史丹佛大學退休,利用TeX專心進行TAOCP 系列書籍的撰寫,預計陸續再完成四部巨著。TeX的影響深遠,這一款複雜的程式改變了許多規則,讓不是排版專業的科學家能在沒有數學符號鍵盤的計算機上進行專業的數學公式排版。TeX使科學論文變得更美觀,更易於專家閱讀並理解。

他和排版設計師交談,以了解他們試圖達到的目標。數學的作用是以定量方式輔助設計。透過數學,高德納在每個物件上加裝了一些小控制器。例如,字母A有這個點、這個厚度、這個角度,在某處漸變,底部有一個凸起,還有一個特定的裝飾線長度。字母的設計師按照某種邏輯把線條變成字母形狀。高德納在撰寫計算機程式的過程,希望捕捉到的不僅僅是設計的結果,還有其中的智慧。他從未打算取代設計師,而只是希望把當下所做的事準確記錄下來,以供後人參考。透過TeX,設計可以重現。

演算法的分析是高德納一生的工作,用以進行「演算法有多好」的定量研究,一邊考慮了某個問題的所有可能演算法,另一邊則考慮了某個問題的一種特定演算法。過去人們都只說「演算法A比演算法B好」,而高德納能證明「演算法A比演算法B好14.8%」。他說:「演算法必須眼見為憑。」(An algorithm must be seen to be believed.)而「眼見」就是定量分析。「我是否理解某件事的最終測試,取決於我是否可以寫成程式,讓計算機正確執行。」

高德納並無學者專家的傲慢,他說:「在數學中,我知道定理何時是正確的。但有些事超出了我的理解範圍,我不明白的神秘事物令我謙卑。」「科學是我們理解得足夠好的事,可以向計算機解釋;而超越科學的其他一切,就是藝術。」我們應該不斷努力把每一種藝術轉化為一門科學:在這個過程中,我們便推進了藝術的發展。

年過古稀的高德納說:「我希望繼續以我所知最好的方式,撰寫優質內容,並涵蓋我對某些議題的獨到見解。我將盡可能這樣做,而不是說我必須在特定期限內完成。我非常幸運能沿著浪潮前進,出生在對我這種特殊性格來說剛剛好的時代。除了TAOCP這套書之外,我已經實現生活中的所有目標。我現在的情況就是:我將繼續講述我所發現的任何故事,並傳遞下去。」

本專欄感謝中華民國資訊軟體協會支持




# 關鍵字:機器思維科學史
更多文章
活動推薦更多
追蹤科學人