【991教學大網】演算法設計與分析
|
系所 |
資訊科技與管理研究所 |
1 年級 |
|
課號 / 班別 |
ms1103 / A |
3 學分 |
|
科目中文名稱 |
演算法設計與分析 |
|
|
科目英文名稱 |
Algorithm Design and Analysis |
|
|
每週授課時數 |
3 小時 |
必選科目 |
|
|
張肇明 |
|
|
開課期間 |
一學期 |
|
|
人數上限 |
15 人 |
|
中文說明：
|
一、教學目標 |
藉由學習好的演算技巧，使得學生可以設計有效率的電腦程式，進而了解問題的難易。 |
|
二、先修科目 |
資料結構 |
|
三、教材內容 |
Introduction to the Design and analysis of Algorithms (2nd Ed) --- R.C.T. Lee（旗標圖書） |
|
四、教學方式 |
課堂講授（使用 PowerPoint）
課程內容包括學習如何分析一個演算法的複雜度與界定一個問題難度的下界，並完整介紹整套NP-completeness計算理論。
其中關於解決問題所使用的有效技巧，課程中將介紹一般常用的「貪婪法」、「各個擊破法」、「樹狀搜尋法」、「修剪與搜尋」、與「動態規劃法」。
同時課程中也將簡介一些演算法新的發展方向，包括「近似演算法」、「攤還分析」、「隨機演算法」、「線上演算法」等概念。 |
|
五、參考書籍 |
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 theory of NP-completeness 第四章 The greedy method 第五章 The divide-and-conquer strategy 第六章 Tree searching strategies 第七章 Prune and Search 第八章 Dynamic programming |
|
七、評量方式 |
平常考核 20%，期中考 40%，期末報告 40% |
|
八、講義位址 |
|