并行算法导论PDF电子书下载

0.1计算机简介 1

目 录出版者的话专家指导委员会译者序前言致谢作者简介第一部分并行计算基础第0章引言 1

0.2并行计算机 5

0.3并行处理的概念 6

0.4高性能计算机 8

0.5本书的结构和内容 9

参考文献 10

第1章并行计算要素 11

1.1并行的层次 11

1.2.1 Flynn分类 12

1.2并行计算机分类 12

1.2.2 Erlangen分类（Handler分类） 14

1.2.3 Giloi分类 15

1.2.4 Hwang-Brigg分类 15

1.2.5 Duncan分类 15

1.3并行计算模型 18

1.3.1二叉树模型 18

1.3.2网络模型 20

1.3.3超立方体（k-立方体） 21

1.3.5金字塔网络 26

1.3.4网格网络 26

1.3.6星形图 27

1.4 PRAM模型 28

1.5一些简单算法 32

1.6并行算法的性能 34

1.7小结 37

参考文献 37

习题 38

第2章并行计算数据结构 40

2.1数组和列表 40

2.2链接列表 41

2.3图与树 44

2.3.1预备知识 44

2.3.2欧拉图与哈密顿图 48

2.3.3树 49

2.3.4图的遍历 57

2.3.5连通性 58

2.3.6可平面图 62

2.3.7染色与独立集 64

2.3.9交图 65

2.3.8团覆盖 65

2.3.10弦图 66

2.3.11更多的交图 70

2.3.12图的匹配问题 70

2.3.13图的中心 71

2.3.14控制理论 72

2.3.15图论中的一些问题 73

参考文献 74

3.1二叉树设计环境 76

第3章并行算法设计环境 76

3.2二倍增长 79

3.3指针跳转 79

3.4分而治之 82

3.5划分 83

3.6 小结 86

参考文献 86

习题 86

4.1向量内积 88

4.2矩阵乘法 88

第4章简单并行算法 88

4.3部分和 90

4.4二项式系数 94

4.5范围内最小值问题 98

参考文献 101

习题 101

第二部分图模型算法第5章树算法 103

5.1欧拉圈 103

5.2给树加根 104

5.3后序编号 105

5.4后代个数 107

5.5顶点层数 107

5.6最低公共祖先 108

5.7树收缩 110

5.8算术表达式的计算 114

5.9森林求根问题 117

5.10到根的路 119

5.11树变为二叉树 123

5.12顶点直径 125

5.13最远邻居 128

参考文献 130

习题 131

第6章图算法 132

6.1简单图算法 132

6.2并行连通度算法 135

6.2.1广度优先搜索（BFS） 135

6.2.2利用BFS搜索连通支 139

6.2.3传递闭包矩阵 141

6.2.4顶点收缩 141

6.3 2-连通支 145

6.4支撑树 146

6.5最短路问题 148

参考文献 151

习题 152

第7章弦图的NC算法 154

7.1弦图判别 154

7.2弦图的极大团 161

7.3 CV图的特征 163

7.4路图判别 164

7.4.1一些概念和事实 164

7.4.2算法概述 168

7.4.3两个UV图的并 169

7.4.4 正确性和复杂度 175

参考文献 177

第三部分数组处理算法第8章搜索与合并 179

8.1串行搜索 179

8.2 CREW PRAM模型下的并行搜索 180

8.3更多数据的并行搜索 181

8.4无序数组搜索 182

8.5秩合并 182

8.6双调合并 184

参考文献 187

第9章排序算法 188

9.1串行排序算法 188

9.1.1冒泡排序 188

9.1.2插入排序 189

9.1.3 Shell递减步长排序 190

9.1.4堆排序 191

9.2合并排序 193

9.3排序网络 194

参考文献 195

习题 196

第四部分数值算法第10章代数方程和矩阵 197

10.1代数方程 197

10.1.1几何解释 197

10.1.2对分法 198

10.2矩阵的行列式 199

10.3线性方程组 202

10.3.1高斯消元法 205

10.3.2 Givens旋转 206

10.4傅里叶变换 208

10.5多项式乘法 215

10.6矩阵求逆 217

10.7 Toeplitz矩阵 219

10.8三对角方程组 222

10.8.1 高斯消元法 222

10.8.2奇偶约化法 223

参考文献 226

习题 227

11.1微分 228

第11章微分与积分 228

11.2偏微分 229

11.3定积分 233

11.4插值 235

11.4.1线性插值 235

11.4.2二次插值 236

11.4.3拉格朗日插值 236

参考文献 237

习题 238

12.2偏微分方程 239

第12章微分方程 239

12.1欧拉公式 239

12.3抛物方程 240

12.3.1施密特法（求解抛物方程） 242

12.3.2 Laasonen法（求解抛物方程） 246

12.3.3 Crank Nickolson法 248

12.3.4三层差分法 249

参考文献 251

部分习题解答 252

索引 258