課程簡介
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
