计算机硕士课程

默认只展示每周独有的知识重点；节奏、考核、Tutorial 和避坑信息按需展开。

1. 1

   算法分析基础 (Algorithm Analysis)

   ### 📊 核心知识点：渐近复杂性 探讨算法分析的基石。深入理解大O、大Ω、大Θ记号（Big-O, Big-Omega, Big-Theta notation）。 - **核心概念/公式**: Asymptotic Notation, Master Theorem, Recurrence Relations. ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 12h 🎯 **考试关联**: 利用主定理求解递推关系的复杂度。 🧪 **Tutorial/Lab**: 练习从伪代码推导时间复杂度。 📌 **作业关联**: 培养严格的算法证明习惯。 ⚠️ **易错点**: 混淆最坏情况（Worst-case）与大O记号的概念。

2. 2

   分治策略 (Divide and Conquer)

   ### 🔀 核心知识点：分治与递归 学习如何将大问题拆解为子问题。重点分析归并排序（Merge Sort）、快速排序（Quick Sort）及其平均情况复杂度。 - **核心概念/公式**: Randomized Quicksort, Median of Medians, Closest Pair of Points. ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 12h 🎯 **考试关联**: 手写归并排序的合并过程与复杂度证明。 🧪 **Tutorial/Lab**: 实现求解数组中第 K 大元素的线性时间算法。 📌 **作业关联**: Project 1 的基础。 ⚠️ **易错点**: 递归基础情况（Base case）处理遗漏导致无限递归。

3. 3

   动态规划 I (Dynamic Programming)

   ### 🧠 核心知识点：最优子结构与重叠子问题 引入动态规划（DP）思想。学习自底向上的打表法与自顶向下的备忘录法。 - **核心概念/公式**: Overlapping Subproblems, Optimal Substructure, Bellman Equation. ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 15h 🎯 **考试关联**: 写出 DP 状态转移方程（Recurrence relation）。 🧪 **Tutorial/Lab**: 解决经典问题：最长公共子序列（LCS）和矩阵链乘法。 📌 **作业关联**: 复杂数据处理中的最优解问题。 ⚠️ **易错点**: 状态定义不清晰，导致状态转移方程无法涵盖所有情况。

4. 4

   动态规划 II & 贪心算法 (DP & Greedy)

   ### 🎯 核心知识点：背包问题与贪心选择 对比 DP 与贪心算法。解析 0/1 背包问题（必须用 DP）与分数背包问题（可用贪心）。 - **核心概念/公式**: Greedy-choice Property, Knapsack Problem, Huffman Coding. ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 14h 🎯 **考试关联**: 证明某特定问题可以使用贪心算法（交换论证法 Exchange Argument）。 🧪 **Tutorial/Lab**: 实现哈夫曼树进行数据压缩。 📌 **作业关联**: **Assignment 1 发布**，考察 DP 与图算法基础。 ⚠️ **易错点**: 错误地将贪心策略应用于不具备贪心选择性质的问题（如 0/1 背包）。

5. 5

   图算法 I：遍历与拓扑排序 (Graph Algorithms)

   ### 🕸️ 核心知识点：BFS 与 DFS 系统学习图的表示方法（邻接矩阵与邻接表）。深入探索广度优先搜索（BFS）与深度优先搜索（DFS）的应用。 - **核心概念/公式**: Topological Sorting, Strongly Connected Components (SCC), Kosaraju's Algorithm. ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 12h 🎯 **考试关联**: 给出有向图，画出强连通分量。 🧪 **Tutorial/Lab**: 利用有向无环图（DAG）寻找任务的执行顺序。 📌 **作业关联**: 为处理复杂网络网络数据打底。 ⚠️ **易错点**: 混淆有向图中的树边、后向边、前向边与交叉边。

6. 6

   图算法 II：最短路径 (Shortest Paths)

   ### 📍 核心知识点：Dijkstra 与 Bellman-Ford 解决单源最短路径（SSSP）与多源最短路径（APSP）问题。处理带负权边的图网络。 - **核心概念/公式**: Dijkstra's Algorithm, Bellman-Ford, Floyd-Warshall, Negative Cycles. ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 15h 🎯 **考试关联**: 追踪 Dijkstra 算法中优先队列的状态变化。 🧪 **Tutorial/Lab**: 编写算法检测外汇交易中的套利机会（负权环）。 📌 **作业关联**: **Assignment 1 截止**。 🔥 ⚠️ **易错点**: 将 Dijkstra 算法用于包含负权边的图。

7. 7

   图算法 III：最小生成树 (MST) & 网络流 (Network Flow)

   ### 💧 核心知识点：Kruskal, Prim 与最大流 学习贪心算法在 MST 中的经典应用。引入最大流/最小割定理（Max-flow Min-cut Theorem）。 - **核心概念/公式**: Kruskal's, Prim's, Disjoint-Set Data Structure (Union-Find), Ford-Fulkerson. ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 15h 🎯 **考试关联**: 给定流量网络，寻找增广路径并计算最大流。 🧪 **Tutorial/Lab**: 使用并查集优化 Kruskal 算法。 📌 **作业关联**: 二分图匹配问题（Bipartite Matching）。 ⚠️ **易错点**: 混淆网络流中的反向边容量更新逻辑。

8. 8

   字符串匹配算法 (String Matching)

   ### 🔤 核心知识点：KMP 算法与前缀函数 处理大规模文本搜索问题。学习朴素字符串匹配、Rabin-Karp 滚动哈希以及 KMP 算法。 - **核心概念/公式**: Knuth-Morris-Pratt (KMP) Algorithm, Prefix Function (Pi array), Rabin-Karp. ⏰ **本周节奏**: 难度 ⭐⭐⭐ | 预计投入 12h 🎯 **考试关联**: 计算给定模式串的 KMP 前缀数组。 🧪 **Tutorial/Lab**: 比较不同字符串算法在长文本中的执行时间。 📌 **作业关联**: **Assignment 2 发布**，重点考察图论高级应用与高级数据结构。 ⚠️ **易错点**: KMP 算法中状态回退（Fallback）的逻辑边界错误。

9. 9

   计算复杂性理论 I (Complexity Theory)

   ### ⏱️ 核心知识点：P 与 NP 类问题 跨越算法设计，进入计算理论领域。探讨多项式时间可解问题（P）与多项式时间可验证问题（NP）。 - **核心概念/公式**: P vs NP, Deterministic vs Non-deterministic Turing Machines, Polynomial-time Verification. ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐⭐ | 预计投入 18h 🎯 **考试关联**: 简述 NP 类的严格数学定义。 🧪 **Tutorial/Lab**: 理论推演，无编程代码。 📌 **作业关联**: 理解某些问题的不可解性边界。 ⚠️ **易错点**: 误以为 NP 问题就是“Non-Polynomial（非多项式）”问题。

10. 10

    计算复杂性理论 II：NP-Hardness

    ### 🧱 核心知识点：NP 完全性与归约 (Reductions) 学习多项式时间归约（Polynomial-time Reductions）。证明问题的 NP-Complete (NPC) 性质。 - **核心概念/公式**: NP-Complete, NP-Hard, SAT Problem, Clique, Vertex Cover. ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐⭐ | 预计投入 20h 🎯 **考试关联**: 证明问题 B 是 NP-Hard（通过将已知 NPC 问题 A 归约到 B）。 🧪 **Tutorial/Lab**: 练习经典的图论问题归约链条。 📌 **作业关联**: 证明某些算法任务不存在多项式精确解。 ⚠️ **易错点**: 归约方向搞反（必须从已知难问题归约到未知问题）。

11. 11

    近似算法与随机化算法 (Approximation & Randomized Algorithms)

    ### 🎲 核心知识点：应对 NP 难问题 既然 NPC 问题无法在多项式时间内完美解决，我们学习如何寻找有性能保证的近似解（Approximation Ratio）及随机化策略。 - **核心概念/公式**: Approximation Ratio, Vertex Cover Approximation, Randomized Algorithms (Las Vegas vs Monte Carlo). ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 14h 🎯 **考试关联**: 证明某种贪心近似算法的近似比界限。 🧪 **Tutorial/Lab**: 实现 TSP（旅行商问题）的近似算法。 📌 **作业关联**: **Assignment 2 截止**。 🔥 ⚠️ **易错点**: 混淆 Las Vegas 算法（时间随机，结果一定正确）与 Monte Carlo 算法。

12. 12

    期末复习与全课程串讲 (Review)

    ### 📝 复习周：算法思想大一统 串联分治、DP、贪心三大设计范式；总结图论与字符串匹配；回顾 P/NP 的理论天花板。 - **核心概念/公式**: Algorithm Design Paradigms, Reductions summary, Exam Strategy. ⏰ **本周节奏**: 难度 ⭐⭐⭐⭐ | 预计投入 20h+ 🎯 **考试关联**: 综合设计题：给定一个全新的问题，要求分析其复杂度并设计最优算法。 🧪 **Tutorial/Lab**: 历年 Final 真题冲刺解析。 📌 **作业关联**: 查漏补缺。 ⚠️ **易错点**: 考试时只写代码不写证明。COMP90038 极度强调算法正确性的数学证明。