计算机算法引论:设计与分析技术

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 算法索引

主要参考文献