計算理論

  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)
  7. 先修課程:自動機與形式語言、演算法
  8. 課程目標:介紹計算理論中幾個重要議題
  9. 評量方式:期中考試 30%,平時成績(作業及小考等)40%,期末考試 30%
  10. 主要教科書:
  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. Approximability
  12. 教學進度:依同學實際接受情形調整