计算机科学

首页 > 计算机科学

计算机程序设计艺术

2018-07-27 11:00:09     所属分类:电脑书籍

计算机程序设计艺术》(The Art of Computer Programming),简称TAOCP,是高德纳编著的关于计算机程序设计的七卷本著作。作者并因此获得美国计算机协会1974年图灵奖。[1]

目录

  • 1 概述
  • 2 章节
  • 3 章节概述
    • 3.1 第4A卷 - 枚举与回溯(Enumeration and Backtracking)的大纲
    • 3.2 第4B卷 - 图论与网络算法(Graph and Network Algorithms)的大纲
    • 3.3 第4C及4D(可能)卷 - 最优化与递归(Optimization and Recursion)的大纲
  • 4 英文版本
    • 4.1 当前版本
    • 4.2 以前版本
  • 5 中译本
  • 6 注释
  • 7 参考文献

概述

高德纳

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.)[注 1]。比尔·盖茨在1995年说,“如果你认为你是一名真正优秀的程序员,就去读第一卷,确定可以解决其中所有的问题。”“如果你能读懂整套书的话,请给我发一份你的简历。”《计算机程序设计艺术》是Knuth一生中最重要的事业,他写这本书的目的是“组织和总结所知道的计算机方法的相关知识,并打下坚实的数学、历史基础”。

同时他在进行第二卷的校样时,发觉书商把他书中的数学式子排得太难看了,因此发明数学排版软件TeX,和字形设计系统METAFONT。等到他再回来要写第四册的时候,发现他想讨论的东西,现在都写成API了[来源请求]。1992年Knuth自大学退休,处于隐居的生活,退休的原因是为了完成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卷 - 枚举与回溯(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)

英文版本

当前版本

按卷排序:

  • 第一卷: 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年)

注释

  1. ^ 1999年,高德纳教授腾出时间回复了所有信件,共汇出125张支票。其中Axel Böttcher曾先后5次得到2.56美元的支票,3次得到5.12美元的支票。

参考文献

  1. ^ 1974 – Donald E. Knuth See the ACM Author Profile in the Digital Library[失效链接]
  2. ^ American Scientist Online - 100 or so Books that shaped a Century of Science. (原始内容存档于2009-09-28). 
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/339135.html

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
支付宝扫一扫赏金或者微信支付5毛钱,阅读全文

打开微信扫一扫,即可进行阅读全文哦


下一篇:未来之路
相关推荐
爱淘宝