并行算法 排序和选择pdf电子书版本下载

点此进入-本书在线PDF格式电子书下载【推荐-云解压-方便快捷】直接下载PDF格式图书。移动端-PC端通用
种子下载[BT下载速度快] 温馨提示：（请使用BT下载软件FDM进行下载）软件下载地址页 直链下载[便捷但速度慢]   [在线试读本书]   [在线获取解压码]

并行算法 排序和选择PDF格式电子书版下载

下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。

建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如 BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！

（文件页数 要大于 标注页数，上中下等多册电子书除外）

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

第一章 并行计算机与并行计算 1

1.1 并行计算机及其分类 1

1.1.1 并行计算机的发展 1

1.1.2 并行计算机简介 2

1.1.3 并行计算机的分类 4

1.2 处理器的互连方式 5

1.2.1 一维线性连接 5

1.2.2 网孔结构 5

1.2.3 树形结构 6

1.2.4 树网结构 7

1.2.5 金字塔结构 7

1.2.6 超立方连接 8

1.2.8 立方环连接 9

1.2.7 q-维网格连接 9

1.2.9 洗牌交换网络 10

1.2.10 蝶形结构 11

1.3 并行计算模型 12

1.3.1 不同互连结构的SIMD模型 13

1.3.2 共享存贮的SIMD模型 14

1.3.3 MIMD并行计算模型 15

1.4 并行计算的若干理论问题 15

1.4.1 Grosch定律 15

1.4.2 Minsky猜想 15

1.4.3 Amdahl定律 16

1.4.4 构造高性能并行计算机的策略 16

1.5 并行算法的一般概念 17

1.5.1 并行算法的定义、分类和术语 17

1.5.2 并行算法的复杂性 18

1.5.3 并行算法的表达 20

参考文献 21

第二章 并行算法的设计 23

2.1 引言 23

2.2 SIMD-IN机器上开发的并行算法 24

2.2.1 SIMD-CC机器上的求和计算 24

2.2.2 SIMD-SE机器上的求和计算 26

2.2.3 SIMD-MC2机器上的求和计算 27

2.3 MIMD机器上开发的并行算法 27

2.3.1 MIMD算法的种类 28

2.3.2 限制加速的因素 29

2.3.3 MIMD算法复杂性分析 31

2.4 MIMD机器上的进程通信和同步 32

2.4.1 并发性表示 32

2.4.2 使用共享变量同步 33

2.4.3 通过传递信息的低级同步 34

2.4.4 远程过程调用 35

2.4.5 并发程序设计语言的分类 36

2.5 MIMD机器中的死锁和任务调度 37

2.5.1 死锁 37

2.5.2 确定性调度模式 37

2.5.3 非确定性调度模式 38

参考文献 39

第三章 递归方程的求解 40

3.1 分治法 40

3.2 递归式展开法 41

3.3 齐次递归方程的解 41

3.4 齐次方程 43

3.5 非齐次方程 44

3.6.1 因子求和 47

3.6 变换术 47

3.6.2 域变换 49

3.7 猜测解 51

参考文献 52

第四章 排序和选择网络 53

4.1 Batcher归并和排序网络 53

4.1.1 比较器网络和［0.1］原理 53

4.1.2 奇偶归并网络 56

4.1.3 双调归并网络 59

4.1.4 Batcher排序网络 62

4.2 布尔排序网络和枚举排序网络 66

4.2.1 布尔对称函数及其性质 66

4.2.2 布尔对称函数在分析和综合排序网络时的应用 68

4.2.3 Muller和Preparata的枚举排序网络 72

4.3.1 AKS排序网络的基本原理 74

4.3 AKS排序网络 74

4.3.2 扩展图、ε-对分和ε-准排序 75

4.3.3 寄存器的指派和划分 77

4.3.4 AKS算法的形式描述 78

4.4 分组选择网络 79

4.4.1 选择问题和选择网络 79

4.4.2 分组原理在选择算法中的应用 80

4.4.3 分组选择网络 81

4.4.4 平衡分组选择网络 83

4.5 递归选择网络 86

4.5.1 分离原理在递归算法中的应用 86

4.5.2 选择网络上、下界的研究 87

4.5.3 递归选择网络 89

参考文献 92

5.1.1 奇偶转置排序算法 94

第五章 固定连接的SIMD机器上的并行排序和选择算法 94

5.1 一维线性阵列上的并行排序算法 94

5.1.2 归拆(Merge-Splitting)排序 96

5.1.3 流水线机上的归并排序 98

5.2 树机上的并行排序算法 100

5.2.1 抽取最小值排序法 100

5.2.2 桶排序和归并 102

5.2.3 中值排序法 106

5.3 混洗连接的SIMD机器上的双调排序算法 108

5.3.1 均匀洗牌函数及其性质 108

5.3.2 Stone的观察及其计算模型 109

5.3.3 Stone的并行排序算法 111

5.4 网孔连接的SIMD机器上的双调排序算法 112

5.4.1 处理器编号方式 113

5.4.2 Thompson和Kung的观察 114

5.4.3 Tkompson和Kung的双调排序算法 115

5.5 立方连接的SIMD机器上的双调排序算法 117

5.5.1 Siegel的观察 118

5.5.2 双调归并在SIMD-CC机器上的实现 118

5.5.3 双调排序在SIMD-CC机器上的实现 119

5.6 SIMD机器上实现的双调选择算法 120

5.6.1 双调选择网络 120

5.6.2 对双调选择网络之观察 122

5.6.3 SIMD机器上实现的双调选择算法 123

5.7 SIMD-IN机器上的数据传输 124

5.7.1 互连网络中的数据选路 125

5.7.2 用排序网络实现选路 125

5.7.3 SIMD-IN机器上的数据传播 126

参考文献 128

第六章 共享存贮的SIMD机器上的并行排序和选择算法 129

6.1 引言 129

6.2 Akl的并行算法 130

6.2.1 并行h-选择算法 130

6.2.2 并行快排序算法 133

6.3 Valiant归并和排序算法 136

6.3.1 求极大值的下界 136

6.3.2 Valiant并行归并 137

6.3.3 Valiant并行排序 139

6.4 Hirschberg排序算法 140

6.4.1 并行桶排序算法 140

6.4.2 快速并行排序 143

6.5 Preparata排序算法 145

6.5.1 枚举排序及其实现方法 145

6.5.2 排序算法的设计和分析 146

6.6 SIMD-SM机器上实现的归并选择算法 148

6.6.1 归并选择原理 149

6.6.2 归并选择算法的设计和分析 149

6.7 Cole归并排序算法 151

6.7.1 Cole算法原理 152

6.7.2 CREW模型上的算法描述 152

6.7.3 CREW模型上的算法分析 155

参考文献 156

第七章 MIMD机器上的并行排序和选择算法 157

7.1 引言 157

7.2 MIMD-CREW模型上的枚举异步排序 158

7.2.1 算法原理 158

7.2.2 算法的形式描述 158

7.3.1 算法原理 159

7.2.3 算法分析 159

7.3 MIMD-TC模型上的异步快排序 159

7.3.2 算法的形式描述 160

7.3.3 算法分析 162

7.4 分布式选择算法 163

7.4.1 分布式k-选择算法 163

7.4.2 分布式多项选择算法 166

7.4.3 分布式求中值算法 167

7.4.4 分布式求极值算法 169

7.5 分布式定序算法 173

7.5.1 计算模型 173

7.5.2 分布式定序算法 174

7.5.3 算法复杂性分析 176

7.6.2 各场点只有一个元素(|X1|=1)时的分布式排序算法 177

7.6.1 模型和定义 177

7.6 分布式静态排序算法 177

7.6.3 基于分布式k-选择的分布式排序算法 178

7.6.4 基于分布式多项选择的分布式排序算法 179

7.7 分布式动态排序算法 180

7.7.1 问题描述 180

7.7.2 分布式动态排序算法 182

7.7.3 算法复杂性分析 182

参考文献 183

第八章 并行外排序 185

8.1 引言 185

8.2 两路磁带外排序 185

8.2.1 树机上的归并外排序算法 185

8.2.2 算法8.1在磁带机上的实现 186

8.3.1 一维线性阵列上的外排序算法 188

8.3 流水线式磁带外排序 188

8.3.2 算法8.2在磁带机上的实现 190

8.4 并行磁盘排序 194

参考文献 197

第九章 VLSI计算模型上的排序算法 198

9.1 VLSI计算模型和面-时下界 198

9.1.1 VLSI计算模型 198

9.1.2 时-空论 199

9.1.3 面-时下界 200

9.2 常用电路结构图的布局 202

9.2.1 树的布局 202

9.2.2 网孔和树网的布局 203

9.2.3 洗牌-交换网的布局 204

9.2.4 CCC的布局 205

9.3.1 平面图分离定理 206

9.2.5 蝶形结构的布局 206

9.3 VLSI布局理论 206

9.3.2 分治布局法 207

9.3.3 布局的下界理论 208

9.4 VLSI计算模型上的几种排序算法 208

9.4.1 基本的VLSI电路模块 208

9.4.2 Batcher排序网络的VLSI实现 209

9.4.3 SIMD-SE上双调排序的VLSI实现 210

9.4.4 SIMD-MC2上奇偶归并排序的VLSI实现 210

9.4.5 树网结构上的枚举排序算法 212

9.4.6 CCC结构上的双调排序算法 213

参考文献 217

第十章 选择和排序的概率并行算法 218

10.1 引言 218

10.2.1 概率判定树和串行选择算法 219

10.2 并行判定树模型上的概率k-选择算法 219

10.2.2 概率并行k-选择算法描述 222

10.2.3 概率并行k-选择算法分析 223

10.3 并行判定树模型上的概率排序算法 226

10.4 并行RAM模型上的概率排序算法 227

10.4.1 PRAM-CREW模型上的概率排序算法描述 228

10.4.2 PRAM-CREW模型上的概率排序算法分析 231

参考文献 235

附录A 并行排序算法的下界 236

A.1 排序问题的一组基本下界 236

A.2 基于比较的并行排序算法之下界 237

A.3 q-维网格上的并行排序之下界 237

A.4 树机上的并行排序之下界 238

参考文献 239

B.1.1 整数函数及其等式 240

附录B 数学知识 240

B.1 数和不等式 240

B.1.2 数列求和 241

B.1.3 代数不等式 241

B.2 阶乘及其应用 242

B.2.1 和与积 242

B.2.2 阶乘 243

B.2.3 二项式系数 244

B.3 调和数、斐波那契数和渐近表示 246

B.3.1 调和数 246

B.3.2 斐波那契数 246

B.3.3 渐近表示 247

B.4 数学归纳法 248

参考文献 248