課程內容回顧：核心知識點梳理

　　本學期圍繞算法設計與分析展開，主要涉及以下幾類內容：

　　1. 基礎知識(Fundamentals)

　　Big-O、Big-Ω 等時間復雜度表示法

　　常見算法復雜度分析方法

　　2. 分治(Divide & Conquer)與最大流(Max Flow)

　　分治思想與主定理

　　最大流模型構造(超級節點、節點裂變)

　　最大流算法 FF / EK 的復雜度比較

　　3. 貪心算法與動態規劃(Dynamic Programming)

　　貪心策略的正確性與反例構造

　　DP 的五大回答結構：

　　子問題定義

　　狀態轉移

　　基礎情況

　　計算順序

　　最終答案位置

　　4. 計算理論(Computational Theory)

　　NP / NP-hard / NPC

　　規約流程及常見題型

　　期末復習課結構：4+1 復習模式

　　復習通常由四節核心復習課與一節綜合答疑課構成：

　　復習 1：基礎知識 + 分治

　　復習 2：貪心 + 最大流

　　復習 3：計算理論 + 動態規劃

　　復習 4：大題示例講解(算法設計)

　　答疑課：綜合答疑、典型錯題講解

　　由于今年取消選擇題，整體復習時長縮短，更聚焦于算法大題的設計與分析。

　　期末試卷結構變化：僅剩五道大題

　　今年題型改革后，試卷由五大題構成，整體呈現 3+2 的結構：

　　3 道算法分析題(Analysis)

　　2 道算法設計題(Design)

　　其中，算法分析題難度集中、考點明確，而算法設計題分值高(通常為 25+25)，對學生的整體算法思維要求更高。

　　三道算法分析題：高頻考點拆解

　　根據 sample 試卷與往年題型總結，三道分析題通常來自以下模塊：

　　(1)動態規劃(DP)分析(必考)

　　常見考點包括：

　　給定偽代碼，判斷其子問題定義

　　寫出狀態轉移過程

　　判斷基礎情況是否合理

　　找到最終答案的返回位置

　　識別算法中的陷阱并指出錯誤原因

　　出題方式通常為給出看似正確的算法，要求分析其邏輯、指出缺陷并修正。

　　(2)計算理論(Computational Theory)(高概率必考)

　　考點主要集中在兩個方向：

　　① 規約(Reduction)

　　將給定問題規約到標準 NP 或 NPC 問題

　　證明其復雜性類別(P / NP / NP-hard / NPC)

　　② 時間復雜度與可優化性(小概率)

　　分析給定算法復雜度

　　給出可行的優化方式(例如：從 O(n!) 優化至 O(2?) 等)

　　計算理論變化多端，但考點穩定，整體難度較高。

　　(3)貪心(Greedy)或最大流(Max Flow)(二選一)

　　二者的出現概率為：

　　貪心 60%

　　最大流 30%

　　貪心常見考法：

　　給出一個錯誤的貪心策略

　　要求：

　　找到可被該策略“碰巧解決”的實例

　　構造反例證明其錯誤

　　在原策略基礎上進行 輕微修改(而非完全重寫)

　　最大流常見考法：

　　可能出現兩種形式：

　　A. 給出錯誤的最大流模型(高概率)

　　找出其構造錯誤(尤其是節點裂變錯誤最常見)

　　給出正確構造方式

　　B. 給出正確模型(低概率)

　　證明其正確性(節點構造/邊權設置)

　　分析時間復雜度(FF / EK 比較)

　　兩道算法設計題：25+25 的核心難點

　　設計題通常是整份試卷中最難的部分，題目開放度大、要求高。

　　(1)動態規劃設計(DP Design)—100% 會考

　　幾乎必考 DP，且通常為 多變量 DP。

　　重點方法：

　　從題目中“可變化的量”尋找 DP 維度

　　設計狀態、轉移與邊界條件

　　DP 是本課程最能體現思維深度的部分，也是最重要的高分點。

　　(2)分治 + (貪心 / 最大流)組合設計

　　第二道設計題通常是一個組合結構：

　　分治 + 貪心

　　分治 + 最大流

　　二者出現概率約為 50% / 50%。

　　例如：

　　類似作業中的“運輸車問題”(分治 + 最大流)

　　類似分治搜索 + 貪心的混合策略

　　重點在于學生是否能識別題目結構并選擇合適的算法框架。

　　整體解題策略：快速識別題型的“四步法”

　　為了幫助應試時迅速分辨題目類型，可建立題型識別框架：

　　① 是否出現圖(Graph)?

　　→ 大概率最大流(Max Flow)

　　② 是否強調“最優”“最小”“最大”“最早”等關鍵詞?

　　→ 大概率貪心(Greedy)

　　③ 是否出現明顯的“子問題遞推關系”?

　　→ 典型 DP(Analysis 或 Design 均可能)

　　④ 是否出現“divide”、“split”、“median”、“two groups”?

　　→ 分治(Divide & Conquer)

　　此框架可幫助在看到大題時迅速鎖定大類，提升整體答題效率。

　　今年復習時間變化：選擇題取消后的影響

　　由于今年考試取消選擇題，意味著：

　　復習內容更集中于大題

　　每節復習課時長減少

　　課程重點進一步向算法思維、推導邏輯與模型構建傾斜

　　此外，復習階段仍會穿插典型 Problem Set 題目，用于幫助學生熟悉大題類型與算法思想積累。

　　結語：建立“整體結構感”是高分關鍵

　　COMP9101/3121 的期末核心不在于題量，而在于對算法思想的全面理解。

　　無論是 DP、分治、最大流還是規約，本質都包含：

　　抽象建模

　　結構拆解

　　正確性論證

　　復雜度分析

　　掌握結構化的思考方式，將是順利通過期末考試的關鍵。