課程簡介
Course Introduction
《算法與計算復(fù)雜性理論》是計算機科學(xué)與技術(shù)專業(yè)研究生的一門基礎(chǔ)理論課程,包括兩部分內(nèi)容: 算法理論和計算復(fù)雜性理論。通過本課程的學(xué)習(xí), 初步了解NP完全性理論，掌握求解NP難度問題的典型方法和技術(shù)，并在科研工作中能利用這些理論與技術(shù)有效地解決實際問題。
教學(xué)大綱
Teaching Syllabus
本課程包括兩部分內(nèi)容:算法理論和計算復(fù)雜性理論。計算復(fù)雜性理論主要介紹NP完全性理論及其應(yīng)用，特別是NP難度問題的證明方法；算法理論主要介紹算法的基本設(shè)計和分析方法，以及處理NP難度問題的典型技術(shù)與方法，包括啟發(fā)式算法、近似算法、精確算法的設(shè)計技術(shù)。
一、算法基礎(chǔ)
1. 算法及其復(fù)雜性
2. 算法分析的基本技術(shù)
3. 算法設(shè)計的基本方法
二、NP完全性理論
1. 問題及其復(fù)雜性
2. 問題間的歸約技術(shù)
3. 基本的復(fù)雜性類
4. Cook定理
5. 典型NP難度問題的證明
三、NP難度問題求解方法和技術(shù)
1. 啟發(fā)式算法設(shè)計技術(shù)
2. 近似算法設(shè)計技術(shù)
3. 精確算法設(shè)計技術(shù)
教材或參考書:
[1] Jon Kleinberg, Eva Tardos 著, 張立昂,屈婉玲譯. 算法設(shè)計(Algorithm Design). 北京:清華大學(xué)出版社, 2007
[2] Ingo Wegener. 復(fù)雜性理論(影印版) (Complexity Theory). 北京: 科學(xué)出版社, 2006
( Ingo Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms. Springer, 2005 )
[3] M.H.Alsuwaiyel著, 吳偉昶等譯. 算法設(shè)計技巧與分析. 北京: 電子工業(yè)出版社, 2010
[4] 堵丁柱, 葛可一, 胡曉東. 近似算法的設(shè)計與分析. 北京: 高等教育出版社, 2011
