跳至內容

計算機程序設計藝術

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

計算機程序設計藝術》(英語:The Art of Computer Programming),簡稱TAOCP,是美國電腦科學家高德納Donald Ervin Knuth)編著的關於計算機程序設計之七卷本著作。作者並因此獲得美國計算機協會1974年圖靈獎[1]

概述

[編輯]
高德納

1962年,高德納還是個研究生的時候就開始了程式設計的工作,在攻讀博士期間,艾迪生韋斯利公司(Addison-Wesley)的顧問Richard Varga找他出書,因課業繁忙,一時沒時間草稿。1963年高德納獲得加州理工學院數學博士學位,開始投入撰寫工作。1968年,當時31歲的高德納完成前六卷並首次出版,一口氣寫了三千多頁,自此他計劃寫7卷。1999年底被《美國科學家》(American Scientist)期刊列為20世紀最佳12部學術專著之一,與狄拉克的「量子力學」、愛因斯坦的「相對論」、本華·曼德博的「分形論」、鮑林的「化學鍵」、羅素阿爾弗雷德·諾斯·懷海德的《數學原理》、約翰·馮·諾伊曼摩根斯坦的「博弈論」、維納的「控制論」、伍德沃霍夫曼的「軌道對稱性」、費曼的「量子電動力學」等科學史上的重要著作並列必讀經典[2]。至1976年,已賣出超過一百萬冊。

任何人發現書上的錯誤,都可以向他舉發,並領取2.56美元,因為「256美分剛好是十六進位的一美元」(256 pennies is one hexadecimal dollar.)[註 1]比爾·蓋茨在1995年說,「如果你認為你是一名真正優秀的程序員,就去讀第一卷,確定可以解決其中所有的問題。」「如果你能讀懂整套書的話,請給我發一份你的簡歷。」《計算機程序設計藝術》是高德納一生中最重要的事業,他寫這本書的目的是「組織和總結所知道的計算機方法的相關知識,並打下堅實的數學、歷史基礎」。

同時高德納在進行第二卷的校樣時,發覺書商把他書中的數學式子排得太難看了,因此發明數學排版軟體TeX,和字形設計系統METAFONT。等到他再回來要寫第四冊的時候,發現他想討論的東西,現在都寫成API[來源請求]。1992年高德納自大學退休,處於隱居的生活,退休的原因是為了完成TAOCP這部巨著,他估計大約要花20年來完成。第四冊預計分為A、B、C、D四個分卷出版,其中A分卷已於2005年和2011年陸續出版了平裝本和精裝本。

章節

[編輯]
  • 第一冊 - 基礎演算法(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),計劃中。

章節概述

[編輯]

第4A卷 - 列舉與回溯

[編輯]
  • 7 - 導言(82pp)- 出版於第4卷,第0分冊
    • 7.1 - 零和一(Zeros and ones)
      • 7.1.1 - Boolean basics (88 pp) - 出版於第4卷,第0分冊
      • 7.1.2 - 布爾運算(Boolean evaluation)(67 pp) - 出版於第4卷,第0分冊
      • 7.1.3 - Bitwise tricks and techniques (122 pp) - 出版於第4卷,第1分冊
      • 7.1.4 - Binary decision diagrams (150 pp) - 出版於第4卷,第1分冊
    • 7.2 - Generating all possibilities
      • 7.2.1 - Combinatorial generators(397 pp)
        • 7.2.1.1 - Generating all n-tuples - 出版於第4卷4,第2分冊
        • 7.2.1.2 - Generating all permutations - 出版於第4卷,第2分冊
        • 7.2.1.3 - Generating all combinations - 出版於第4卷,第3分冊
        • 7.2.1.4 - Generating all partitions - 出版於第4卷,第3分冊
        • 7.2.1.5 - Generating all set partitions - 出版於第4卷,第3分冊
        • 7.2.1.6 - Generating all trees - 出版於第4卷,第4分冊
        • 7.2.1.7 - History and further references - 出版於第4卷,第4分冊

第4B卷 - 圖論與網路演算法

[編輯]
      • 7.2.2 - Basic backtrack
      • 7.2.3 - Efficient backtracking
    • 7.3 - Shortest paths
    • 7.4 - Graph algorithms
      • 7.4.1 - Components and traversal
      • 7.4.2 - Special classes of graphs
      • 7.4.3 - Expander graphs
      • 7.4.4 - Random graphs
    • 7.5 - Network algorithms
      • 7.5.1 - Distinct representatives
      • 7.5.2 - The assignment problem
      • 7.5.3 - Network flows
      • 7.5.4 - Optimum subtrees
      • 7.5.5 - Optimum matching
      • 7.5.6 - Optimum orderings
    • 7.6 - Independence theory
      • 7.6.1 - Independence structures
      • 7.6.2 - Efficient matroid algorithms

第4C及4D卷 - 最佳化與遞歸

[編輯]
    • 7.7 - Discrete dynamic programming(也見傳遞矩陣法
    • 7.8 - Branch-and-bound techniques
    • 7.9 - Herculean tasks (又名NP-hard問題)
    • 7.10 - Near-optimization
  • 8 - 遞歸(Recursion)

英文版本

[編輯]

當前版本

[編輯]

按卷排序:

以前版本

[編輯]

按出版日期排序:

中譯本

[編輯]

注釋

[編輯]
  1. ^ 1999年,高德納教授騰出時間回覆了所有信件,共匯出125張支票。其中Axel Böttcher曾先後5次得到2.56美元的支票,3次得到5.12美元的支票。

參考文獻

[編輯]

外部連結

[編輯]