1. 課程代號：210072
2. 課程名稱（中文）：計算理論 (Theory of Computation)
3. 授課教師：黃光璿 (HUANG, Guan-Shieng)
4. 開授年級：研究生與大學部三年級以上同學
5. 學分數：3
6. 授課時數：3 小時（5bcd, 星期五早上 9:10~12:00, 科三 301）
7. 師生晤談時間及地點：科三館314，星期二下午兩點
8. 先修課程：自動機與形式語言、演算法、離散數學
9. 課程目標：介紹資訊科學的幾個核心理論基礎：計算模型(computation models)、可計算性(computability)、NP-completeness, 計算複雜度(computational complexity)
10. 評量方式：期中考試 30%，平時成績（作業及小考等）40%，期末考試 30%
11. 主要教科書：
    Arora, S. and B. Barak, Computational Complexity: A Modern Approach. 2009: Cambridge University Press. (全華圖書公司) (修課同學皆需有課本，請遵守智慧財產權勿非法影印)
12. 重要參考書籍：
    (1) Garey, M.R. and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979: W. H. Freeman and Company.
    (2) Ausiello, G., et al., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. 2003: Springer-Verlag.
    (3) Vazirani, V.V., Approximation Algorithms. 2004: Springer Verlag.
    (4) Sipser, M., Introduction to the Theory of Computation. 2 ed. 2005: Course Technology.
    (5) Kozen, D.C., Theory of Computation. 2006: Springer Verlag.
    (6) Goldreich, O., Computational Complexity: A Conceptual Perspective. 2008: Cambridge University Press.
    (7) Papadimitriou, C.H., Computational Complexity. 1994: Addison-Wesley, ISBN: 978-0201530827. （台北書局代理）
13. 課程綱要：
    (1) The computational model
    (2) NP and NP completeness
    (3) Diagonalization
    (4) Space complexity
    (5) The polynomial hierarchy and alternations
    (6) Boolean circuits
    (7) Randomized computation
    (8) Interactive proofs
    (9) Cryptography
    (10) Quantum computation
    (11) PCP theorem and hardness of approximation: an introduction
14. 教學進度：依課本進度逐頁講授，無課程投影片
15. 滿足本系教育目標：
    配合國家科技發展，培養具備前瞻資訊科技研發潛能的人才。 (學士班)
    配合國家科技及學術發展，培養具備前瞻資訊科技研發能力的人才。 (研究所）
16. 滿足本系下列學生核心能力：
    具備資訊科學基礎數理知識並應用於發掘、分析與解釋數據的能力。 (學士班)
    具備使用英文閱讀資訊領域技術文件的能力。 (學士班)
    具備資訊科學基礎數理知識並應用於發掘、分析與解釋數據的能力。 (研究所）
    具備使用英文閱讀資訊領域技術文件及學術論文的能力。 (研究所）
17. 課程網頁：
    http://staffweb.ncnu.edu.tw/shieng/