第1章 预备知识1
1.1 简介1
1.2 什么是算法1
1.3 程序符号4
1.4 数学符号5
1.4.1 命题演算5
1.4.2 集合论6
1.4.3 整数、实数和区间7
1.4.4 函数和关系7
1.4.5 量词8
1.4.6 累加与累积9
1.4.7 杂项10
1.5 证明技巧1——反证法11
1.6 证明技巧2——数学归纳法12
1.6.1 数学归纳法的法则15
1.6.2 不同颜色的马18
1.6.3 一般化的数学归纳法19
1.6.4 构造性归纳22
1.7 一些回顾24
1.7.1 极限24
1.7.2 简单级数26
1.7.3 基本组合30
1.7.4 概率基础32
1.8 习题38
1.9 参考与深入阅读43
第2章 基本算法45
2.1 简介45
2.2 问题和实例45
2.3 算法的效率46
2.4 平均和最坏情况分析48
2.5 什么是基本运算？50
2.6 为什么寻求效率？52
2.7 一些例子53
2.7.1 计算行列式的值53
2.7.2 排序53
2.7.3 大整数的乘法55
2.7.4 计算最大公约数55
2.7.5 计算斐波纳契序列56
2.7.6 傅立叶变换57
2.8 什么时候算法是确定的？58
2.9 习题58
2.10 参考与深入阅读61
第3章 渐近记法62
3.1 引言62
3.2 同阶记法62
3.3 其他渐近记法67
3.3.1 Ω记法67
3.3.2 Θ记法68
3.4 条件渐近记法69
3.5 具有多个参数的渐近记法71
3.6 渐近记法的操作71
3.7 习题72
3.8 参考与深入阅读75
第4章 算法分析76
4.1 引言76
4.2 分析控制结构76
4.2.1 先后顺序76
4.2.2 For循环76
4.2.3 递归调用78
4.2.4 while和repeat循环79
4.3 使用标称80
4.4 补充例子82
4.4.1 选择排序82
4.4.2 插入排序83
4.4.3 欧几里德算法83
4.4.4 汉诺塔85
4.4.5 计算行列式的值86
4.5 平均情况分析86
4.6 分期分析87
4.6.1 势函数88
4.6.2 账户戏法90
4.7 求解递归式90
4.7.1 推测90
4.7.2 齐次递归式92
4.7.3 非齐次递归式96
4.7.4 变量变换100
4.7.5 范围转换105
4.7.6 渐近递归式106
4.8 习题107
4.9 参考与深入阅读113
第5章 一些数据结构114
5.1 数组、栈和队列114
5.2 记录和指针116
5.3 链表117
5.4 图118
5.5 树119
5.6 关联表124
5.7 堆126
5.8 二项堆132
5.9 不相交集结构136
5.10 习题141
5.11 参考与深入阅读144
第6章 贪婪算法146
6.1 找零钱(1)146
6.2 贪婪算法的一般特性147
6.3 图：最小生成树148
6.3.1 Kruskal算法150
6.3.2 Prim算法152
6.4 图：最短路径154
6.5 背包问题(1)157
6.6 日程安排160
6.6.1 最小化时间160
6.6.2 有期限的日程安排162
6.7 习题168
6.8 参考与深入阅读170
第7章 分治算法171
7.1 简介：大整数乘法171
7.2 通用模板174
7.3 二分搜索176
7.4 排序178
7.4.1 归并排序178
7.4.2 快速排序180
7.5 查找中值184
7.6 矩阵乘法188
7.7 求幂189
7.8 综合：密码学简介192
7.9 习题194
7.10 参考与深入阅读200
第8章 动态规划202
8.1 两个简单的例子202
8.1.1 计算二项式系数202
8.1.2 系列赛203
8.2 找零钱(2)205
8.3 最优性原则207
8.4 背包问题(2)208
8.5 最短路径209
8.6 链式矩阵乘法211
8.7 使用递归214
8.8 存储函数216
8.9 习题217
8.10 参考与深入阅读221
第9章 搜索图223
9.1 图和游戏：简介223
9.2 遍历树228
9.2.1 预处理228
9.3 深度优先搜索：无向图230
9.3.1 关节点232
9.4 深度优先搜索：有向图233
9.4.1 无环图：拓扑排序234
9.5 广度优先搜索236
9.6 回溯法239
9.6.1 背包问题(3)240
9.6.2 八皇后问题242
9.6.3 通用模板244
9.7 分支界限244
9.7.1 分配任务问题245
9.7.2 背包问题(4)248
9.7.3 一般考虑248
9.8 极小化原则248
9.9 习题251
9.10 参考与深入阅读256
第10章 概率算法257
10.1 简介257
10.2 概率不意味着不确定258
10.3 预期与平均时间259
10.4 生成伪随机数259
10.5 数值概率算法261
10.5.1 Buffon的针261
10.5.2 数值积分264
10.5.3 概率计数265
10.6 Monte Carlo算法267
10.6.1 验证矩阵乘法267
10.6.2 素数性测试269
10.6.3 一个数可能是素数吗？272
10.6.4 随机优势的扩大274
10.7 Las Vegas算法276
10.7.1 重访八皇后问题278
10.7.2 概率选择与排序281
10.7.3 通用散列282
10.7.4 大整数分解因数284
10.8 习题287
10.9 参考与深入阅读293
第11章 并行算法295
11.1 并行计算的模型295
11.2 一些基本的技术297
11.2.1 计算完全二叉树297
11.2.2 指针倍增298
11.3 工作量与效率301
11.4 图论的两个例子303
11.4.1 最短路径303
11.4.2 连通分量304
11.5 表达式的并行求值308
11.6 并行排序网络312
11.6.1 0-1原理313
11.6.2 并行合并网络314
11.6.3 改进的排序网络315
11.7 并行排序316
11.7.1 预备工作316
11.7.2 核心思想317
11.7.3 算法317
11.7.4 细节概述318
11.8 EREW和CRCW p-ram的一些注意点319
11.9 分布式计算320
11.10 习题321
11.11 参考与深入阅读323
第12章 计算复杂性324
12.1 引言：一个简单的例子324
12.2 信息理论论证325
12.2.1 排序的复杂性327
12.2.2 复杂性对算法设计的帮助330
12.3 对手论证331
12.3.1 查找数组的最大项332
12.3.2 测试图的连通性333
12.3.3 中值再考察333
12.4 线性归约335
12.4.1 形式定义337
12.4.2 矩阵问题中的归约338
12.4.3 最短路径问题中的归约342
12.5 NP完全性介绍344
12.5.1 P和NP类345
12.5.2 多项式归约348
12.5.3 NP完全性问题351
12.5.4 一些NP完全性证明353
12.5.5 NP难问题356
12.5.6 非确定性算法357
12.6 复杂性类纵览359
12.7 习题362
12.8 参考与深入阅读366
第13章 启发式和近似算法369
13.1 启发式算法369
13.1.1 图着色369
13.1.2 旅行商371
13.2 近似算法372
13.2.1 度量旅行商372
13.2.2 背包问题（5）374
13.2.3 装箱问题375
13.3 NP难近似问题377
13.3.1 绝对难近似问题378
13.3.2 相对难近似问题379
13.4 相同，惟一不同380
13.5 近似模式383
13.5.1 重访装箱问题383
13.5.2 背包问题（6）384
13.6 习题386
13.7 参考与深入阅读389
参考文献390
鄂公网安备 42010302001612号 