计算机算法设计与分析导论PDF电子书下载

第1章　引论 1

1.1　算法的基本概念 1

1.2　算法的数学基础 4

1.2.1　集合论 4

1.2.2　逻辑学 6

1.2.3　概率论 7

1.2.4　求和与递归 11

1.2.5　快速估算法 16

1.3　算法的效率与复杂度 16

1.4　习题 20

1.5　参考文献 21

第2章　算法设计与分析技术 22

2.1　算法的渐近复杂度 22

2.2　算法的优化与最优算法 26

2.3　算法设计中的常用方法 32

2.3.1　分治法 32

2.3.2　回溯法 33

2.3.3　贪心法 34

2.3.4　分支限界法 35

2.3.5　动态规划 36

2.4　习题 41

2.5　参考文献 42

第3章　排序问题 43

3.1 引言 43

3.2　基于相邻元素之间的比较排序算法 44

3.2.1　插入排序法 44

3.2.2　冒泡排序法 46

3.2.3　选择排序法 49

3.3　基于分治策略的排序算法 50

3.3.1 归并排序法 51

3.3.2　快速排序法 52

3.3.3　谢尔排序法 56

3.4　堆排序 58

3.4.1　堆的性质 58

3.4.2　堆排序算法 59

3.4.3　加速堆排序 63

3.5　基于比较的排序算法复杂度下界 67

3.6　基数排序 69

3.7　习题 72

3.8　参考文献 73

第4章　图的算法 74

4.1 引言 74

4.2 图的概念 74

4.2.1 历史回顾 74

4.2.2　图的基本概念 75

4.2.3 图的表示 76

4.2.4　树与图的生成树 78

4.2.5　独立集、覆盖与控制集 80

4.3　图的搜索问题 81

4.3.1　宽度优先搜索 81

4.3.2　宽度优先树 83

4.3.3　深度优先搜索算法 84

4.3.4　深度优先搜索的性质 86

4.4　拓扑排序 89

4.5　强连通支 91

4.6　最小生成树算法 95

4.6.1　最小生成树的形成 95

4.6.2　Kruskal算法和Prim算法 98

4.7　最短路径算法 102

4.7.1 问题描述 102

4.7.2　松弛技术 103

4.7.3 Bellman-Ford算法 104

4.7.4　Dijkstra算法 107

4.8　欧拉回路与中国邮递员问题 110

4.8.1　欧拉回路 110

4.8.2　中国邮递员问题 111

4.9　网络流及其应用 113

4.9.1 网络流与最大流最小截集定理 114

4.9.2　最大流的算法 116

4.9.3 网络流的应用 117

4.10 习题 121

4.11 参考文献 122

第5章　NP完全性理论 123

5.1 引言 123

5.2 图灵机 124

5.3　判定问题、语言和编码 128

5.4　P类问题、多项式变换和可满足性问题 129

5.5　NP类问题、NP完全问题和NP困难问题 130

5.5.1　NP类 130

5.5.2　NP完全问题和NP困难问题 132

5.6　Cook定理 135

5.7　NP完全性证明 135

5.7.1　直接变换法 136

5.7.2 限制法 138

5.8　P类问题的证明 139

5.9　近似算法 141

5.9.1　装箱问题 141

5.9.2　0/1背包问题 143

5.9.3　旅行商问题 143

5.10　DNA计算 145

5.10.1 DNA背景知识 145

5.10.2　DNA计算哈密顿路径问题 145

5.11　丘奇-图灵论点的启示 148

5.12　习题 149

5.13　参考文献 150

第6章　并行计算基础 151

6.1 引言 151

6.2　并行计算机 151

6.2.1　并行计算机发展简史 151

6.2.2　并行计算机体系结构 153

6.2.3 并行计算机存储器模型 156

6.2.4　多处理机中高速缓存一致性问题 159

6.3　并行计算机通信机制 162

6.3.1　静态网络 162

6.3.2　动态网络 167

6.3.3 并行计算机的消息传递方式 170

6.3.4　互连网络的路由选择 172

6.4　并行计算模型 173

6.4.1　PRAM模型 173

6.4.2　BSP模型 175

6.4.3　LogP模型 177

6.4.4　C3模型 179

6.5　习题 179

6.6　参考文献 182

第7章　并行算法设计技术 184

7.1 引言 184

7.2　并行算法的基本概念 184

7.3 串行算法的并行化 185

7.3.1　设计方法描述 185

7.3.2　快速排序算法的并行化 185

7.4　并行算法的PCAM设计方法 188

7.5　任务分解 189

7.5.1 域分解 189

7.5.2　功能分解 192

7.5.3　分解判据 193

7.6　通信设计 193

7.6.1　局部／全局通信 194

7.6.2　结构化／非结构化通信 196

7.6.3　静态／动态通信 196

7.6.4　同步／异步通信 197

7.6.5　通信判据 197

7.7　任务组合 198

7.7.1　增加粒度 198

7.7.2　保持灵活性和减少软件工程的代价 200

7.7.3　组合判据 201

7.8　处理器映射 201

7.8.1 负载均衡算法 202

7.8.2　任务调度算法 204

7.8.3　映射判据 206

7.9　习题 207

7.10　参考文献 208

第8章　并行算法效率分析 209

8.1 引言 209

8.2　并行算法的性能指标 209

8.2.1　执行时间 209

8.2.2　效率与加速比 211

8.2.3　可扩展性 212

8.2.4　并行度 214

8.3　并行算法性能分析 214

8.3.1　Brent定理 214

8.3.2　阿姆达尔定律 215

8.3.3 古斯塔夫森定理 215

8.3.4　Sun-Ni定理 216

8.4　习题 216

8.5　参考文献 219

第9章　并行求和与排序 220

9.1 引言 220

9.2　基于不同计算模型的并行求和算法 221

9.2.1 二维网格机器（SIMD-MC2）上的同步并行求和算法 221

9.2.2　超立方机器（SIMD-CC）上的同步并行求和算法 222

9.2.3 洗牌交换网络（SIMD-SE）上的同步并行求和算法 224

9.2.4　共享存储器机器（SIMD-SM）上的并行求和算法 226

9.3　基于不同计算模型的并行排序算法 228

9.3.1 SIMD-EREW上的并行排序算法 228

9.3.2　BSP上的并行排序算法 229

9.4　基于功能划分的并行排序算法 230

9.4.1 并行双调排序算法 230

9.4.2　奇偶交换并行排序 231

9.5　并行快速排序算法 233

9.5.1 PRAM-CRCW计算模型上的快速排序算法 233

9.5.2　超立方体网络上的模拟快速排序 235

9.6　比较器网络上的并行排序 237

9.6.1 比较器网络 237

9.6.2　奇偶归并网络 237

9.6.3　双调归并网络 237

9.6.4　Batcher排序网络 238

9.7　习题 239

9.8　参考文献 241

第10章　并行数值算法 243

10.1　矩阵并行计算 243

10.1.1　并行矩阵乘法 243

10.1.2　LU分解 245

10.1.3　QR分解 247

10.1.4　矩阵求逆 251

10.2　线性方程组的解 253

10.2.1 高斯消去法 253

10.2.2　高斯-塞德尔迭代法 257

10.2.3　松弛法 259

10.3　快速傅里叶变换和离散小波变换 259

10.3.1　快速傅里叶变换 260

10.3.2 离散小波变换 262

10.4　习题 266

10.5　参考文献 268

第11章　并行计算工具与并行程序设计语言HPF简介 269

11.1 并行计算工具 269

11.1.1　概述 269

11.1.2　并行程序设计工具PVM 270

11.1.3　并行程序设计工具MPI 272

11.2　HPF并行编程 275

11.2.1 高性能FORTRAN简介 275

11.2.2　数据并行机制 276

11.2.3　数据映射 276

11.2.4 实例：高斯消去法的HPF程序 277