计算机算法基础

第一章 导引与基本数据结构

1.1 算法

1.2 分析算法

1.2.1 计算时间的渐近表示

1.2.2 常用的整数求和公式

1.2.3 作时空性能分布图

1.3 用sparks语言写算法

1.4 基本数据结构

1.4.1 栈和队列

1.4.2 树

1.4.3 集合的树表示和不相交集合的合并——树结构应用实例

1.4.4 图

1.5 递归和消去递归

1.5.1 递归

1.5.2 消去递归

习题一

第二章 分治法

2.1 一般方法

2.2 二分检索

2.2.1 二分检索算法

.2.2.2 以比较为基础检索的时间下界

2.3 找最大和最小元素

2.4 归并分类

2.4.1 基本方法

2.4.2 改进的归并分类算法

2.4.3 以比较为基础分类的时间下界

2.5 快速分类

2.5.1 快速分类算法

2.5.2 快速分类分析

2.6 选择问题

2.6.1 选择问题算法

2.6.2 最坏情况时间是o(n)的选择算法

2.6.3 select2的实现

2.7 斯特拉森矩阵乘法

习题二

第三章 贪心方法

3.1 一般方法

3.2 背包问题

3.3 带有限期的作业排序

3.3.1 带有限期的作业排序算法

3.3.2 一种更快的作业排序算法

3.4 最优归并模式

3.5 最小生成树

3：6 单源点最短路径

习题三

第四章 动态规划

4.1 一般方法

4.2 多段图

4.3 每对结点之间的最短路径

4.4 最优二分检索树

4.5 0／1背包问题

4.5.1 0／1背包问题的实例分析

4.5.2 dkp的实现

4.5.3 过程dknap的分析

4.6 可靠性设计

4.7 货郎担问题

4.8 流水线调度问题

习题四

第五章 基本检索与周游方法

5.1 一般方法

5.1.1 二元树周游

5.1.2 树周游

5.1.3 图的检索和周游

5.2 代码最优化

5.3 双连通分图和深度优先检索

5.4 与／或图

5.5 对策树

习题五

第六章 回溯法

6.1 一般方法

6.1.1 回溯的一般方法

6.1.2 效率估计

6.2 8-皇后问题

6.3 子集和数问题

6.4 图的着色

6.5 哈密顿环

6.6 背包问题

习题六

第七章 分枝-限界法

7.1 一般方法

7.1.1 lc-检索

7.1.2 15-谜问题——一个例子

7.1.3 lc-检索的抽象化控制

7.1.4 lc-检索的特性

7.1.5 分枝-限界算法

7.1.6 效率分析

7.2 0／1背包问题

7.2.1 lc分枝-限界求解

7.2.2 fifo分枝-限界求解

7.3 货郎担问题

习题七

第八章 np-难度和np-完全的问题

8.1 基本概念

8.1.1 不确定的算法

8.1，2 np-难度和np-完全类

8.2 cook定理

8.3 np-难度的图问题

8.3.1 集团判定问题(cdp)

8.3.2 结点覆盖的判定问题

8.3.3 着色数判定问题(cn)

8.3.4 有向哈密顿环(dhc)

8.3.5 货郎担判定问题(tsp)

8.3.6 与／或图的判定问题(aog)

8.4 np-难度的调度问题

8.4.1 相同处理器调度

8.4.2 流水线调度

8.4.3 作业加工调度

8.5 np-难度的代码生成问题

8.5.1 有公共子表达式的代码生成

8.5.2 并行赋值指令的实现

8.6 若干简化了的np-难度问题

习题八

第九章 并行算法

9.1 并行计算机与并行计算模型

9.2 并行算法的基本概念

9.2.1 并行算法的复杂性度量

9.2.2 并行算法的性能评价

9.2.3 并行算法的设计

9.2.4 并行算法的描述

9.3 simd共享存储模型上的并行算法

9.3.1 广播算法

9.3.2 求和算法

9.3.3 并行归并分类算法

9.3.4 求图的连通分支的并行算法

9.4 simd互连网络模型上的并行算法

9.4.1 超立方模型上的求和算法

9.4.2 一维线性模型上的并行排序算法

9.4.3 树型模型上求最小值算法

9.4.4 二维网孔模型上的连通分支算法

9.5 mimd共享存储模型上的并行算法

9.5.1 并行求和算法

9.5.2 矩阵乘法的并行算法

9.5.3 枚举分类算法

9.5.4 二次取中的并行选择算法

9.5.5 并行快速排序算法

9.5.6 求最小元的并行算法

9.5.7 求单源点最短路径的并行算法

9.6 mimd异步通信模型上的并行算法

9.6.1 选择问题的并行算法

9.6.2 求极值问题的并行算法

9.6.3 网络生成树的并行算法

习题九

参考文献