本课程主要介绍算法设计与分析的基本方法以及算法复杂性理论基础。通过本课程的学习,要求学生理解并熟练掌握递归与分治法、贪心法、动态规划方法、回溯法、分支定界法,以及高级图论算法、线性规划算法等,理解并掌握算法复杂性的分析方法、NP完全性理论基础等计算复杂性的基本知识及完备性证明概要。
本课程的培养目标是,通过教学和实践,培养学生从算法的角度运用数学工具分析问题和解决问题的基本能力,从而使他们能够正确地分析和评价一个算法,进一步设计出真正有效的算法。此外,配合实验课程的教学,学生应理论联系实际,理论指导实践,通过规范地完成一系列算法设计实验进一步巩固所学的相关书本知识,在知识、能力、素质上得到进一步的提高。
单元作业占50%,期末考试占50%, 按百分制计分,60分至79分为合格,80分至100分为优秀。成绩合格及优秀的同学可付费申请认证证书。
高等数学或数学分析、线性代数或高等代数、概率论与数理统计、离散数学(含图论、集合论、近世代数、数理逻辑基础)、数字逻辑、高级语言程序设计、数据结构
《算法设计与分析》,张德富,高等教育出版社,2009
《算法设计与分析》,王秋芬,清华大学出版社,2011
《算法设计与分析》,王红梅,清华大学出版社,2013
《Introduction to Algorithms》,The MIT Press,2001