计算机程序设计艺术介绍

《计算机程序设计艺术 》（The Art of Computer Programming ），簡稱TAOCP，是高德纳（Donald Ervin Knuth）编著的关于计算机程序设计的七卷本著作。作者並因此获得美国计算机协会1974年图灵奖。^[1]

1 概述
2 章節
3 第4A卷,列舉與回溯（Enumeration and Backtracking）的大綱
4 第4B卷,圖形與網路演算法（Graph and Network Algorithms）的大綱
5 第4C及4D(可能)卷, 最佳化與遞歸（Optimization and Recursion）的大綱
6 發佈
7 英文版本
- 7.1 當前版本
- 7.2 以前版本
8 中譯本
9 注釋

[编辑 ] 概述

高德纳

1962年，Knuth還是個研究生的時候就開始了程式設計的工作。高德納在攻讀博士其間，Addison-Wesley 公司的顧問 Richard Varga 找他出書，因課業繁忙，一時沒時間草稿，1963年高德納獲得加州理工學院數學博士學位。1968年，31歲開始出版他的歷史性經典巨著： The Art of Computer Programming ，一口氣寫了三千多頁，自此他計劃寫7卷。1999年底被美國科學家期刊（American Scientist）列为20世纪最佳12部学术专著之一，与狄拉克的「量子力学」、爱因斯坦的「相对论」、曼德布罗特的「分形论」、鲍林的「化学键」、罗素和怀特海德的「数学基础」、冯诺依曼和摩根斯坦的「博弈论」、维纳的「控制论」、伍德沃和霍夫曼的「轨道对称性」、费曼的「量子电动力学」等科学史上的重要著作并列必讀經典^[2] 。1976年為止，已賣出超過一百萬冊。

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

同時他在進行第二卷的校樣時，發覺書商把他書中的數學式子排得太難看了，因此發明數學排版軟體T_E X，和字形设计系统METAFONT 。等到他再回來要寫第四冊的時候，發現他想討論的東西，現在都寫成API了。1992年Knuth自大學退休，處於隱居的生活，退休的原因是為了完成 TAOCP 這部巨著，他估計大約要花 20 年來完成。目前此書出版至第三冊，第四冊預計2005年2月出版，他期望第四卷的篇幅約為2000頁，並分為三個獨立的章節。

[编辑 ] 章節

第一冊 - 基礎演算法（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）, 計劃中(預計2015年完成).
- 第九章 - 語句掃瞄（Lexical scanning）
- 第十章 - 剖析技術（Parsing techniques）
第六冊 - 與上下文無關語言理論（Theory of Context-Free Languages）, 計劃中
第七冊 - 編譯器技術（Compiler Techniques）,計劃中

[编辑 ] 第4A卷,列舉與回溯（Enumeration and Backtracking）的大綱

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卷,圖形與網路演算法（Graph and Network Algorithms）的大綱

- - 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(可能)卷, 最佳化與遞歸（Optimization and Recursion）的大綱

- 7.7 - Discrete dynamic programming
- 7.8 - Branch-and-bound techniques
- 7.9 - Herculean tasks (又名NP-hard 問題)
- 7.10 - Near-optimization
8 - 遞歸 (Recursion)

[编辑 ] 發佈

第一卷:1968年
第二卷:1969年
第三卷:1973年
第四卷:2005年2月(第1期)

[编辑 ] 英文版本

[编辑 ] 當前版本

按卷排序：

第一卷: Fundamental Algorithm s . 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 Tuple s and Permutation s , (Addison-Wesley, February 14, 2005) v+127pp, ISBN 0-201-85393-0
第四卷, 第三分冊: Generating All Combination s 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 .

[编辑 ] 中譯本

《计算机程序设计艺术》，國防工業出版社，譯者：蘇運霖 ISBN 978-7-118-02799-0

[编辑 ] 注釋

^ 1974 – Donald E. Knuth See the ACM Author Profile in the Digital Library
^ American Scientist Online - 100 or so Books that shaped a Century of Science ．
^ 1999年，高纳德教授腾出时间回覆了所有信件，共汇出125张支票。其中Axel Böttcher 曾先后5次得到2.56美金的支票，3次得到5.12美金的支票。