1 绪论
1. 1 交通信号灯问题
1. 1. 1 问题
1. 1. 2 实例
1. 1. 3 图着色问题
1. 1. 4 算法设计讨论
1. 1. 5 讨论
1. 2 什么是算法
1. 2. 1 算法
1. 2. 2 算法与问题
1. 2. 3 算法与程序
1. 3 算法的评估
1. 3. 1 正确性
1. 3. 2 时间代价
1. 3. 3 空间代价
1. 3. 4 最优性
1. 4 算法理论的基本概念
1. 4. 1 摹本操作
1. 4. 2 问题实例长度
1. 4. 3 复杂度的渐进性质
1. 4. 4 最坏情形和最好情形
1. 4. 5 平均情形和算法的期望复杂度
1. 4. 6 复杂度函数的表示
* 1. 5 算法的研究与Moore定律
* 1. 6 MAXMIN问题
1. 6. 1 平凡算法
1. 6. 2 改进一
1. 6. 3 改进二
1. 6. 4 改进三
1. 6. 5 讨论
习题1
2 排序算法与算法的分析技术
2. 1 排序问题
2. 2 O(n )阶的排序算法
2. 2. 1 选择排序
2. 2. 2 插入排序
2. 2. 3 起泡排序
2. 3 基于相邻元比较的排序算法和希尔排序
2. 3. 1 插入排序的最优性
2. 3. 2 希尔排序
2. 4 O(nlogn)阶的排序算法
2. 4. 1 快速排序算法
2. 4. 2 合并排序算法
2. 4. 3 堆排序算法
2. 5 比较排序算法的时间复杂度下界
2. 5. 1 判定树模型
2. 5. 2 最坏情形
2. 5. 3 平均情形
2. 6 排序算法的有关研究
习题2
3 分治技术
3. 1 分治策略的思想
3. 2 大整数乘法
3. 3 矩阵相乘的Strassen算法
3. 3. 1 问题
3. 3. 2 分治
3. 3. 3 Strassen的分治方法
3. 3. 4 Strassen算法的描述
3. 3. 5 讨论
3. 4 选择问题的线性算法
3. 4. 1 问题
3. 4. 2 简单算法
3. 4. 3 O(n)阶选择算法的思路
3. 4. 4 选择算法
3. 4. 5 选择算法Select的分析
3. 4. 6 讨论
习题3
4 数据集合上的搜索算法
4. 1 动态数据集与抽象数据类型
4. 2 二叉搜索树
4. 2. 1 二叉搜索树
4. 2. 2 查询的实现
4. 2. 3 插入与删除操作
4. 3 随机二叉搜索树
4. 4 红黑树
4. 4. 1 红黑树的性质
4. 4. 2 RB树的插入与删除算法
4. 4. 3 关于RB树的几点讨论
4. 5 2—3—4树
4. 5. 1 2—3—4树及其实例
4. 5. 2 2—3—4树上的查询操作算法
4. 5. 3 2—3—4树的构造过程
4. 5. 4 2—3—4树的性能分析
4. 5. 5 有关2—3—4树的几点讨论
4. 6 Hash技术
4. 6. 1 Hash算法的基本思想与一般模型
4. 6, 2 Hash函数的设计
4. 6. 3 解决冲突的策略
4. 6. 4 Hash算法的优劣分析
4. 6. 5 Hash技术的几种新发展
习题4
5 贪心技术
5. 1 贪心策略的思想
5. 1. 1 付款问题
5. 1. 2 铺砖问题
5. 1. 3 贪心算法的基本思想
5. 2 背包问题
5. 3 Huffman编码
5. 4 多机调度问题的近似解法
5. 5 单源最短路径的Dijkstra算法
习题5
6 字符串匹配
6. 1 字符串匹配问题
6. 2 KMP算法
6. 2. 1 KMP算法的思路
6. 2. 2 KMP算法
6. 2. 3 KMP算法的正确性
6. 2. 4 KMP算法的分析
6. 2. 5 有关KMP算法的讨论
6. 3 BM算法
6. 3. 1 BM算法的两种处理思路
6. 3. 2 BM算法的时间复杂度分析
6. 3. 3 对BM算法的进一步讨论
6. 4 RK算法
6. 4. 1 RK算法的思路
6. 4. 2 RK算法的描述
6. 4. 3 RK算法的分析与讨论
习题6
7 动态规划
7. 1 动态规划的基本原理
7. 1. 1 Fibonacci数的计算
7. 1. 2 矩阵连乘的顺序问题
7. 1. 3 动态规划算法的基本条件
7. 2 最优二分搜索树
7. 2. 1 最优二分搜索树问题
7. 2. 2 动态规划算法的思路
7. 2. 3 OBST算法
7. 2. 4 OBST算法的复杂度分析
7. 2. 5 讨论
7. 3 近似串匹配问题
7. 3. 1 近似串匹配问题的描述
7. 3. 2 动态规划算法的思路
7. 3. 3 动态规划算法
7. 3. 4 算法的复杂度分析与实例
7. 3. 5 讨论
习题7
8 回溯与分枝限界技术
8. 1 回溯和分枝限界的基本思想
8. 1. 1 八皇后问题
8. 1. 2 子集合问题
8. 1. 3 回溯与分枝限界算法的基本思路
8. 2 0—1背包问题的回溯算法
8. 2. 1 0—1背包问题
8. 2. 2 回溯策略的解题思路
8. 2. 3 0—1背包问题的回溯算法
8. 2. 4 算法的复杂度分析
8. 2. 5 一个运行实例
8. 3 无向图的团集问题
8. 3. 1 团集问题
8. 3. 2 解题思路
8. 3. 3 团集问题的回溯算法
8. 3. 4 算法Max Clique()的分析与讨论
8. 4 旅行商问题的回溯算法
8. 4. 1 旅行商问题
8. 4. 2 旅行商问题的回溯算法
8. 5 分枝限界算法思路的特征
8. 5. 1 0—1背包问题的分枝限界策略
8. 5. 2 分枝限界算法的优点和缺点
8. 5. 3 用分枝限界算法解旅行商问题的一个实例
习题8
9 计算机难解问题与NP—完全性问题
9. 1 一些难解问题
9. 1. 1 图着色问题
9. 1. 2 0—1背包问题
9. 1. 3 子集合问题
9. 1. 4 装箱问题
9. 1. 5 作业调度问题
9. 1. 6 可满足性问题
9. 1. 7 图的团集问题
9. 1. 8 Hamiltonian回路问题与Hamiltonian路径问题
9. 1. 9 旅行商问题
9. 2 多项式界与P类问题
9. 2. 1 多项式(时间)界
9. 2. 2 问题求解与判定问题
9. 2. 3 P类
9. 3 不确定算法与NP类
9. 3. 1 问题求解与验证
9. 3. 2 非确定算法与NP类
9. 4 问题的多项式归约和NP—完全性
9. 4. 1 多项式归约
9. 4. 2 NP—完全性
9. 4. 3 Cook定理
9. 5 与NP—完全问题相关的理论问题与实际问题
9. 5. 1 理论可计算性与实际可计算性
9. 5. 2 “P=NP”问题
9. 5. 3 NP—完全问题的计算处理
习题9
10 近似算法
10. 1 近似算法的思想与基本概念
10. 1. 1 顶点覆盖问题的近似算法
10. 1. 2 顶点覆盖问题的近似算法a VertexCover()
10. 1. 3 近似算法a VertexCover()的复杂度分析
10. 1. 4 算法a VertexCover()的近似度分析
10. 2 装箱问题的近似算法
10. 2. 1 装箱问题
10. 2. 2 装箱问题的近似策略的讨论
10. 2. 3 装箱问题的FF策略近似算法
10. 2. 4 bpFFD算法的复杂度
10. 2. 5 近似算法bqFFD()解的最优性分析
10. 2. 6 讨论
10. 3 旅行商问题的近似算法
10. 3. 1 最近邻点策略
10. 3. 2 最短链接策略
10. 3. 3 满足三角不等式的旅行商问题
10. 3. 4 几点讨论
习题10
11 数论算法及其在计算机安全系统中的应用
11. 1 RSA公钥密码系统
11. 1. 1 数据加密的历史及现状
11. 1. 2 公钥密码系统
11. 1. 3 RSA公钥密码系统
11. 1. 4 公钥密码系统的数字签名功能
11. 1. 5 公钥密码系统与计算机网络安全
11. 1. 6 RSA公钥密码系统的主要技术问题
11. 2 判素问题的概率算法
11. 2. 1 判素问题
11. 2. 2 输入长度和算术计算的时间代价
11. 2. 3 基于数论的素数判别概率算法
11. 3 大素数的获得和Miller—Rabin算法的应用
11. 3. 1 素数的稠密性
11. 3. 2 Miller-Rabin测试算法的时间代价
11. 3. 3 Miller-Rabin算法判定素数的正确性
11. 4 加密解密算法
11. 5 大整数分解与RSA系统的安全性
11. 5. 1 整数的因子分解问题
11. 5. 2 Pollard的rho启发式算法
习题11
附录A 递归方程(递归不等式)的求解判定方法
附录B 实际性能最佳的排序算法的设计
附录C 计算模型
附录D Cook定理
附录E 若干数论知识
附录F 算法索引
主要参考文献
鄂公网安备 42010302001612号 