新南威尔士大学25T3 COMP9101/3121 final考前解析

　　课程内容回顾：核心知识点梳理

　　本学期围绕算法设计与分析展开，主要涉及以下几类内容：

　　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、分治、最大流还是规约，本质都包含：

　　抽象建模

　　结构拆解

　　正确性论证

　　复杂度分析

　　掌握结构化的思考方式，将是顺利通过期末考试的关键。