第1章 算法概述 1
1.1 算法概念 1
1.1.1 什么是算法 1
1.1.2 抽象表达算法机制 2
1.2 算法的复杂度 4
1.2.1 算法三性态 4
1.2.2 算法复杂度 5
1.3 算法设计与分析的步骤 12
1.3.1 利用算法进行问题求解的过程 12
1.3.2 如何设计算法 13
1.3.3 如何表示算法 14
1.3.4 如何确认算法 14
1.3.5 如何分析算法 14
1.4 算法描述语言简介 16
1.4.1 C语言中的标准数据类型 16
1.4.2 C语言中的运算符 17
1.4.3 C语言中的语句简介 18
小结 20
习题一 20
一、选择题 20
二、填空题 21
三、简答题 22
四、计算题 22
五、上机题 23
第2章 递归技术 24
2.1 递归技术概述 24
2.1.1 什么是递归技术 24
2.1.2 递归技术的基本思想 26
2.2 Hanoi塔问题 27
2.3 递归方程的建立与求解 28
2.3.1 递推法 29
2.3.2 生成函数法 30
2.3.3 特征方程法 31
2.3.4 数学归纳法 32
2.3.5 不规则解法 33
2.4 递归消除 33
2.4.1 简单递归消除 34
2.4.2 基于栈的递归消除 36
小结 38
习题二 38
一、选择题 38
二、填空题 38
三、简答题 38
四、计算题 38
五、上机题 39
第3章 分治法 40
3.1 分治法概述 40
3.1.1 什么是分治法 40
3.1.2 分治法的基本思想 41
3.1.3 分治法的基本要素 41
3.2 二分检索技术 41
3.2.1 二分检索算法描述 42
3.2.2 最坏情况分析 42
3.2.3 平均复杂度分析 44
3.2.4 以比较为基础的检索时间下界 45
3.3 找第K小元素 47
3.3.1 分划点m的选取 47
3.3.2 随机选择算法 49
3.4 分治乘法 50
3.4.1 大整数相乘 50
3.4.2 多项式乘法 51
3.4.3 矩阵乘法 58
3.5 棋盘覆盖 59
3.6 分治合并排序 61
3.6.1 什么是合并 62
3.6.2 合并排序的基本思想 62
3.6.3 二路合并排序算法 63
3.7 分治快速排序 65
3.7.1 快速排序的基本思想 65
3.7.2 示例 67
3.8 常见分治 68
3.8.1 快速傅立叶变换 68
3.8.2 傅立叶变换的逆变换 70
3.8.3 利用傅立叶理论求解多项式相乘 71
小结 72
习题三 72
一、选择题 72
二、填空题 72
三、简答题 72
四、计算题 72
五、上机题 73
第4章 贪心法 74
4.1 贪心算法概述 74
4.1.1 什么是贪心法 74
4.1.2 贪心法的基本思想 75
4.1.3 贪心法基本要素 75
4.2 背包问题 77
4.3 磁带存储 81
4.3.1 单磁带最优存储 81
4.3.2 多磁带最优存储 83
4.4 作业调度 84
4.4.1 顺序选择法 85
4.4.2 最大期限选择法 86
4.5 启发式算法 88
4.6 贪心法的理论基础 91
4.6.1 拟阵 91
4.6.2 带权拟阵的贪心算法 92
4.6.3 任务时间表问题 94
4.7 常见贪心算法问题 97
4.7.1 最优装载 97
4.7.2 哈夫曼编码 99
4.7.3 单源最短路径 100
4.7.4 最小生成树 101
小结 103
习题四 104
一、选择题 104
二、填空题 104
三、简答题 104
四、计算题 104
五、上机题 105
第5章 动态规划 106
5.1 动态规划概述 106
5.1.1 什么是动态规划 106
5.1.2 动态规划的基本思想 106
5.1.3 动态规划的基本要素 108
5.2 最短路径 109
5.3 0/1背包问题 112
5.4 多矩阵乘积 120
5.5 货郎担问题 125
5.6 资源分配 127
小结 130
习题五 130
一、选择题 130
二、填空题 130
三、简答题 131
四、计算题 131
五、上机题 131
第6章 回溯法 132
6.1 概述 132
6.1.1 什么是回溯法 132
6.1.2 回溯法的基本思想 133
6.1.3 回溯法的算法框架与符号 133
6.2 n-皇后问题 135
6.3 图的m着色问题 140
6.3.1 图m着色问题的回溯法求解 140
6.3.2 图m着色问题的递归回溯算法 140
6.4 批处理作业调度问题 141
6.5 其他常见回溯法问题 142
6.5.1 最大团问题 142
6.5.2 旅行售货员问题 143
6.5.3 连续邮资问题 144
6.5.4 电路板排列问题 145
小结 147
习题六 147
一、选择题 147
二、填空题 147
三、简答题 147
四、计算题 147
五、上机题 147
第7章 分支限界法 148
7.1 概述 148
7.1.1 什么是分支限界法 148
7.1.2 分支限界的基本思想 148
7.2 复杂的有限期作业调度问题 149
7.3 贷郎担问题的分支限界法 151
7.4 其他分支限界问题 154
7.4.1 布线问题 154
7.4.2 0/1背包问题 157
7.4.3 单源最短路径的分支限界法 160
7.5 分支限界法与回溯法的比较 162
小结 163
习题七 163
一、选择题 163
二、填空题 163
三、简答题 163
四、计算题 164
五、上机题 164
第8章 概率算法概述 165
8.1 概率算法概述 165
8.1.1 什么是概率算法 165
8.1.2 概率算法的基本思想 166
8.2 数值概率算法 167
8.3 蒙特卡罗算法 168
8.4 其他概率算法 169
8.4.1 舍伍德算法 169
8.4.2 拉斯维加斯算法 170
小结 173
习题八 173
一、选择题 173
二、填空题 173
三、简答题 173
四、计算题 173
五、上机题 173
第9章 NP问题 174
9.1 NP问题概述 174
9.2 P类与NP类问题 175
9.2.1 非确定性图灵机 175
9.2.2 P类与NP类语言 176
9.2.3 多项式时间验证 177
9.3 NP完全问题 178
9.3.1 多项式时间变换 178
9.3.2 Cook定理 179
9.4 一些典型的NP完全问题 182
9.4.1 合取范式的可满足性问题CNF-SAT 183
9.4.2 三元合取范式的可满足性问题3-SAT 183
9.4.3 团问题CLIQUE 184
9.4.4 顶点覆盖问题VERTEX-COVER 185
9.4.5 子集和问题SUBSET-SUM 186
9.4.6 哈密顿回路问题HAM-CYCLE 188
9.4.7 旅行售货员问题TSP 191
小结 192
习题九 192
一、选择题 192
二、填空题 192
三、简答题 192
四、计算题 192
五、上机题 193
第10章 近似算法 194
10.1 近似算法概述 194
10.1.1 什么是近似算法 194
10.1.2 近似算法的基本思想及性能 194
10.2 顶点覆盖问题的近似算法 196
10.3 集合覆盖问题的近似算法 198
10.4 子集合问题的近似算法 199
10.4.1 子集和问题的指数时间算法 200
10.4.2 子集合问题的完全多项式时间近似格式 200
小结 202
习题十 202
一、选择题 202
二、填空题 202
三、简答题 203
四、计算题 203
五、上机题 203
第11章 新型算法 204
11.1 加密算法概述 204
11.2 初等数论 205
11.3 DES以及3重DES算法 208
11.3.1 DES算法 208
11.3.2 三重DES算法 210
11.4 AES算法 213
11.4.1 Rijndael加密算法描述 214
11.4.2 Rijndael解密算法描述 215
11.5 RSA算法 215
小结 216
习题十一 216
一、选择题 216
二、填空题 217
三、简答题 217
四、计算题 217
五、上机题 217
第12章 并行算法 218
12.1 并行算法概述 218
12.2 并行计算机 218
12.2.1 并行计算机分类 218
12.2.2 并行计算机的处理机互连方式 222
12.2.3 并行计算模型 224
12.3 并行算法 228
12.3.1 数据并行模型 229
12.3.2 消息传递模型 230
12.3.3 共享变量模型 231
12.4 并行算法编程实现 231
12.4.1 枚举排序 232
12.4.2 快速排序 233
12.4.3 并行正则采样排序 234
小结 235
习题十二 236
一、选择题 236
二、填空题 236
三、简答题 236
四、计算题 236
五、上机题 236
第13章 上机实训 237
13.1 递归技术应用 237
13.2 运用贪心算法求解实际问题 239
13.2.1 套汇问题 239
13.2.2 汽车加油问题 239
13.3 动态规划法应用 240
13.3.1 最好费用购物 240
13.3.2 租用游艇问题 242
13.4 回溯法应用 242
13.4.1 重排九宫问题 243
13.4.2 智力拼图问题 247
13.5 分支限界法应用 251
13.5.1 0/1问题的栈式分支限界法 251
13.5.2 用最大堆存储活结点的优先队列式分支限界法 253
小结 255
参考文献 256