Type of Credit: Elective
Credit(s)
Number of Students
我們身處在 AI 的時代，常常聽到各大平台網紅們討論「演算法」如何對上架影音、文字披露於目標對象的影響力。此外，在現今的科技業界，主管在面試軟體工程師時經常提出具體問題，並要求應試者現場解題或說明思路，已是相當普遍的作法。熟悉語法、選擇實作框架....等等撰寫程式的技能，對開發進度固然重要，然而，對軟體工程專案而言，演算法無疑地扮演猶如經脈的角色。經脈若順暢，人們自然神清氣爽、活動自如；一個「不複雜」的演算法，不只帶來高效率的執行結果，更能創造絕佳的使用者體驗。
本課程從經典的電腦科學問題開始，帶領同學們思考一個演算法一般是如何產生的？如何拆解問題、組合結果？如何設計資料結構、因應演算法的需求？如何將模糊不明的解題方向，具體為解題步驟？最後藉由作業、上機練習等方式，讓同學從實作過程中，體會演算法和程式設計之間的緊密連結，並在面對特定問題時，能夠從所學中分析、提出解決方案／演算法，在小組專案中實作應用。
能力項目說明
| 教學週次Course Week | 彈性補充教學週次Flexible Supplemental Instruction Week | 彈性補充教學類別Flexible Supplemental Instruction Type |
|---|---|---|
|
週次 |
課程主題 |
課程內容與指定閱讀 |
教學活動與作業 |
學習投入時間 |
|
|
課堂講授 |
課程前後 |
||||
|
1 |
Introduction |
本學期簡介、重點複習 Python |
講授、上機練習 |
3 |
3 |
|
2 |
Data Structures and Algorithms |
演算法設計策略：歸納、分解與重組、貪婪演算法、動態規劃 |
講授 |
3 |
3 |
|
3 |
Design of Algorithm by Induction |
從經典問題思考設計演算法：Skyline Problem, Balance Factor in Binary Tree, Finding Maximum Consecutive Subsequence, Knapsack Problem |
講授、上機練習、作業（一） |
3 |
3 |
|
4 |
Sequence and Sets |
序列與集合：搜尋問題 |
講授 |
3 |
3 |
|
5 |
序列與集合：排序問題 |
10/09放假、作業（二） |
3 |
3 |
|
|
6 |
序列與集合：比對、對齊、配對、及相關應用 |
講授、上機練習 |
3 |
3 |
|
|
7 |
Graph Algorithms (I) |
圖形演算法：簡介、定義、基本問題 |
講授 |
3 |
3 |
|
8 |
期中上機考 |
公開資料集簡介 |
上機寫作業（三）、期末報告分組 |
3 |
3 |
|
9 |
Graph Algorithms(II) |
經典圖形問題：拓樸排序、無權重最短路徑、有向圖最短路徑 |
講授 |
3 |
3 |
|
10 |
最短路徑問題：經典演算法及應用 |
講授、上機練習、作業（四） |
3 |
3 |
|
|
11 |
更多圖形問題：圖著色問題、最大流問題、圖分解問題 |
講授 |
3 |
3 |
|
|
12 |
Geometric Algorithms |
幾何演算法：簡介、定義、基本問題 |
講授、上機練習、作業（五） |
3 |
3 |
|
13 |
Reduction |
演算法設計策略：化簡問題、思考、及演練 |
講授 |
3 |
3 |
|
14 |
NP-Completeness |
決策問題與最優化問題：簡介、定義、基本問題 |
講授、上機練習 |
3 |
3 |
|
15 |
好困難的問題：簡介、定義、經典問題 |
講授 |
3 |
3 |
|
|
16 |
期末報告 |
|
|
3 |
6 |
|
17 |
自主學習 |
|
|
|
|
|
18 |
自主學習 |
|
|
|
|
課堂參與、上機練習：30%
作業（5次）：50%
期末報告（小組）：20%
*學生使用生成式AI完成作業時，須註明使用的工具或軟體所涵蓋的作業範圍。
指定書：
• Introduction to Algorithms: A Creative Approach, Udi Manber, Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA.
參考書：
• Introduction to Algorithms (fourth edition), Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein., MIT Press.
• Cracking the Coding Interview (6th Edition), Gayle Laakmann Mcdowell, Careercup..