演算法
Algorithms
學期
106-2
學分
3
學分
當期課號
5405
永久課號
IAM6506
開課單位
應用數學系
授課教師
陳秋媛
校區
光復
類別
選修
上課時間表
| 節 | 週三 | 週五 |
|---|---|---|
3 10:10–11:00 | 演算法 SC206 2 節連堂 | 演算法 SC206 2 節連堂 |
4 11:10–12:00 |
* 根據陽明交大上課時間表所列
概述
「演算法」這門課的全名是「計算機方法設計與分析」,換句話說,「演算法」是要給「計算機」用的方法,我們當然希望方法是有效率的,因此,要如何「設計」及如何進行「分析」,就是重點! 「演算法」是最基本的「資訊工程」之課程,身為E-世代或C-世代的你絕對需要具備「資訊」能力,「演算法」課程的目的在學習 “設計演算法” 及 “分析演算法” 的各種技巧,進而明白 -- 如何為自己所要解決的問題設計出有效率的演算法,以及分析演算法所使用的資源之多寡。
先修科目
需有程式寫作之經驗,並修過或自學過"資料結構"。
教學方式
(i) 修課人數上限為15人,優先順序為:交大應數乙組>其餘交大應數碩博>交大應數系大三大四(大學部均需經授課老師同意) (ii) 會點名,會經常缺課者切勿修本課程!我很在意學生是否盡力學習,因此會經常缺課者、或無法自動自發努力者,請勿修本課程! (iii) 請注意:實際進度有可能改變!
評分方式
平時表現 (上課出席,課堂參與) 及作業表現佔20%,projects佔20%,期中考1佔20%,期中考2佔20%,期末考佔20%
週次計畫
| 週次 | 主題 |
|---|---|
| 第 1 週 | 1 The Role of Algorithms in Computing 2 Getting Started 3 Growth of Functions 4 Divide-and-Conquer (Matrix Multiplication) 6 Heapsort 7 Quicksort 8 Sorting in Linear Time *9 Medians and Order Statistics *15 Dynamic Programming ===期中考1 |
| 第 2 週 | *16 Greedy Algorithms *17 Amortized Analysis *19 Fibonacci Heaps ===project 1 *21 Data Structures and Disjoint Sets 22 Elementary Graph Algorithms 23 Minimum Spanning Trees 24 Single-source Shortest Paths ===期中考2 |
| 第 3 週 | 25 All-pairs Shortest Paths *26 Maximum Flow *32 String Matching ===project 2 *34 NP-Completeness *35 Approximation Algorithms ===期末考 |
教科書
Introduction to Algorithms, 3rd Edition, 2009, The MIT Press Cormen, Leiserson, Rivest, and Stein
Office Hours
- 地點
- SA345
- 時間
- 開學後確定
- 聯絡方式
- 31767(O) cychen@mail.nctu.edu.tw