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

并行算法的设计与分析PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第一章 并行算法基础1

1.1 并行算法的硬件基础2

1.1.1 当代并行计算机体系结构2

1.1.2 并行计算机互连网络9

1.2 并行计算模型16

1.2.1 SIMD同步并行计算模型17

1.2.2 MIMD异步并行计算模型19

1.2.3 其他并行计算模型29

1.3 并行算法编程模型31

1.3.1 数据并行模型31

1.3.2 消息传递模型33

1.3.3 共享变量模型34

1.4.1 并行算法的定义和分类36

1.4 并行算法的一般概念36

1.4.2 并行算法的表达37

1.4.3 并行算法的复杂性度量38

1.4.4 并行算法的WT表示41

1.4.5 并行算法的同步和通信44

习题47

参考文献51

第二章 并行算法的基本设计技术54

2.1 平衡树方法55

2.1.1 求取最大值55

2.1.2 计算前缀和55

2.2 倍增技术59

2.2.1 表序问题的计算60

2.2.2 求森林的根61

2.3 分治策略62

2.3.1 SIMD模型上分治算法的描述62

2.3.2 SIMD共享存储模型上的FFT算法63

2.4 划分原理66

2.4.1 归并原理66

2.4.2 划分算法与归并算法66

2.5 流水线技术68

2.5.1 一维阵列上的流水线归并排序原理68

2.5.2 一维阵列上的流水线归并排序算法69

2.6 加速级联策略70

2.6.1 常数时间求最大值算法71

2.6.2 双对数时间算法71

2.6.3 加速级联算法72

2.7 破对称技术73

2.7.1 基本着色算法73

2.7.2 快速3-着色算法75

2.7.3 最优3-着色算法75

习题77

参考文献79

第三章 比较器网络上的排序和选择算法80

3.1 Batcher归并和排序网络81

3.1.1 比较操作和[0，1]原理81

3.1.2 奇偶归并网络82

3.1.3 双调归并网络84

3.1.4 Batcher排序网络85

3.2 (m，n)-选择网络87

3.2.1 分组选择网络88

3.2.2 平衡分组选择网络91

3.3 AKS排序网络92

3.3.1 扩展图和划分网络92

3.3.2 部分排序算法95

3.3.3 完全排序算法98

习题103

参考文献104

第四章 排序和选择的同步算法106

4.1 Stone双调排序算法107

4.1.1 均匀洗牌函数及其性质107

4.1.2 Stone的观察及其计算模型107

4.1.3 Stone的并行排序算法110

4.2.1 处理器编号方式112

4.2 Thompson和Kung双调排序算法112

4.2.2 Thompson和Kung的观察113

4.2.3 Thompson和Kung的双调排序算法114

4.3 Preparata和Vuilemin双调排序算法117

4.3.1 算法原理117

4.3.2 流水线技术119

4.3.3 算法描述120

4.4 Akl并行k-选择算法121

4.4.1 算法原理及物理描述122

4.4.2 并行k-选择算法122

4.4.3 算法分析124

4.5 Valiant并行归并算法125

4.5.1 归并算法的基本原理125

4.5.2 k=？时Valiant归并126

4.5.3 k=？时Valiant归并127

4.6 Hirschberg并行桶排序算法128

4.6.1 并行桶排序算法原理128

4.6.2 并行桶排序算法描述129

4.7 Preparata并行枚举排序算法130

4.7.1 枚举排序及其实现方法130

4.7.2 排序算法的设计和分析132

4.8 Cole并行归并排序算法134

4.8.1 使用覆盖和位序的归并方法134

4.8.2 Cole最佳排序算法136

4.8.3 算法的正确性证明及分析139

习题144

参考文献146

第五章 排序和选择的异步和分布式算法147

5.1 MIMD-CREW模型上的异步枚举排序算法148

5.1.1 算法原理和描述148

5.1.2 算法举例和分析149

5.2 MIMD-TC模型上的异步快排序算法150

5.2.1 算法原理和描述150

5.2.2 算法举例和分析151

5.3 分布式k-选择算法153

5.3.1 随机k-选择算法153

5.3.2 确定k-选择算法155

5.4 分布式求中值算法157

5.4.1 分布式中值157

5.4.2 分布式求中值算法158

5.5.1 分布式计算模型159

5.5 分布式定序算法159

5.5.2 分布式定序算法160

5.5.3 算法复杂度分析162

5.6 分布式排序算法163

5.6.1 模型和定义163

5.6.2 静态排序算法164

5.6.3 算法复杂度分析165

习题166

参考文献167

第六章 并行搜索169

6.1.1 单处理机上的顺序搜索170

6.1.2 单处理机上有序表的对半搜索170

6.1 单处理机上的搜索170

6.2 SIMD共享存储模型上有序表的搜索171

6.2.1 SIMD-EREW模型上的搜索171

6.2.2 SIMD-CREW模型上的搜索172

6.3 SIMD共享存储模型上随机序列的搜索176

6.3.1 SIMID-SM模型上的随机序列搜索算法描述176

6.3.2 SIMD-SM模型上的随机序列搜索算法分析177

6.4 树连接的SIMD模型上随机序列的搜索177

6.4.1 提问177

6.4.2 维护178

6.5 网孔连接的SIMD模型上随机序列的搜索180

6.5.1 提问180

6.5.2 维护183

6.6.1 AVL树及其顺序插入算法184

6.6 MIMD共享存储模型上有序表的搜索184

6.6.2 Ellis并行搜索和插入算法186

习题189

参考文献190

第七章 排列和组合191

7.1 产生排列的顺序算法192

7.1.1 排列和组合192

7.1.2 产生词典序的排列算法193

7.1.3 产生排列的计数方法195

7.2 产生组合的顺序算法198

7.2.1 产生词典序的组合算法198

7.2.2 产生组合的计数方法199

7.3.1 串行排列算法的并行化202

7.3 产生排列的并行算法202

7.3.2 自适应排列产生器207

7.3.3 全排列产生器208

7.4 产生组合的并行算法210

7.4.1 非自适应组合产生器210

7.4.2 自适应组合产生器212

习题215

参考文献216

第八章 数据传输与选路217

8.1 引言218

8.2 贪心选路算法219

8.2.1 一维阵列上的贪心选路算法219

8.2.2 二维阵列上贪心选路算法的分析220

8.2.3 蝶形网络上的贪心选路算法222

8.3.1 二维阵列上的随机选路算法225

8.3 随机和确定选路算法225

8.3.2 超立方网络上的随机选路算法227

8.3.3 二维阵列上的确定选路算法228

8.4 数据的分布和集中230

8.4.1 数据的分布230

8.4.2 多到一选路算法233

8.5 线路交换模式下的选路算法235

习题238

参考文献240

第九章 并行串匹配241

9.1 引言242

9.1.1 基本概念和研究现状242

9.1.2 基本定义和术语243

9.2.1 SIMD-CREW模型上的非周期串的匹配算法244

9.2 正文分析244

9.2.2 SIMD-CREW模型上的周期串的匹配算法248

9.3 模式预处理250

9.3.1 求WIT表的一般方法250

9.3.2 完全非周期串的WIT表求法251

9.3.3 SIMD-CREW模型上任意串的WIT表求法254

9.3.4 模式匹配算法的复杂度256

9.4 后缀树上的串匹配256

9.4.1 数字搜索树与后缀树256

9.4.2 子串的编码258

9.4.3 后缀树的构造261

9.4.4 后缀树上的并行串匹配264

习题266

参考文献268

第十章 表达式求值270

10.1 构造表达式树271

10.1.1 全括号表达式的表达式树271

10.1.2 表达式树上的括号操作272

10.1.3 计算match(i)的并行算法274

10.2 填充游戏用于表达式求值275

10.2.1 二叉树上的填充游戏275

10.2.2 填充游戏用于算术表达式求值276

10.3 最优的并行表达式求值算法278

10.4 一般表达式求值算法282

10.4.1 一般表达式与直线程序282

10.4.2 仅有乘法操作符的dag的计算283

习题284

10.4.3 仅有加法操作符的dag的计算284

10.4.4 gbdag图和直线程序的计算285

10.5.1 基本概念和术语289

10.5 正则表达式到非确定自动机的最优并行转换289

10.5.2 SIMD-CREW模型上的HU转换方法291

参考文献295

第十一章 上下文无关语言的并行识别与语法分析296

11.1 一般的上下文无关语言的并行识别297

11.1.1 基本概念和术语297

11.1.2 残缺部分语法树及其合成规则299

11.1.3 共享存储模型上歧义性上下文无关语言并行识别算法302

11.2 一般上下文无关语言的并行语法分析304

11.2.1 基本概念和算法原理304

11.2.2 SIMD-CREW模型上一般上下文无关语言的语法分析算法306

11.3.1 基本概念和算法原理310

11.3 括号语言的最优并行识别和语法分析310

11.3.2 算法的具体实现311

11.3.3 树的压缩技术313

11.3.4 SIMD-CREW模型上括号语言的语法分析算法317

习题317

参考文献318

第十二章 矩阵运算319

12.1 矩阵转置320

12.1.1 单处理机上的矩阵转置算法320

12.1.2 SIMD-MC2模型上的矩阵转置320

12.1.3 SIMD-PS模型上的矩阵转置323

12.2 矩阵相乘325

12.2.1 单处理机上的矩阵乘法325

12.1.4 SIMD-EREW模型上的矩阵转置325

12.2.2 SIMD-MC2模型上的矩阵乘法326

12.2.3 SIMD-CC模型上的矩阵乘法328

12.2.4 MIMD机器上的矩阵乘法331

12.3 矩阵和向量相乘335

12.3.1 树连接的机器上的矩阵和向量乘法335

12.3.2 树网结构上的矩阵和向量乘法337

12.4 心动阵列上的矩阵运算337

12.4.1 二维六角形阵形上的矩阵乘法338

12.4.2 二维六角形阵列上方阵的LU分解340

12.4.3 六角形阵列上的方阵求逆343

12.4.4 一维阵列上求解三角形线性系344

习题347

参考文献350

第十三章 数值计算351

13.1 n阶线性代数方程组的求解352

13.1.1 SIMD-CREW模型上的Gauss-Jordan算法352

13.1.2 MIMD-CREW模型上的Gauss-Seidel算法355

13.1.3 紧耦合多处理机系统中LU算法的效率分析357

13.2 非线性方程的求根359

13.2.1 SIMD-CREW模型上的求根算法360

13.2.2 MIMD-CREW模型上的牛顿求根法362

13.2.3 Fibonacci分点法异步求根算法364

13.3 偏微分方程的求解367

13.3.1 偏微分方程的差分数值求解法367

13.3.2 SIMD-MC2模型上的PDE求解方法368

13.4.1 对称方阵对角化方法372

13.4 方阵的特征值与特征向量Jacobi求法372

13.4.2 SIMD-CC模型上的求特征值算法375

习题377

参考文献378

第十四章 FFI和卷积与滤波380

14.1 快速傅里叶变换381

14.1.1 离散傅里叶变换381

14.1.2 顺序的FFT算法382

14.1.3 FFT应用于多项式乘积382

14.2 DFT直接并行计算法384

14.2.1 SIMD模型上系数矩阵的计算384

14.2.2 SIMD-MT模型上的DFT算法385

14.3 并行FFT算法388

14.3.1 SIMD-MC2模型上的FFT算法388

14.3.2 SIMD-BF模型上的FFT算法391

14.3.3 SIMD-PS模型上的FFT计算393

14.3.4 SIMD-CC模型上的FFT计算396

14.3.5 一维心动阵列上的DFT计算401

14.4 心动阵列上的卷积与滤波计算402

14.4.1 一维卷积在线性阵列上的实现402

14.4.2 无限冲激滤波在线性阵列上的实现404

14.4.3 中值滤波在线性阵列的实现405

习题407

参考文献409

第十五章 图论算法410

15.1.1 算法原理411

15.1.2 p-深度优先搜索411

15.1 图的并行搜索411

15.1.3 p-宽深优先搜索412

15.1.4 p-宽度优先搜索412

15.2 图的传递闭包414

15.2.1 传递闭包问题414

15.2.2 SIMD-CC模型上的传递闭包算法415

15.2.3 二维心动阵列上的传递闭包算法416

15.3 图的连通分量419

15.3.1 SIMD-CC模型上的连通分量算法419

15.3.2 SIMD-SM模型上的连通分量算法421

15.3.3 SIMD-TC模型上的连通分量算法422

15.3.4 SIMD-MT模型上的连通分量算法425

15.4 图的最短路径428

15.4.1 所有顶点对间的最短路径算法428

15.4.2 MIMD-SM模型上单源最短路径算法430

15.5 图的最小生成树434

15.5.1 SIMD-EREW模型上最小生成树算法435

15.5.2 MIMD-SM模型上最小生成树算法438

15.5.3 树机模型上最小生成树算法441

15.6 图的着色444

15.6.1 二分图的边着色算法445

15.6.2 外平面图最优顶点着色算法446

15.6.3 外平面图最优边着色算法453

15.6.4 Halin图最优边着色算法457

习题461

参考文献464

第十六章 图象分析和计算几何466

16.1.1 二维阵列上分量标定平易算法467

16.1 分量标定467

16.1.2 二维阵列上Levialdi分量标定算法469

16.1.3 二维阵列上递归的分量标定算法471

16.2 Hough变换473

16.2.1 二维图象的Hough变换473

16.2.2 二维阵列上象素Hough变换的计算474

16.3 近邻问题475

16.4 包含问题476

16.4.1 判断点在多边形中477

16.4.2 判断点在平面细图中480

16.5 相交问题482

16.6 构造问题483

16.6.1 求凸壳问题的下界484

16.6.2 顺序求凸壳算法484

16.6.3 SIMD-MT模型上求凸壳算法486

16.6.4 SIMD-EREW模型上求凸壳算法489

习题495

参考文献496

第十七章 组合搜索497

17.1 基于分治法的与树搜索498

17.1.1 搜索树498

17.1.2 SIMD模型上的与树搜索499

17.2 基于分枝限界法的或树搜索499

17.2.1 8-谜问题500

17.2.2 串行分枝限界算法501

17.2.3 用串行分枝限界法求TSP503

17.2.4 并行TSP算法507

17.3.1 博弈树与最大最小原理509

17.3 串行的α-β搜索算法509

17.3.2 串行的α-β算法510

17.4 树机上的并行搜索算法512

17.4.1 树分裂算法512

17.4.2 主变量分裂算法514

17.5 MIMD模型上α-β搜索算法515

17.5.1 基本设计原理516

17.5.2 算法的形式描述518

17.5.3 算法讨论和分析521

习题523

参考文献524

第十八章 随机算法526

18.1.1 概率论的基本知识527

18.1 引言527

18.1.2 随机算法的模型及其度量530

18.1.3 随机算法的设计方法531

18.2 部分独立集533

18.2.1 有向环图534

18.2.2 平面图535

18.3 三角形平面细图中点的位置537

18.3.1 细图层次538

18.3.2 细图层次的构造算法538

18.4 模式匹配540

18.4.1 指纹函数541

18.4.2 串匹配544

18.4.3 二维数组的匹配546

18.5 多项式恒等的验证547

18.5.1 基本技术548

18.5.2 矩阵乘积的验证549

18.6 排序550

18.6.1 随机采样及随机快排序550

18.6.2 并行随机快排序算法551

18.6.3 快速随机并行排序算法553

18.7 最大匹配和完备匹配556

18.7.1 图的代数性质557

18.7.2 测试完备匹配存在的随机算法559

习题563

参考文献564

第十九章 VLSI计算理论567

19.1.1 VLSI电路模型568

19.1 VLSI电路模型和计算模型568

19.1.2 VLSI计算模型570

19.2 VLSI面-时下界理论572

19.2.1 几种基本的下界论点572

19.2.2 信息流和穿越序列574

19.3 典型计算图的结构布局法576

19.3.1 树的布局576

19.3.2 网孔和树网的布局578

19.3.3 洗牌交换网的布局578

19.3.4 立方环的布局581

19.3.5 蝶形网的布局583

19.4 典型计算图的布局下界584

19.4.1 树的布局下界584

19.4.2 树网的布局下界585

19.4.3 洗牌交换网的布局下界589

19.4.4 蝶形网的布局下界589

19.5 分治布局法590

19.5.1 分离集590

19.5.2 强分离集593

19.5.3 通道生成595

19.5.4 分治布局法596

19.6 VLSI布局理论599

19.6.1 平面图的分离定理599

19.6.2 图的交叉点数600

19.6.3 布局下界定理601

习题603

参考文献604

第二十章 模型与下界605

20.1 不同PRAM模型的相互模拟606

20,1.1 在PRAM-EREW上模拟PPRAM-CRCW606

20.1.2 在CPRAM-CRCW上模拟PPRAM-CRCW607

20.1.3 在APRAM-CRCW上模拟PPRAM-CRCW609

20.2 PRAM-CREW的下界610

20.2.1 理想的PRAM模型610

20.2.2 形式描述611

20.2.3 特定问题的下界614

20.3 PRAM-EREW的下界614

20.3.1 工具和方法614

20.3.2 主要下界615

20.4 PRAM-CRCW的下界617

20.4.1 PRAM-CRCW与无界扇入电路618

20.4.2 无界扇入电路的下界625

20.5 P-完全导论629

20.5.1 问题的可并行化629

20.5.2 NC类和RNC类632

20.5.3 P-完全问题范例636

20.5.4 小结644

习题645

参考文献646

附录A 复杂度表示及其符号648

A.1 大-O及其运算648

A.2 大-Ω和大-Θ649

A.3 小-o和小-ω649

附录B 算法复杂界一览表650

附录C 索引660