| 當期課號 |
2730 |
Course Number |
2730 |
| 授課教師 |
陳永福 |
Instructor |
CHEN,YUNG FU |
| 中文課名 |
演算法概論 |
Course Name |
Introduction to Algorithm |
| 開課單位 |
資訊管理系(四日)二C |
Department |
|
| 修習別 |
選修 |
Required/Elective |
Elective |
| 學分數 |
3 |
Credits |
3 |
| 課程目標 |
演算法概論主要探討排序、遞迴、動態規劃、貪婪演算法、... 等等問題，同時也延續資料結構的課程，探討運作於平衡樹及圖等進階資料結構的演算法，如尋訪、最短路徑等等。教學內容包括 1. 演算法概論 2. Divide-and-Conquer 3. 動態規劃 4. 貪婪演算法 5. 回溯 6. Branch-and-Bound 7. 複雜度計算 8. NP Theory。 |
Objectives |
In this course, we study methods for sorting, recursion,dynamic programming, greedy algorithms, ...etc. In continuation of the data structures course, we also study algorithms for balanced trees and graphs. The contents of the course are as follows: 1.Introduction 2.Divide-and-Conquer 3.Dynamic Programming 4.Greedy Algorithm 5.Backtracking 6.Branch-and-Bound 7.Complexity Computation 8.NP Theory. |
| 教材 |
R.C.T. Lee,R.C. Chang, S.S. Tseng, Y.T.Tsai, Introduction to the Design and Analysis of Algorithms: A strategic approach, McGraw Hill, 2005. (旗標圖書代理) |
Teaching Materials |
R.C.T. Lee,R.C. Chang, S.S. Tseng, Y.T.Tsai, Introduction to the Design and Analysis of Algorithms: A strategic approach, McGraw Hill, 2005. |
| 成績評量方式 |
1.出席(Participation): 10%
2.期中考(Midterm Exam): 25%
3.期末考(Final Exam): 25%
4.隨堂考: 20%
5.作業: 20% |
Grading |
1. Attendance: 10%
2. Midterm Exam: 25%
3. Final Exam: 25%
4. Quiz: 20%
5. Homework: 20% |
| 教師網頁 |
|
| 教學內容 |
(1) 演算法簡介
(2) 演算法的複雜度及問題的下限
(3) 貪婪方法
(4) 各個擊破法的策略
(5) 樹狀搜尋策略
(6) 修整搜尋策略
(7) 動態規劃
(8) NP-complete理論
(9) 近似演算法
(10)分期償還分析 |
Syllabus |
(1) Introduction to Algorithm
(2) The Complexity of Algorithms and Lower Bounds of Problems
(3) The Greedy Method
(4) The Divide-and-conquer Strategy
(5) Tree Searching Strategies
(6) Prune-and-Search Strategy
(7) Dynamic Programming
(8) The Theory of NP-complete
(9) Approximation Algorithms
(10)Amortized analysis |