高等演算法
Advanced Computer Algorithms
| 節 | 週二 |
|---|---|
2 09:00–09:50 | 高等演算法 MB311（光復） 3 節連堂 |
3 10:10–11:00 | |
4 11:10–12:00 |
* 根據陽明交大上課時間表所列
The theme is to prepare the participants with fundamentals of combinatorial optimization and solution approaches for solving optimization problems. Through theoretical studies as well as computer implementation, we will gain analytical and computational techniques that are useful for optimization research.
Computer Programming or Data Structures
無備註
教師未提供此項資料
Grading: homework & programming assignment 40% paper presentation: 15% term-project 35%; participation 10%
教師未提供此項資料
| 週次 | 主題 |
|---|---|
| 第 1 週 | Overview and Introduction 0917 |
| 第 2 週 | Review on Time Complexity 0926 |
| 第 3 週 | Lower bounds on Problem's Complexity 1001 |
| 第 4 週 | Greedy Algorithms 1008 |
| 第 5 週 | Theory of NP-completeness 1015 |
| 第 6 週 | Theory of NP-completeness 1022 |
| 第 7 週 | Dynamic programming 1029 |
| 第 8 週 | Dynamic programming 1105 |
| 第 9 週 | Mid-term 1112 |
| 第 10 週 | Lower Bounds and Upper Bounds (Lagrangian relaxation) 1119 |
| 第 11 週 | Branch-and-Bound Algorithms 1126 |
| 第 12 週 | Branch-and-Bound Algorithms 1203 |
| 第 13 週 | Design and analysis of heuristics 1210 |
| 第 14 週 | Approximation Algorithms (Meta-Heuristics) 1217 |
| 第 15 週 | Design of PTAS and FPTAS 1224 |
| 第 16 週 | Randomized analysis 1231 |
| 第 17 週 | Presentation: Term Project 0107 |
| 第 18 週 | Presentation: Term Project 0114 |
1. R.C.T. Lee, S.S. Tseng, R.C. Chang, Y.T.Tsai, Introduction to the Design and Analysis of Algorithms, McGraw-Hill, 2005. 2. T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 3rd Ed., MIT Press, 2008. 3. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979, San Francisco. 4. G. Ausiello, P. Cresenzi, G. Gambois, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag, 2003, Germany. 5. Selected journal papers
- 地點
- MB310
- 時間
- Monday EF, Thursday E
- 聯絡方式
- 5712121-57052 bmtlin@mail.nctu.edu.tw