哈尔滨工业大学 哈尔滨工业大学

算法设计与分析之近似算法篇

所属微专业:

图片
课程概述

算法设计与分析专题之近似算法。

证书要求

证书规则将在开课前发布

预备知识

集合论图论,高等数学,数据结构与算法。

授课大纲

算法设计与分析之近似算法篇

第一周 近似算法概述

1-1 NP-完全问题

1-2 性能比

1-3 近似算法的例子

第二周 贪心法

2-1 独立系统与拟阵

2-2 独立集合问题

2-3 次模函数

2-4 加权集合覆盖问题

第三周 限制法

3-1 Steiner树问题

3-2 k-限制Steiner树问题

3-3 最小生成树

第四周 松弛法

4-1 松弛概述

4-2超串问题

4-3 LP-松弛

第五周 拟合与对偶

5-1 对偶概述

5-2 集合覆盖的对偶分析

5-3 最大可满足性

第六周 不可近似性

6-1 不可近似性的证明

6-2 旅行商问题

6-3 背包问题

6-4 L-归约

参考资料

殷建平, 徐云, 王刚, 刘晓光, 苏明, 邹恒明, 王宏志 (译). 算法导论. 机械工业出版社, 2012. 12. 

所属微专业

所属系列课程

分享