難解計算問題專論
Selected Topics in Intractable Problems
學期
109-2
學分
0
學分
當期課號
5296
永久課號
IDS5012
開課單位
數據科學與工程研究所碩士班
授課教師
蔡孟宗
校區
光復
類別
選修
上課時間表
| 節 | 週二 |
|---|---|
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
Office Hours
- 地點
- TBA
- 時間
- TBA
- 聯絡方式
- mttsai@iis.sinica.edu.tw