計算複雜度
Computational Complexity
學期
112-1
學分
3
學分
當期課號
535521
永久課號
CSIC30162
開課單位
資訊科學與工程研究所
授課教師
蔡錫鈞
校區
光復
類別
選修
上課時間表
| 節 | 週一 |
|---|---|
3 10:10–11:00 | 計算複雜度 ED302 2 節連堂 |
4 11:10–12:00 |
* 根據陽明交大上課時間表所列
概述
使學生了解有關計算問題的複雜度,學習相關證明方法及最近相關發展
先修科目
演算法概論、正規語言概論或瞭解Turing Machine及NP-Complete等概念
教學方式
課堂講授
評分方式
5-6 次作業: 30% 期中考: 40% 報告: 30%
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | NP and NP completeness |
| 第 2 週 | NP and NP completeness Diagonalization |
| 第 3 週 | Space complexity |
| 第 4 週 | Polynomial Hierarchy and Alternations |
| 第 5 週 | Boolean Circuits |
| 第 6 週 | Randomized computation |
| 第 7 週 | Interactive proofs |
| 第 8 週 | PCP theorem and hardness of approximation: An introduction |
| 第 9 週 | Decision trees |
| 第 10 週 | Circuit lower bounds |
| 第 11 週 | Hardness amplification and error-correcting codes |
| 第 12 週 | Derandomization |
| 第 13 週 | Pseudorandom constructions: Expanders and extractors |
| 第 14 週 | Proof of PCP theorems and the Fourier transform technique |
| 第 15 週 | Communication complexity (if time permit) |
| 第 16 週 | Cryptography (if time permit) |
教科書
參考書: 1. Computational Complexity: A Modern Approach, Sanjeev Arora, Boaz Barak, published by Cambridge University Press, 2009 2. Theory of Computational Complexity, 2nd Ed, Ding-Zhu Du and Ker-I Ko, published by John Wiley & Sons, 2014 3. Introduction to the Theory of Computation, 3rd Ed. Michael Sipser, published by Cengage Learning, 2012
Office Hours
- 地點
- EC623
- 時間
- By appointment
- 聯絡方式
- sctsai@cs.nycu.edu.tw