當期課號 | 2687 | Course Number | 2687 |
---|---|---|---|
授課教師 | 洪若偉 | Instructor | HUNG,RUO WEI |
中文課名 | 演算法概論 | Course Name | Introduction to Algorithm |
開課單位 | 資訊工程系(四日)三B | Department | |
修習別 | 必修 | Required/Elective | Required |
學分數 | 3 | Credits | 3 |
課程目標 | 本課程主要介紹演算法的設計與觀念,學生在完成本課程後,將可了解關於演算法的設計理念,其主要涵蓋的範圍有: 1. 演算法的複雜度與計算下限的方法 2. NP-Complete的問題 3. 貪婪方法的介紹 4. Divide-and-conquer的方法 5. 搜尋的方法 6. Prune-and-search的策略 7. 動態規劃 |
Objectives | The goal of this course is to provide the students with a basic knowledge of computer algorithm. The students will realize the following important algorithm topics after finishing this course: 1. Complexity of algorithms and lower bounds of problems 2. NP-complete 3. Greedy method 4. Divide-and-conquer 5. Tree searching strategies 6. Prune-and-search strategy 7. Dynamic programming |
教材 | 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. 隨堂考n次: 20% 2. 期中考(Midterm Exam) 2次: 60% 3. 期末考(Final Exam): 30% 4. 課程參與(Participation): 5% |
Grading | 1. Quizzes in Class: 20% 2. Midterm Exam*2: 60% 3. Final Exam: 30% 4. Participation: 5% |
教師網頁 | http://www.cyut.edu.tw/~rwhung | ||
教學內容 | 本課程主要目標為學習設計有效率演算法及瞭解設計好的演算法來解決問題的困難處. 此課程的內容包括: (1) 演算法簡介 (2) 演算法的複雜度及問題的下限 (3) 貪婪方法 (4) 各個擊破法的策略 (5) 樹狀搜尋策略 (6) 修整搜尋策略 (7) 動態規劃 (8) NP-complete理論 (9) 近似演算法 (10)分期償還分析 |
Syllabus | The main goals of the course are to learn strategies to design efficient algorithms and to understand the difficulty of designing good algorithms for some problems, namely NP-complete problems. The contents of this course include: (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 |