计算机算法引论 设计与分析技术2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

计算机算法引论 设计与分析技术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

习题122

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

习题257

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

习题367

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

习题4102

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

习题5122

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

习题6141

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

习题7157

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

习题8185

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

习题9208

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

习题10225

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

习题11242

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

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

附录C 计算模型252

附录D Cook定理256

附录E 若干数论知识260

附录F 算法索引266

主要参考文献268