《算法导论（原书第4版）》以高度的严谨性与全面的覆盖性著称，深入阐述计算机算法设计与分析的各个重要领域。从排序和顺序统计量、数据结构、图算法等经典内容，到动态规划、贪心算法、摊还算法等高级设计和分析技术，再到NP完全性理论与近似算法等前沿课题，全书体系完整，条理清晰。各章自成体系，均可作为独立的学习单元；算法以伪代码形式呈现，说明与解释力求深入浅出而不失数学严谨性，具备基础程序设计经验的读者即可理解。 本书适合计算机及相关专业本科生、研究生作为教材使用，亦是软件工程师、算法工程师、数据科学家、研究人员，以及所有希望夯实算法基础、提升编程内功的开发人员案头必备的参考书。 本书是《算法导论（原书第4版）》的扩展篇（第26~35章），包含一些选编的算法问题。

托马斯·H. 科尔曼（Thomas H. Cormen），达特茅斯学院计算机科学系荣休教授、系主任。他的研究兴趣包括算法工程、并行计算、具有高延迟的加速计算。他分别于1993年、1986年获得麻省理工学院电子工程和计算机科学博士、硕士学位。由于他在计算机教育领域的突出贡献，Cormen教授荣获2009年ACM杰出教员奖。
查尔斯·E. 雷瑟尔森（Charles E. Leiserson），麻省理工学院计算机科学与电气工程系教授。他曾担任MIT计算机科学与人工智能实验室副主任兼首席运营官，并主持计算理论研究组。他的研究兴趣集中在并行和分布式计算，尤其是与工程实践相关的理论研究。Leiserson教授还是ACM、IEEE和SIAM的会士。
罗纳德·L. 李维斯特（Ronald L. Rivest），麻省理工学院电子工程和计算机科学系教授。他是MIT计算机科学与人工智能实验室的成员，同时也是实验室密码学与信息安全组的创始人。他以在密码学领域的研究而闻名，在算法与组合学、机器学习及选举完整性等多个领域也做出了重要贡献。他和Adi Shamir与Leonard M. Adleman共同发明了RSA公钥算法，并因此荣获2002年图灵奖。他还是对称密钥加密算法RC2、RC4、RC5的发明者，以及RC6的共同发明者。
克利福德·斯坦（Clifford Stein），哥伦比亚大学计算机科学系教授、工业工程与运筹学系教授兼系主任。他的研究兴趣包括算法设计与分析、组合优化、运筹学、网络算法、调度、算法工程和生物计算。Stein教授曾担任ACM Transactions on Algorithms, Mathematical Programming, Journal of Algorithms, SIAM Journal on Discrete Mathematics 等期刊的编委。

目　　录
Introduction to Algorithms, Fourth Edition



译者序
前言

第七部分　算法问题选编
第26章　并行算法　　3
26.1　fork-join并行基础　　4
26.2　并行矩阵乘法　　17
26.3　并行归并排序　　20
思考题　　26
本章注记　　29
第27章　在线算法　　31
27.1　等待电梯　　31
27.2　维护搜索链表　　33
27.3　在线缓存　　38
27.3.1　确定性缓存算法　　38
27.3.2　随机化缓存算法　　41
思考题　　46
本章注记　　47
第28章　矩阵运算　　49
28.1　求解线性方程组　　49
28.2　矩阵求逆　　59
28.3　对称正定矩阵和最小二乘
逼近　　62
思考题　　68
本章注记　　69
第29章　线性规划　　70
29.1　线性规划的形式化和算法　　72
29.2　将问题形式化为线性规划　　76
29.3　对偶性　　80
思考题　　85
本章注记　　86
第30章　多项式与离散傅里叶
变换　　87
30.1　多项式的表示　　88
30.2　DFT与FFT　　92
30.3　FFT电路　　98
思考题　　101
本章注记　　103
第31章　数论算法　　104
31.1　基础数论概念　　104
31.2　最大公约数　　108
31.3　模运算　　112
31.4　求解模线性方程　　117
31.5　中国剩余定理　　120
31.6　元素的幂　　122
31.7　RSA公钥密码系统　　125
31.8　素性测试　　129
思考题　　136
本章注记　　137
第32章　字符串匹配　　139
32.1　朴素字符串匹配算法　　141
32.2　Rabin-Karp算法　　142
32.3　采用有限自动机进行字符串
匹配　　146
32.4　Knuth-Morris-Pratt算法　　151
32.5　后缀数组　　158
思考题　　165
本章注记　　169
第33章　机器学习算法　　170
33.1　聚类　　171
33.2　乘法权重算法　　178
33.3　梯度下降　　182
思考题　　193
本章注记　　195
第34章　NP完全性　　196
34.1　多项式时间　　199
34.2　多项式时间的验证　　204
34.3　NP完全性与可归约性　　207
34.4　NP完全性的证明　　214
34.5　NP完全问题　　220
34.5.1　团问题　　220
34.5.2　顶点覆盖问题　　222
34.5.3　哈密顿回路问题　　223
34.5.4　旅行商问题　　227
34.5.5　子集和问题　　228
34.5.6　归约策略　　230
思考题　　232
本章注记　　234
第35章　近似算法　　235
35.1　顶点覆盖问题　　236
35.2　旅行商问题　　238
35.2.1　满足三角不等式的旅行商
问题　　239
35.2.2　一般旅行商问题　　240
35.3　集合覆盖问题　　242
35.4　随机化和线性规划　　244
35.5　子集和问题　　247
思考题　　252
本章注记　　254
附录　数学基础知识
附录A　求和　　256
附录B　集合等离散数学内容　　265
附录C　计数与概率　　281
附录D　矩阵　　304
参考文献　　312