算法设计与分析基础 (2008 年度畅销榜NO.1454 )

作者基于丰富的教学经验，开发了一套对算法进行分类的新方法。这套方法站在通用问题求解策略的高度，对现有的大多数算法都能进行很好的分类，从而使本书的读者能够沿着一条清晰的、——致的、连贯的道路来探索算法设计与分析这一迷人领域。
本书十分适合计算机专业的本科高年级学生或者研究生学习。另外，由于本书的介绍深入浅出，只要具备数据结构和离散数学的知识，任何有兴趣探究算法秘密的读者也可以自学本书。

第1章 绪论
1.1 算法的概念
习题1.1
1.2 算法问题求解基础
习题1.2
1.3 重要的问题类型
习题1.3
1.4 基本数据结构
习题1.4
小结
第2章 算法效率分析基础
2.1 分析框架
习题2.1
2.2 渐进符号和基本效率类型
习题2.2
2.3 非递归算法的数学分析
习题2.3
2.4 递归算法的数学分析
习题2.4
2.5 例题：斐波那契数列
习题2.5
2.6 算法的经验分析
习题2.6
2.7算法可视法
小结
第3章 蛮力法
3.1 选择排序和冒泡排序
习题3.1
3.2 顺序查找和蛮力字符串匹配
习题3.2
3.3 最近对和凸包问题的蛮力算法
习题3.3
3.4 穷举查找
6.6 问题化简
习题6.6
小结
第7章 时空权衡
7.1 计数排序
习题7.1
7.2 串匹配中的输入增强技术
习题7.2
7.3 散列法
习题7.3
7.4 B树
习题7.4
小结
第8章 动态规划
8.1 计算二项式系数
习题8.1
8.2 Warshall算法和Floyd算法
习题8.2
8.3 最优二叉查找树
习题8.3
8.4 背包问题和记忆功能
习题8.4
小结
第9章 贪婪技术
9.1 Prim算法
习题9.1
9.2 Kruskal算法
习题9.2
9.3 Dijkstra算法
习题9.3
9.4 哈大曼树
习题9.4
小结
第10章算法能力的极限
10.1 如何求下界
习题10.1
10.2 决策树
习题10.2
10.3 P、NP和NP完全问题
习题10.3
10.4 数值算法的挑战
习题10.4
小结
第11章 超越算法能力的极限
11.1 回溯
习题11.1
11.2 分支界限
习题11.2
11.3 NP困难问题的近似算法
习题11.3
11.4 解非线性方程的算法
习题11.4
小结
跋
附录A：算法分析的实用公式
对数的性质
组合学
重要的求和公式
求和乘法法则
用定积分逼近求和式
向下取整和向上取整公式
其他
附录B：递推关系简明指南
序列和递推关系
递推关系的求解方法
算法分析中的常见递推类型
习题提示
第1章
第2章
第3章
第4章
第5章
第6章
第7章
第8章
第9章
第10章
第11章
参考文献

关于这本书的意义和它的主要内容，作者在序和跋中讲得已经够多够好的了。我只想谈谈自己在翻译过程中的一些感想。 首先，我要恭喜拿到这本书的读者，你们是幸运的。我们读书的年代，很少有大学会教授算法课，惟一和这门课程比较相近的是数据结构。这一点我求证过很多人，只是遇到一个例外，一位毕业于西南师范大学的同事告诉我，她的母校同时开设了数据结构课程和算法课程。遗憾的是，十年过去了，她很难回忆起这两门课程之间的显著区别。很明显，如果算法设计课程真的像本书所描述得那么精彩的话，我们很有必要对算法设计及分析课程给予高度的重视。之所以这么说不是因为数据结构不重要，而是因为，算法设计与分析的角度和高度都是不同于数据结构的： ● 从考虑问题的角度来看，数据结构主要关心不同的数据结构在计算机解题中的作 用和效率；而算法设计与分析则关心不同的算法设计技术的适用性和效率。这使 得这两门课程在某种程度上有所重叠，但又无法相互替代。 ● 从考虑问题的高度来看，数据结构关心的是计算机解题的具体问题，所以很适合 作为计算机技术的入门课程之一：但算法设计与分析则要宽泛地多，它很适合计 算机专业的学生学习，但又不仅限于解决计算机解题的问题。本书的作者说得好， “授人以鱼，不如授人以渔”(LearningsuchtechniquesiSakintOlearningtOfishaS opposedtobeinggivenafishcaughtbysomebodyelse)。当把算法设计与分析提升 为一种解决问题的通用方法时，读者一定会有很大的收获，而且有可能终生受益。 其次，我要庆幸自己有机会翻译一本这么好的图书。这不仅因为在翻译的过程当中，我为自己补上了一门算法设计与分析课程，而且，能够普及优秀的图书也是我的愿望。惟一的担心是自己的能力不足，所以书中无法避免会存在种种失误。读者应该及时向我指出，以便在未来的版本中不断完善。 最后，我要感谢清华大学出版社对我的信任，以及在翻译过程中，诸位编辑给予的帮助。还要感谢我的家人，他们都大力支持我的工作，使我能够以饱满的热情完成翻译工作。尤其是我的太太李靓，她辅助我翻译了本书的大部分章节，并且输入了所有的公式，我很感激她的时刻陪伴。

一个人接受科技教育得到的最大收获，是那些能够受用一生的一般性智能工具”。 ——GeorgeForsythe， 《计算机科学家到来以前我们做什么》，1968 无论是计算科学还是计算实践，算法都在其中扮演着重要角色。由于这一事实，这门学科中出现了大量的教科书。它们在介绍算法的时候，基本上都选择了以下两种方案中的一种。第一种方案是按照问题的类型对算法分类。这类教科书安排了不同的章节分别讨论排序、查找、图等算法。这种做法的优点是，对于解决同一问题的不同算法，它能够立即比较这些算法的效率。其缺点在于，由于过于强调问题的类型，它忽略了对算法设计技术的讨论。 第二种方案围绕着算法设计技术来组织章节。在这种结构中，即使算法来自于不同的计算领域，如果它们采用了相同的设计技术，就会被编成一组。从各方获得的信心(例如[BAY951)使我相信，这种结构对算法设计与分析的基础课程尤为适合。强调算法设计技术有3个重要原因。第一，学生们在解决新问题时，可以运用这些技术设计出新的算法。从实用的角度看，这使学习算法设计技术成为一种很有价值的努力。第二，学生们会尝试着按照算法的内在设计方法，来对已知的众多算法进行分类。计算机科学教育的一个主要目的，就是使学生们通过学习，能够了解不同应用领域的算法间的共性。毕竟，每门科学都会倾向于把它的重要主题归纳为几个甚至一个理论。第三，依我看来，算法设计技术作为问题求解的一般性策略，在解决计算机领域以外的问题时，也能发挥相当大的作用。 目前已经出版了一些围绕算法设计技术进行组织的教科书(参见[BB96]，[HSR98]，[NN981)。但这些书的问题在于，它们未加批判地遵循了相同的设计技术分类法。无论是从理论还是从教育的观点来看，这种分类法都存在一些严重的缺陷。其中最显著的缺陷就是无法对许多重要的算法进行分类。由于这种局限性，这些书的作者不得不在按照设计技术进行分类的同时，另外增加一些章节，来讨论特殊的问题类型。遗憾的是，这种改变导致课程缺乏一致性，而且很可能会使学生产生疑惑。 算法设计技术的新分类法 现有的算法设计技术分类法的缺陷给我带来了困难，它激发我开发一个基于设计技术的新分类法ILev99]，该分类法就是本书的基础。以下是这个新分类法的几个主要优势： ● 新分类法比传统分类法更容易理解。它包含的某些设计策略，比如蛮力法、减治 法、变治法和时空权衡，几乎从不被人们当作重要的设计范例。 ● 新分类法很自然地覆盖了许多传统方法无法分类的经典算法(欧几里得算法、堆 排序、查找树、散列法、拓扑排序、高斯消去法、霍纳法则等，不胜枚举)。所 以，它能够以一种连贯、一致的方式表达这些经典算法的标准内容。 ● 新分类法很自然地包容了一些设计技术的重要变种(比如：它涵盖了减治法的3 个变种和变治法的3个变种)。 ● 在分析算法效率时，新分类法与分析方法结合得更好(参见附录B)。 设计技术作为问题求解的一般性策略 本书中，设计技术主要应用于计算机科学中的经典问题。这里惟一的创新是引入了一些数值算法的内容，这些算法也包含在相同的通用框架之中。(“计算机教育大纲2001一种全新模式的计算机科学课程体系”[CC01]中提倡包含数值算法)但我们也可以把这些设计技术看成问题求解的一般性工具，它们的应用不仅限于传统的计算问题和数学问题。有两个因素令这一点变得尤其重要。第一，越来越多的计算应用超越了它们传统的领域，并且有足够理由使人相信，这种趋势会愈演愈烈。第二，人们渐渐认识到，提高学生们的问题求解能力是高等教育的一个主要目标。为了满足这个目标，在计算机科学课程体系中，安排一门关于算法设计和分析的课程是非常合适的，因为它会告诉学生如何应用一些特定的策略来解决问题。虽然我并不建议将算法设计和分析课程变成一门教授一般性问题求解方法的课程，但我的确认为，我们不应错过算法设计和分析课程提供的这样一个独一无二的机会。所以，本书包含的某些应用是和谜题相关的。虽然利用谜题来教授算法课程决不是一个新的想法，但本书打算通过引进一些全新的例子来系统地实现这个思路。 如何使用本书 我的目标是写一本既不泛泛而谈，又能被学生们独立阅读的教材。为了实现这个目标本书做了如下努力： ● 根据George Forsythe的观点(参见引语)，我试图着重强调那些隐藏在算法设计 和分析背后的主要思想。在选择特定的算法宋阐述这些思想的时候，我并不倾向 于涉及大量的算法，而是选择那些能够揭示出一个根本的设计技术或是分析方法 的算法。幸运的是，大多数经典算法满足这个要求。 ● 第2章主要分析算法的效率，该章将分析非递归算法的方法和分析递归算法的方 法区别开来。这一章还花了一些篇幅介绍算法实证分析以及算法可视化。 ● 书中系统地为读者安排了一些问题。其中有些问题是经过精心设计的，而且立即 文部分所涉及内容的重要意义，或是为了介绍一些书中没有涉及到的算法。有一 些习题是从因特网上找到的，还有些习题是让读者为后面章节将要涉及的内容做 准备的。较难的习题数量不多，会在教师用书中用一种特殊的记号标注出来(因 为有些学生可能没有勇气做那些标有难度的习题，所以本书没有对习题标注难 度)。谜题类的习题用了一种特殊的图标做标注。 ● 本书所有的习题都附有提示。除了编程练习，习题的详细解法都能够在教师用书 中找到，符合条件的读者可以从出版社得到教师用书(请联系Addison·Wesley公 司的销售代表，或者发电子邮件至aw.cse@aw.com)。本书的任何读者都可以向 www.aw.com/cssupport网站寻求支持。 读者所需的知识背景 本书假定读者已经学习了离散数学的标准课程和一门基础性的编程课程。在这样一种知识背景下，读者应该能够掌握本书的内容而不会遇到太大的困难。尽管如此，1.4节、附录A和附录B仍然会对基本的数据结构、必须用到的求和公式和递推关系分别做了复习和回顾。只有3个小节(2.2节、10.4节和11.4节)会用到一些简单的微积分知识；如果学生们缺少必要的微积分知识，完全可以跳过这3个包含微积分内容的小节，这样做不会妨碍对本书其余部分的理解。 进度安排 如果打算开设一门围绕算法设计技术来讲解算法设计和分析理论的基础课程，本书可以作为这门课的教科书。对于——门典型的单学期课程来说，本书涵盖的内容可能过于丰富了。大体上来说，跳过第3章至第11章的部分内容不会影响读者对后面部分的理解。本书的任何一个部分都可以安排学生自学。特别要指出的是，2.6节和2.7节分别介绍了实证分析和算法可视化，这两小节的内容可以结合练习布置给学生。 下面提供一种针对一个学期课程的教学安排，它是按照40课时的集中授课时间设计的。