本书不仅讲解传统的算法设计策略和技巧，而且关注算法领域不断涌现的新概念、新方法和新应用，帮助读者把握技术热点及发展趋势。书中引入了降维技术、并行算法、随机算法、层次化存储结构算法和流算法等新内容，大量使用概率分析和随机化技术，并包含众多新颖的示例，特别是强调计算模型和计算环境，不再局限于理想化的随机存取机模型。全书内容简洁明快，并配有丰富的习题和拓展阅读资料，适合作为高等院校计算机相关专业的教材，也适合业界技术人员阅读参考。

关注算法领域的新概念、新方法和新应用，强调计算模型和计算环境

过去20年间，我们在印度理工学院德里分校（IIT Delhi）任教，讲授了多门与算法设计和分析相关的本科生课程和研究生课程，本书即由其中的精华内容提炼而成。本书主要面向计算机科学（CS）专业的三年级本科生及入学第一学期的研究生。本书旨在为高阶算法课程提供支撑材料，在那些课程中，读者可以接触到越来越常用和适用的其他更现代的计算框架。
快速浏览一下目录就会发现，书中近一半的主题都已为讲授算法的大量标准教科书所涵盖，例如Aho等人的著作[7]、Horowitz等人的著作[65]、Cormen等人的著作[37]，以及较新的Kleinberg和Tardos的著作[81]、Dasgupta等人的著作[40]等。该领域的第一本经典教材是Aho等人的著作，他们认为“算法研究是计算机科学的核心”，并由此引入“算法”这一主题。在过去50年中，伴随着计算机科学的快速发展以及信息技术在更多领域中的应用，这一结论得到了更广泛的认可。由于算法具有这一基本属性，因此大约50年前发现的许多早期算法——例如快速傅里叶变换（FFT）、快速排序、Dijkstra最短道路算法等——依然被收录在（包括本书在内的）每一本教材中。
　该书有影印版“Alfred V.Aho,John E.Hopcroft,Jeffrey D.Ullman著.计算机算法的设计与分析（英文版）.机械工业出版社,2006”及中译本“（美）阿霍，（美）霍普克劳夫特，（美）乌尔曼著，黄林鹏，王德俊，张仕译.计算机算法的设计与分析.机械工业出版社,2007”。——译者注
该书第2版有中译本“（美）霍洛维兹，（美）萨尼，（美）拉贾瑟克雷恩著，赵颖等译.计算机算法（C++语言描述）（第2版）.清华大学出版社，2015”。——译者注　
该书第3版有中译本“Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein著，殷建平等译.算法导论（原书第3版）.机械工业出版社,2012”。——译者注
该书有影印版“Jon Kleinberg,va Tardos著.算法设计（英文影印版）.清华大学出版社，2006”及中译本“Jon Kleinberg,va Tardos著，张立昂,屈婉玲译.算法设计.清华大学出版社，2007”。——译者注

该书有英文注释版“Sanjoy Dasgupta,Christos H.Papadimitriou,Umesh Vazirani著，钱枫,邹恒明注释.算法概论（注释版）.机械工业出版社，2008”及中译本“Sanjoy Dasgupta,Christos H.Papadimitriou,Umesh Vazirani著，王沛,唐扬斌,刘齐军译.算法概论.清华大学出版社，2008”。——译者注
对于很多计算模式及从令人惊叹的新发现与不断变更的新工艺中涌现出来的重要技术，我们的理解有了一些重要而微妙的变化，这促使我们编写了这本关于算法的新书。作为教师，我们有责任向年轻一代传递正确的关注重点，使之得以持续享受这种批判性的智力活动，并对科研领域的拓展做出贡献。越来越多的人类活动中都有计算机的辅助，高效快速算法的重要性必须随之凸显，因为这是所有自动化处理过程的核心。我们常被迫使用设计不合理的算法和蛮力算法，而这些算法通常都是错误的，会导致错误的科学结论或不当的决策。因此，将算法设计与分析的一些形式化描述引入学校课程中，并给予这门课程与数学和科学教育同等的重视程度，使学生对这门学科有充分认识，这是非常重要的。
读者对象
本书适用于已掌握基本的编程技能以及基本的数据结构知识（如数组、堆栈、列表，甚至平衡树）的学生。基于对这门课程的长期教学经验，我们确信“算法设计”可能是一个看起来很难理解的科目，需要温和细腻的教学方式——这对于理解课程内容和维持学习兴趣都非常重要。在印度理工学院德里分校，计算机科学专业的本科生在学习完一门编程课程后将学习数据结构课程，该课程中包括一些基本的算法技术。本书面向具有这些知识背景的学生，因此我们不会正式地讲解任何基础数据结构——包括基本的图搜索算法，例如深度优先搜索（BFS）和广度优先搜索（DFS），而是侧重于已有知识的数学处理，并凸显对新思想和新技术所进行的简单明了的分析。印度理工学院德里分校计算机科学专业的本科生在学习这门课程之前，已经完成了离散数学和概率课程的学习。高效算法的设计和迅速甄别糟糕算法（无论是算法效率还是正确性方面的不足）的直觉是息息相关的。在本书中，尽管我们时刻强调严谨性，但还是刻意回避了需要漫长枯燥的形式化描述的主题和内容。
将算法设计应用于具体计算环境是非常重要的，这正是本书所追求的一个重要方向。尽管对于在真实计算模型（例如并行模型和高速缓存层次化结构模型）下的算法设计的研究已经有悠久的历史，然而这些研究依然局限于非常理想化的环境及计算能力，以及部分特定的研究生课程的教学环境。目前在一般的基础性教材中，都默认或假定问题的运行环境是对存储器的访问成本一致且支持随机存储的机器(RAM)。然而我们坚信：算法设计不仅仅针对特定的问题，也针对特定的执行模型；如果忽视算法实现所依赖的具体计算环境，那么很多问题和算法将变得不够完整，（实际上）效率也将变得较低。因此，尝试在分布式模型上运行教科书式的数据结构或者在并行计算机上运行Dijkstra算法将会徒劳无功。综上所述，
算法=问题的定义+模型
本书最后3章专门针对3个非常重要的计算环境，即并行计算、层次化存储结构和流数据。它们构成了印度理工学院德里分校“以模型为中心的算法设计”课程的核心内容，而这也可以丰富算法核心课程的多样性。当然，对于任何课程而言，添加新的内容都意味着替换掉其他一些同等课时中同样重要的主题，因此是否使用这些教学材料最终取决于授课教师。
在本书中，另一个被不断提及的方法就是在算法设计中大量使用的随机技术。为了帮助学生理解这一点，我们在第2章中介绍了一些基本工具及应用。即使是精通概率计算的学生（我们希望所有计算机科学专业的学生都学习过一门大学水平的概率课程），也可能会发现书中这些应用实例并不是那么容易理解。不过，对于具有数学化思维方式的学生而言，这种技术也可以转化为非常实用的工具。
过去十年中的另一个主要发展方向是：越来越多地使用代数（特别是“谱”）方法求解组合问题。这使得传统的连续数学更有意义，也更加重要。但即使是对经验丰富的研究者而言，将离散方法和连续方法这两个截然不同的世界进行协调和弥合也是一个巨大的挑战，更何况一个普通的学生。在一本书中完成这一点着实困难，但是我们依然在第13章中对此做出了一些尝试（介绍了“随机投影”技术）。
每章的最后都会对一些问题的历史渊源进行简要讨论，并提供现有的相关文献。书中标有的章节更适合进阶读者，其他读者可以跳过这些内容而不会影响学习的连贯性。
算法课程的主要目标之一是在不牺牲严谨性的前提下鼓励对创造力的欣赏。这一点恰恰使得算法设计成为对人类最具挑战性和吸引力的智力探索之一。
教学建议
本书共16章，可供教师从容地完成两个学期的教学工作，例如可以开设两门“算法”的系列课程。如果作为第一门算法课程（学生具有基本的数据结构知识背景）来讲授，教师可以选择第3~11章的主要内容及第12章的部分内容。而高阶的算法课程可以使用第12~16章中的材料进行教学。第14~16章中的内容可作为“以模型为中心的算法设计”课程的核心内容，该课程可以以更贴近实际应用的方式讲授现代框架下的计算理论。

Sandeep Sen
Amit Kumar
2019年于新德里

计算机\算法

随着大数据和人工智能等领域的发展，算法领域也在不断涌现新概念、新方法和新应用。本书在传统算法技术的基础上融入了对当前新技术方向的讨论，更具现代性和前瞻性。全书内容简洁明快，为每个概念都提供了严格的数学证明，并配有丰富的习题和拓展阅读资料。本书要求读者已掌握基本的数据结构知识和编程技能，适用于将“数据结构”与“算法”分为两门课程的教学。
本书特色
关注新研究和新技术。引入了降维技术、并行算法、随机算法、层次化存储结构算法和流算法等新内容，对传统算法的讲解则采用了大量不同于同类书的新颖示例，从而帮助读者把握技术热点及发展趋势。
强调计算模型和计算环境。不再局限于一致化开销的随机存取机模型，而是考虑真实环境，提出“算法=问题的定义+模型”，并围绕并行计算等重要的计算环境深入讨论了以模型为中心的算法设计。
采用新视角和新方法。充分利用概率分析和随机化技术——当前众多新研究中的关键技术，这是同类书较少涉及的。此外，还在协调和弥合离散方法与连续方法方面做了尝试，以应用代数方法解决数值问题。
作者简介
桑迪普·森（Sandeep Sen） 印度理工学院德里分校计算机科学与工程系教授，印度国家科学院院士，印度科学院院士，研究领域包括随机算法、计算几何、动态图算法和计算模型等。曾在IBM研究实验室、微软研究实验室、北卡罗莱纳大学教堂山分校等机构担任访问研究员。
阿米特·库玛尔（Amit Kumar） 印度理工学院德里分校计算机科学与工程系教授，印度科学院院士，研究领域包括组合优化、调度、图论和聚类等。曾任职于贝尔实验室，并曾在微软印度研究院和IBM印度研究院担任访问教授。曾荣获2018年印度Shanti Swarup Bhtanagar数学科学奖。
译者简介
刘铎　于清华大学计算机科学与技术系获工学博士学位，现为北京交通大学软件学院副教授。主要研究方向为应用密码学、信息安全、组合算法的设计与分析。主持和参与国家级、省部级科研项目多项，以第一作者身份在各类重要刊物和会议上发表论文20余篇，目前主持建设并讲授的“离散数学”课程被评为首批国家级（线上）一流本科课程。

[印]桑迪普·森（Sandeep Sen） 阿米特·库玛尔（Amit Kumar）著：---作者简介---

桑迪普•森（Sandeep Sen） 印度理工学院德里分校计算机科学与工程系教授，印度国家科学院院士，印度科学院院士，研究领域包括随机算法、计算几何、动态图算法和计算模型等。曾在IBM研究实验室、微软研究实验室、北卡罗莱纳大学教堂山分校等机构担任访问研究员。

阿米特•库玛尔（Amit Kumar） 印度理工学院德里分校计算机科学与工程系教授，印度科学院院士，研究领域包括组合优化、调度、图论和聚类等。曾任职于贝尔实验室，并曾在微软印度研究院和IBM印度研究院担任访问教授。曾荣获2018年印度Shanti Swarup Bhtanagar数学科学奖。

---译者简介---
刘铎 于清华大学计算机科学与技术系获工学博士学位，现为北京交通大学软件学院副教授。主要研究方向为应用密码学、信息安全、组合算法的设计与分析。主持和参与国家级、省部级科研项目多项，以第一作者身份在各类重要刊物和会议上发表论文20余篇，目前主持建设并讲授的“离散数学”课程被评为首批国家级（线上）一流本科课程。

算法设计与分析一直是计算机科学技术的核心。伴随着硬件技术的提升和应用场景的扩展，它现在也堪称现代所有信息技术和计算技术的核心。而且，和早期算法研究相比，它已经产生了细微而重要的变化——新概念、新理论、新方法、新应用的不断涌现给它带来了持久的生命力和活力。
本书是关于“算法设计与分析”的一本新作，两位作者都是来自印度理工学院德里分校计算机科学与工程系的著名计算机科学家。他们不仅对算法研究和应用有深刻的见解和前瞻性，而且对于算法教学有丰富的经验。
本书共16章，包括贪婪策略、分治技术、动态规划、网络流、快速傅里叶变换（FFT）等经典策略和技术，具有分析细致、习题丰富、繁简适中等优点。作为一部新作，其更本质性的特点如下：
●简洁明快。本书涉及数据结构的部分较少，不会让读者感到与已经学过的数据结构课程重复，因此比较适合国内大学计算机系/学院或软件学院中“数据结构”与“算法”分为两门课程开设的实际状况。这使得本书篇幅适中、重点集中。
●内容丰富、取材新颖。除了讲授关于算法的大量标准教科书所涵盖的经典策略和技术之外，特别介绍了降维技术、并行算法、随机算法、层次化存储结构算法和流算法/在线算法等非常新颖且活跃的算法研究领域。而且，即使是对于传统算法设计策略和技巧等内容，本书也都尽量采用了与目前一些经典和流行的算法教科书所不同的示例。
●强调计算模型。与通常在一致化开销的随机存取机模型中介绍和分析传统算法不同，本书强调底层计算环境在算法设计中的重要作用，特别指出：算法设计不仅仅针对特定的问题，也针对特定的计算模型。此外，本书还专门针对3个非常重要的计算环境，即并行计算、层次化存储结构和流模型，进行了关于算法设计与分析的探讨。
●大量使用概率分析和随机技术，它们是算法领域很多新进展中的关键技术，也是近来算法研究中发展迅猛的方向，但事实上这也恰恰是现有很多有关算法的教材没有给予足够重视的方面。
●在第4章和第13章中，在将离散方法和连续方法进行协调和弥合以解决实际应用和数值问题方面做出了一些尝试，这也是本书的重要特色之一。
本书第3章由李令昆翻译，其余内容主要由刘铎翻译，并由刘铎审阅全书。对于发现的原书中的错误，我们已做了适当修正和说明。
特别感谢机械工业出版社曲熠编辑对本书翻译工作的支持与帮助。
由于译者水平有限，翻译中难免有疏漏与错误之处，恳请读者批评指正。

译者
2021年2月
于北京市百万庄

出版者的话
译者序
前言
致谢
第1章　模型与分析1
　1.1　计算斐波那契数1
　1.2　快速乘法3
　1.3　计算模型3
　1.4　随机算法简介4
　　1.4.1　另一种随机算法6
　1.5　其他计算模型8
　　1.5.1　外部存储器模型8
　　1.5.2　并行模型8
　拓展阅读10
　习题10
第2章　概率基础与尾部不等式13
　2.1　概率基础13
　2.2　尾部不等式17
　2.3　生成随机数20
　　2.3.1　生成具有任意分布的随机变量21
　　2.3.2　由顺序文件生成随机变量21
　　2.3.3　生成随机置换23
　拓展阅读25
　习题25
第3章　热身问题27
　3.1　计算最大公因子的欧几里得算法27
　　3.1.1　扩展欧几里得算法27
　　3.1.2　在密码学中的应用28
　3.2　寻找第k小的元素28
　　3.2.1　选择随机的划分元29
　　3.2.2　中位数的中位数30
　3.3　词的排序32
　3.4　可归并的堆34
　　3.4.1　归并二项堆35
　3.5　一个简单的半动态词典35
　　3.5.1　势能法与平摊分析36
　3.6　下界37
　拓展阅读39
　习题39
第4章　优化Ⅰ：蛮力法与贪婪策略42
　4.1　启发式搜索方法42
　　4.1.1　博弈树44
　4.2　贪婪算法的框架46
　　4.2.1　最大支撑树49
　　4.2.2　寻找最小权值子集49
　　4.2.3　一个调度问题50
　4.3　最小支撑树算法的高效数据结构51
　　4.3.1　并查集的一种简单数据结构52
　　4.3.2　更快的方案53
　　4.3.3　增长最慢的函数54
　　4.3.4　整合55
　　4.3.5　仅做道路压缩56
　4.4　其他不同形式的贪婪策略57
　4.5　与贪婪策略的折中58
　4.6　梯度下降59
　　4.6.1　应用63
　拓展阅读65
　习题66
第5章　优化Ⅱ：动态规划69
　5.1　背包问题70
　5.2　上下文无关文法的解析71
　5.3　最长单调子序列72
　5.4　函数逼近74
　5.5　最大似然估计的Viterbi算法75
　5.6　树中的最大权独立集76
　拓展阅读76
　习题77
第6章　查找80
　6.1　跳表——一个简单的字典80
　　6.1.1　跳表的构造80
　　6.1.2　分析81
　　6.1.3　更强的尾部估计82
　6.2　树堆：随机查找树83
　6.3　全域哈希86
　　6.3.1　全域哈希函数的存在性88
　6.4　完美哈希函数88
　　6.4.1　将期望界转换为最差情况的界89
　6.5　一个复杂度为log log N的优先级队列89
　拓展阅读91
　习题92
第7章　多维查找与几何算法94
　7.1　区间树与范围树94
　　7.1.1　一维范围查找94
　　7.1.2　二维范围查找96
　7.2　kd树97
　7.3　优先级查找树99
　7.4　平面凸包101
　　7.4.1　Jarvis March算法102
　　7.4.2　Graham扫描算法102
　　7.4.3　排序与凸包103
　7.5　快速凸包算法104
　　7.5.1　分析105
　　7.5.2　期望运行时间106
　7.6　使用持久化数据结构的点定位107
　7.7　增量构造法109
　拓展阅读111
　习题111
第8章　字符串匹配与指纹函数114
　8.1　RabinKarp指纹字符串查找算法114
　8.2　KMP算法117
　　8.2.1　KMP算法的分析120
　　8.2.2　模式分析120
　8.3　字典树及其应用121
　拓展阅读123
　习题123
第9章　快速傅里叶变换及其应用125
　9.1　多项式求值与插值125
　　9.1.1　多项式相乘126
　9.2　CooleyTukey算法126
　9.3　蝶形网络128
　9.4　SchonageStrassen快速乘法算法129
　9.5　广义字符串匹配131
　　9.5.1　基于卷积的方法131
　拓展阅读133
　习题133
第10章　图算法135
　10.1　深度优先搜索135
　10.2　深度优先搜索的应用138
　　10.2.1　强连通分支138
　　10.2.2　双连通分支140
　10.3　道路问题142
　　10.3.1　BellmanFord单源最短道路算法143
　　10.3.2　Dijkstra单源最短道路算法143
　　10.3.3　任意两点之间的最短道路算法145
　10.4　计算赋权图中的支撑子145
　10.5　全局最小割148
　　10.5.1　收缩算法149
　　10.5.2　最小割的概率149
　拓展阅读150
　习题151
第11章　最大流及其应用153
　11.1　最大流的性质与算法155
　　11.1.1　最大流与最小割155
　　11.1.2　FordFulkerson算法156
　　11.1.3　EdmondKarp可增广道路策略157
　　11.1.4　单调性引理及迭代次数的界158
　11.2　最大流的应用159
　　11.2.1　边不相交的道路159
　　11.2.2　二部图的匹配159
　　11.2.3　环流问题162
　　11.2.4　项目规划164
　拓展阅读165
　习题165
第12章　NP完全性与近似算法168
　12.1　分类与可归约性170
　12.2　CookLevin定理172
　12.3　常见的NP完全问题173
　12.4　NP完全性的证明175
　　12.4.1　顶点覆盖及相关问题175
　　12.4.2　图的3着色问题176
　　12.4.3　背包问题及相关问题177
　12.5　其他重要的复杂度类179
　12.6　使用近似算法处理困难性181
　　12.6.1　最大背包问题182
　　12.6.2　最小集合覆盖183
　　12.6.3　几何旅行商问题184
　　12.6.4　3着色问题185
　　12.6.5　最大割问题185
　拓展阅读186
　习题186
第13章　降维188
　13.1　随机投影与JohnsonLindenstrauss引理188
　13.2　高斯消元法191
　13.3　奇异值分解及其应用192
　　13.3.1　矩阵代数与SVD定理192
　　13.3.2　使用SVD的低秩近似194
　　13.3.3　低秩近似的应用196
　　13.3.4　聚类问题197
　　13.3.5　SVD定理的证明199
　拓展阅读200
　习题200
第14章　并行算法201
　14.1　并行计算模型201
　14.2　排序和比较问题202
　　14.2.1　寻找最大值202
　　14.2.2　排序204
　14.3　并行前缀208
　14.4　基本的图算法212
　　14.4.1　列表排名212
　　14.4.2　连通分支214
　14.5　基本的几何算法216
　14.6　并行模型之间的关系217
　　14.6.1　网格上的路由218
　拓展阅读220
　习题220
第15章　层次化存储结构及高速缓存223
　15.1　层次化存储模型223
　15.2　矩阵转置224
　　15.2.1　矩阵乘法225
　15.3　在外部存储器中进行排序226
　　15.3.1　我们可以改进这个算法吗227
　15.4　高速缓存参数无关的算法设计228
　　15.4.1　参数无关的矩阵转置229
　拓展阅读231
　习题232
第16章　流数据模型233
　16.1　引言233
　16.2　查找流中的频繁元素233
　16.3　流中的相异元素236
　16.4　频数矩问题及其应用238
　　16.4.1　均值的中位数241
　　16.4.2　二阶频数矩的特例241
　16.5　流模型下界的证明243
　拓展阅读244
　习题245
附录A　递推关系与生成函数247
参考文献253