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

算法设计与分析之进阶篇

所属微专业:

图片
课程概述

本课程不提供教学服务、作业批改及证书发放。

证书要求

本课程不提供证书服务。

预备知识

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

授课大纲

算法设计与分析之进阶篇

第一周 从排序看算法设计与分析

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.

所属微专业

所属系列课程

分享