I3400A 教學大綱表

教學大綱表 (113學年度第1學期)

請遵守智慧財產權，勿使用非法影印教科書，避免觸法。

課程名稱 Course Title	(中文) 計算機演算法 (英文) Algorithms			開課單位 Departments	資訊工程學系
				課程代碼 Course No.	I3400A
授課教師 Instructor	葉慶隆
學分數 Credit	3.0	必/選修 core required/optional	必修	開課年級 Level	大三
先修科目或先備能力(Course Pre-requisites)：
課程概述與目標(Course Overview and Goals)： The course will cover three main areas in computer sciences. (1) Present several important computer science problems and their solutions (2) Present algorithms that can be applied to various problems (3) Introduce mathematical ways to show the correctness and evaluate the performance of algorithms
教科書(Textbook)	Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L. and Stein, Clifford. Introduction to Algorithms Third Edition. The MIT Press on 2009
參考教材(Reference)

課程大綱 Syllabus			學生學習目標 Learning Objectives	單元學習活動 Learning Activities	學習成效評量 Evaluation	備註 Notes
序 No.	單元主題 Unit topic	內容綱要 Content summary	學生學習目標 Learning Objectives	單元學習活動 Learning Activities	學習成效評量 Evaluation	備註 Notes
1	課程簡介及演算法概觀	1. 學習目標、課程大綱 2. 評分方式：筆記、作業、小考、期中考、期末考 3. 演算法定義 4. 排序問題介紹 5. 演算法正確性及效率	學習演算法基礎，包括演算法定義、問題範例。了解演算法正確性及效率
2	演算法入門 I	1. 插入排序法 2. 虛擬碼表示法 3. 迴圈不變性 4. 插入排序法之迴圈不變性 5. 演算法分析法 6. 執行時間分析 7. 執行時間的成長級數 8. 演算法效率 9. 演算法設計：遞增法、分而治之法 10.合併排序法 11.合併排序法之迴圈不變性 12.合併排序法執行時間分析	學習遞增法、分而治之法以排序問題為例學習演算法的正確性及執行時間分析
3	演算法入門 II	1. 插入排序法 2. 虛擬碼表示法 3. 迴圈不變性 4. 插入排序法之迴圈不變性 5. 演算法分析法 6. 執行時間分析 7. 執行時間的成長級數 8. 演算法效率 9. 演算法設計：遞增法、分而治之法 10.合併排序法 11.合併排序法之迴圈不變性 12.合併排序法執行時間分析	學習遞增法、分而治之法以排序問題為例學習演算法的正確性及執行時間分析
4	函數的成長率	1. 演算法的漸進式效率 2. 漸進式表示法、定義、及範例 3. 漸進式數學性質：遞移性、反身性、對稱性、反身對稱性	學習函數成長率及其數學性質
5	分而治之 I	1. 分而治之概述 2. 極大子陣列問題 3. 矩陣乘法 4. 以替代法解遞迴 5. 以遞迴樹法解遞迴 6. 以支配理論法解遞迴	學習分而治之及其範例：極大子陣列、矩陣乘法。學習解數學遞迴的方法，包括替代法、遞迴樹、支配理論
6	分而治之 II	1. 分而治之概述 2. 極大子陣列問題 3. 矩陣乘法 4. 以替代法解遞迴 5. 以遞迴樹法解遞迴 6. 以支配理論法解遞迴	學習分而治之及其範例：極大子陣列、矩陣乘法。學習解數學遞迴的方法，包括替代法、遞迴樹、支配理論
7	堆積排序法	1. 堆積定義、性質 2. 堆積的各種程序、正確性及執行時間分析 3. 堆積排序法	學習利用堆積結構及程序來做排序
8	快速排序法	1. 快速排序法的分而治之架構 2. 快速排序法正確性、執行時間分析	學習快速排序法之分而治之架構極其分析
9	期中考	期中考	評估學生到期中考前課程內容之理解程度
10	雜湊表(哈希表)	1. 雜湊表概觀極其機制 2. 雜湊表之直接定址、串鍊、及開放尋址 2. 碰撞解決及各種探索法	學習雜湊表技術、直接定址、串鍊、及開放尋址。了解碰撞解決及各種探索法
11	動態規劃	1. 動態規劃概述 2. 裝配線調度問題 3. 矩陣串乘法 4. 最長共同子序列問題	學習動規劃方法及各種問題，包括裝配線調度、矩陣串乘法、最長共同子序列問題
12	動態規劃	1. 動態規劃概述 2. 裝配線調度問題 3. 矩陣串乘法 4. 最長共同子序列問題	Learn the main concept of greedy algorithms, and the knapsack problem
13	貪婪演算法	1. 貪婪演算法概述 2. 活動選擇問題 3. 霍夫曼編碼	學習貪婪演算法及各種問題，包括活動選擇問題、霍夫曼編碼
14	基本圖演算法 I	1. 圖的表示法 2. 深度優先搜尋 3. 廣度優先搜尋 4. 拓樸排序法 5. 找出強連通元件	學習圖表示法、基本演算法。延伸至拓樸排序法、及找出強連通元件
15	基本圖演算法 II	1. 圖的表示法 2. 深度優先搜尋 3. 廣度優先搜尋 4. 拓樸排序法 5. 找出強連通元件	學習圖表是法、基本演算法。延伸至拓樸排序法、及找出強連通元件
16	最小生成樹	1. 接線問題概述 2. 最小生成樹形成演算架構 3. 最小生成樹形成演算架構之迴圈不變量 4. Kruskal演算法 5. Prim演算法	從問題中認識最小生成樹，以通用最小生成樹演算架構為基礎，學習不同做法，包括Kruskal和Prim法。
17	單一起點最短路徑	1 最短路徑問題 2. 單一起點最短路徑問題 3. Bellman-Ford 演算法 4. Dijkistra 演算法	學習單一起點最短路徑問題，及各種演算法包括Bellman-Ford及Dijkistra
18	期末考	期末考	評估學生期中考後課程內容理解程度

教學要點概述：
1.自編教材 Handout by Instructor：
□ 1-1.簡報 Slids
□ 1-2.影音教材 Videos
□ 1-3.教具 Teaching Aids
□ 1-4.教科書 Textbook
□ 1-5.其他 Other
□ 2.自編評量工具/量表 Educational Assessment
□ 3.教科書作者提供 Textbook

成績考核 Performance Evaluation：

教學資源(Teaching Resources)：
□ 教材電子檔(Soft Copy of the Handout or the Textbook)
□ 課程網站(Website)
課程網站(Website)：https://ilearn.ttu.edu.tw/course/15149/content#/
扣考規定：https://curri.ttu.edu.tw/p/412-1033-1254.php