計算理論(Theory of Computation)

1. 課程代號：210039
2. 課程名稱（中文）：計算理論
   課程名稱（英文）：Theory of Computation
3. 授課教師：黃光璿 (HUANG, Guan-Shieng)
4. 開授年級：研究生與大學部三年級以上同學
5. 學分數：3
6. 授課時數：3 小時（2cd, 4i, 星期二早上 10:00 ~ 12:00, 星期四下午 5:00 ~ 6:00）科三 301
7. 先修課程：自動機與形式語言、演算法、離散數學
8. 課程目標：介紹計算理論中幾個重要觀念
9. 評量方式：期中考試 30%，平時成績（作業及小考等）40%，期末考試 30%
10. 主要教科書：
    • Computational Complexity, C. H. Papadimitriou, Addison-Wesley Pub Co, 1994. （台北書局代理）
11. 課程綱要：
    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. Primality Testing
    9. Approximability
12. 教學進度：依同學實際接受情形調整