          算法设计与分析培训

一 基础知识（1）：算法的基本概念及伪码描述，函数的渐近的界

1.1 本教学内容简介

1.2 算法设计的两个例子

1.3 问题的计算复杂度：排序问题

1.4 货郎问题与计算复杂性

1.5 算法及其时间复杂度

1.6 算法的伪码表示

1.7 函数的渐近的界

1.8 有关函数渐近的界的定理

1.9 几类重要函数

二 基础知识（2）：序列求和方法，递推方程求解

2.1 本教学内容简介

2.2 序列求和的方法

2.3 递推方程与算法分析

2.4 迭代法求解递推方程

2.5 差消法化简递推方程

2.6 递归树

2.7 主定理及其证明

2.8 主定理的应用

三 分治策略（1）

3.1 本教学内容简介

3.2 分治策略的设计思想

3.3 分治策略的一般描述和分析方法

3.4 芯片测试

3.5 快速排序

3.6 幂乘算法及应用

3.7 改进分治算法的途径1：减少子问题数

3.8 改进分治算法的途径2：增加预处理

四 分治策略（2）

4.1 本内容简介

4.2 选最大与最小

4.3 选二大

4.4 一般选择问题的算法设计

4.5.选择问题的算法分析

4.6 卷积及应用

4.7 卷积计算

4.8 快速傅立叶变换FFT算法

4.9 平面点集的凸包

五 动态规划（1）

5.1 本教学内容简介

5.2 动态规划算法的例子

5.3 动态规划算法设计

5.4 动态规划算法的递归实现

5.5 动态规划算法的迭代实现

5.6 投资问题

5.7 背包问题

5.8 最长公共子序列

六 动态规划（2）

6.1 本教学内容简介

6.2 图像压缩

6.3 最大子段和

6.4 最优二叉检索树的概念

6.5 最优二叉检索树的算法

6.6 RNA二级结构预测

6.7 序列比对

七 贪心法（1）

7.1 本教学内容简介

7.2 贪心法的例子

7.3 贪心法的正确性证明

7.4 最优装载问题

7.5 最小延迟调度

7.6 得不到最优解的处理方法

八 贪心法（2）

8.1 本教学内容简介

8.2 最优前缀码及哈夫曼算法

8.3 哈夫曼算法的正确性证明

8.4 最小生成树

8.5 Prim算法

8.6 Kruskal算法

8.7 单源最短路径问题及算法

8.8 Dijkstra算法的证明

单元作业

九 回溯与分支限界（1）

9.1 本教学内容简介

9.2 几个回溯算法的例子

9.3 回溯算法的设计思想和适用条件

9.4 回溯算法实现及实例

9.5 图的着色

9.6 搜索树结点数的估计

作业测试

十 回溯与分支限界

10.1 本教学内容简介

10.2 分支限界

10.3 最大团问题

10.4 货郎问题

10.5 圆排列问题

10.6 连续邮资问题