第一章 绪论
  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 专业术语中英文对照表及
 索引