課程編碼 Course Code | 中文課程名稱 Course Name (Chinese) | 英文課程名稱 Course Name (English) | 總學分數 Credits | 總時數 Hours |
---|---|---|---|---|
3105125 | 演算法分析與設計 | Design and Analysis of Computer Algorithms | 3.0 | 3 |
中文概述 Chinese Description | 本課程介紹電腦科學中演算法的原理、分析與設計策略,使學生了解各種演算法的設計,訓練如何分析解決實際的問題,以便學生可以設計有效率的電腦演算法程式,進而了解問題的難易,增加實作演算法能力。課程內容包括學習分析一個演算法的複雜度與界定一個問題難度的下界,並完整介紹整套NP-completeness計算理論。其中關於解決問題所使用的有效技巧,課程中將介紹一般常用的「貪婪法」、「各個擊破法」、「樹狀搜尋法」、「修剪與搜尋」、與「動態規劃法」及其它主題。同時課程中也將簡介演算法新的發展方向,包括「近似演算法」、「攤還分析」、「隨機演算法」、「線上演算法」等概念。最後並透過相關論文的研讀及討論,以了解近代演算法的最新發展趨勢。 | |||
英文概述 English Description | The course includes: Mathematical background、Basic analysis techniques、Computational complexities、Worst case analysis and average case analysis、Basic Design Paradigms、Divide and conquer、Greedy methods、Dynamic programming、Probabilistic algorithms、Computational Complexity、Linear reduction of problems、NP-completeness。 |
備註: