難解計算問題專論
Selected Topics in Intractable Problems
| 節 | 週二 |
|---|---|
5 13:20–14:10 | 難解計算問題專論 EC115（光復） 3 節連堂 |
6 14:20–15:10 | |
7 15:30–16:20 |
* 根據陽明交大上課時間表所列
Understand the limit of computers, and learn how to design algorithms for intractable problems.
Introduction to Algorithms, Introduction to Formal Language, Probability, Linear Algebra, Data Structures and Object-Oriented Programming 學士班學生須修通演算法概論和正規語言概論才可修難解計算問題專論
無備註
Course Materials: https://e3new.nctu.edu.tw/login/index.php ; Online Judge: https://oj.nctu.me
4 written assignments and 4 programming assignments. Take best 5 out of the 8 assignments.
教師未提供此項資料
| 週次 | 主題 |
|---|---|
| 第 1 週 | NP-hardness, Exponential-time Hypothesis |
| 第 2 週 | NP-intermediate, Sparse Languages |
| 第 3 週 | Enumeration, Bitwise Parallelism |
| 第 4 週 | Pruning by Fractional Solutions |
| 第 5 週 | #P-hardness |
| 第 6 週 | Probabilistic Methods |
| 第 7 週 | PTAS, Separator Theorems |
| 第 8 週 | PCP Theorem |
| 第 9 週 | PCP Theorem |
| 第 10 週 | APX-hardness |
| 第 11 週 | Approximation Algorithms |
| 第 12 週 | Approximation Algorithms |
| 第 13 週 | W Hierarchy |
| 第 14 週 | Fixed-Parameter Algorithms |
| 第 15 週 | Fixed-Parameter Algorithms |
| 第 16 週 | RP, co-RP, BPP, ZPP |
| 第 17 週 | Randomized Algorithms |
| 第 18 週 | Semidefinite Programming |
Research papers
- 地點
- TBA
- 時間
- TBA
- 聯絡方式
- mttsai@iis.sinica.edu.tw