计算机算法引论 设计与分析技术PDF格式文档图书下载

1 绪论 1

1.1 交通信号灯问题 1

1.1.1 问题 1

1.1.2 实例 1

1.1.3 图着色问题 1

1.1.4 算法设计讨论 3

1.1.5 讨论 4

1.2 什么是算法 5

1.2.1 算法 5

1.2.2 算法与问题 6

1.2.3 算法与程序 6

1.3 算法的评估 7

1.3.1 正确性 7

1.3.2 时间代价 8

1.3.3 空间代价 8

1.3.4 最优性 8

1.4 算法理论的基本概念 9

1.4.1 基本操作 9

1.4.2 问题实例长度 10

1.4.3 复杂度的渐进性质 10

1.4.4 最坏情形和最好情形 11

1.4.5 平均情形和算法的期望复杂度 12

1.4.6 复杂度函数的表示 13

1.5 算法的研究与Moore定律 15

1.6 MAXMIN问题 17

1.6.1 平凡算法 17

1.6.2 改进一 18

1.6.3 改进二 18

1.6.4 改进三 19

1.6.5 讨论 20

习题1 22

2 排序算法与算法的分析技术 25

2.1 排序问题 25

2.2 O(n2)阶的排序算法 26

2.2.1 选择排序 27

2.2.2 插入排序 28

2.2.3 起泡排序 29

2.3 基于相邻元比较的排序算法和希尔排序 30

2.3.1 插入排序的最优性 30

2.3.2 希尔排序 31

2.4 O(nlogn)阶的排序算法 33

2.4.1 快速排序算法 33

2.4.2 合并排序算法 39

2.4.3 堆排序算法 42

2.5 比较排序算法的时间复杂度下界 52

2.5.1 判定树模型 52

2.5.2 最坏情形 53

2.5.3 平均情形 54

2.6 排序算法的有关研究 55

习题2 57

3 分治技术 59

3.1 分治策略的思想 59

3.2 大整数乘法 60

3.3 矩阵相乘的Strassen算法 61

3.3.1 问题 61

3.3.2 分治 61

3.3.3 Strassen的分治方法 62

3.3.4 Strassen算法的描述 62

3.3.5 讨论 62

3.4 选择问题的线性算法 63

3.4.1 问题 63

3.4.2 简单算法 63

3.4.3 O(n)阶选择算法的思路 64

3.4.4 选择算法 64

3.4.5 选择算法Select的分析 65

3.4.6 讨论 66

习题3 67

4 数据集合上的搜索算法 70

4.1 动态数据集与抽象数据类型 70

4.2 二叉搜索树 72

4.2.1 二叉搜索树 72

4.2.2 查询的实现 73

4.2.3 插入与删除操作 75

4.3 随机二叉搜索树 77

4.4 红黑树 79

4.4.1 红黑树的性质 80

4.4.2 RB树的插入与删除算法 81

4.4.3 关于RB树的几点讨论 84

4.5 2-3-4树 85

4.5.1 2-3-4树及其实例 85

4.5.2 2-3-4树上的查询操作算法 86

4.5.3 2-3-4树的构造过程 86

4.5.4 2-3-4树的性能分析 87

4.5.5 有关2-3-4树的几点讨论 88

4.6 Hash技术 89

4.6.1 Hash算法的基本思想与一般模型 89

4.6.2 Hash函数的设计 90

4.6.3 解决冲突的策略 91

4.6.4 Hash算法的优劣分析 95

4.6.5 Hash技术的几种新发展 96

习题4 102

5 贪心技术 104

5.1 贪心策略的思想 104

5.1.1 付款问题 104

5.1.2 铺砖问题 105

5.1.3 贪心算法的基本思想 105

5.2 背包问题 108

5.3 Huffman编码 110

5.4 多机调度问题的近似解法 115

5.5 单源最短路径的Dijkstra算法 117

习题5 122

6 字符串匹配 125

6.1 字符串匹配问题 125

6.2 KMP算法 127

6.2.1 KMP算法的思路 127

6.2.2 KMP算法 127

6.2.3 KMP算法的正确性 129

6.2.4 KMP算法的分析 130

6.2.5 有关KMP算法的讨论 130

6.3 BM算法 131

6.3.1 BM算法的两种处理思路 131

6.3.2 BM算法的时间复杂度分析 134

6.3.3 对BM算法的进一步讨论 135

6.4 RK算法 137

6.4.1 RK算法的思路 137

6.4.2 RK算法的描述 139

6.4.3 RK算法的分析与讨论 140

习题6 141

7 动态规划 142

7.1 动态规划的基本原理 142

7.1.1 Fibonacci数的计算 142

7.1.2 矩阵连乘的顺序问题 143

7.1.3 动态规划算法的基本条件 146

7.2 最优二分搜索树 147

7.2.1 最优二分搜索树问题 147

7.2.2 动态规划算法的思路 149

7.2.3 OBST算法 150

7.2.4 OBST算法的复杂度分析 151

7.2.5 讨论 151

7.3 近似串匹配问题 152

7.3.1 近似串匹配问题的描述 152

7.3.2 动态规划算法的思路 153

7.3.3 动态规划算法 154

7.3.4 算法的复杂度分析与实例 155

7.3.5 讨论 156

习题7 157

8 回溯与分枝限界技术 158

8.1 回溯和分枝限界的基本思想 159

8.1.1 八皇后问题 159

8.1.2 子集合问题 161

8.1.3 回溯与分枝限界算法的基本思路 162

8.2 O-1背包问题的回溯算法 165

8.2.1 O-1背包问题 165

8.2.2 回溯策略的解题思路 166

8.2.3 O-1背包问题的回溯算法 166

8.2.4 算法的复杂度分析 169

8.2.5 一个运行实例 169

8.3 无向图的团集问题 170

8.3.1 团集问题 170

8.3.2 解题思路 171

8.3.3 团集问题的回溯算法 171

8.3.4 算法Max Clique()的分析与讨论 173

8.4 旅行商问题的回溯算法 173

8.4.1 旅行商问题 173

8.4.2 旅行商问题的回溯算法 174

8.5 分枝限界算法思路的特征 175

8.5.1 O-1背包问题的分枝限界策略 175

8.5.2 分枝限界算法的优点和缺点 177

8.5.3 用分枝限界算法解旅行商问题的一个实例 178

习题8 185

9 计算机难解问题与NP-完全性问题 187

9.1 一些难解问题 187

9.1.1 图着色问题 188

9.1.2 O-1背包问题 188

9.1.3 子集合问题 188

9.1.4 装箱问题 188

9.1.5 作业调度问题 189

9.1.6 可满足性问题 189

9.1.7 图的团集问题 189

9.1.8 Hamiltonian回路问题与Hamiltonian路径问题 190

9.1.9 旅行商问题 190

9.2 多项式界与P类问题 191

9.2.1 多项式(时间)界 191

9.2.2 问题求解与判定问题 193

9.2.3 P类 195

9.3 不确定算法与NP类 195

9.3.1 问题求解与验证 195

9.3.2 非确定算法与NP类 196

9.4 问题的多项式归约和NP-完全性 199

9.4.1 多项式归约 200

9.4.2 NP-完全性 201

9.4.3 Cook定理 201

9.5 与NP-完全问题相关的理论问题与实际问题 204

9.5.1 理论可计算性与实际可计算性 204

9.5.2 “P=NP”问题 206

9.5.3 NP-完全问题的计算处理 207

习题9 208

10 近似算法 210

10.1 近似算法的思想与基本概念 211

10.1.1 顶点覆盖问题的近似算法 212

10.1.2 顶点覆盖问题的近似算法aVertexCover() 213

10.1.3 近似算法aVertexCover()的复杂度分析 214

10.1.4 算法aVertexCover()的近似度分析 214

10.2 装箱问题的近似算法 214

10.2.1 装箱问题 214

10.2.2 装箱问题的近似策略的讨论 214

10.2.3 装箱问题的FF策略近似算法 217

10.2.4 bpFFD算法的复杂度 218

10.2.5 近似算法bqFFD()解的最优性分析 218

10.2.6 讨论 219

10.3 旅行商问题的近似算法 220

10.3.1 最近邻点策略 220

10.3.2 最短链接策略 221

10.3.3 满足三角不等式的旅行商问题 223

10.3.4 几点讨论 225

习题10 225

11 数论算法及其在计算机安全系统中的应用 227

11.1 RSA公钥密码系统 227

11.1.1 数据加密的历史及现状 227

11.1.2 公钥密码系统 229

11.1.3 RSA公钥密码系统 229

11.1.4 公钥密码系统的数字签名功能 230

11.1.5 公钥密码系统与计算机网络安全 231

11.1.6 RSA公钥密码系统的主要技术问题 232

11.2 判素问题的概率算法 232

11.2.1 判素问题 232

11.2.2 输入长度和算术计算的时间代价 233

11.2.3 基于数论的素数判别概率算法 234

11.3 大素数的获得和Miller-Rabin算法的应用 236

11.3.1 素数的稠密性 236

11.3.2 Miller-Rabin测试算法的时间代价 237

11.3.3 Miller-Rabin算法判定素数的正确性 237

11.4 加密解密算法 237

11.5 大整数分解与RSA系统的安全性 239

11.5.1 整数的因子分解问题 240

11.5.2 Pollard的rho启发式算法 240

习题11 242

附录A 递归方程(递归不等式)的求解判定方法 243

附录B 实际性能最佳的排序算法的设计 247

附录C 计算模型 252

附录D Cook定理 256

附录E 若干数论知识 260

附录F 算法索引 266

主要参考文献 268

查看更多关于计算机算法引论 设计与分析技术的内容