本书是一本面向计算机、软件工程和网络工程专业及相关专业的本科生(高年级)和研究生教材,根据国内外计算机技术的*新发展,讲述计算机算法的各种设计策略,包括分治技术、贪心技术、动态规划技术、回溯和分支限界技术等;介绍算法分析技术、算法的时间和空间复杂度分析方法,包括*坏情况和平均情况的分析等;讨论各类经典和应用问题的算法,包括排序算法、搜索算法、字符串匹配算法、图论算法、调度算法、组合优化算法、数论算法等。并在计算复杂性理论的基础上,引入近似算法、概率算法等*新内容。

1 绪论
1·1 交通信号灯问题
1·2 什么是算法
1·3 算法的评估
1·4 算法理论的基本概念
*1·5 算法的研究与Moore定律
*1·6 MAXMIN问题
习题1
2 排序算法与算法的分析技术
2·1 排序问题
2·2 O(n2)阶的排序算法
2·3 基于相邻元比较的排序算法和希尔排序
2·4 O(n1ogn)阶的排序算法
2·5 比较排序算法的时间复杂度下界
*2·6 排序算法的有关研究
习题2
3 分治技术
3·1 分治策略的思想
3·2 大整数乘法
3·3 矩阵相乘的Strassen算法
3·4 选择问题的线性算法
习题3
4 数据集合上的搜索算法
4·1 动态数据集与抽象数据类型
4·2 二叉搜索树
**4·3 随机二叉搜索树
4·4 红黑树
4·5 2-3-4树
4·6 Hash技术
习题4
5 贪心技术
5·1 贪心策略的思想
5·2 背包问题
5·3 Huffman编码
*5·4 多机调度问题的近似解法
5·5 单源*短路径的Dijkstra算法
习题5
6 字符串匹配
6·1 字符串匹配问题
6·2 KMP算法
6·3 BM算法
6·4 RK算法
习题6
7 动态规划
7·1 动态规划的基本原理
7·2 *优二分搜索树
*7·3 近似串匹配问题
习题7
*8 回溯与分枝限界技术
8·1 回溯和分枝限界的基本思想
8·2 0-1背包问题的回溯算法
8·3 无向图的团集问题
8·4 旅行商问题的回溯算法
8·5 分枝限界算法思路的特征
习题8
9 计算机难解问题与NP-完全性问题
9·1 一些难解问题
9·2 多项式界与P类问题
9·3 不确定算法与NP类
9·4 问题的多项式归约和NP-完全性
9·5 与NP-完全问题相关的理论问题与实际问题
习题9
*10 近似算法
10·1 近似算法的思想与基本概念
10·2 装箱问题的近似算法
10·3 旅行商问题的近似算法
习题10
*11 数论算法及其在计算机**系统中的应用
11·1 RSA公钥密码
11·2 判素问题的概率算法
11·3 大素数的获得和Miller-Rabin算法的应用
11·4 加密解密算法
11·5 大整数分解与RSA系统的**性
习题11
附录A 递归方程(递归不等式)的求解判定方法
附录B 实际性能*佳的排序算法的设计
附录C 计算模型
附录D Cook定理
附录E 若干数论知识
附录F 算法索引
主要参考文献