計算複雜度
Computational Complexity
| 節 | 週一 |
|---|---|
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 2023-09-11(一) |
| 第 2 週 | NP and NP completeness Diagonalization 2023-09-18(一) |
| 第 3 週 | Space complexity 2023-09-25(一) |
| 第 4 週 | Polynomial Hierarchy and Alternations 2023-10-02(一) |
| 第 5 週 | Boolean Circuits 2023-10-09(一) |
| 第 6 週 | Randomized computation 2023-10-16(一) |
| 第 7 週 | Interactive proofs 2023-10-23(一) |
| 第 8 週 | PCP theorem and hardness of approximation: An introduction 2023-10-30(一) |
| 第 9 週 | Decision trees 2023-11-06(一) |
| 第 10 週 | Circuit lower bounds 2023-11-13(一) |
| 第 11 週 | Hardness amplification and error-correcting codes 2023-11-20(一) |
| 第 12 週 | Derandomization 2023-11-27(一) |
| 第 13 週 | Pseudorandom constructions: Expanders and extractors 2023-12-04(一) |
| 第 14 週 | Proof of PCP theorems and the Fourier transform technique 2023-12-11(一) |
| 第 15 週 | Communication complexity (if time permit) 2023-12-18(一) |
| 第 16 週 | Cryptography (if time permit) 2023-12-25(一) |
參考書: 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
- 地點
- EC623
- 時間
- By appointment
- 聯絡方式
- sctsai@cs.nycu.edu.tw