1. 課程代號：210072
2. 課程名稱（中文）：計算理論
3. 課程名稱（英文）：Theory of Computation
4. 授課教師：黃光璿 (HUANG, Guan-Shieng)
5. 開授年級：研究生與大學部三年級以上同學
6. 學分數：3
7. 授課時數：3 小時（5bcd, 星期五早上 9:10~12:00, 科三 301）
8. 師生晤談時間及地點：科三館314，星期二下午兩點
9. 先修課程：自動機與形式語言、演算法、離散數學
10. 課程目標：介紹資訊科學的幾個核心理論基礎：計算模型(computation models)、可計算性(computability)、NP-completeness, 計算複雜度(computational complexity)
11. 評量方式：期中考試 30%，平時成績（作業及小考等）40%，期末考試 30%
12. 主要教科書：
    Papadimitriou, C.H., Computational Complexity. 1994: Addison-Wesley, ISBN: 978-0201530827. （台北書局代理）
(修課同學需要有課本，請遵守智慧財產權勿非法影印)
13. 重要參考書籍：
    (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.
14. 課程綱要：
    (1) Turing Machines
    (2) Computability
    (3) Boolean Logic
    (4) Relations Between Complexity Classes
    (5) Reductions and Completeness
    (6) NP-complete Problems
    (7) Randomized Computation
    (8) Approximation Computation
15. 教學進度：依同學實際接受情形調整