第一章　并行算法基础
  1.1　并行算法的硬件基础
   1.1.1　当代并行计算机体系结构
   1.1.2　并行计算机互连网络
  1.2　并行计算模型
   1.2.1　SIMD同步并行计算模型
   1.2.2　MIMD异步并行计算模型
   1.2.3　其他并行计算模型
  1.3　并行算法编程模型
   1.3.1　数据并行模型
   1.3.2　消息传递模型
   1.3.3　共享变量模型
  1.4　并行算法的一般概念
   1.4.1　并行算法的定义和分类
   1.4.2　并行算法的表达
   1.4.3　并行算法的复杂性度量
   1.4.4　并行算法的WT表示
   1.4.5　并行算法的同步和通信
  习题
  参考文献
 第二章　并行算法的基本设计技术
  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　Batcher归并和排序网络
   3.1.1　比较操作和[0,1]原理
   3.1.2　奇偶归并网络
   3.1.3　双调归并网络
   3.1.4　Batcher排序网络
  3.2　(m,n)-选择网络
   3.2.1　分组选择网络
   3.2.2　平衡分组选择网络
  3.3　AKS排序网络
   3.3.1　扩展图和划分网络
   3.3.2　部分排序算法
   3.3.3　完全排序算法
  习题
  参考文献
 第四章　排序和选择的同步算法
  4.1　Stone双调排序算法
   4.1.1　均匀洗牌函数及其性质
   4.1.2　Stone的观察及其计算模型
   4.1.3　Stone的并行排序算法
  4.2　Thompson和Kung双调排序算法
   4.2.1　处理器编号方式
   4.2.2　Thompson和Kung的观察
   4.2.3　Thompson和Kung的双调排序算法
  4.3　Preparata和Vuilemin双调排序算法
   4.3.1　算法原理
   4.3.2　流水线技术
   4.3.3　算法描述
  4.4　Akl并行k-选择算法
   4.4.1　算法原理及物理描述
   4.4.2　并行k-选择算法
   4.4.3　算法分析
  4.5　Valiant并行归并算法
   4.5.1　归并算法的基本原理
   4.5.2　k=pq」时Valiant归并
   4.5.3　k=rpq」时Valiant归并
  4.6　Hirschberg并行桶排序算法
   4.6.1　并行桶排序算法原理
   4.6.2　并行桶排序算法描述
  4.7　Preparata并行枚举排序算法
   4.7.1　枚举排序及其实现方法
   4.7.2　排序算法的设计和分析
  4.8　Cole并行归并排序算法
   4.8.1　使用覆盖和位序的归并方法
   4.8.2　Cole最佳排序算法
   4.8.3　算法的正确性证明及分析
  习题
  参考文献
 第五章　排序和选择的异步和分布式算法
  5.1　MIMD-CREW模型上的异步枚举排序算法
   5.1.1　算法原理和描述
   5.1.2　算法举例和分析
  5.2　MIMD-TC模型上的异步快排序算法
   5.2.1　算法原理和描述
   5.2.2　算法举例和分析
  5.3　分布式k-选择算法
   5.3.1　随机k-选择算法
   5.3.2　确定k-选择算法
  5.4　分布式求中值算法
   5.4.1　分布式中值
   5.4.2　分布式求中值算法
   5.5　分布式定序算法
   5.5.1　分布式计算模型
   5.5.2　分布式定序算法
   5.5.3　算法复杂度分析
  5.6　分布式排序算法
   5.6.1　模型和定义
   5.6.2　静态排序算法
   5.6.3　算法复杂度分析
  习题
  参考文献
 第六章　并行搜索
  6.1　单处理机上的搜索
   6.1.1　单处理机上的顺序搜索
   6.1.2　单处理机上有序表的对半搜索
  6.2　SIMD共享存储模型上有序表的搜索
   6.2.1　SIMD-EREW模型上的搜索
   6.2.2　SIMD-CREW模型上的搜索
  6.3　SIMD共享存储模型上随机序列的搜索
   6.3.1　SIMD-SM模型上的随机序列搜索算法描述
   6.3.2　SIMD-SM模型上的随机序列搜索算法分析
  6.4　树连接的SIMD模型上随机序列的搜索
   6.4.1　提问
   6.4.2　维护
  6.5　网孔连接的SIMD模型上随机序列的搜索
   6.5.1　提问
   6.5.2　维护
  6.6　MIMD共享存储模型上有序表的搜索
   6.6.1　AVL树及其顺序插入算法
   6.6.2　Ellis并行搜索和插入算法
  习题
  参考文献
 第七章　排列和组合
  7.1　产生排列的顺序算法
   7.1.1　排列和组合
   7.1.2　产生词典序的排列算法
   7.1.3　产生排列的计数方法
  7.2　产生组合的顺序算法
   7.2.1　产生词典序的组合算法
   7.2.2　产生组合的计数方法
  7.3　产生排列的并行算法
   7.3.1　串行排列算法的并行化
   7.3.2　自适应排列产生器
   7.3.3　全排列产生器
  7.4　产生组合的并行算法
   7.4.1　非自适应组合产生器
   7.4.2　自适应组合产生器
  习题
  参考文献
 第八章　数据传输与选路
  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　线路交换模式下的选路算法
  习题
  参考文献
 第九章　并行串匹配
  9.1　引言
   9.1.1　基本概念和研究现状
   9.1.2　基本定义和术语
  9.2　正文分析
   9.2.1　SIMD-CREW模型上的非周期串的匹配算法
   9.2.2　SIMD-CREW模型上的周期串的匹配算法
  9.3　模式预处理
   9.3.1　求WIT表的一般方法
   9.3.2　完全非周期串的WIT表求法
   9.3.3　SIMD-CREW模型上任意串的WIT表求法
   9.3.4　模式匹配算法的复杂度
  9.4　后缀树上的串匹配
   9.4.1　数字搜索树与后缀树
   9.4.2　子串的编码
   9.4.3　后缀树的构造
   9.4.4　后缀树上的并行串匹配
  习题
  参考文献
 第十章　表达式求值
  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　SIMD-CREW模型上的HU转换方法
  习题
  参考文献
 第十一章　上下文无关语言的并行识别与语法分析
  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　算法的具体实现
   11.3.3　树的压缩技术
   11.3.4　SIMD-CREW模型上括号语言的语法分析算法
  习题
  参考文献
 第十二章　矩阵运算
  12.1　矩阵转置
   12.1.1　单处理机上的矩阵转置算法
   12.1.2　SIMD-MC2模型上的矩阵转置
   12.1.3　SIMD-PS模型上的矩阵转置
   12.1.4　SIMD-EREW模型上的矩阵转置
  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　n阶线性代数方程组的求解
   13.1.1　SIMD-CREW模型上的Gauss-Jordan算法
   13.1.2　MIMD-CREW模型上的Gauss-Seidel算法
   13.1.3　紧耦合多处理机系统中LU算法的效率分析
  13.2　非线性方程的求根
   13.2.1　SIMD-CREW模型上的求根算法
   13.2.2　MIMD-CREW模型上的牛顿求根法
   13.2.3　Fibonacci分点法异步求根算法
  13.3　偏微分方程的求解
   13.3.1　偏微分方程的差分数值求解法
   13.3.2　SIMD-MC2模型上的PDE求解方法
  13.4　方阵的特征值与特征向量Jacobi求法
   13.4.1　对称方阵对角化方法
   13.4.2　SIMD-CC模型上的求特征值算法
  习题
  参考文献
 第十四章　FFT和卷积与滤波
  14.1　快速傅里叶变换
   14.1.1　离散傅里叶变换
   14.1.2　顺序的FFT算法
   14.1.3　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　算法原理
   15.1.2　p-深度优先搜索
   15.1.3　p-宽深优先搜索
   15.1.4　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　二维阵列上Levialdi分量标定算法
   16.1.3　二维阵列上递归的分量标定算法
  16.2　Hough变换
   16.2.1　二维图象的Hough变换
   16.2.2　二维阵列上象素Hough变换的计算
  16.3　近邻问题
  16.4　包含问题
   16.4.1　判断点在多边形中
   16.4.2　判断点在平面细图中
  16.5　相交问题
  16.6　构造问题
   16.6.1　求凸壳问题的下界
   16.6.2　顺序求凸壳算法
   16.6.3　SIMD-MT模型上求凸壳算法
   16.6.4　SIMD-EREW模型上求凸壳算法
  习题
  参考文献
 第十七章　组合搜索
  17.1　基于分治法的与树搜索
   17.1.1　搜索树
   17.1.2　SIMD模型上的与树搜索
  17.2　基于分枝限界法的或树搜索
   17.2.1　8-谜问题
   17.2.2　串行分枝限界算法
   17.2.3　用串行分枝限界法求TSP
   17.2.4　并行TSP算法
  17.3　串行的α-β搜索算法
   17.3.1　博弈树与最大最小原理
   17.3.2　串行的α-β算法
  17.4　树机上的并行搜索算法
   17.4.1　树分裂算法
   17.4.2　主变量分裂算法
  17.5　MIMD模型上α-β搜索算法
   17.5.1　基本设计原理
   17.5.2　算法的形式描述
   17.5.3　算法讨论和分析
  习题
  参考文献
 第十八章　随机算法
  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　P-完全导论
   20.5.1　问题的可并行化
   20.5.2　NC类和RNC类
   20.5.3　P-完全问题范例
   20.5.4　小结
  习题
  参考文献
 附录A　　复杂度表示及其符号
  A.1　大-O及其运算
  A.2　大-Ω和大-Θ
  A.3　小-o和小-ω
 附录B　算法复杂界一览表
 附录C　索引