算法导论（原书第3版）/计算机科学丛书

[美] Thomas H.Cormen，[美] Charles E.Leiserson，[美] Ronald L.Rivest，[美] Clifford Stein 著，殷建平，徐云，王刚 等 译

• 出版社： 机械工业出版社
• ISBN：9787111407010
• 版次：3
• 商品编码：11144230
• 品牌：机工出版
• 包装：平装
• 丛书名： 计算机科学丛书
• 外文名称：Introduction to Algorithms, third edition
• 开本：16开
• 出版时间：2012-12-01
• 用纸：胶版纸
• 页数：796
• 正文语种：中文

点此购买

编辑推荐

　　MIT四大名师联手铸就，影响全球千万程序员的“算法shengjing”！国内外千余所高校采用！

内容简介

　　在有关算法的书中，有一些叙述非常严谨，但不够全面；另一些涉及了大量的题材，但又缺乏严谨性。《算法导论（原书第3版）/计算机科学丛书》将严谨性和全面性融为一体，深入讨论各类算法，并着力使这些算法的设计和分析能为各个层次的读者接受。全书各章自成体系，可以作为独立的学习单元；算法以英语和伪代码的形式描述，具备初步程序设计经验的人就能看懂；说明和解释力求浅显易懂，不失深度和数学严谨性。

　　《算法导论（原书第3版）/计算机科学丛书》全书选材经典、内容丰富、结构合理、逻辑清晰，对本科生的数据结构课程和研究生的算法课程都是非常实用的教材，在IT专业人员的职业生涯中，《算法导论（原书第3版）/计算机科学丛书》也是一本案头必备的参考书或工程实践手册。

　　第3版的主要变化：

　　·新增了van Emde Boas树和多线程算法，并且将矩阵基础移至附录。

　　·修订了递归式（现在称为“分治策略”）那一章的内容，更广泛地覆盖分治法。

　　·移除两章很少讲授的内容：二项堆和排序网络。

　　·修订了动态规划和贪心算法相关内容。

　　·流网络相关材料现在基于边上的全部流。

　　·由于关于矩阵基础和Strassen算法的材料移到了其他章，矩阵运算这一章的内容所占篇幅更小。

　　·修改了对Knuth-Morris-Pratt字符串匹配算法的讨论。

　　·新增100道练习和28道思考题，还更新并补充了参考文献。

作者简介

　　Thomas H. Cormen （托马斯·科尔曼），达特茅斯学院计算机科学系教授、系主任。目前的研究兴趣包括：算法工程、并行计算、具有高延迟的加速计算。他分别于1993年、1986年获得麻省理工学院电子工程和计算机科学博士、硕士学位，师从Charles E. Leiserson教授。由于他在计算机教育领域的突出贡献，Cormen教授荣获2009年ACM杰出教员奖。

　　Charles E. Leiserson（查尔斯·雷瑟尔森），麻省理工学院计算机科学与电气工程系教授，Margaret MacVicar Faculty Fellow。他目前主持MIT超级计算技术研究组，并是MIT计算机科学和人工智能实验室计算理论研究组的成员。他的研究兴趣集中在并行和分布式计算的理论原理，尤其是与工程现实相关的技术研究。Leiserson教授拥有卡内基·梅隆大学计算机科学博士学位，还是ACM、IEEE和SIAM的会士。

　　Ronald L. Rivest （罗纳德·李维斯特），现任麻省理工学院电子工程和计算机科学系安德鲁与厄纳·维特尔比（Andrew and Erna Viterbi）教授。他是MIT计算机科学和人工智能实验室的成员，并领导着其中的信息安全和隐私中心。他1977年从斯坦福大学获得计算机博士学位，主要从事密码安全、计算机安全算法的研究。他和Adi Shamir和Len Adleman一起发明了RSA公钥算法，这个算法在信息安全中获得大的突破，这一成果也使他和Shamir、Adleman一起得到2002年ACM图灵奖。他现在担任国家密码学会的负责人。

　　Clifford Stein（克利福德·斯坦），哥伦比亚大学计算机科学系和工业工程与运筹学系教授，他还是工业工程与运筹学系的系主任。在加入哥伦比亚大学大学之前，他在达特茅斯学院计算机科学系任教9年。Stein教授拥有MIT硕士和博士学位。他的研究兴趣包括：算法的设计与分析，组合优化、运筹学、网络算法、调度、算法工程和生物计算。

精彩书评

　　★“鉴于数据量的爆炸性增长，和计算应用的多样性，现在比以往更需要有效算法。这本书条理清晰，是一本非常好的算法设计与分析方面的导论性书籍。每章前半部分介绍了讲授和学习算法的有效方法，后半部分为更专业的读者和求知欲强的学生提供了更引人入胜的资料来讨论这个迷人领域的各种可能性和挑战。”

　　——Shang-Hua Teng（腾尚华），南加州大学维特比工学院计算机系Seeley G. Mudd 教授

　　★“本书是算法领域的一部经典著作，书中系统、全面地介绍了现代算法：从较快算法和数据结构到用于看似难以解决问题的多项式时间算法；从图论中的经典算法到用于字符匹配、计算集合和数论的特殊算法。本书第3版尤其增加了两章专门讨论van Emde Boas树（有用的数据结构之一）和多线程算法（日益重要的一个主题）。”

　　——Daniel Spielman，耶鲁大学计算机科学和应用数学Henry Ford II教授

目录

精彩书摘

　　证明 每个结点的秩从0开始，并且只有执行了LINK操作，它才会增加。因为最多有n—1个UNION操作，所以同样最多有n—1个LINK操作。因为每个LINK操作或者不改变任何的秩，或者将某结点的秩加1，所以所有的秩最大为n—1。

　　引理21.6提供了一个关于结点秩的较弱的界。事实上，每个结点的秩最大为（lgn）（见练习21.4—2）。然而，引理21.6的这个较松的界已足够满足我们的要求。

　　时间界的证明 我们将利用摊还分析中的势方法（见17.3节）来证明O（ma（n））的时间界。在进行摊还分析时，为了方便起见，我们假设不调用UNION操作，而是调用LINK操作。也就是说，因为LINK过程的参数是指向两个根的指针，故我们独立使用相应的FIND—SET操作。下面的引理说明即使因调用UNION而导致额外的FIND—SET操作，其渐近运行时间仍然保持不变。

　　……

前言/序言

　　在计算机出现之前，就有了算法。现在有了计算机，就需要更多的算法，算法是计算的核心。

　　本书提供了对当代计算机算法研究的一个全面、综合的介绍。书中给出了多个算法，并对它们进行了较为深入的分析，使得这些算法的设计和分析易于被各个层次的读者所理解。我们力求在不牺牲分析的深度和数学严密性的前提下，给出深入浅出的说明。

　　书中每一章都给出了一个算法、一种算法设计技术、一个应用领域或一个相关的主题。算法是用英语和一种“伪代码”来描述的，任何有一点程序设计经验的人都能看得懂。书中给出了244幅图，说明各个算法的工作过程。我们强调将算法的效率作为一种设计标准，对书中的所有算法，都给出了关于其运行时间的详细分析。

　　本书主要供本科生和研究生的算法或数据结构课程使用。因为书中讨论了算法设计中的工程问题及其数学性质，所以，本书也可以供专业技术人员自学之用。

　　本书是第3版。在这个版本里，我们对全书进行了更新，包括新增了若干章、修订了伪代码等。

　　致使用本书的教师

　　本书的设计目标是全面、适用于多种用途。它可用于若干课程，从本科生的数据结构课程到研究生的算法课程。由于书中给出的内容比较多，只讲一学期一般讲不完，因此，教师们应该将本书看成是一种“缓存区”或“瑞典式自助餐”，从中挑选出能最好地支持自己希望教授的课程的内容。

　　教师们会发现，要围绕自己所需的各个章节来组织课程是比较容易的。书中的各章都是相对独立的，因此，你不必担心意想不到的或不必要的各章之间的依赖关系。每一章都是以节为单位，内容由易到难。如果将本书用于本科生的课程，可以选用每一章的前面几节内容；用于研究生的课程中，则可以完整地讲授每一章。

　　全书包含957道练习和158道思考题。每一节结束时给出练习，每一章结束时给出思考题。练习一般比较短，用于检查学生对书中内容的基本掌握情况。有一些是简单的自查性练习，有一些则要更充实，可以作为家庭作业布置给学生。每一章后的思考题都是一些叙述较为详细的实例研究，它们常常会介绍一些新的知识。一般来说，这些思考题都会包含几个小问题，引导学生逐步得到问题的解。

　　鉴于本书前几版使用的反馈，我们在本书配套网站上公布了其中一些练习和思考题的答案（但不是全部）。我们会定期更新这些答案，因此需要教师每次授课前都到这个网站上来查看。　　在那些不太适合本科生、更适合研究生的章节和练习前面，都加上了星号（）。带星号的章节也不一定就比不带星号的更难，但可能要求了解更多的数学知识。类似地，带星号的练习可能要求有更好的数学背景或创造力。

　　致使用本书的学生

　　希望本教材能为学生们提供关于算法这一领域的有趣介绍。我们力求使书中给出的每一个算法都易于理解和有趣。为了在同学们遇到不熟悉或比较困难的算法时提供帮助，我们逐个步骤地描述每一个算法。此外，为了便于大家理解书中对算法的分析，对于其中所需的数学知识，我们给出了详细的解释。如果对某一主题已经有所了解，会发现根据书中各章的编排顺序，可以跳过一些介绍性的小节，直接阅读更高级的内容。

　　本书是一本大部头著作，读者所修的课程可能只讲授其中的一部分。我们试图使它能成为一本现在对读者有用的教材，将来在读者的职业生涯中，也能成为一本案头的数学参考书或工程实践手册。

　　阅读本书需要哪些预备知识呢·

　　读者需要有一些程序设计方面的经验，尤其需要理解递归过程和简单的数据结构，如数组和链表。

　　读者应该能较为熟练地利用数学归纳法进行证明。书中有一些内容要求读者具备初等微积分方面的知识。除此之外，本书的第一部分和第八部分将介绍读者需要用到的所有数学技巧。

　　我们收到读者的反馈，他们强烈希望提供练习和思考题的答案，为此，我们在站上给出了少数练习和思考题的答案，读者可以根据我们的答案来检验自己的解答。　　致使用本书的专业技术人员

　　本书涉及的主题非常广泛，因而是一本很好的算法参考手册。因为每一章都是相对独立的，所以读者可以重点查阅自己感兴趣的主题。　　在我们所讨论的算法中，多数都有着极大的实用价值。因此，我们在书中涉及了算法实现方面的考虑和其他工程方面的问题。对于那些为数不多的、主要具有理论研究价值的算法，通常还给出其实用的替代算法。　　如果希望实现这些算法中的任何一个，你会发现将书中的伪代码翻译成你熟悉的某种程序设计语言是一件相当直接的事。伪代码被设计成能够清晰、简明地描述每一个算法。因此，我们不考虑错误处理和其他需要对读者所用编程环境有特定假设的软件工程问题。我们力求简单而直接地给出每一个算法，而不会让某种特定程序设计语言的特殊性掩盖算法的本质内容。

　　如果你是在课堂外使用本书，那么可能无法从教师那里得到答案来验证自己的解答，因此，我们在网站上给出了部分练习和思考题的答案，读者可以免费下载参考。

　　致我们的同事

　　我们在本书中给出了详尽的参考文献。每一章在结束时都给出了“本章注记”，介绍一些历史性的细节和参考文献。但是，各章的注记并没有提供整个算法领域的全部参考文献。有一点可能是让人难以置信的，就是在本书这样一本大部头中，由于篇幅的原因，很多有趣的算法都没能包括进来。

　　尽管学生们发来了大量的请求，希望我们提供思考题和练习的解答，但我们还是决定基本上不提供思考题和练习的参考答案（少数除外），以打消学生们试图查阅答案，而不是自己动手得出答案的念头。

　　第3版中所做的修改

　　在本书的第2版和第3版之间有哪些变化呢·这两版之间的变化量和第2版与第1版之间的变化量相当，正如在第2版的变化中所说，这些变化可以说不太大，也可以说很大，具体要看读者怎么看待这些变化了。

　　快速地浏览一遍目录，你就会发现，第2版中的多数章节在第3版中都出现了。在第3版中，去掉了两章和一节的内容，新增加了三章以及两节的内容。如果单从目录来判断第3版中改动的范围，得出的结论很可能是改动不大。

　　我们依然保持前两版的组织结构，既按照问题领域又根据技术来组织章节内容。书中既包含基于技术的章，如分治法、动态规划、贪心算法、摊还分析、NP完全性和近似算法，也包含关于排序、动态集的数据结构和图问题算法的完整部分。我们发现虽然读者需要了解如何应用这些技术来设计和分析算法，但是思考题中很少提示应用哪个技术来解决这些问题。

　　下面总结了第3版的主要变化：

　　新增了讨论van Emde Boas树和多线程算法的章节，并且将矩阵基础移至附录。

　　修订了递归式那一章的内容，更广泛地覆盖分治法，并且前两节介绍了应用分治法解决两个问题。4.2节介绍了用于矩阵乘法的Strassen算法，关于矩阵运算的内容已从本章移除。

　　移除两章很少讲授的内容：二项堆和排序网络。排序网络中的关键思想——0-1原理，在本版的思考题8-7中作为比较交换算法的0-1排序引理进行介绍。斐波那契堆的处理不再依赖二项堆。

　　修订了动态规划和贪心算法相关内容。与第2版中的装配线调度问题相比，本版用一个更有趣的问题——钢条切割来引入动态规划。而且，我们比在第2版中更强调助记性，并且引入子问题图这一概念来阐释动态规划算法的运行时间。在我们给出的贪心算法例子（活动选择问题）中，我们以更直接的方式给出贪心算法。　　我们从二叉搜索树（包括红黑树）删除一个结点的方式，现在保证实际所删除的结点就是请求删除的结点（在前两版中，有些情况下某个其他结点可能被删除）。用这种新的方式删除结点，如果程序的其他部分保持指针指向树中的结点，那么终止时就不会错误地将指针指向已删去的结点。

　　流网络相关材料现在基于边上的全部流。这种方法比前两版中使用的净流更直观。

　　由于关于矩阵基础和Strassen算法的材料移到了其他章，矩阵运算这一章的内容比第2版中所占的篇幅更小。

　　修改了对Knuth-Morris-Pratt字符串匹配算法的讨论。

　　修正了上一版中的一些错误。在网站上，这些错误大多数都已在第2版的勘误中给出，但是有些没有给出。

　　根据许多读者的要求，我们改变了书中伪代码的语法，现在用“=”表示赋值，用“==”表示检验相等，正如C、C++、Java和Python所用的。同样，我们不再使用关键字do和then而是使用“//”作为程序行末尾的注释符号。我们现在还使用点标记法表明对象属性。书中的伪代码仍是过程化的，而不是面向对象的。换句话说，我们只是简单地调用过程，将对象作为参数传递，而不是关于对象的运行方法。

　　新增100道练习和28道思考题，还更新并补充了参考文献。

　　最后，我们对书中的语句、段落和小节进行了一些调整，以使本书条理更清晰。

　　网站

　　读者可以通过网站来获取补充资料，以及与我们联系。这个网站上给出了已知错误的清单、部分练习和思考题的答案等。此外，网站上还告诉读者如何报告错误或者提出建议。

　　第3版致谢

　　我们已经与MIT Press合作20多年，建立了很好的合作关系！感谢Ellen Faran、Bob Prior、Ada Brunstein和Mary Reilly的帮助和支持。

　　在出版第3版时，我们在达特茅斯学院计算机科学系、MIT计算机科学与人工智能实验室、哥伦比亚大学工业工程与运筹学系从事教学和科研工作。感谢这些学校和同事为我们提供的支持和实验环境。

　　Julie Sussman，P.P.A担当本书第3版的技术编辑，再次拯救了我们。每次审阅，我们都觉得已经消除了错误，但是Julie还是发现了许多错误。她还帮我们改进了几处文字表述。如果有技术编辑名人堂，Julie一定第一轮就可以入选。Julie是非凡的，我们怎么感谢都是不够的。Priya Natarajan也发现了一些错误，使得我们可以在将本书交给出版社前修正这些错误。书中的任何错误（毫无疑问，一定存在一些错误）都由作者负责（或许这些错误有些是Julie审阅材料后引入的）。

　　对于van Emde Boas树的处理出自于Erik Demaine的笔记，转而也受到Michael Bender的影响。此外，我还将Javed Aslam、Bradley Kuszmaul和Hui Zha的思想也整合到这一版。

　　多线程算法这一章是基于与Harald Prokop一起撰写的笔记，其他在MIT从事Cilk项目的同事也对本部分内容有所贡献，包括Bradley Kuszmaul和Matteo Frigo。多线程伪代码的设计灵感来自MIT Cilk扩展到C，以及由Cilk Arts的Cilk++扩展到C++。

　　我们还要感谢许多第1版和第2版的读者，他们报告了所发现的错误，或者提出了改进本书的建议。我们修正了全部报告来的真实错误，并且尽可能多地采纳了读者的建议。我们很高兴有这么多的人为本书做出贡献，但是很遗憾我们无法全部列出这些贡献者。

　　最后，非常感谢我们各自的妻子Nicole Cormen、Wendy Leiserson、Gail Rivest和Rebecca Ivry，还有我们的孩子Ricky、Will、Debby和Katie Leiserson，Alex和Christopher Rivest，以及Molly、Noah和Benjamin Stein。感谢他们在我们写作本书过程中给予的爱和支持。正是由于有了来自家庭的耐心和鼓励，本书的写作工作才得以完成。谨将此书献给他们。

　　Thomas H.Cormen，新罕布什尔州黎巴嫩市

　　Charles E.Leiserson，马萨诸塞州剑桥市

　　Ronald L.Rivest，马萨诸塞州剑桥市

　　Clifford Stein，纽约州纽约市

　　译者序

　　我从1994年开始每年都为本科生讲授《算法设计与分析》课程，粗略地统计一下发现至今已有5000余名各类学生听过该课。算法的重要性不言而喻，因为不管新概念、新方法、新理论如何引人注目，信息的表示与处理总是计算技术（含软件、硬件、应用、网络、安全、智能等）永恒的主题。信息处理的核心是算法，在大数据时代，设计高效的算法显得格外重要。

　　当初，为了教好这门基础必修课，提高教学质量，我觉得应该从教学内容的改革入手，具体来说，采用的教材应该与国际一流大学接轨。1997年访美期间，在Stanford大学了解到他们采用的教材是Thomas H. Cormen等编著的《Introduction to Algorithms》，于是从Stanford书店买了一本带回来，从第二年开始便改用该书作教材。至今，15年过去了，我们一直追随其变迁，从第二版到第三版。教学实践证明它确实是一本好教材，难怪世界范围内包括MIT、CMU、Stanford、UCB、Cornell、UIUC等国际国内名校在内的1000余所大学都一直用它作为教材或教学参考书，也难怪它印数巨大且在《高引用计算机科学文献》（《Most Cited Computer Science Citations》）一览表中名列前茅。

　　这是一本有1200多页的厚书，教学内容非常丰富，不但涵盖了典型算法、算法分析、算法设计方法和NP完全等内容，而且还包括数据结构，甚至高级数据结构的介绍。后者可作为国内《数据结构》课程的教材或教学参考资料。在学时有限的情况下，要在本科阶段教完前者的所有内容也是困难的，故要做取舍。好在该书的各个章节相对独立且难度由浅入深，我们的做法是将相对容易的一般的入门性内容留在本科阶段，而将相对难的专门的较深入的内容并入研究生课程《算法及复杂性》或《计算复杂性》。除本校外，本人就曾多次应邀在兰州大学、湖南大学和浙江师范大学等院校为研究生讲授过这些内容。其实该书也适合希望增强自身程序设计能力和程序评判能力的广大应用计算技术的社会公众，特别是参加信息学奥林匹克竞赛和ACM程序设计竞赛的选手及其教练员。

　　教学过程中我们发现该书具有以下特点：

（1）选材与时俱进，具有实用性且能引起读者的兴趣。该书中研究的许多问题都是当前现实应用中的关键技术问题。

（2）采用伪码描述算法，既简洁易懂又便于抓住本质，再配上丰富的插图来描述和解释算法的执行过程使得教学内容更加通俗，便于自学。

（3）对算法正确性和复杂性的分析比较全面，既有严密的论证，又有直观的解释。

（4）既有结论性知识的介绍，也有逐步导出结论的研究过程的展示。

（5）丰富的练习题和思考题使得及时检验所学知识掌握情况和进一步拓展学习内容成为可能。

　　同时，我们也注意到：学生们总是反映看英文版教材速度太慢，所以他们总是想方设法再找一本中译版来阅读。正是这样的背景，在第三版的《Introduction to Algorithms》出版后，我们应机械工业出版社编辑的邀请，启动了长久的翻译工程，先后参加翻译工作的老师有：国防科学技术大学的殷建平教授（翻译第1~3章）、中国科学技术大学的徐云教授（翻译第10~14章、第18~21章和第27章）、南开大学的王刚教授（翻译第4章和第15~17章）、南开大学的刘晓光教授（翻译第6~9章）、南开大学的苏明副研究员（翻译第5章和第28~30章）、上海交通大学的邹恒明教授（翻译第22~26章）、哈尔滨工业大学的王宏志副教授（翻译第31~35章和附录部分）。由于水平有限且工作量巨大，译文中一定存在许多不足，在此敬请各位同行专家学者和广大读者批评指正，欢迎大家将发现的错误或提出的意见与建议发送到邮箱。在整个工程即将完成之际，我们特别要感谢机械工业出版社的温莉芳老师和王春华老师，没有你们的信任、耐心和支持整个翻译工作不可能完成。

　　殷建平

　　2012年11月于长沙

点此购买