第1章 引论 1
1．1 算法分析的基本概念和理论 2
1．2 搜索有序表算法的分析 6
练习1 10
第2章 算法设计技术和分析方法 12
2．1 算法设计技术 12
2．1．1 分治方法 12
2．1．2 回溯法 13
2．1．3 贪心法 13
2．1．4 动态规划法 14
2．1．5 分支限界法 15
2．2 递归方程解的展开方法 15
2．3 一类特殊递归方程的解 16
2．4 毋函数方法 20
练习2 22
3．1 大整数相乘算法 23
第3章 计算的算术复杂性 23
3．2 矩阵乘积算法 25
3．2．1 Winograd矩阵乘法 25
3．2．2 Strassen矩阵乘法 27
3．3 判定素数的算法 28
3．4 RSA数据加解密算法 31
3．5 HASH函数和数字签名 34
3．6 数据压缩技术 35
3．6．1 ASCII码压缩方法 35
3．6．2 模式置换压缩方法 35
3．6．3 LZ压缩技术 36
练习3 37
第4章 排序算法 39
4．1 冒泡排序算法 39
4．2 基于比较的排序时间复杂性下界 43
4．3．1 基数排序算法 44
4．3 分配排序技术 44
4．3．2 分配分块排序算法 46
4．3．3 分配和归并混合排序算法 48
4．3．4 循环分组散列和循环两路归并排序算法 49
4．4 基于映射的汉字字符串排序方法 52
练习4 53
第5章 字符串匹配技术 54
5．1 简单的字符串匹配算法 54
5．2 Knuth-Morris-Pratt串匹配算法 55
5．3 改进的Knuth-Morris-Pratt串匹配算法 58
5．4 Boyer-Moore串匹配算法 59
5．5 改进的Boyer-Moore串匹配算法 60
5．6 KARP-RABIN串匹配随机算法 64
5．7 字符串近似匹配简介 66
练习5 66
6．1 并行处理技术及其应用 69
第6章 并行计算基础 69
6．2 并行计算机分类 70
6．2．1 Flynn分类法 70
6．2．2 Handler分类法 71
6．2．3 按机器体系结构分类 71
6．3 并行计算机的处理器互联方式 72
6．3．1 一维线性阵列结构 73
6．3．2 二维网格结构 73
6．3．3 树结构 74
6．3．4 树网结构 75
6．3．5 超立方连接结构 75
6．3．6 q维网格结构 76
6．3．7 洗牌-交换网络 76
6．3．8 蝶形结构 77
6．4 并行计算模型 77
6．4．1 SIMD互联网络模型 77
6．4．3 MIMD并行计算模型 78
6．4．2 共享存储的SIMD模型 78
6．5 并行计算的若干理论 79
6．5．1 Groseh定律 79
6．5．2 Minsky猜想 79
6．5．3 Amdahl定律 80
6．6 并行算法基础 80
6．6．1 并行算法的基本概念 80
6．6．2 并行算法的复杂性 81
6．6．3 并行算法的形式描述 82
6．6．4 并行算法设计的基本技术 83
练习6 84
第7章 程序的基本并行特性 85
7．1 多处理机系统的并行程序设计 85
7．2 程序并行性的条件 90
7．2．1 数据和计算资源的关系 90
7．2．2 计算机硬件和软件的并行性 95
7．3 并行程序的划分和调度 97
7．3．1 计算粒度规模和通信时延 98
7．3．2 粒度的组合和调度 100
练习7 102
第8章 并行求和算法 106
8．1 SIMD-MC2二维网格机器上的同步并行求和算法 106
8．2 SIMD-CC超立方机器上的同步并行求和算法 108
8．3 SIMD-SE洗牌交换网络上的同步并行求和算法 109
8．4 SIMD-SM机器上的同步并行求和算法 111
8．5 MIMD-SM机器上的异步并行求和算法 112
练习8 114
第9章 并行排序 115
9．1 线性阵列上的奇偶转置排序同步并行算法 115
9．2 线性阵列上的奇偶归拆排序同步并行算法 117
9．3 树机器上的最小抽取排序同步并行算法 118
9．4 树机器上的桶分配和归并排序同步并行算法 122
9．5 共享存储器并行系统上的valiant归并和排序同步并行算法 123
9．5．1 valiant归并同步并行算法 124
9．5．2 valiant排序同步并行算法 127
9．6 共享存储MIMD-TC模型上的快速排序异步并行算法 128
9．7 MIMD-SM机器上基于散列技术的异步并行排序算法 130
练习9 133
第10章 并行查找与并行匹配 134
10．1 共享存储器并行系统上范围查找同步并行算法 134
10．2 共享存储器并行系统上任意两序列公共元素的同步并行查找算法 136
10．3 共享存储器并行系统上KARP-RABIN串匹配并行算法 140
练习10 142
第11章 数值并行算法 143
11．1 SIMD-SM机器上基于LDU分解的方程组求解同步并行算法 143
11．2 MIMD-SM机器上的矩阵相乘异步并行算法 145
11．3 SIMD-SM机器上非线性方程求根同步并行算法 146
练习11 147
12．1 选择、投影和集合操作并行算法 149
第12章 数据库操作并行算法 149
12．1．1 并行选择算法 150
12．1．2 并行投影算法 153
12．1．3 关系元组集合操作并行算法 155
12．2 并行连接算法 159
12．2．1 并行嵌套循环连接算法 159
12．2．2 基于排序和合并方法的并行连接算法 161
12．2．3 基于Hash方法的并行连接算法 163
练习12 168
附录 并行MULTIPASCAL系统简介及并行程序实例 169
附录1．1 并行MULTIRASCAL系统简介 169
附录1．1．1 并行MULTIPASCAL系统的上机操作步骤 169
附录1．1．2 并行MULTIPASCAL部分语句简介 169
附录1．2 基于散列技术的(m,n)选择并行算法及程序实例 171
附录1．2．1 并行散列选择算法的设计 171
附录1．2．2 并行散列选择程序实例 174
参考文献 180