課程內(nèi)容回顧：核心知識(shí)點(diǎn)梳理

　　本學(xué)期圍繞算法設(shè)計(jì)與分析展開，主要涉及以下幾類內(nèi)容：

　　1. 基礎(chǔ)知識(shí)(Fundamentals)

　　Big-O、Big-Ω 等時(shí)間復(fù)雜度表示法

　　常見算法復(fù)雜度分析方法

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

　　分治思想與主定理

　　最大流模型構(gòu)造(超級(jí)節(jié)點(diǎn)、節(jié)點(diǎn)裂變)

　　最大流算法 FF / EK 的復(fù)雜度比較

　　3. 貪心算法與動(dòng)態(tài)規(guī)劃(Dynamic Programming)

　　貪心策略的正確性與反例構(gòu)造

　　DP 的五大回答結(jié)構(gòu)：

　　子問題定義

　　狀態(tài)轉(zhuǎn)移

　　基礎(chǔ)情況

　　計(jì)算順序

　　最終答案位置

　　4. 計(jì)算理論(Computational Theory)

　　NP / NP-hard / NPC

　　規(guī)約流程及常見題型

　　期末復(fù)習(xí)課結(jié)構(gòu)：4+1 復(fù)習(xí)模式

　　復(fù)習(xí)通常由四節(jié)核心復(fù)習(xí)課與一節(jié)綜合答疑課構(gòu)成：

　　復(fù)習(xí) 1：基礎(chǔ)知識(shí) + 分治

　　復(fù)習(xí) 2：貪心 + 最大流

　　復(fù)習(xí) 3：計(jì)算理論 + 動(dòng)態(tài)規(guī)劃

　　復(fù)習(xí) 4：大題示例講解(算法設(shè)計(jì))

　　答疑課：綜合答疑、典型錯(cuò)題講解

　　由于今年取消選擇題，整體復(fù)習(xí)時(shí)長縮短，更聚焦于算法大題的設(shè)計(jì)與分析。

　　期末試卷結(jié)構(gòu)變化：僅剩五道大題

　　今年題型改革后，試卷由五大題構(gòu)成，整體呈現(xiàn) 3+2 的結(jié)構(gòu)：

　　3 道算法分析題(Analysis)

　　2 道算法設(shè)計(jì)題(Design)

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

　　三道算法分析題：高頻考點(diǎn)拆解

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

　　(1)動(dòng)態(tài)規(guī)劃(DP)分析(必考)

　　常見考點(diǎn)包括：

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

　　寫出狀態(tài)轉(zhuǎn)移過程

　　判斷基礎(chǔ)情況是否合理

　　找到最終答案的返回位置

　　識(shí)別算法中的陷阱并指出錯(cuò)誤原因

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

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

　　考點(diǎn)主要集中在兩個(gè)方向：

　?、?規(guī)約(Reduction)

　　將給定問題規(guī)約到標(biāo)準(zhǔn) NP 或 NPC 問題

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

　?、?時(shí)間復(fù)雜度與可優(yōu)化性(小概率)

　　分析給定算法復(fù)雜度

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

　　計(jì)算理論變化多端，但考點(diǎn)穩(wěn)定，整體難度較高。

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

　　二者的出現(xiàn)概率為：

　　貪心 60%

　　最大流 30%

　　貪心常見考法：

　　給出一個(gè)錯(cuò)誤的貪心策略

　　要求：

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

　　構(gòu)造反例證明其錯(cuò)誤

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

　　最大流常見考法：

　　可能出現(xiàn)兩種形式：

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

　　找出其構(gòu)造錯(cuò)誤(尤其是節(jié)點(diǎn)裂變錯(cuò)誤最常見)

　　給出正確構(gòu)造方式

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

　　證明其正確性(節(jié)點(diǎn)構(gòu)造/邊權(quán)設(shè)置)

　　分析時(shí)間復(fù)雜度(FF / EK 比較)

　　兩道算法設(shè)計(jì)題：25+25 的核心難點(diǎn)

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

　　(1)動(dòng)態(tài)規(guī)劃設(shè)計(jì)(DP Design)—100% 會(huì)考

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

　　重點(diǎn)方法：

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

　　設(shè)計(jì)狀態(tài)、轉(zhuǎn)移與邊界條件

　　DP 是本課程最能體現(xiàn)思維深度的部分，也是最重要的高分點(diǎn)。

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

　　第二道設(shè)計(jì)題通常是一個(gè)組合結(jié)構(gòu)：

　　分治 + 貪心

　　分治 + 最大流

　　二者出現(xiàn)概率約為 50% / 50%。

　　例如：

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

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

　　重點(diǎn)在于學(xué)生是否能識(shí)別題目結(jié)構(gòu)并選擇合適的算法框架。

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

　　為了幫助應(yīng)試時(shí)迅速分辨題目類型，可建立題型識(shí)別框架：

　?、?是否出現(xiàn)圖(Graph)?

　　→ 大概率最大流(Max Flow)

　　② 是否強(qiáng)調(diào)“最優(yōu)”“最小”“最大”“最早”等關(guān)鍵詞?

　　→ 大概率貪心(Greedy)

　?、?是否出現(xiàn)明顯的“子問題遞推關(guān)系”?

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

　?、?是否出現(xiàn)“divide”、“split”、“median”、“two groups”?

　　→ 分治(Divide & Conquer)

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

　　今年復(fù)習(xí)時(shí)間變化：選擇題取消后的影響

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

　　復(fù)習(xí)內(nèi)容更集中于大題

　　每節(jié)復(fù)習(xí)課時(shí)長減少

　　課程重點(diǎn)進(jìn)一步向算法思維、推導(dǎo)邏輯與模型構(gòu)建傾斜

　　此外，復(fù)習(xí)階段仍會(huì)穿插典型 Problem Set 題目，用于幫助學(xué)生熟悉大題類型與算法思想積累。

　　結(jié)語：建立“整體結(jié)構(gòu)感”是高分關(guān)鍵

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

　　無論是 DP、分治、最大流還是規(guī)約，本質(zhì)都包含：

　　抽象建模

　　結(jié)構(gòu)拆解

　　正確性論證

　　復(fù)雜度分析

　　掌握結(jié)構(gòu)化的思考方式，將是順利通過期末考試的關(guān)鍵。