课程概述
高级算法设计与分析。
证书要求
证书规则将在开课前发布
预备知识
集合论图论，高等数学，数据结构与算法。
授课大纲
算法设计与分析之高级篇
第一周 NP完全问题
1-1 NP完全性
1-2 NP完全性的证明
1-3 有代表性的NP完全问题
第二周 近似算法概论
2-1 近似算法与近似比
2-2 顶点覆盖问题
2-3 旅行商问题
第三周 近似算法例析
3-1 贪心法：集合覆盖问题
3-2 线性规划法：带权顶点覆盖问题
3-3 FPTA：子集和问题
第四周 随机算法
4-1 随机算法概述
4-2蒙特卡洛算法
4-3 拉斯维加斯算法
4-4 舍伍德算法
第五周 在线算法
5-1 在线算法概念介绍
5-2 在线磁盘调度算法
5-3 在线最小生成树算法
第六周 智能优化算法
6-1 智能优化算法简介
6-2 遗传算法
6-3 局部搜索与模拟退火算法
6-4 蚁群算法
参考资料
殷建平, 徐云, 王刚, 刘晓光, 苏明, 邹恒明, 王宏志 (译). 算法导论. 机械工业出版社, 2012. 12.
