计算机算法设计与分析导论【2025|PDF下载-Epub版本|mobi电子书|kindle百度云盘下载】

计算机算法设计与分析导论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　并行程序设计工具PVM270

11.1.3　并行程序设计工具MPI272

11.2　HPF并行编程275

11.2.1 高性能FORTRAN简介275

11.2.2　数据并行机制276

11.2.3　数据映射276

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