算法与计算复杂性理论

本课程包括两部分内容:算法理论和计算复杂性理论。计算复杂性理论主要介绍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