并行算法导论

定　价：¥35.00

作　者：	（印）C.Xavier，（美）S.S.Iyengar著；张云泉，陈英译；张云泉译
出版社：	机械工业出版社
丛编项：	计算机科学丛书
标　签：	并行计算

购买这本书可以去

ISBN：	9787111133902	出版时间：	2004-02-01	包装：	简裝本
开本：	26cm	页数：	263	字数：

内容简介

　　并行计算的广泛采用和现今应用问题的日趋复杂，使得并行算法的设计和分析日益引起人们的兴趣。这本书满足了并行算法的入门者，特别是计算机科学、数学和工程专业的大学生的需求。本书系统地讲述最新的设计技术，并对所描述的每一个算法提供分析和详细的实现细节。它的主要内容包括并行计算的基础，树和图的并行算法，排序、搜索和合并的并行算法以及数值算法等。本书的特色在于： ●用清晰简单的术语讲述基本的概念 ●提供大量的例子加强学生的理解 ●展示怎样为计算机科学、数学和工程的典型问题开发并行算法 ●对新的设计技术作扩展性的阐述 ●在PRAM模型环境中讨论并行算法 ●在章节后面附有大量的习题和关于并行计算的参考文献本书对并行算法作了入门级的介绍，用四部分讲解并行算法的设计过程和最新的设计方法，并对书中所描述的每一个算法提供分析和详细的实现细节。全书包括并行计算的基础，树和图的并行算法，排序、搜索和合并的并行算法及数值算法等内容。其中重点强调了图模型算法。在章节后面附有大量的习题和关于并行计算的参考文献。本书可以作为大学计算机科学与工程专业高年级学生的并行算法课教材。对于计算机科学、数学和工程领域的研究生、科研工作者和工程师，也是一本不可多得的参考书。

作者简介

　　C.Xavier执教于印度Palayamkottai圣Xavier学院的计算机科学系。他在并行算法领域已经发表了大量的论文，并出版了十多部计算机机科学教材。张云泉，男，1995年获北京理工大学计算机科学技术系计算机应用专业工学学士学位；2000年获中科院软件所计算机软件与理论专业工学博士学位（硕、博连续）。现为中科院软件所并行计算实验室副研究员，中科院计算机科学开放重点实验兼职副研究员，中科院软件所并行计算实际室副主任，中国软件行业协会数学软件分会秘书长。

图书目录

出版者的话
专家指导委员会
译者序
前言
致谢
作者简介
第一部分并行计算基础
第0章引言 1
0.1 计算机简介 1
0.2 并行计算机 5
0.3 并行处理的概念 6
0.4 高性能计算机 8
0.5 本书的结构和内容 9
参考文献 10
第1章并行计算要素 11
1.1 并行的层次 11
1.2 并行计算机分类 12
1.2.1 Flynn分类 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.4 网格网络 26
1.3.5 金字塔网络 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.8 团覆盖 65
2.3.9 交图 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章并行算法设计环境 76
3.1 二叉树设计环境 76
3.2 二倍增长 79
3.3 指针跳转 79
3.4 分而治之 82
3.5 划分 83
3.6 小结 86
参考文献 86
习题 86
第4章简单并行算法 88
4.1 向量内积 88
4.2 矩阵乘法 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章微分与积分 228
11.1 微分 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章微分方程 239
12.1 欧拉公式 239
12.2 偏微分方程 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