| 課程編碼 Course Code | 中文課程名稱 Course Name (Chinese) | 英文課程名稱 Course Name (English) | 總學分數 Credits | 總時數 Hours |
|---|---|---|---|---|
| 5905101 | 演算法分析與設計 | Design and Analysis of Computer Algorithms | 3.0 | 3 |
| 中文概述 Chinese Description | 1. 數學基礎 1.1 函數成長率之漸近性質 1.2 遞迴關係之解 1.3 數學歸納法 2. 基本分析技巧 2.1 計算複雜度之上下限2.2 最差情況分析及平均情況分析 2.3 動態平均分析 3. 基本設計技巧 3.1 分擊法 3.2 貪婪法 3.3 動態規劃 3.4 隨機演算法 4. 計算複雜度 4.1 資訊理論證明法 4.2 對抗式證明法 4.3 問題之線性轉換 4.4 完全NP | |||
| 英文概述 English Description | 1. Mathematical background 1.1 Asymptotic growth rate of functions 1.2 Solving recurrence relations 1.3 Mathematical induction 2. Basic analysis techniques 2.1 Computational complexities -- lower bounds and upper bounds 2.2 Worst case analysis and average case analysis 2.3 Amortized analysis 3. Basic Design Paradigms 3.1 Divide and conquer 3.2 Greedy methods 3.3 Dynamic programming 3.4 Probabilistic algorithms 4. Computational Complexity 4.1 Information-theoretic arguments 4.2 Adversary arguments 4.3 Linear reduction of problems 4.4 NP-completeness | |||
| 核心能力指標 | A.具備運用資訊、數學之能力，並能充分溝通與表 C.能分析、設計、實作、整合、測試、與評估資訊系統 E.具備策劃及執行研究計畫之能力，並能撰寫論文及進行簡報 | |||
備註：