哈尔滨工业大学

算法设计与分析入门

图片
课程概述

“算法设计与分析”有用

算法是计算机科学的核心主题之一,其重要性不言而喻。有一个好的算法设计与分析功底是从事计算机相关各种工作的坚实基础。从就业来看,算法基础是许多名企面试必考的内容;从科学研究来看,算法设计与分析是计算机科学诸多领域研究中必须的技能。

“算法设计与分析”有趣

这是一门有趣的课程,算法给了我们一个看待世界和看待生活的新方式,从中学到的不仅是让计算机做事情的方式,还有“递归”、“分治”“优化”、“剪枝”等等一系列可能改变生活的思维方法。

“算法设计与分析”需要努力学习

和很多知识性的课程不同,算法设计与分析是一门重视能力的课程,如同九阴真经,是一门既修炼“内功”也修炼内功的学科。因此学习算法设计与分析既需要像数学课一样的证明、又需要像程序设计语言一样的写码,因而需要格外的努力才可以学得好。


证书要求

60分以上颁发合格证书

80分以上颁发优秀证书

预备知识

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

授课大纲


第一周

1-1     什么是算法?

1-2     计算机科学中算法的位置

1-3     算法分析引论

1-4     算法设计引论

第二周

2-1 阶:描述复杂性的语言

2-2 和的估计

2-3 递归方程的求解

第三周

3-1 分治法

3-2 分治法的简单实例:整数乘法与最大最小值选取

3-3 元素选取问题的线性时间算法 (选修)

3-4 快速傅里叶变换

第四周

4-1 动态规划的原理

4-2 矩阵乘法问题

4-3 最长公共子序列问题

第五周

5-1 贪心法的基本原理

5-2 任务安排问题

5-3 哈夫曼编码问题

第六周

6-1 暴力美学:搜索漫谈

6-2 深度优先与广度优先

6-3 搜索的优化

第七周

7-1 字符串搜索概述

7-2 Rabin-Karp算法

7-3 KMP算法

7-4 BMH算法


参考资料

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