算法设计与分析 (2022秋季)

课程简介

算法是计算机科学的核心和基石. 本课程关注算法的两个重要方面: 设计与分析. 课程将介绍经典的算法设计范式和技术, 包括分治、动态规划、贪心算法和回溯算法, 进而介绍复杂性理论初步和一些高级的算法设计技术, 如随机算法. 课程还将介绍算法分析方法, 包括算法的正确性证明和复杂度分析技术. 通过课程的学习, 希望学生能够掌握基本算法设计与分析技术, 掌握用算法高效、正确求解问题的全过程, 即建模—设计—分析.

课程的主要内容安排如下:

• 课程简介 [lec 0]
• 引论及基础知识 [lec 1]
• 算法分析的数学基础 [lec 2] [lec 3]
• 分治算法 [lec 4] [lec 5]
• 贪心算法 [lec 6] [lec 7]
• 动态规划算法 [lec 8] [lec 9] [lec 10]
• 回溯算法 [lec 11] [lec 12]
• 计算复杂性理论初步 [lec 13]
• 随机算法 [lec 14]
• 课程小结 [summary]

作业: [homework]

必备知识

• 离散数学
• 程序语言设计
• 数据结构

参考书目

• Algorithms. Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. The McGraw-Hill Companies, 2008.
• 算法设计与分析(第二版), ISBN: 978-7-302—42450-5. 屈婉玲, 刘田, 张立昂, 王捍贫. 清华大学出版社, 2016.2.
• 算法设计与分析(第四版), ISBN: 978-7-302—51010-9. 王晓东. 清华大学出版社, 2018.10.

考试