| 一、教學目標 |
藉由學習好的演算技巧，使得學生可以設計有效率的電腦程式，
進而了解問題的難易。 |
| 二、先修科目 |
資料結構 |
| 三、教材內容 |
課程內容包括學習如何分析一個演算法的複雜度與界定一個問題難度的下界，
並完整介紹整套NP-completeness計算理論。
其中關於解決問題所使用的有效技巧，課程中將介紹一般常用的「貪婪法」、
「各個擊破法」、「樹狀搜尋法」、「修剪與搜尋」、與「動態規劃法」。
同時課程中也將簡介一些演算法新的發展方向，包括「近似演算法」、
「攤還分析」、「隨機演算法」、「線上演算法」等概念。 |
| 四、教學方式 |
課堂講授（使用 PowerPoint） |
| 五、參考書籍 |
1. Introduction to the Design and analysis of Algorithms (2nd Ed)
--- R.C.T. Lee
2. Introduction to Algorithms (2nd Ed)
--- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein |
| 六、教學進度 |
第一章 Introduction (對應系所指標 - 資管專才)
第二章 The complexity of algorithms and the lower bound of problems
(對應系所指標 - 務實學習)
第三章 The greedy method (對應系所指標 - 創新研究)
第四章 The divide-and-conquer strategy (對應系所指標 - 創新研究)
第五章 Tree searching strategies (對應系科指標 - 創新研究)
第六章 Prune and Search (對應系所指標 - 創新研究)
第七章 Dynamic programming (對應系所指標 - 創新研究)
第八章 The theory of NP-completeness (對應系所指標 - 資管專才) |
| 七、評量方式 |
期中考 40%，期末報告 50%，作業 10% |
| 八、講義位址 |
ftp://140.131.114.243/教材/陳恩航老師/演算法 |
