算法设计与分析培训

01
算法概述及复杂性理论
了解该课程要解决的问题；了解算法的概念；掌握算法的正确性证明方法；了解问题的下界的描述方法。

1 问题
2 算法的概念
3 算法的正确性
4 算法的效率
5 问题的下界
02
算法分析方法
掌握概率分析在算法复杂度分析中的应用；掌握分摊分析方法；了解实验分析方法。

1 概率分析
2 合计方法
3 记账方法
4 势能方法
5 实验分析
03
递归
了解递归的算法思想；根据选择排序和全排列生成问题掌握设计递归算法的一般步骤；求解递归方程。

1 递归的算法思想
2 选择排序
3 生成排列
4 递归方程的求解
04
分治（上）
了解分治的算法思想；根据案例掌握分治算法设计的一般步骤；

1 算法思想
2 二分搜索
3 快速排序
4 归并排序
05
分治（下）与动态规划（上）
根据残缺棋盘游戏进一步了解分治算法，难点在于理解分治算法“分”出的子问题必须具有相似的结构；初步了解动态规划算法，难点在于如何根据递推关系式填表；

1 残缺棋盘游戏
2 大整数乘法
3 矩阵乘法
4 动态规划引言
5 动态规划算法思想
6 矩阵链乘法问题
06
动态规划（中）
根据多个案例进一步了解掌握动态规划算法，难点在于递推关系式的推导；根据装配线调度问题了解动态规划的另一种求解方法：备忘录法； 掌握如何使用递归方法构造最优解；

1 最优二叉搜索树问题
2 最大字段和问题
3 装配线调度问题
4 最长公共子序列问题
07
动态规划（下）与贪心算法（上）
由背包问题理解动态规划最优子结构性质；根据任务调度问题理解贪心算法； 对比区分贪心算法与动态规划算法，难点在于贪心算法的证明；

1 0/1背包问题
2 动态规划的基本性质
3 贪心算法思想
4 任务选择问题（上）
08
贪心算法（下）
由任务选择问理解贪心算法；由背包问题进一步区分动态规划与贪心算法； 理解Huffman编码中的贪心策略；

1 任务选择问题（下）
2 背包问题
3 哈夫曼编码问题
4 任务选择实验
09
图算法（上）
了解图的基本概念、表示方法、了解两种存储图的方式（邻接矩阵与邻接表）及各自优势；掌握图的深度优先搜索与广度优先搜索算法，难点在于DFS的递归与非递归实现； 掌握图的最小生成树问题及其解法；

1 图的表示
2 宽度优先搜索
3 深度优先搜索
4 最小生成树问题--Kruskal算法
10
图算法（下）
了解最短路问题的定义；掌握两种基本最短路问题求解算法； 掌握、区分Prim算法与Kruskal算法；

1最小生成树问题--Kruskal 与 Prim 比较
2 最短路径问题
3 单源最短路径问题
4 所有点对的最短路径问题
11
网络流与匹配
了解最大流问题的定义；掌握求解最大流问题的基本算法； 了解最大费用流问题的定义；

1 最大流问题
2 最大流问题求解
3 最小费用流
12
回溯
了解回溯的定义；掌握0-1背包问题、货箱装载问题的基本解法；

1 算法思想
2 货箱装载问题
3 0-1背包问题
4 着色问题
13
分支限界
了解分支限界算法；掌握0-1背包问题、装载问题、旅行商问题的基本解法；并与回溯算法进行比较，加深理解；

1 算法思想
2 装载问题
3 0/1背包问题
4 旅行商问题
14
NP完全理论
初步了解算法复杂性理论，了解NP完全理论，以及P、NP和NPC问题的定义和意义。

1 判定问题
2 P和NP问题
3 NPC的定义
4 电路可满足性问题
5 NPC的证明