難解計算問題專論
Selected Topics in Intractable Problems
學期
111-2
學分
3
學分
當期課號
535529
永久課號
CSIC30158
開課單位
資訊科學與工程研究所
授課教師
高孟駿
校區
光復
類別
選修
上課時間表
| 節 | 週五 |
|---|---|
5 13:20–14:10 | 難解計算問題專論 ED102 2 節連堂 |
6 14:20–15:10 |
* 根據陽明交大上課時間表所列
概述
This course aims to provide an in-depth introduction on fixed-parameter tractability (FPT) and a mild introduction on computational complexity theory with a focus on NP characterization and polynomial-time approximability. Course website: https://sites.google.com/nycu.edu.tw/111-2-int-problem-complexity
先修科目
Linear Algebra, Probability, Algorithms, Formal Language
教學方式
Lecture, prepared material, online material.
評分方式
Topic study & presentation (book chapter / research paper): 60% Final exam: 40%
課程大綱
- Parameterized Algorithms & Fixed-parameter Tractability
- Hierarchies of integer programming relaxations
- Hardness of Approximation
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | *** Parameterized Algorithms & FPT *** Introduction |
| 第 2 週 | Kernelization, Bounded search trees |
| 第 3 週 | Iterative compression, Randomized methods |
| 第 4 週 | Treewidth and Tree decomposition |
| 第 5 週 | Fixed-parameter intractability, The W-hierarchy |
| 第 6 週 | Other topics (TBA) |
| 第 7 週 | (Tentative) *** Hierarchies of Integer Programming Relaxations *** Lovasz-Schrijver Hierarchy, Sherali-Adams Hierarchy |
| 第 8 週 | The Lasserre Hierarchy |
| 第 9 週 | *** NP Characterization & Hardness of Approximation *** Interactive proof system The PCP theorem and Characterization of NP |
| 第 10 週 | PCP theorem and Hardness of Approximation |
| 第 11 週 | The Unique Game Conjecture (UGC), Best algorithm & best lower-bound for the problems? |
| 第 12 週 | (Tentative) Proof of PCP theorem (sketch) |
| 第 13 週 | Final Exam |
| 第 14 週 | Group Presentation |
| 第 15 週 | Group Presentation |
| 第 16 週 | Group Presentation |
| 第 17 週 | |
| 第 18 週 |
教科書
1. Parameterized algorithms, by Marek Cygan et al., 2016. 2. Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak, 2009.