1974 Donald Knuth —— 一個人寫一部程式設計的百科全書#

「一個 25 歲的博士生為出版社寫了份校對建議，出版社直接邀他寫書。他答應了——然後這本書寫了六十年還沒寫完。」

案件檔案#

項目	內容
得主	Donald E. Knuth (b. 1938)
得獎理由	演算法分析與程式設計藝術（TAOCP），多重分支結構理論
關鍵詞	TAOCP、演算法分析、TeX、文學編程

1962 年前，程式設計知識散落於手冊與江湖傳說，沒有一門「演算法的科學」：沒有複雜度記號、沒有系統性分析。Knuth 在 Caltech 就讀時為 Addison-Wesley 校稿，被邀請寫成《The Art of Computer Programming》（TAOCP）。

TAOCP 的革命性寫法：每個演算法不只給步驟，還證明其正確性與效率界。Knuth 與同事推廣了大 O 記號的現代用法：

插入排序：平均比較次數 ≈ n²/4    → O(n²)
合併排序：n log n − n + 1        → Θ(n log n)
排序下界：比較排序至少需 log₂(n!) = Θ(n log n) 次比較

他確立了「最壞情況 / 平均情況」兩軸分析法，使演算法成為可比較、可改進的科學對象（影響 1978 Floyd 案）。

為避免 TAOCP 綁死任何真實電腦（過時即作廢），Knuth 設計虛構機器 MIX/MMIX。抽象化保證了書的永生。

因不滿第 2 卷新版校樣品質，Knuth 決定自己寫排版系統。 TeX 的核心是段落斷行的最佳化：

把斷行視為動態規劃：
  cost(段落) = Σ (badness of each line)²
badness ∝ (伸縮量/彈性)³
以 Dijkstra 最短路徑式方法求全域最小壞度（參見 1972 案！）

這是「用演算法解決藝術問題」的極致範例。Metafont 則以方程式定義字體形狀，合稱「電腦與排版」（Computers and Typesetting）。

主張：程式是寫給人讀的文學作品，WEB 系統將敘述與代碼交織。 TeX 本身即以 WEB 撰寫——自證範例。

Knuth 的元方法論：從具體案例中提煉不變量。他反對過度抽象（「過早最佳化是萬惡之源」也出自他），主張理論必須回到真實的計算代價。