并行算法的设计与分析

第一章 绪论

1.1 引言

1.2 并行算法的硬件基础

1.3 并行计算模型

1.4 并行算法的基础知识

1.5 并行算法的性能分析

习题

参考文献

第二章 设计技术

2.1 平衡树方法

2.2 倍增技术

2.3 分治策略

2.4 划分原理

2.5 流水线技术

2.6 加速级联策略

2.7 破对称技术

习题

参考文献

第三章 前缀计算

3.1 引言

3.2 并行前缀计算算法

3.3 线性递归方程求解

3.4 排序

3.5 最大和子序列

习题

参考文献

第四章 排序和选择网络

4.1 Batcher归并和排序网络

4.2 （m，n）—选择网络

4.3 AKS排序网络

习题

参考文献

第五章 排序和选择算法

5.1 Stone双调排序算法

5.2 Thompson和Kung双调排序算法

5.3 Preparata和Vuilemin双调排序算法

5.4 Akl并行k-选择算法

5.5 Valiant并行归并算法

5.6 Hirschberg并行桶排序算法

5.7 Preparata并行枚举排序算法

5.8 Cole并行归并排序算法

5.9 MIMD—CREW模型上的异步枚举排序算法

5.10 MIMD-TC模型上的异步快排序算法

习题

参考文献

第六章 分布式算法

6.1 分布式算法概述

6.2 构造生成树算法

6.3 环上选举算法

6.4 分布式k-选择算法

6.5 定序与排序

习题

参考文献

第七章 并行搜索

7.1 单处理机上的搜索

7.2 SIMD共享存储模型上有序表的搜索

7.3 SIMD共享存储模型上随机序列的搜索

7.4 树连接的SIMD模型上随机序列的搜索

7.5 网孔连接的SIMD模型上随机序列的搜索

7.6 MIMD共享存储模型上有序表的搜索

习题

参考文献

第八章 选路算法

8.1 引言

8.2 贪心选路算法

8.3 随机和确定选路算法

8.4 数据的分布和集中

8.5 线路交换模式下的选路算法

习题

参考文献

第九章 串匹配

第十章 表达式求值

第十一章 上下文无关语言

第十二章 矩阵运算

第十三章 数值计算

第十四章 快速傅氏变换

第十五章 图论算法

第十六章 计算几何

第十七章 组合搜索

第十八章 随机算法

第十九章 VLSI计算理论

第二十章 并行计算理论

附录A 复杂度表示及其符号

附录B 算法复杂界一览表

附录C 专业术语中英文对照表及索引

第3版在修订版的基础上进行了大幅度的修订，新增加3章、重写3章，改写8章。《普通高等教育十一五国家级规划教材·并行算法的设计与分析（第3版）》系统深入地讨论了计算机领域中诸多计算问题的并行算法的设计和分析方法。在着重介绍各种并行计算模型上的常用和典型的并行算法的同时，也力图反映本学科的最新成就、学科前沿和发展趋势。

　　《普通高等教育十一五国家级规划教材：并行算法的设计与分析（第3版）共分二十章，包括基础篇4章（绪论、设计技术、前缀计算、排序和选择网络），并行算法篇9章（排序和选择算法、分布式算法、并行搜索、选路算法、串匹配、表达式求值、上下文无关语言、图论算法、计算几何），数值并行算法篇3章（矩阵运算、数值计算、快速傅氏变换），理论篇4章（组合搜索、随机算法、VLSI计算理论、并行计算理论）。

　　《普通高等教育十一五国家级规划教材：并行算法的设计与分析（第3版）》取材丰富，内容系统深入，可作为高等学校计算机及其他信息类有关专业高年级本科生和研究生的教材，也可供从事计算机科学理论和并行算法研究的科技人员阅读参考。

　　《普通高等教育十一五国家级规划教材：并行算法的设计与分析（第3版）》初版曾获1994年度教育部高等学校优秀教材一等奖和1997年度国家级教学成果二等奖。