高级算法设计与分析
课程编码：180086081202P2002H
英文名称：Advanced Algorithm - Design and Analysis
课时：60
学分：3.00
课程属性：专业核心课
主讲教师：蔡少伟等
教学目的要求
本课程为计算机学科研究生的专业核心课。本课程讲授和讨论当代算法前沿研究领域的主要思想和关键技术。主要内容有近似算法、随机算法、局部搜索算法、回溯搜索算法等。通过本课程的学习，希望学生能了解信息时代算法前沿研究领域，了解算法研究最新研究成果，掌握基本思想和关键技术，培养学生计算机理论与应用的学科研究能力。要求学生完成课程作业，并通过期末考试。
预修课程
计算机算法设计与分析，离散数学
大纲内容
第一章 近似算法 12学时 陈世腾
第1节 基本概念与一些简单近似算法
第2节 贪心法与次模函数优化
第3节 松弛与取整
第4节 不可近似性
第二章 随机算法 12学时 陈世腾
第1节 拉斯维加斯与蒙特卡洛
第2节 随机行走
第3节 随机变量取值估计：马尔可夫，切比雪夫和切诺夫不等式
第4节 随机算法下界证明：姚的极小极大原则
第三章 回溯算法 9学时 蔡少伟
第1节 约束问题模型
第2节 回溯算法基础
第3节 分支限界算法
第4节 冲突分析算法
第四章 局部搜索算法 9学时 蔡少伟
第1节 局部搜索基础
第2节 局部搜索算法技术
第3节 局部搜索算法分析
第4节 局部搜索算法评估
第五章 线性整数规划算法 9学时 马菲菲
第1节 基于分支限界的线性整数规划
第2节 割平面法
第3节 域传播方法
第4节 线性规划求解器
第六章 约束满足算法 6学时 马菲菲
第1节 CSP回溯算法
第2节 弧相容技术
第3节 CSP求解器
教材信息
1、
Algorithm Design
Jon Kleinberg and Eva Tardos
2005-3
Pearson
参考书
1、
近似算法的设计与分析
堵丁柱,葛可一,胡晓东
2011-8
高等教育出版社
2、
Decision Procedures: An Algorithmic Point of View
Daniel Kroening,Ofer Strichman
2016
Springer
3、
Stochastic Local Search: Foundations and Applications
Holger H. Hoos, Thomas Stützle
2004-9
Morgan Kaufmann
课程教师信息
蔡少伟，中科院软件所研究员，研究方向为约束求解和组合优化；陈世腾，中科院软件所副研究员，研究方向为算法复杂度；马菲菲，中科院软件所研究员，研究方向为自动推理与计数算法。