第1章 引论 1
1.1 算法分析 3
1.2 算法的渐近性态分析 5
1.2.1 渐近表示法 6
1.2.2 大O表示法中的误区 6
1.2.3 大O的特性 7
1.2.4 紧凑大O界 9
1.2.5 常用的大O表达式 10
1.2.6 渐近下界——Ω表示法 10
1.3 搜索有序表 11
1.2.7 ？及小o表示法 11
练习1 16
第2章 算法设计技术和分析方法 18
2.1 穷举算法和贪心算法 18
2.2 回溯方法 26
2.2.1 构造解空间 26
2.2.2 回溯和裁剪 27
2.2.3 收费公路重建问题 29
2.3 分支限界算法 33
2.4 动态规划 36
2.4.1 阶段的划分 37
2.4.3 将递归算法变换成非递归算法 38
2.4.2 根据子问题的特性建立计算最优解的递归算法 38
2.5 分治方法 40
2.6 随机化算法 42
2.6.1 如何选取随机数序列 43
2.6.2 随机算法的分类 46
2.6.3 拉斯维加斯选择算法 46
2.6.4 蒙特卡罗方法 49
2.6.5 模拟退火算法 50
2.7 一类递归方程的解 51
2.8 母函数方法 54
练习2 55
3.1 大整数相乘算法 57
第3章 计算的算术复杂性 57
3.2 矩阵的乘积 59
3.2.1 Winograd矩阵乘积算法 59
3.2.2 Strassen矩阵乘法 60
3.3 快速傅里叶变换和卷积 62
3.3.1 预备知识 63
3.3.2 向量卷积 63
3.3.3 离散傅里叶变换 63
3.4 判定素数的算法 65
3.5 RSA数据加密算法 67
3.6 数据压缩算法 69
3.6.1 ACSII码压缩方法 69
练习3 70
3.6.2 模式置换压缩方法 70
第4章 排序算法 72
4.1 冒泡排序算法 72
4.2 基于比较的排序算法时间复杂性下界 76
4.3 分配排序技术 76
4.3.1 基数排序算法 77
4.3.2 分配分块排序算法 79
4.3.3 分配和归并混合排序算法 80
4.3.4 循环分组散列和循环两路归并排序算法 82
4.4 Quick排序的随机算法 84
练习4 87
5.2 线性期望时间的选择算法 88
5.1 最大元素和最小元素选择问题 88
第5章 选择问题 88
5.3 最坏情形下线性时间的选择算法 90
练习5 91
第6章 字符串匹配 92
6.1 简单的字符串匹配算法 92
6.2 Knuth-Morris-Pratt串匹配算法 93
6.3 Boyer-Moore串匹配算法 96
6.4 KARP-RABIN串匹配算法 98
6.5 允许k-差别的近似串匹配算法 100
6.6 求最长公共子序列算法 102
练习6 104
7.1 网络路由的概念 107
第7章 网络路由算法 107
7.2 LS路由算法 108
7.3 DV路由算法 110
7.4 分层路由 112
7.5 无QoS约束的组播路由算法 113
7.5.1 最小生成树算法 114
7.5.2 无约束的Steiner树算法 114
7.6 基于时延约束的组播路由算法 114
7.7 无线移动通信网络的路由算法 116
7.7.1 支持单向链路的路由选择算法 116
7.7.2 附加处理模块 119
练习7 121
8.1.1 什么是好算法 122
第8章 NP难解问题与近似算法 122
8.1 NP难解问题的基本理论 122
8.1.2 NP完全性 124
8.1.3 绕过NP完全性问题 126
8.2 NP完全问题的近似解法 126
8.2.1 近似算法的性能 127
8.2.2 顶点覆盖问题的近似算法 127
8.3 旅行商问题 128
8.3.1 最邻近策略 128
8.3.2 最短链路策略 129
8.4.1 依次着色算法 130
8.4 图的着色问题 130
8.4.2 四色猜想 132
8.4.3 Ramsey数 133
练习8 134
第9章 生物信息处理算法 135
9.1 DNA计算的基本原理与模型及算法 135
9.2 序列比对的基本问题 139
9.2.1 序列比对的记分方法 139
9.2.2 替换矩阵 140
9.2.3 空格罚分 141
9.3 生物序列比对模型及算法 141
9.3.1 双序列比对 141
9.3.2 多序列比对及其比对模型 142
9.3.3 多序列比对方法 144
9.3.4 多序列比对算法的分析与比较 148
练习9 151
第10章 并行计算基础 152
10.1 并行处理技术及其应用 152
10.2 并行计算机分类 153
10.2.1 Flynn分类法 153
10.2.2 Handler分类法 153
10.2.3 按机器体系结构分类 154
10.3 并行计算机的处理器的互连方式 155
10.3.1 一维线性阵列结构 155
10.3.2 二维网格结构 156
10.3.4 树网结构 157
10.3.3 树结构 157
10.3.5 超立方连接结构 158
10.3.6 q维网格结构 159
10.3.7 洗牌-交换网络 159
10.3.8 蝶形结构 160
10.4 并行计算模型 160
10.4.1 SIMD互连网络模型 160
10.4.2 共享存储的SIMD模型 161
10.4.3 MIMD并行计算模型 161
10.5.2 Minsky猜想 162
10.5.3 Amdahl定律 162
10.5.1 Grosch定律 162
10.5 并行计算的若干理论 162
10.6 并行算法基础 163
10.6.1 并行算法的基本概念 163
10.6.2 并行算法的复杂性 163
10.6.3 并行算法的形式描述 165
10.6.4 并行算法设计的基本技术 165
练习10 167
第11章 并行求和算法 168
11.1 SIMD-MC2二维网格机器上的同步并行求和算法 168
11.2 SIMD-CC超立方机器上的同步并行求和算法 170
11.3 SIMD-SE洗牌交换网络上的同步并行求和算法 171
11.4 SIMD-SM机器上的同步并行求和算法 172
11.5 MIMD-SM机器上的异步并行求和算法 174
练习11 175
第12章 并行排序算法 177
12.1 线性阵列上的奇偶转置排序同步并行算法 177
12.2 线性阵列上的奇偶归拆排序同步并行算法 178
12.3 树机器上的最小抽取排序同步并行算法 180
12.4 树机器上的桶分配和归并排序同步并行算法 184
12.5 共享存储并行系统上的Valiant归并和排序同步并行算法 185
12.5.1 Valiant归并同步并行算法 186
12.6 共享存储MIMD-TC模型上的快速排序异步并行算法 189
12.5.2 Valiant排序同步并行算法 189
12.7 MIMD-SM机器上基于散列技术的异步并行排序算法 192
12.8 共享存储并行系统上Multisets排序的最优并行算法 194
12.9 SMP Clusters系统上的并行外部排序算法 199
练习12 201
第13章 并行查找与并行串匹配 203
13.1 共享存储器并行系统上范围查找同步并行算法 203
13.2 共享存储器并行系统上任意两序列公共元素的同步并行查找算法 205
13.3 共享存储器并行系统上KARP-RABIN串匹配并行算法 209
13.4 PRAM模型上允许k-差别的近似串匹配并行算法 210
13.4.1 波前式并行计算编辑距离的允许k-差别的近似串匹配动态规划并行算法 210
13.4.2 水平和斜向双并行计算编辑距离的允许k-差别的近似串匹配并行算法 213
练习13 216
第14章 数值并行算法 217
14.1 SIMD-SM机器上基于LDU分解的方程组求解同步并行算法 217
14.2 MIMD-SM机器上的矩阵相乘异步并行算法 218
14.3 SIMD-SM机器上非线性方程求根同步并行算法 220
练习14 221
第15章 数据库操作并行算法 222
15.1 选择、投影和集合操作并行算法 222
15.1.1 并行选择算法 223
15.1.2 并行投影算法 225
15.1.3 关系元组集合操作并行算法 228
15.2.1 并行嵌套循环连接算法 231
15.2 并行连接算法 231
15.2.2 基于排序和合并方法的并行连接算法 232
15.2.3 基于Hash方法的并行连接算法 234
练习15 239
附录 并行MULTIPASCAL系统简介及并行程序实例 240
附录1 并行MULTIPASCAL系统简介 240
附录1.1 并行MULTIPASCAL系统的上机操作步骤 240
附录1.2 并行MULTIPASCAL语句简介 240
附录2 基于散列技术的（m，n）选择并行算法及程序实例 242
附录2.1 并行散列选择算法的设计 242
附录2.2 并行散列选择程序实例 244
参考文献 250