计算机算法

第1章绪论
1.1算法的时间复杂性
1.2算法的空间复杂性
1.3两个算法的分析实例
1.4算法设计技术
1.4.1分治方法
1.4.2回溯法
1.4.3贪心法
1.4.4动态规划法
1.4.5分支限界法
1.4.6递归方程解的展开式
习题

第2章排序算法
2.1插入算法
2.1.1直接插入排序
2.1.2折半插入排序
2.1.3希尔排序
2.2选择排序
2.2.1直接选择排序
2.2.2堆排序
2.3交换排序
2.3.1冒泡排序
2.3.2快速排序
2.4归并排序
2.5基数排序
2.6外部排序
2.6.1归并排序
2.6.2多步归并算法
2.7各种内部排序方法的比较讨论
习题

第3章查找树
3.1二分查找树
3.22—3—4树
3.3红黑树
3.48树
习题

第4章图的算法
4.1基本概念
4.2图的表示方法
4.3图的遍历
4.4所有点对之间的最短路径
4.5最小生成树
习题

第5章串匹配
5.1简单的字符串匹配算法
5.2Knuth—Morris—Pratt（KMP）字符串匹配
5.3BM算法
5.4RK算法
习题

第6章分治算法
6.1二分搜索
6.2求最大元和最小元
6.3大整数乘法
6.4矩阵乘法算法
6.5矩阵乘积的Winograd算法
习题

第7章贪心算法
7.1背包问题
7.2带时限的作业排序
7.3单源最短路径问题
7.4最小生成树问题
7.5Dijkstra各点之间最短路径的优化算法
习题

第8章回溯法
8.1n皇后问题
8.2图的着色问题
8.30—1背包问题
8.4哈密顿回路
8.5子集和数
习题

第9章动态规划法
9.1最长公共子序列问题
9.2矩阵连乘问题
9.3多阶段决策过程最优化问题
9.40—1背包问题
9.5流水线调度问题
习题

第10章分支限界法
10.1分支限界的策略
10.20－1背包问题
习题

第11章概率算法
11.l随机数
11.2数值概率算法
11.3蒙特卡罗算法
11.4拉斯维加斯算法
11.5舍伍德算法
习题

第12章几何问题算法
12.1直线相交问题的算法
12.2点是否包含在多边形内部
12.3求凸包问题
习题

第13章NP完全问题
13.1不确定算法和不确定图灵机
13.2NP难度和NP完全问题
13.3COOK定理
13.4几个NP完全问题
习题

第14章密码学算法
14.1什么是密码
14.2基本数论
14.3背包公钥密码
14.4RSA算法
14.5数字签名
习题

第15章近似算法
15.1任务调度近似算法.
15.2顶点覆盖问题近似算法
15.3旅行商问题的近似解
15.4子集和数问题的近似算法
习题

第16章并行算法
16.1并行计算机
16.2并行算法的基本概念
16.3并行算法的描述
16.4SIMD-SM上的非线性方程求根同步并行算法
16.5SIMD-SM上的同步并行求和算法
16.6SIMD-CC超立方机器上的同步并行求和算法
16.7MIMD-SM上的异步并行求和算法
习题
参考文献