演算法是電腦科學與軟體開發中不可或缺的一部分。在現實生活中，我們會遇到各式各樣的計算問題，並撰寫程式來解決它們。透過學習演算法的設計，我們得以將前人發展出的解題策略應用到未來可能出現的各種問題中。藉由演算法的分析，我們可以估算並掌握程式的執行效能。此外，解決一個問題的方法往往不止一種，如何分析與比較不同解法的優劣，將有助於在實作方面做出較佳的選擇。 這門課是資訊工程學系大二上必修課程。這是一門偏向理論的課程。在這門課中，我們會先討論一些演算法設計的典範 (algorithm paradigms, 如試誤法、貪婪策略、分而治之、動態規劃等經典策略) 與分析方法 (如複雜度的分析、近似演算法的分析等)。接著，我們將介紹兩項近年來對於演算法設計，非常重要的數學模型媒介：圖 (graph, as in graph theory) 與線性規劃 (linear programs)。在接近期末的時候，我們將討論一點點演算法與計算理論之間的關聯，並將不同的題目透過轉化 (reduction) 連結在一起。惟有透過一點點的理論分析，我們才能夠證明某個問題的解法是最佳的，從而理解演算法設計的極限。

（一）演算法的分析 ? 能理解演算法的正確性仰賴於數學證明而非測試資料集。 ? 能理解演算法的分析仰賴於計算模型與明確的演算法描述。 ? 能理解並欣賞經典演算法。 （二）演算法的設計 ? 能掌握經典演算法的設計原則並加以應用。 ? 能將自己想出來的演算法以自己熟悉的程式語言實作出來。 ? 能活用兩款常見的數學模型：圖與線性規劃。 （三）演算法效能的極限 ? 能理解 P ?= NP 這個世紀大哉問。 ? 能理解轉化 (reduction) 的重要性、基本原則、常見證明方法。

? 基本程式設計能力 (我會假設您已經修過本系開設之《計算機程式設計》課程) ? 熟悉基本資料結構的觀念與實作：陣列、堆疊、佇列、鏈結串列、樹、二元平衡樹、圖 (我會假設您已經修過本系開設之《資料結構與演算法》課程) ? 基本的數學推理能力 (我會假設您已經修習過高中數學，包含但不限於《指數與對數》、《等比級數》、《排列組合》、《古典機率》、《函數》，以及大一《微積分》課程)

[CLRS] Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms. 4th ed. MIT Press, 2022. ISBN: 978-0262046305 [KT] Jon Kleinberg and Eva Tardos. Algorithm Design. Pearson, 2005. ISBN: 978-0321295354 [R] Tim Roughgarden. Algorithms Illuminated Omnibus Edition. Cambridge University Press, 2022. ISBN: 978-0999282984. URL: https://www.algorithmsilluminated.org/ [E] Jeff Erickson. Algorithms. Independently published. 2019. ISBN: 978-1792644832. URL: https://jeffe.cs.illinois.edu/teaching/algorithms/