课程简介
course introduction
《算法与计算复杂性理论》是计算机科学与技术专业研究生的一门基础理论课程,包括两部分内容: 算法理论和计算复杂性理论。通过本课程的学习, 初步了解np完全性理论，掌握求解np难度问题的典型方法和技术，并在科研工作中能利用这些理论与技术有效地解决实际问题。
教学大纲
teaching syllabus
本课程包括两部分内容:算法理论和计算复杂性理论。计算复杂性理论主要介绍np完全性理论及其应用，特别是np难度问题的证明方法；算法理论主要介绍算法的基本设计和分析方法，以及处理np难度问题的典型技术与方法，包括启发式算法、近似算法、精确算法的设计技术。
一、算法基础
1. 算法及其复杂性
2. 算法分析的基本技术
3. 算法设计的基本方法
二、np完全性理论
1. 问题及其复杂性
2. 问题间的归约技术
3. 基本的复杂性类
4. cook定理
5. 典型np难度问题的证明
三、np难度问题求解方法和技术
1. 启发式算法设计技术
2. 近似算法设计技术
3. 精确算法设计技术
教材或参考书:
[1] jon kleinberg, eva tardos 著, 张立昂,屈婉玲译. 算法设计(algorithm design). 北京:清华大学出版社, 2007
[2] ingo wegener. 复杂性理论(影印版) (complexity theory). 北京: 科学出版社, 2006
( ingo wegener. complexity theory: exploring the limits of efficient algorithms. springer, 2005 )
[3] m.h.alsuwaiyel著, 吴伟昶等译. 算法设计技巧与分析. 北京: 电子工业出版社, 2010
[4] 堵丁柱, 葛可一, 胡晓东. 近似算法的设计与分析. 北京: 高等教育出版社, 2011
留言板
message board
