《算法设计与分析》PPT课件 张德富 厦门大学

 
课件内容： 
算法概述及复杂性理论（授课人：张德富，曾华琳；总时长：1小时32分） 
了解该课程要解决的问题；了解算法的概念；掌握算法的正确性证明方法；了解问题的下界的描述方法。 
1 问题 
2 算法的概念 
3 算法的正确性 
4 算法的效率 
5 问题的下界 
算法分析方法（授课人：张德富；总时长：1小时37分） 
掌握概率分析在算法复杂度分析中的应用；掌握分摊分析方法；了解实验分析方法。 
1 概率分析 
2 合计方法 
3 记账方法 
4 势能方法 
5 实验分析 
递归（授课人：张德富；总时长：1小时19分） 
了解递归的算法思想；根据选择排序和全排列生成问题掌握设计递归算法的一般步骤；求解递归方程。 
1 递归的算法思想 
2 选择排序 
3 生成排列 
4 递归方程的求解 
分治（上）（授课人：曾华琳；总时长：1小时31分） 
了解分治的算法思想；根据案例掌握分治算法设计的一般步骤； 
1 算法思想 
2 二分搜索 
3 快速排序 
4 归并排序 
分治（下）与动态规划（上）（授课人：曾华琳；总时长：1小时35分） 
根据残缺棋盘游戏进一步了解分治算法，难点在于理解分治算法“分”出的子问题必须具有相似的结构；初步了解动态规划算法，难点在于如何根据递推关系式填表； 
1 残缺棋盘游戏 
2 大整数乘法 
3 矩阵乘法 
4 动态规划引言 
5 动态规划算法思想 
6 矩阵链乘法问题 
动态规划（中）（授课人：张德富，曾华琳；总时长：1小时38分） 
根据多个案例进一步了解掌握动态规划算法，难点在于递推关系式的推导；根据装配线调度问题了解动态规划的另一种求解方法：备忘录法； 掌握如何使用递归方法构造最优解； 
1 最优二叉搜索树问题 
2 最大字段和问题 
3 装配线调度问题 
4 最长公共子序列问题 
动态规划（下）与贪心算法（上）（授课人：张德富；总时长：1小时33分） 
由背包问题理解动态规划最优子结构性质；根据任务调度问题理解贪心算法； 对比区分贪心算法与动态规划算法，难点在于贪心算法的证明； 
1 0/1背包问题 
2 动态规划的基本性质 
3 贪心算法思想 
4 任务选择问题（上） 
贪心算法（下）（授课人：曾华琳；总时长：1小时49分） 
由任务选择问理解贪心算法；由背包问题进一步区分动态规划与贪心算法； 理解Huffman编码中的贪心策略； 
1 任务选择问题（下） 
2 背包问题 
3 哈夫曼编码问题 
4 任务选择实验 
图算法（上）（授课人：张德富；总时长：1小时19分） 
了解图的基本概念、表示方法、了解两种存储图的方式（邻接矩阵与邻接表）及各自优势；掌握图的深度优先搜索与广度优先搜索算法，难点在于DFS的递归与非递归实现； 掌握图的最小生成树问题及其解法； 
1 图的表示 
2 宽度优先搜索 
3 深度优先搜索 
4 最小生成树问题–Kruskal算法 
图算法（下）（授课人：张德富；总时长：1小时21分） 
了解最短路问题的定义；掌握两种基本最短路问题求解算法； 掌握、区分Prim算法与Kruskal算法； 
1最小生成树问题–Kruskal 与 Prim 比较 
2 最短路径问题 
3 单源最短路径问题 
4 所有点对的最短路径问题 
网络流与匹配（授课人：张德富；总时长：1小时38分） 
了解最大流问题的定义；掌握求解最大流问题的基本算法； 了解最大费用流问题的定义； 
1 最大流问题 
2 最大流问题求解 
3 最小费用流 
回溯（授课人：曾华琳；总时长：1小时27分） 
了解回溯的定义；掌握0-1背包问题、货箱装载问题的基本解法； 
1 算法思想 
2 货箱装载问题 
3 0-1背包问题 
4 着色问题 
分支限界（授课人：曾华琳；总时长：1小时29分） 
了解分支限界算法；掌握0-1背包问题、装载问题、旅行商问题的基本解法；并与回溯算法进行比较，加深理解； 
1 算法思想 
2 装载问题 
3 0/1背包问题 
4 旅行商问题 
NP完全理论（授课人：张德富；总时长：1小时31分） 
初步了解算法复杂性理论，了解NP完全理论，以及P、NP和NPC问题的定义和意义。 
1 判定问题 
2 P和NP问题 
3 NPC的定义 
4 电路可满足性问题 
5 NPC的证明