1. 課程代號：210072
2. 課程名稱（中文）：計算理論
3. 課程名稱（英文）：Theory of Computation
4. 授課教師：黃光璿 (HUANG, Guan-Shieng)
5. 開授年級：研究生與大學部三年級以上同學
6. 學分數：3
7. 授課時數：3小時（5bcd, 星期五早上9:10~12:00, 科三119）
8. 先修課程：自動機與形式語言、演算法、離散數學
9. 課程目標：介紹計算理論中幾個重要觀念
10. 評量方式：期中考試30%，平時成績（作業及小考等）40%，期末考試30%
11. 主要教科書：
Computational Complexity, by C. H. Papadimitriou, Addison-Wesley, 1994, ISBN-13:
978-0201530827. （台北書局代理）
12. 重要參考書籍：
(1) Introduction to the Theory of Computation, Second Edition, bu Michael Sipser, Course Technology, 2005, ISBN-13: 978-0534950972.
(2) Theory of Computation (Texts in Computer Science), by Dexter C. Kozen, Springer, 2006, ISBN-13: 978-1846282973.
(3) Approximation Algorithms, by Vijay V. Vazirani, Springer, 2004, ISBN-13: 978-3540653677.
(4) Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, by G. Ausiello (Author), P. Crescenzi (Author), V. Kann (Author), Marchetti-sp (Author), Giorgio Gambosi (Author), Alberto M. Spaccamela, Springer, 2003, ISBN-13: 978-3540654315.
(5) Computers and Intractability: A Guide to the Theory of NP-Completeness, by M. R. Garey (Author), D. S. Johnson, W. H. Freeman, 1979, ISBN-13: 978-0716710455.
13. 課程綱要：
(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
14. 教學進度：依同學實際接受情形調整