课程概述
本课程不提供教学服务、作业批改及证书发放。
证书要求
本课程不提供证书服务。
预备知识
集合论图论，高等数学，数据结构与算法。
授课大纲
算法设计与分析之进阶篇
第一周 从排序看算法设计与分析
1-1 从排序看算法分析
1-2快速排序深入剖析
1-3 问题复杂度下界
1-4 基于比较的排序算法的时间复杂度下界
第二周 再论动态规划
2-1 优化子结构的分类
2-2 三角剖分问题
2-3 编辑距离问题
2-4 0-1背包问题
第三周 图上的动态规划算法
3-1 最优二分搜索树
3-2 树的独立集合
3-3 任意两点最短路径问题
第四周 贪心法与拟阵
4-1 最小生成树算法
4-2 拟阵概述
4-3 从拟阵看任务安排问题
第五周 再论搜索
5-1 剪枝方法论与人员安排问题
5-2 旅行商问题
5-3 A*算法
第六周 平摊分析
6-1 平摊分析原理
6-2聚集方法
6-3 会计方法
6-4 势能方法
6-5 动态表操作的平摊分析
参考资料
殷建平, 徐云, 王刚, 刘晓光, 苏明, 邹恒明, 王宏志 (译). 算法导论. 机械工业出版社, 2012. 12.
