演算法
Algorithms
學期
107-2
學分
3
學分
當期課號
5398
永久課號
IAM6506
開課單位
應用數學系
授課教師
陳秋媛
校區
光復
類別
選修
上課時間表
| 節 | 週一 | 週三 |
|---|---|---|
1 08:00–08:50 | 演算法 SC206 2 節連堂 | |
2 09:00–09:50 | ||
3 10:10–11:00 | 演算法 SC206 2 節連堂 | |
4 11:10–12:00 |
* 根據陽明交大上課時間表所列
概述
「演算法」這門課的全名是「計算機方法設計與分析」,換句話說,「演算法」是要給「計算機」用的方法,我們當然希望方法是有效率的,因此,要如何「設計」及如何進行「分析」,就是重點! 「演算法」是最基本的「資訊工程」課程之一。 「演算法」課程的目的在學習 “設計演算法” 及 “分析演算法” 的各種技巧,進而明白 -- 如何為自己所要解決的問題設計出有效率的演算法,以及分析演算法所使用的資源之多寡。
先修科目
需有 "程式寫作" 之經驗,並修過或自學過 "資料結構",無 "料結構基礎" 的同學不適合修這門課。
教學方式
(i) 修課人數上限為15人,優先順序為:交大應數乙組>其餘交大應數碩博>交大應數系大三大四 (大學部需經授課老師同意); 基於校際合作,另接受清華大學數學系碩士班同學,人數上限為3人 (需經授課老師同意)。 (ii) 期中考、期末考、小組上台報告的時間,原則上排定於 星期四 19:00~21:30。 (iii) 本課程為 3學分 3小時課程,但是老師都會多上一些時數; 請注意: 星期三是由 8:30 才開始上課 (iv) 會點名,會經常缺課者切勿修本課程!我很在意學生是否盡力學習,因此會經常缺課者、或無法自動自發努力者,請勿修本課程! 請注意: 實際進度有可能改變!
評分方式
平時表現 (上課出席、課堂參與) 及作業表現佔20%,小組上台報告佔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: 3月28日(四) 19:00~21:30 |
| 第 2 週 | *16 Greedy Algorithms *17 Amortized Analysis *19 Fibonacci Heaps *21 Data Structures and Disjoint Sets 22 Elementary Graph Algorithms 23 Minimum Spanning Trees 24 Single-source Shortest Paths 期中考2: 5月9日(四) 19:00~21:30 |
| 第 3 週 | 25 All-pairs Shortest Paths *26 Maximum Flow *32 String Matching 小組上台報: 5月30日(四) 19:00~21:30 *34 NP-Completeness *35 Approximation Algorithms 期末考: 6月17日(一) 10:10~12:40 |
教科書
Introduction to Algorithms, 3rd Edition, 2009, The MIT Press Cormen, Leiserson, Rivest, and Stein
Office Hours
- 地點
- SA345
- 時間
- 3E and 5G
- 聯絡方式
- TEL: 31767(O) email: cychen@mail.nctu.edu.tw