顶部
收藏

并行算法的设计与分析(第3版)

“十一五”国家规划教材

作者:
陈国良
定价:
66.00元
ISBN:
978-7-04-026436-4
版面字数:
1010.000千字
开本:
16开
全书页数:
813页
装帧形式:
平装
重点项目:
“十一五”国家规划教材
出版时间:
2009-08-07
读者对象:
高等教育
一级分类:
计算机/教育技术类
二级分类:
计算机科学与技术专业课程

  第3版在修订版的基础上进行了大幅度的修订,新增加3章、重写3章,改写8章。本书系统深入地讨论了计算机领域中诸多计算问题的并行算法的设计和分析方法。在着重介绍各种并行计算模型上的常用和典型的并行算法的同时,也力图反映本学科的最新成就、学科前沿和发展趋势。
  全书共分二十章,包括基础篇4章(绪论、设计技术、前缀计算、排序和选择网络),并行算法篇9章(排序和选择算法、分布式算法、并行搜索、选路算法、串匹配、表达式求值、上下文无关语言、图论算法、计算几何),数值并行算法篇3章(矩阵运算、数值计算、快速傅氏变换),理论篇4章(组合搜索、随机算法、VLSI计算理论、并行计算理论)。
  本书取材丰富,内容系统深入,可作为高等学校计算机及其他信息类有关专业高年级本科生和研究生的教材,也可供从事计算机科学理论和并行算法研究的科技人员阅读参考。
  本书初版曾获1994年度教育部高等学校优秀教材一等奖和1997年度国家级教学成果二等奖。
  • 第一章 绪论
    • 1.1 引言
    • 1.2 并行算法的硬件基础
      • 1.2.1 并行计算机体系结构
      • 1.2.2 并行计算机互连网络
      • 1.2.3 并行计算机存储组织
    • 1.3 并行计算模型
      • 1.3.1 模型的定义、功能和分类
      • 1.3.2 共享存储模型
      • 1.3.3 分布存储模型
      • 1.3.4 层次存储模型
      • 1.3.5 其他并行计算模型
    • 1.4 并行算法的基础知识
      • 1.4.1 并行算法的定义
      • 1.4.2 并行算法的表达
      • 1.4.3 并行算法的复杂性
      • 1.4.4 并行算法的同步和通信
    • 1.5 并行算法的性能分析
      • 1.5.1 算法的执行速度
      • 1.5.2 算法使用的处理器数
      • 1.5.3 并行算法的WT表示
      • 1.5.4 并行算法的通信成本
    • 习题
    • 参考文献
  • 第二章 设计技术
    • 2.1 平衡树方法
      • 2.1.1 求取最大值
      • 2.1.2 计算前缀和
    • 2.2 倍增技术
      • 2.2.1 表序问题的计算
      • 2.2.2 求森林的根
    • 2.3 分治策略
      • 2.3.1 SIMD模型上分治算法的描述
      • 2.3.2 SIMD共享存储模型上的FFT算法
    • 2.4 划分原理
      • 2.4.1 归并原理
      • 2.4.2 划分算法与归并算法
    • 2.5 流水线技术
      • 2.5.1 一维阵列上的流水线归并排序原理
      • 2.5.2 一维阵列上的流水线归并排序算法
    • *2.6 加速级联策略
      • 2.6.1 常数时间求最大值算法
      • 2.6.2 双对数时间算法
      • 2.6.3 加速级联算法
    • 2.7 破对称技术
      • 2.7.1 基本着色算法
      • 2.7.2 快速3-着色算法
      • 2.7.3 最优3-着色算法
    • 习题
    • 参考文献
  • 第三章 前缀计算
    • 3.1 引言
      • 3.1.1 前缀计算的定义
      • 3.1.2 前缀计算的应用
    • 3.2 并行前缀计算算法
      • 3.2.1 组合网络上的前缀计算
      • 3.2.2 互连网络上的前缀计算
      • 3.2.3 PRAM模型上的前缀计算
    • *3.3 线性递归方程求解
      • 3.3.1 平易线性递归方程求解算法
      • 3.3.2 更优线性递归方程求解算法
    • 3.4 排序
      • 3.4.1 基排序
      • 3.4.2 快排序
    • *3.5 最大和子序列
      • 3.5.1 简单串行算法
      • 3.5.2 易于并行化的串行算法
      • 3.5.3 并行算法
    • 习题
    • 参考文献
  • 第四章 排序和选择网络
    • 4.1 Batcher归并和排序网络
      • 4.1.1 比较操作和[0,1]原理
      • 4.1.2 奇偶归并网络
      • 4.1.3 双调归并网络
      • 4.1.4 Batcher排序网络
    • 4.2 (m,n)-选择网络
      • 4.2.1 分组选择网络
      • 4.2.2 平衡分组选择网络
    • *4.3 AKS排序网络
      • 4.3.1 扩展器
      • 4.3.2 对分器
      • 4.3.3 分离器
      • 4.3.4 AKS排序网络的构造及分析
    • 习题
    • 参考文献
  • 第五章 排序和选择算法
    • 5.1 Stone双调排序算法
      • 5.1.1 均匀洗牌函数及其性质
      • 5.1.2 Stone的观察及其计算模型
      • 5.1.3 Stone的并行排序算法
    • 5.2 Thompson和Kung双调排序算法
      • 5.2.1 处理器编号方式
      • 5.2.2 Thompson和Kung的观察
      • 5.2.3 Thompson和Kung的双调排序算法
    • *5.3 Preparata和Vuilemin双调排序算法
      • 5.3.1 算法原理
      • 5.3.2 流水线技术
      • 5.3.3 算法描述
    • 5.4 Akl并行k-选择算法
      • 5.4.1 算法原理及物理描述
      • 5.4.2 并行k-选择算法
      • 5.4.3 算法分析
    • 5.5 Valiant并行归并算法
      • 5.5.1 归并算法的基本原理
      • 5.5.2 k=pq」时Valiant归并
      • 5.5.3 k=rpq」时Valiant归并
    • *5.6 Hirschberg并行桶排序算法
      • 5.6.1 并行桶排序算法原理
      • 5.6.2 并行桶排序算法描述
    • 5.7 Preparata并行枚举排序算法
      • 5.7.1 枚举排序及其实现方法
      • 5.7.2 排序算法的设计和分析
    • *5.8 Cole并行归并排序算法
      • 5.8.1 使用覆盖和位序的归并方法
      • 5.8.2 Cole最佳排序算法
      • 5.8.3 算法的正确性证明及分析
    • 5.9 MIMD-CREW模型上的异步枚举排序算法
      • 5.9.1 算法原理和描述
      • 5.9.2 算法举例和分析
    • 5.10 MIMD-TC模型上的异步快排序算法
      • 5.10.1 算法原理和描述
      • 5.10.2 算法举例和分析
    • 习题
    • 参考文献
  • 第六章 分布式算法
    • 6.1 分布式算法概述
      • 6.1.1 分布式算法特点
      • 6.1.2 计算模型
      • 6.1.3 复杂性度量
    • 6.2 构造生成树算法
      • 6.2.1 广播和敛播算法
      • 6.2.2 构造生成树
      • 6.2.3 构造深度优先生成树
      • 6.2.4 不指定根构造生成树
      • 6.2.5 最小生成树
    • 6.3 环上选举算法
      • 6.3.1 LCR算法
      • 6.3.2 改进算法
    • 6.4 分布式k-选择算法
      • 6.4.1 随机k-选择算法
      • 6.4.2 确定k-选择算法
      • 6.4.3 分布式求中值算法
    • *6.5 定序与排序
      • 6.5.1 定序算法
      • 6.5.2 排序算法
    • 习题
    • 参考文献
  • *第七章 并行搜索
    • 7.1 单处理机上的搜索
      • 7.1.1 单处理机上的顺序搜索
      • 7.1.2 单处理机上有序表的对半搜索
    • 7.2 SIMD共享存储模型上有序表的搜索
      • 7.2.1 SIMD-EREW模型上的搜索
      • 7.2.2 SIMD-CREW模型上的搜索
    • 7.3 SIMD共享存储模型上随机序列的搜索
      • 7.3.1 SIMD-SM模型上的随机序列搜索算法描述
      • 7.3.2 SIMD-SM模型上的随机序列搜索算法分析
    • 7.4 树连接的SIMD模型上随机序列的搜索
      • 7.4.1 提问
      • 7.4.2 维护
    • 7.5 网孔连接的SIMD模型上随机序列的搜索
      • 7.5.1 提问
      • 7.5.2 维护
    • 7.6 MIMD共享存储模型上有序表的搜索
      • 7.6.1 AVL树及其顺序插入算法
      • 7.6.2 Ellis并行搜索和插入算法
    • 习题
    • 参考文献
  • 第八章 选路算法
    • 8.1 引言
    • 8.2 贪心选路算法
      • 8.2.1 一维阵列上的贪心选路算法
      • 8.2.2 二维阵列上贪心选路算法的分析
      • 8.2.3 蝶形网络上的贪心选路算法
    • 8.3 随机和确定选路算法
      • 8.3.1 二维阵列上的随机选路算法
      • 8.3.2 超立方网络上的随机选路算法
      • 8.3.3 二维阵列上的确定选路算法
    • 8.4 数据的分布和集中
      • 8.4.1 数据的分布
      • 8.4.2 多到一选路算法
    • *8.5 线路交换模式下的选路算法
      • 8.5.1 阻塞网络中的竞争分析
      • 8.5.2 阻塞网络中的自选路算法
      • 8.5.3 可重排网络中的中级选路算法
    • 习题
    • 参考文献
  • 第九章 串匹配
    • 9.1 字符串精确匹配并行算法
      • 9.1.1 KMP串匹配顺序算法
      • 9.1.2 分布存储系统上精确串匹配并行算法
      • 9.1.3 基于比较指纹函数值的串匹配算法及其并行化
      • *9.1.4 串匹配的平均时间复杂度分析
      • *9.1.5 后缀树上的串匹配
    • 9.2 多模式匹配并行算法
      • 9.2.1 多模式匹配问题
      • 9.2.2 可重构网孔机器上多模式匹配并行算法
    • 9.3 允许k-差别的近似串匹配并行算法
      • 9.3.1 编辑距离与允许k-差别的近似串匹配问题
      • 9.3.2 PRAM模型上允许k-差别的近似串匹配并行算法
    • 9.4 允许k-误配的近似串匹配并行算法
      • 9.4.1 汉明距离与允许k-误配的近似串匹配问题
      • 9.4.2 LARPBS计算模型及其基本数据移动操作
      • 9.4.3 LARPBS模型上允许k-误配的近似串匹配并行算法
    • *9.5 最长公共子序列查找并行算法
      • 9.5.1 求解最长公共子序列问题的顺序算法
      • 9.5.2 BSR模型上求解最长公共子序列问题的并行算法
      • 9.5.3 心动阵列处理器结构上求解最长公共子序列问题的并行算法
    • 习题
    • 参考文献
  • *第十章 表达式求值
    • 10.1 构造表达式树
      • 10.1.1 全括号表达式的表达式树
      • 10.1.2 表达式树上的括号操作
      • 10.1.3 计算match(i)的并行算法
    • 10.2 填充游戏用于表达式求值
      • 10.2.1 二叉树上的填充游戏
      • 10.2.2 填充游戏用于算术表达式求值
    • 10.3 最优的并行表达式求值算法
    • 10.4 一般表达式求值算法
      • 10.4.1 一般表达式与直线程序
      • 10.4.2 仅有乘法操作符的dag的计算
      • 10.4.3 仅有加法操作符的dag的计算
      • 10.4.4 gbdag图和直线程序的计算
    • 10.5 正则表达式到确定自动机的最优并行转换
      • 10.5.1 基本概念和术语
      • 10.5.2 正则表达式到非确定有限自动机的HU转换方法
      • 10.5.3 有限自动机确定化并行算法
      • 10.5.4 确定自动机的最小化并行算法
    • 习题
    • 参考文献
  • *第十一章 上下文无关语言
    • 11.1 一般的上下文无关语言的并行识别
      • 11.1.1 基本概念和术语
      • 11.1.2 残缺部分语法树及其合成规则
      • 11.1.3 共享存储模型上歧义性上下文无关语言并行识别算法
    • 11.2 一般上下文无关语言的并行语法分析
      • 11.2.1 基本概念和算法原理
      • 11.2.2 SIMD-CREW模型上一般上下文无关语言的语法分析算法
    • 11.3 任意上下文无关语言的并行语法分析
      • 11.3.1 基本概念与算法原理
      • 11.3.2 SIMD-LC模型上任意上下文无关语言的并行语法分析算法
    • 11.4 括号语言的最优并行识别和语法分析
      • 11.4.1 基本概念和算法原理
      • 11.4.2 算法的具体实现
      • 11.4.3 树的压缩技术
      • 11.4.4 SIMD-CREW模型上括号语言的语法分析算法
    • 习题
    • 参考文献
  • 第十二章 矩阵运算
    • 12.1 矩阵转置
      • 12.1.1 单处理机上的矩阵转置算法
      • 12.1.2 SIMD-MC2模型上的矩阵转置
      • 12.1.3 SIMD-PS模型上的矩阵转置
      • 12.1.4 SIMD-CC模型上的矩阵转置
    • 12.2 矩阵相乘
      • 12.2.1 单处理机上的矩阵相乘
      • 12.2.2 SIMD-MC2模型上的矩阵乘法
      • 12.2.3 SIMD-CC模型上的矩阵乘法
      • 12.2.4 MIMD机器上的矩阵乘法
    • *12.3 矩阵和向量相乘
      • 12.3.1 树连接的机器上的矩阵和向量乘法
      • 12.3.2 树网结构上的矩阵和向量乘法
    • 12.4 心动阵列上的矩阵运算
      • 12.4.1 二维六角形阵列上的矩阵乘法
      • 12.4.2 二维六角形阵列上方阵的LU分解
      • *12.4.3 六角形阵列上的方阵求逆
      • 12.4.4 一维阵列上求解三角形线性系
    • 习题
    • 参考文献
  • 第十三章 数值计算
    • 13.1 三对角方程组的求解
      • 13.1.1 三对角方程组直接求解法
      • 13.1.2 三对角方程组奇偶归约求解法
    • 13.2 n阶线性方程组的求解
      • 13.2.1 SIMD-CREW模型上的Gauss-Jordan算法
      • 13.2.2 MIMD-CREW模型上的Gauss-Seidel算法
      • *13.2.3 紧耦合多处理机系统中LU算法的效率分析
    • *13.3 非线性方程的求根
      • 13.3.1 SIMD-CREW模型上的求根算法
      • 13.3.2 MIMD-CREW模型上的牛顿求根法
      • *13.3.3 Fibonacci分点法异步求根算法
    • 13.4 偏微分方程的差分求解
      • 13.4.1 偏微分方程的差分数值求解法
      • 13.4.2 SIMD-MC2模型上的PDE求解方法
    • 13.5 方阵的特征值与特征向量Jacobi方法
      • 13.5.1 对称方阵对角化方法
      • 13.5.2 SIMD-CC模型上的求特征值算法
    • 习题
    • 参考文献
  • 第十四章 快速傅氏变换
    • 14.1 快速傅里叶变换
      • 14.1.1 顺序的FFT算法
      • *14.1.2 FFT应用于多项式乘积
    • 14.2 DFT直接并行计算法
      • 14.2.1 SIMD模型上系数矩阵的计算
      • 14.2.2 SIMD-MT模型上的DFT算法
    • 14.3 并行FFT算法
      • 14.3.1 SIMD-MC2型上的FFT算法
      • 14.3.2 SIMD-BF模型上的FFT算法
      • *14.3.3 SIMD-PS模型上的FFT计算
      • 14.3.4 SIMD-CC模型上的FFT计算
      • *14.3.5 一维心动阵列上的DFT计算
    • *14.4 心动阵列上的卷积与滤波计算
      • 14.4.1 一维卷积在线性阵列上的实现
      • 14.4.2 无限冲激滤波在线性阵列上的实现
      • 14.4.3 中值滤波在线性阵列上的实现习题
    • 参考文献
  • 第十五章 图论算法
    • 15.1 图的并行搜索
      • 15.1.1 p-深度优先搜索
      • 15.1.2 p-宽深优先搜索
      • 15.1.3 p-宽度优先搜索
    • 15.2 图的传递闭包
      • 15.2.1 传递闭包问题
      • 15.2.2 SIMD-CC模型上的传递闭包算法
      • 15.2.3 二维心动阵列上的传递闭包算法
    • 15.3 图的连通分量
      • 15.3.1 SIMD-CC模型上的连通分量算法
      • 15.3.2 SIMD-SM模型上的连通分量算法
      • 15.3.3 SIMD-TC模型上的连通分量算法
      • 15.3.4 SIMD-MT模型上的连通分量算法
    • 15.4 图的最短路径
      • 15.4.1 所有顶点对间的最短路径算法
      • *15.4.2 MIMD-SM模型上单源最短路径算法
    • 15.5 图的最小生成树
      • 15.5.1 SIMD-EREW模型上最小生成树算法
      • *15.5.2 MIMD-SM模型上最小生成树算法
      • 15.5.3 树机模型上最小生成树算法
    • *15.6 图的着色
      • 15.6.1 二分图的边着色算法
      • 15.6.2 外平面图最优顶点着色
      • 15.6.3 外平面图最优边着色算法
      • 15.6.4 Halin图最优边着色算法
    • 习题
    • 参考文献
  • 第十六章 计算几何
    • *16.1 判定问题
      • 16.1.1 近邻问题
      • 16.1.2 相交问题
      • 16.1.3 包含问题
    • 16.2 构造问题
      • 16.2.1 求凸壳问题的下界
      • 16.2.2 顺序求凸壳算法
      • 16.2.3 SIMD-MT模型上的求凸壳算法
      • 16.2.4 SIMD-EREW模型上的求凸壳算法
    • 16.3 Voronoi图问题
      • 16.3.1 基本概念
      • 16.3.2 构造Voronoi图的串行分治算法
      • 16.3.3 超立方模型上构造Voronoi图算法
      • 16.3.4 SIMD-CREW模型上构造Voronoi图算法
    • 16.4 平面点集的三角剖分
      • 16.4.1 基本概念
      • 16.4.2 Delaunay三角剖分串行算法
      • 16.4.3 Delaunay三角剖分并行算法
    • 习题
    • 参考文献
  • 第十七章 组合搜索
    • *17.1 产生排列的算法
      • 17.1.1 产生词典序的排列算法
      • 17.1.2 串行排列算法的并行化
      • 17.1.3 自适应排列产生器
    • *17.2 产生组合的算法
      • 17.2.1 产生组合的顺序算法
      • 17.2.2 产生组合的并行算法
    • 17.3 分支限界法的搜索
      • 17.3.1 8-谜问题
      • 17.3.2 串行分支限界算法
      • 17.3.3 用串行分支限界法求TSP
      • 17.3.4 并行TSP算法
    • 17.4 串行的α-β搜索算法
      • 17.4.1 博弈树与最小最大原理
      • 17.4.2 串行的α-β算法
      • 17.4.3 MIMD模型上α-β搜索算法
    • 17.5 动态规划
      • 17.5.1 矩阵链乘问题
      • 17.5.2 最短路径问题
      • 17.5.3 0/1背包问题
    • 习题
    • 参考文献
  • 第十八章 随机算法
    • 18.1 引言
      • 18.1.1 概率论的基本知识
      • 18.1.2 随机算法的模型及其度量
      • 18.1.3 随机算法的设计方法
    • 18.2 部分独立集
      • 18.2.1 有向环图
      • 18.2.2 平面图
    • 18.3 三角形平面细图中点的位置
      • 18.3.1 细图层次
      • 18.3.2 细图层次的构造算法
    • *18.4 模式匹配
      • 18.4.1 指纹函数
      • 18.4.2 串匹配
      • 18.4.3 二维数组的匹配
    • 18.5 多项式恒等的验证
      • 18.5.1 基本技术
      • 18.5.2 矩阵乘积的验证
    • 18.6 排序
      • 18.6.1 随机采样与随机快排序
      • 18.6.2 并行随机快排序算法
      • 18.6.3 快速随机并行排序算法
    • *18.7 最大匹配和完备匹配
      • 18.7.1 图的代数性质
      • 18.7.2 测试完备匹配存在的随机算法
    • 习题
    • 参考文献
  • 第十九章 VLSI计算理论
    • 19.1 VLSI电路模型和计算模型
      • 19.1.1 VLSI电路模型
      • 19.1.2 VLSI计算模型
    • *19.2 VLSI面-时下界理论
      • 19.2.1 几种基本的下界论点
      • 19.2.2 信息流和穿越序列
    • 19.3 典型计算图的结构布局法
      • 19.3.1 树的布局
      • 19.3.2 网孔和树网的布局
      • 19.3.3 洗牌交换网的布局
      • 19.3.4 立方环的布局
      • 19.3.5 蝶形网的布局
    • 19.4 典型计算图的布局下界
      • 19.4.1 树的布局下界
      • 19.4.2 树网的布局下界
      • 19.4.3 洗牌交换网的布局下界
      • 19.4.4 蝶形网的布局下界
    • 19.5 分治布局法
      • 19.5.1 分离集
      • 19.5.2 强分离集
      • 19.5.3 通道生成
      • *19.5.4 分治布局法
    • *19.6 VLSI局理论
      • 19.6.1 平面图的分离定理
      • 19.6.2 图的交叉点数
      • 19.6.3 布局下界定理
    • 习题
    • 参考文献
  • 第二十章 并行计算理论
    • 20.1 不同PRAM模型的相互模拟
      • 20.1.1 在PRAM-EREW上模拟PPRAM-CRCW
      • *20.1.2 在CPRAM-CRCW上模拟PPRAM-CRCW
      • *20.1.3 在APRAM-CRCW上模拟PPRAM-CRCW
    • 20.2 PRAM-CREW的下界
      • 20.2.1 理想的PRAM型
      • 20.2.2 形式描述
      • 20.2.3 特定问题的下界
    • *20.3 PRAM-EREW的下界
      • 20.3.1 工具和方法
      • 20.3.2 主要下界
    • *20.4 PRAM-CRCW的下界
      • 20.4.1 PRAM-CRCW与无界扇入电路
      • 20.4.2 无界扇入电路的下界
    • *20.5 并行复杂性理论
      • 20.5.1 串行复杂性理论简介
      • 20.5.2 问题的可并行化
      • 20.5.3 NC类和RNC类
      • 20.5.4 P-完全问题范例
      • 20.5.5 小结
    • 习题
    • 参考文献
  • 附录A 复杂度表示及其符号
    • A.1 大-O及其运算
    • A.2 大-Ω和大-Θ
    • A.3 小-o和小-ω
  • 附录B 算法复杂界一览表
  • 附录C 专业术语中英文对照表及
  • 索引

相关图书