計算機程序設計藝術

《**電腦程式設計藝術**》（英語：_The Art of Computer Programming_），簡稱 TAOCP，是美國電腦科學家高德納（Donald Ervin Knuth）編著的關於電腦程式設計之七卷本著作。作者並因此獲得美國電腦協會 1974 年圖靈獎。

## 概述

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

任何人發現書上的錯誤，都可以向他舉發，並領取 2.56 美元，因為「256 美分剛好是十六進位的一美元」（256 pennies is one hexadecimal dollar.）。比爾・蓋茲在 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）

## 英文版本

### 當前版本

按卷排序：

* _第一卷: Fundamental Algorithms_. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xx+650pp. ISBN 0-201-89683-4
* _第一卷，第一分冊: MMIX -- A RISC Computer for the New Millennium_. (Addison-Wesley, February 14, 2005) ISBN 0-201-85392-2（will be in the fourth edition of volume 1）
* _第二卷: Seminumerical Algorithms_. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762pp. ISBN 0-201-89684-2
* _第三卷: Sorting and Searching_. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. ISBN 0-201-89685-0
* _第四卷，第零分冊: Introduction to Combinatorial Algorithms and Boolean Functions_, (Addison-Wesley Professional, April 28, 2008) vi+240pp, ISBN 0-321-53496-4
* _第四卷，第一分冊: Bitwise tricks & techniques; Binary Decision Diagrams_ (Addison-Wesley Professional, March 27, 2009) viii+260pp, ISBN 0-321-58050-8
* _第四卷，第二分冊: Generating All Tuples and Permutations_, (Addison-Wesley, February 14, 2005) v+127pp, ISBN 0-201-85393-0
* _第四卷，第三分冊: Generating All Combinations and Partitions_. (Addison-Wesley, July 26, 2005) vi+150pp, ISBN 0-201-85394-9
* _第四卷，第四分冊: Generating all Trees -- History of Combinatorial Generation_, (Addison-Wesley, February 6, 2006) vi+120pp, ISBN 0-321-33570-8

### 以前版本

按出版日期排序：

* _第一卷_，第一版，1968 年. 634pp. ISBN 0-201-03801-3.
* _第二卷_，第一版，1969 年，xi+624pp, ISBN 0-201-03802-1.
* _第三卷_，第一版，1973 年，xi+723pp+centerfold, ISBN 0-201-03803-X
* _第一卷_，第二版，1973 年，xiii+634pp, ISBN 0-201-03809-9.
* _第二卷_，第二版，1981 年，xiii+ 688pp. ISBN 0-201-03822-6.

## 中譯本

* 《電腦程式設計藝術 (第 1 卷): 基本演算法》，國防工業出版社，譯者：蘇運霖，ISBN 978-7-118-02799-0
* 《電腦程式設計藝術 (卷 1): 基本演算法》，第三版，人民郵電出版社，譯者：李伯民，范明，蔣愛軍，ISBN 9787115360670（出版時間：2016 年）

## 注釋

## 參考文獻

## 外部連結

* Overview of topics（頁面存檔備份，存於網際網路檔案館） (Knuth's personal homepage)（英文）