计算机算法基础 第三版
出版时间：2006
丛编项： 普通高等教育“十五”国家级规划教材
内容简介
　　本书是教育部普通高等教育“十五”国家级规划教材。.计算机算法是计算机科学和计算机应用的核心。无论是计算机系统、系统软件的设计，还是为解决计算机的各种应用课题做的设计都可归结为算法的设计。..本书围绕算法设计的基本方法，对计算机领域中许多常用的非数值算法作了精辟的描述，并分析了这些算法所需的时间和空间。全书共分11章，第1章系统地介绍了计算机算法所涉及的数学知识，第2章至第9章介绍了递归算法、分治法、贪心法、动态规划、基本检索与周游方法、回溯法以及分枝一限界法等基本设计方法，第10章对当今计算机科学的前沿课题——P=NP问题的有关知识作了初步介绍，第11章则对日益兴起的并行算法的基本设计方法作了介绍。本书可作为高等院校与计算机有关的各专业的教学用书，也可作为从事计算机科学、工程和应用的工作人员的自学教材和参考书。...
目录
第1章数学预备知识.
1.1集合
1.1.1集合之间的关系
1.1.2幂集
1.1.3集合的运算
1.2计数方法
1.2.1加法法则及乘法法则
1.2.2一一对应
1.2.3排列
1.2.4组合
1.3母函数
1.3.1母函数的性质及应用
1.3.2指数型母函数
1.4级数求和
1.4.1由组合的实际意义产生的计数公式及级数求和公式
1.4.2其它的一些常用求和公式
习题一
第2章导引与基本数据结构
2.1算法
2.1.1算法的重要特性
2.1.2算法学习的基本内容
2.2分析算法
2.2.1计算时间的渐近表示
2.2.2常用的整数求和公式
2.2.3作时空性能分布图
2.3.用SPARKS语言写算法
2.4基本数据结构
2.4.1栈和队列
2.4.2树
2.4.3集合的树表示和不相交集合的合并——树结构应用实例
2.4.4图
习题二
第3章递归算法
3.1递归算法的实现机制
3.1.1子程序的内部实现原理
3.1.2递归过程的内部实现原理
3.2递归转非递归
3.3递归算法设计
3.4递归关系式的计算
3.4.1递归算法的时间复杂度分析
3.4.2k阶线性齐次递归关系式的解法
3.4.3线性常系数非齐次递归关系式的解法
习题三
第4章分治法
4.1一般方法
4.2二分检索
4.2.1二分检索算法
4.2.2以比较为基础检索的时间下界
4.3找最大和最小元素
4.4归并分类
4.4.1基本方法
4.4.2改进的归并分类算法
4.4.3以比较为基础分类的时间下界
4.5快速分类
4.5.1快速分类算法
4.5.2快速分类分析
4.6选择问题
4.6.1选择问题算法
4.6.2最坏情况时间是O(n)的选择算法
4.6.3SELECT2的实现
4.7斯特拉森矩阵乘法
习题四
第5章贪心方法
5.1一般方法
5.2背包问题
5.3带有限期的作业排序
5.3.1带有限期的作业排序算法
5.3.2一种更快的作业排序算法
5.4最优归并模式
5.5最小生成树
5.6单源点最短路径
习题五
第6章动态规划
6.1一般方法
6.2多段图
6.3每对结点之间的最短路径
6.4最优二分检索树
6.50/1背包问题
6.5.10/1背包问题的实例分析
6.5.2DKP的实现
6.5.3过程DKNAP的分析
6.6可靠性设计
6.7货郎担问题
6.8流水线调度问题
习题六..
第7章基本检索与周游方法
7.1一般方法
7.1.1二元树周游
7.1.2树周游
7.1.3图的检索和周游
7.2代码最优化
7.3双连通分图和深度优先检索
7.4与/或图
7.5对策树
习题七
第8章回溯法
8.1一般方法
8.1.1回溯的一般方法
8.1.2效率估计
8.28-皇后问题
8.3子集和数问题
8.4图的着色
8.5哈密顿环
8.6背包问题
习题八
第9章分枝-限界法
9.1一般方法
9.1.1LC-检索
9.1.215-谜问题——一个例子
9.1.3LC-检索的抽象化控制
9.1.4LC-检索的特性
9.1.5分枝—限界算法
9.1.6效率分析
9.20/1背包问题
9.2.1LC分枝-限界求解
9.2.2FIFO分枝-限界求解
9.3货郎担问题
习题九
第10章NP-难度和NP-完全的问题
10.1基本概念
10.1.1不确定的算法
10.1.2NP-难度和NP-完全类
10.2COOK定理
10.3NP-难度的图问题
10,3.1集团判定问题(CDP)
10.3.2结点覆盖的判定问题
10.3.3着色数判定问题(CN)
10.3.4有向哈密顿环(DHC)
10.3.5货郎担判定问题(TSP)
10.3.6与/或图的判定问题(AOG)
10.4NP-难度的调度问题
10.4.1相同处理器调度
10.4.2流水线调度
10.4.3作业加工调度
10.5NP-难度的代码生成问题
10.5.1有公共子表达式的代码生成
10.5.2并行赋值指令的实现
10.6若干简化了的NP-难度问题
习题十
第11章并行算法
11.1并行计算机与并行计算模型
11.2并行算法的基本概念
11.2.1并行算法的复杂性度量
11.2.2并行算法的性能评价
11.2.3并行算法的设计
11.2.4并行算法的描述
11.3SIMD共享存储模型上的并行算法
11.3.1广播算法
11.3.2求和算法
11.3.3并行归并分类算法
11.3.4求图的连通分支的并行算法
11.4SIMD互连网络模型上的并行算法
11.4.1超立方模型上的求和算法
11.4.2一维线性模型上的并行排序算法
11.4.3树形模型上求最小值算法
11.4.4二维网孔模型上的连通分支算法
11.5MIMD共享存储模型上的并行算法
11.5.1并行求和算法
11.5.2矩阵乘法的并行算法
11.5.3枚举分类算法
11.5.4二次取中的并行选择算法
11.5.5并行快速排序算法
11.5.6求最小元的并行算法
11.5.7求单源点最短路径的并行算法
11.6MIMD异步通信模型上的并行算法
11.6.1选择问题的并行算法
11.6.2求极值问题的并行算法
11.6.3网络生成树的并行算法
习题十一
参考文献...