计算机算法导引 设计与分析 第2版PDF电子书下载

目录 3

第1部分 基本算法 3

第1章 数学准备 3

1.1 母函数 3

1.2 递推关系 5

1.3 Fibonacci数列 9

1.3.1 Fibonacci数列是典型的递推关系 9

1.3.2 问题的解 10

1.4 线性常系数递推关系举例 11

1.5 其他类型的递推关系举例 13

习题 18

2.1 优先策略：求最短树的Kruskal算法 20

第2章 优先策略与分治策略 20

2.2 求最短树的Prim算法 22

2.3 求最短路径的Dijkstra算法 24

2.4 文件存储问题 25

2.5 有期限的任务安排问题 27

2.6 数据压缩和Huffman树 29

2.7 分治策略与二分查找 33

2.8 整数乘法 34

2.9 矩阵乘积的Strassen算法 35

2.10 矩阵乘积的Winograd算法 38

2.11 布尔矩阵乘积的分段预处理方法 39

2.12 归并排序法 41

2.13 快速排序法 43

2.14 求序列中的第k个元素 48

习题 50

第3章 动态规划 53

3.1 最短路径问题 53

3.2 最佳原理 55

3.3 流动推销员问题 65

3.3.1 算法及例题 65

3.3.2 复杂性估计 67

3.4 矩阵链乘问题 68

3.5 最长公共子序列 70

3.6 图的任意两点间的最短距离 72

3.7 同顺序流水作业的任务安排问题 74

3.8 可靠性问题 76

3.9 最佳二分树 78

3.9.1 二分树的一些性质 78

3.9.2 最佳二分树的构成 81

习题 88

第4章 概率算法 91

4.1 生日问题 91

4.2 概率算法举例 92

4.3 随机数的产生器 94

4.3.1 线性同余式法 94

4.3.2 离散对数法 95

4.3.3 BBS法 96

4.3.4 素数法 96

4.4 素数的概率判定算法 96

4.4.1 关于素数的若干定理 96

4.4.2 Fermat数 98

4.4.3 Miller-Rabin的素数概率测试法 98

4.5.1 数论的基本知识 99

4.5 定理证明的数学准备 99

4.5.2 群论的基本知识 101

4.5.3 中国剩余定理 104

4.5.4 xn≡1 mod p的解 105

4.6 定理A的证明 107

4.7 定理B的证明 109

习题 111

第5章 并行算法 113

5.1 并行计算机和并行算法的基本概念 113

5.2 递推关系的并行计算 116

5.3 图的并行算法举例 118

5.4 矩阵乘积的并行计算 121

5.5 分布计算 124

5.6.2 预备定理 125

5.6 快速傅里叶变换 125

5.6.1 FFT问题的背景 125

5.6.3 快速算法 127

5.6.4 傅里叶逆变换 133

5.6.5 计算结果的重排 133

5.6.6 复杂性估计 134

5.7 卷积及其应用 136

5.7.1 卷积 136

5.7.2 多项式的一种快速乘法 137

5.8 数论变换 138

5.9 排序网络 140

5.9.1 引论 141

5.9.2 0-1原理 142

5.9.3 Bn型网络 143

5.9.4 Mn归并网络 145

5.10 Batcher奇偶归并网络 146

5.11 脉动阵列的并行处理 148

5.11.1 矩阵和向量乘法的并行处理 148

5.11.2 矩阵乘法的并行处理 150

5.11.3 带状矩阵的并行乘法 151

习题 153

第6章 搜索法 154

6.1 引论 154

6.2 DFS搜索法 155

6.3 无向图的DFS算法 157

6.4 有向图的DFS算法 160

6.5 互通块问题 163

6.6 强连通块问题 164

6.7 BFS算法 168

6.8 拓扑排序 169

6.9 min-max搜索法 170

6.10 流动推销员问题的分支定界法 171

6.11 同顺序加工任务安排问题 175

习题 177

第7章 数据结构 179

7.1 “堆”和“堆集排序法” 179

7.1.1 堆 179

7.1.2 堆集排序法 182

7.1.3 优先级队和二进制堆 183

7.2 2-3树 186

7.3 2-3-4树 189

7.4.1 RB树性质 191

7.4 红黑树 191

7.4.2 插入 192

7.4.3 删除 195

7.5 B-树 197

7.5.1 B-树性质 197

7.5.2 B-树的插入 199

7.5.3 B-树的删除 201

7.6 关于高度的均衡树 203

7.6.1 AVL树——关于高度均衡的二分树 203

7.6.2 关于高度均衡的二分树的插入和删除 207

7.7 哈希表 210

7.7.1 什么是哈希表 210

7.7.2 哈希函数的构造方法 211

7.7.3 解决冲突的方法 212

7.7.4 哈希算法的分析（线性探测法分析） 214

7.7.5 二重哈希法 216

习题 217

第2部分 若干专题 221

第8章 排序算法 221

8.1 排序 221

8.2 下界估计 221

8.3 二分插入排序法 224

8.4 下溢排序法 226

8.5 Ford-Johnson归并插入排序法 229

8.5.1 算法的非形式化描述 229

8.5.2 一般情形的讨论 230

8.5.3 算法分析 231

8.6.1 外存归并排序法 233

8.6 外存排序 233

8.6.2 三条带的外存归并排序法 235

8.6.3 阶式归并法 238

第9章 计算几何及计算数论 240

9.1 关于线段问题 240

9.2 凸包问题与Voronoi问题 244

9.2.1 凸包问题 244

9.2.2 Voronoi图 247

9.2.3 Voronoi图的构造法 248

9.2.4 Voronoi图的应用简介 249

9.2.5 Voronoi图的拓广 249

9.3 串匹配 250

9.3.1 搜索法 250

9.3.2 KMP算法 251

9.3.3 BM算法 253

9.3.4 RK算法 254

9.4 数论的算法问题 255

9.4.1 求最大公因数 255

9.4.2 因数分解之一：Pollardρ法 257

9.4.3 Dixon随机平方因数分解法 260

9.4.4 椭圆曲线因数分解法 261

9.5 大数模幂运算 270

9.6 N mod M 273

9.6.1 Barrett归约 273

9.6.2 模乘算法 274

9.6.3 Montgomery模幂运算 277

9.6.4 n是偶数的情况 280

10.1 问题的提出 282

第10章 线性规划 282

10.2 线性规划的几何意义 284

10.3 单纯形法理论基础 287

10.4 单纯形法及单纯形表格 291

10.5 改善的单纯形法表格 297

10.6 对偶原理 300

10.6.1 对偶概念 300

10.6.2 对偶问题的经济意义 301

10.6.3 对偶问题的性质 302

10.6.4 对偶定理 303

10.6.5 影子价格 304

10.7 对偶单纯形法 307

10.8 退化情况及其他 311

10.8.1退化情况 312

10.8.2 退化情况的循环不已与Bland法则 313

10.9 Dantzig-Wolfe分解算法 314

10.10 整数规划 322

10.10.1 问题的提出 322

10.10.2 0-1规划和DFS搜索法 324

10.10.3 分支定界法 333

10.11 Klee与Minty举例 335

第3部分 复杂性理论与智能型算法 341

第11章 算法复杂性理论 341

11.1 图灵机 341

11.2 图灵机和算法 345

11.3 k条带的图灵机 347

11.4 非确定型图灵机 348

11.5 停机问题 349

11.6 布尔表达式 351

11.7 布尔变量和网络 353

11.8 问题的转换 354

11.9 Cook定理 356

11.10 几个NP完备的例子 360

11.11 复杂度类 368

11.12 近似解法 370

11.12.1 任务安排的近似算法 370

11.12.2 装箱问题的近似算法 374

11.12.3 流动推销员问题的近似算法 376

11.12.4 顶点覆盖问题的近似算法 384

11.13.1 密码概念 385

11.13 近代密码学简介 385

11.13.2 背包公钥密码 388

11.13.3 RSA公钥密码 389

第12章 智能型算法 391

12.1 遗传算法 391

12.2 什么是遗传算法 398

12.3 TSP问题 398

12.3.1 编码 398

12.3.2 初始“种群”的生成 398

12.3.3 杂交 400

12.3.4 变异算术 403

12.3.5 模式定理 404

12.4 模拟退火算法简介 405

习题 412