高等演算法
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: mind-term exam 25%; homework & programming assignment 25% term-project 15%; final exam 25%; participation 10%
| 週次 | 主題 |
|---|---|
| 第 1 週 | Overview and Introduction |
| 第 2 週 | Review on Time Complexity |
| 第 3 週 | Lower bounds on Problem’s Complexity |
| 第 4 週 | Greedy Algorithms |
| 第 5 週 | Theory of NP-completeness |
| 第 6 週 | Theory of NP-completeness |
| 第 7 週 | Dynamic programming |
| 第 8 週 | Dynamic programming |
| 第 9 週 | Mid-term |
| 第 10 週 | Lower Bounds and Upper Bounds (Lagrangian relaxation) |
| 第 11 週 | Branch-and-Bound Algorithms |
| 第 12 週 | Branch-and-Bound Algorithms |
| 第 13 週 | Design and analysis of heuristics |
| 第 14 週 | Approximation Algorithms (Meta-Heuristics) |
| 第 15 週 | Design of PTAS and FPTAS |
| 第 16 週 | Randomized analysis |
| 第 17 週 | Presentation: Term Project |
| 第 18 週 | Presentation: Term Project |
1. R.C.T. Lee, S.S. Tseng, R.C. Chang (Author), 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
- 時間
- Tuesday EF, Thursday E
- 聯絡方式
- 5712121-57052 bmtlin@mail.nctu.edu.tw