算法设计与分析——C++语言描述 第3版

第1部分算法和算法分析
第1章算法问题求解基础1
1.1算法概述1
1.1.1什么是算法1
1.1.2为什么学习算法3
1.2问题求解方法3
1.2.1问题和问题求解4
1.2.2问题求解过程4
1.2.3系统生命周期5
1.3算法设计与分析5
1.3.1算法问题求解过程5
1.3.2如何设计算法6
1.3.3如何表示算法6
1.3.4如何确认算法6
1.3.5如何分析算法7
1.4递归和归纳7
1.4.1递归7
1.4.2递归算法示例9
1.4.3归纳证明11
本章小结12
习题113
第2章算法分析基础14
2.1算法复杂度14
2.1.1什么是好的算法14
2.1.2影响程序运行时间的因素15
2.1.3算法的时间复杂度16
2.1.4使用程序步分析算法17
2.1.5算法的空间复杂度18
2.2渐近表示法19
2.2.1大O记号19
2.2.2?记号20
2.2.3?记号21
2.2.4小o记号21
2.2.5算法按时间复杂度分类21
2.3递推关系22
2.3.1递推方程22
2.3.2替换方法23
2.3.3迭代方法23
2.3.4主方法24
2.4分摊分析25
2.4.1聚集方法26
2.4.2会计方法26
2.4.3势能方法27
本章小结28
习题228
第3章伸展树与跳表30
3.1伸展树30
3.1.1二叉搜索树30
3.1.2自调节树和伸展树30
3.1.3伸展操作31
3.1.4伸展树类32
3.1.5旋转的实现34
3.1.6插入运算的实现34
3.1.7分摊分析36
3.2跳表38
3.2.1什么是跳表38
3.2.2跳表类39
3.2.3级数分配41
3.2.4插入运算的实现42
3.2.5性能分析43
本章小结44
习题344
第2部分算法设计策略
第4章基本搜索和遍历方法45
4.1基本概念45
4.2图的搜索和遍历46
4.2.1搜索方法46
4.2.2邻接表类47
4.2.3广度优先搜索48
4.2.4深度优先搜索50
4.3双连通分量53
4.3.1基本概念53
4.3.2发现关节点54
4.3.3构造双连通图57
4.4与或图58
4.4.1问题分解58
4.4.2判断与或树是否可解59
4.4.3构建解树61
本章小结62
习题462
第5章分治法64
5.1一般方法64
5.1.1分治法的基本思想64
5.1.2算法分析65
5.1.3数据结构66
5.2求优选最小元67
5.2.1分治法求解67
5.2.2时间分析68
5.3二分搜索69
5.3.1分治法求解69
5.3.2对半搜索70
5.3.3二叉判定树71
5.3.4搜索算法的时间下界73
5.4排序问题74
5.4.1合并排序74
5.4.2快速排序76
5.4.3排序算法的时间下界80
5.5选择问题82
5.5.1分治法求解82
5.5.2随机选择主元82
5.5.3线性时间选择算法84
5.5.4时间分析86
5.5.5允许重复元素的选择算法86
5.6斯特拉森矩阵乘法87
5.6.1分治法求解87
5.6.2斯特拉森分治法88
本章小结88
习题588
第6章贪心法91
6.1一般方法91
6.2背包问题92
6.2.1问题描述92
6.2.2贪心法求解92
6.2.3算法正确性94
6.3带时限的作业排序95
6.3.1问题描述95
6.3.2贪心法求解95
6.3.3算法正确性97
6.3.4可行性判定97
6.3.5作业排序贪心算法98
6.3.6一种改进算法99
6.4很好合并模式102
6.4.1问题描述102
6.4.2贪心法求解103
6.4.3算法正确性104
6.5最小代价生成树105
6.5.1问题描述105
6.5.2贪心法求解105
6.5.3普里姆算法106
6.5.4克鲁斯卡尔算法109
6.5.5算法正确性111
6.6单源最短路径111
6.6.1问题描述112
6.6.2贪心法求解112
6.6.3迪杰斯特拉算法112
6.6.4算法正确性115
6.7磁带很优存储116
6.7.1单带很优存储116
6.7.2多带很优存储117
6.8贪心法的基本要素119
6.8.1很优量度标准119
6.8.2很优子结构119
本章小结120
习题6120
第7章动态规划法122
7.1一般方法和基本要素122
7.1.1一般方法122
7.1.2基本要素123
7.1.3多段图问题123
7.1.4资源分配问题126
7.1.5关键路径问题127
7.2每对结点间的最短路径129
7.2.1问题描述129
7.2.2动态规划法求解130
7.2.3弗洛伊德算法131
7.2.4算法正确性132
7.3矩阵连乘132
7.3.1问题描述132
7.3.2动态规划法求解133
7.3.3矩阵连乘算法134
7.3.4备忘录方法136
7.4最长公共子序列137
7.4.1问题描述137
7.4.2动态规划法求解137
7.4.3最长公共子序列算法138
7.4.4算法的改进140
7.5很优二叉搜索树140
7.5.1问题描述140
7.5.2动态规划法求解141
7.5.3很优二叉搜索树算法143
7.60/1背包144
7.6.1问题描述144
7.6.2动态规划法求解145
7.6.30/1背包算法框架147
7.6.40/1背包算法150
7.6.5性能分析152
7.6.6使用启发式方法153
7.7流水作业调度154
7.7.1问题描述154
7.7.2动态规划法求解155
7.7.3Johnson算法157
本章小结158
习题7158
第8章回溯法160
8.1一般方法160
8.1.1基本概念160
8.1.2剪枝函数和回溯法161
8.1.3回溯法的效率分析163
8.2n-皇后163
8.2.1问题描述163
8.2.2回溯法求解164
8.2.3n-皇后算法165
8.2.4时间分析166
8.3子集和数167
8.3.1问题描述167
8.3.2回溯法求解167
8.3.3子集和数算法168
8.4图的着色170
8.4.1问题描述170
8.4.2回溯法求解170
8.4.3图着色算法171
8.4.4时间分析172
8.5哈密顿环172
8.5.1问题描述172
8.5.2哈密顿环算法173
8.60/1背包174
8.6.1问题描述174
8.6.2回溯法求解174
8.6.3限界函数175
8.6.40/1背包算法176
8.7批处理作业调度178
8.7.1问题描述178
8.7.2回溯法求解178
8.7.3批处理作业调度算法178
本章小结180
习题8180
第9章分枝限界法182
9.1一般方法182
9.1.1分枝限界法概述182
9.1.2LC分枝限界法184
9.1.315谜问题185
9.2求很优解的分枝限界法187
9.2.1上下界函数187
9.2.2FIFO分枝限界法188
9.2.3LC分枝限界法189
9.3带时限的作业排序190
9.3.1问题描述190
9.3.2分枝限界法求解190
9.3.3带时限作业排序算法191
9.40/1背包193
9.4.1问题描述193
9.4.2分枝限界法求解194
9.4.30/1背包算法195
9.5旅行商问题197
9.5.1问题描述197
9.5.2分枝限界法求解198
9.6批处理作业调度201
9.6.1问题描述201
9.6.2分枝限界法求解201
9.6.3批处理作业调度算法202
本章小结205
习题9205
第3部分求解困难问题
第10章NP接近问题207
10.1基本概念207
10.1.1不确定算法和不确定机208
10.1.2可满足性问题210
10.1.3P类和NP类问题211
10.1.4NP难度和NP接近问题211
10.2Cook定理和证明212
10.2.1Cook定理212
10.2.2简化的不确定机模型212
10.2.3证明Cook定理214
10.3一些典型的NP接近问题217
10.3.1优选集团217
10.3.2顶点覆盖218
10.3.3三元CNF可满足性219
10.3.4图的着色数220
10.3.5有向哈密顿环221
10.3.6恰切覆盖223
10.3.7子集和数225
10.3.8分划问题225
本章小结226
习题10226
第11章随机算法228
11.1基本概念228
11.1.1随机算法概述228
11.1.2随机数发生器228
11.1.3随机算法分类228
11.2拉斯维加斯算法229
11.2.1标识重复元素算法229
11.2.2性能分析230
11.3蒙特卡罗算法231
11.3.1素数测试问题231
11.3.2伪素数测试231
11.3.3米勒-拉宾算法232
11.3.4性能分析233
11.4舍伍德算法234
11.4.1随机快速排序算法234
11.4.2舍伍德算法的其他应用234
本章小结234
习题11235
第12章近似算法236
12.1近似算法的性能236
12.1.1基本概念236
12.1.2绝对性能保证236
12.1.3相对性能保证237
12.1.4近似方案238
12.2绝对近似算法238
12.2.1最多程序存储问题238
12.2.2NP难度绝对近似算法239
12.3?-近似算法240
12.3.1顶点覆盖近似算法240
12.3.2旅行商问题241
12.3.3NP难度?-近似旅行商问题242
12.3.4具有三角不等式性质的旅行商问题243
12.3.5任务调度近似算法244
12.4?(n)-近似算法247
12.4.1集合覆盖问题247
12.4.2集合覆盖近似算法247
12.4.3ln(n)-近似算法248
12.5多项式时间近似方案249
12.5.1任务调度近似方案249
12.5.2多项式时间近似方案251
12.6子集和数的接近多项式时间近似方案251
12.6.1子集和数的指数时间算法251
12.6.2接近多项式时间近似方案252
本章小结254
习题12254
第13章遗传算法256
13.1进化计算256
13.2遗传算法的生物学基础257
13.3遗传算法的基本思想258
13.4基本遗传算法259
13.4.1基本遗传算法构成要素259
13.4.2基本遗传算法流程图262
13.5遗传算法的特点和应用262
13.5.1遗传算法的特点262
13.5.2遗传算法的应用263
13.6基本遗传算法实现方法263
13.6.1数据结构263
13.6.2主程序264
13.6.3选择运算264
13.6.4交叉运算266
13.6.5变异运算267
13.7旅行商问题268
13.7.1排列编码268
13.7.2目标函数和适应度函数269
13.7.3锦标赛选择269
13.7.4顺序交叉269
13.7.5交换变异271
13.7.6参数选择272
13.7.7实例运行结果272
本章小结272
习题13272
第14章密码算法274
14.1信息安全和密码学274
14.1.1信息安全274
14.1.2什么是密码274
14.1.3密码体制275
14.2数论初步276
14.3背包密码算法277
14.3.1背包算法277
14.3.2超递增背包278
14.3.3由私人密钥产生公开密钥279
14.3.4加密方法279
14.3.5解密方法279
14.3.6背包安全性280
14.4RSA算法280
14.4.1RSA算法概述280
14.4.2RSA的安全性281
14.5散列函数和消息认证282
14.5.1散列函数282
14.5.2散列函数结构282
14.5.3消息认证283
14.6数字签名283
14.6.1RSA数字签名体制283
14.6.2需仲裁的数字签名284
本章小结284
习题14284
附录A专有名词中英文对照表285
附录BC++程序设计概要290
参考文献304