课程信息
讲授: 陈宇                           yuchen@sdu.edu.cn
助教: 郑萌、梁文宁     SDU_Algorithms_TA@163.com
上课安排
课程简介
算法是计算机科学的核心和基石. 本课程关注算法的两个重要方面: 设计与分析. 课程将介绍经典的算法设计范式和技术, 包括分治、动态规划、贪心算法和回溯算法, 进而介绍复杂性理论初步和一些高级的算法设计技术, 如随机算法. 课程还将介绍算法分析方法, 包括算法的正确性证明和复杂度分析技术. 通过课程的学习, 希望学生能够掌握基本算法设计与分析技术, 掌握用算法高效、正确求解问题的全过程, 即建模—设计—分析.
课程的主要内容安排如下:
- 课程简介 [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.