算法导论（扩展篇）（原书第4版） / 计算机科学丛书
定价：￥99.00
作者： [美]托马斯·H. 科尔曼（Thomas H. Cormen） [美]查尔斯·E. 雷瑟尔森（Charles E. Leiserson） [美]罗纳德·L. 李维斯特（Ronald L. Rivest） [美]克利福德·斯坦（Clifford Stein）
出版时间：2026-05-29
出版社：机械工业出版社
- 机械工业出版社
- 9787111800125
- 1-1
- 2026-05-29
- 561
内容简介
《算法导论（原书第4版）》以高度的严谨性与全面的覆盖性著称，深入阐述计算机算法设计与分析的各个重要领域。从排序和顺序统计量、数据结构、图算法等经典内容，到动态规划、贪心算法、摊还算法等高级设计和分析技术，再到NP完全性理论与近似算法等前沿课题，全书体系完整，条理清晰。各章自成体系，均可作为独立的学习单元；算法以伪代码形式呈现，说明与解释力求深入浅出而不失数学严谨性，具备基础程序设计经验的读者即可理解。
本书适合计算机及相关专业本科生、研究生作为教材使用，亦是软件工程师、算法工程师、数据科学家、研究人员，以及所有希望夯实算法基础、提升编程内功的开发人员案头必备的参考书。
本书是《算法导论（原书第4版）》的扩展篇（第26~35章），包含一些选编的算法问题。
本书适合计算机及相关专业本科生、研究生作为教材使用，亦是软件工程师、算法工程师、数据科学家、研究人员，以及所有希望夯实算法基础、提升编程内功的开发人员案头必备的参考书。
本书是《算法导论（原书第4版）》的扩展篇（第26~35章），包含一些选编的算法问题。
目录
目 录
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
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
