最新文章

《算法导论》学习要点（全 35 章）¶

本讲义以 CLRS《算法导论》（Introduction to Algorithms，第四版）为基础，按章节提取核心学习要点，帮助学习者系统掌握算法设计与分析的完整知识体系。

教学建议：建议按”基础（1–9）→ 数据结构（10–19）→ 图算法（20–25）→ 高级专题（26–31）→ 应用与前沿（32–35）”的顺序学习；每章先掌握核心概念与算法流程，再理解正确性证明与复杂度分析，最后通过习题巩固。

目录¶

第一部分 基础（第 1–5 章）¶

• 第 1 章 算法在计算中的作用
• 第 2 章 起步（插入排序与分治法入门）
• 第 3 章 刻画运行时间（渐近记号）
• 第 4 章 分治策略与递归式求解
• 第 5 章 概率分析与随机化算法

第二部分 排序与顺序统计（第 6–9 章）¶

• 第 6 章 堆排序
• 第 7 章 快速排序
• 第 8 章 线性时间排序
• 第 9 章 中位数与顺序统计

第三部分 数据结构（第 10–13 章）¶

• 第 10 章 基本数据结构
• 第 11 章 散列表
• 第 12 章 二叉搜索树
• 第 13 章 红黑树

第四部分 高级设计与分析技术（第 14–19 章）¶

• 第 14 章 动态规划
• 第 15 章 贪心算法
• 第 16 章 摊还分析
• 第 17 章 扩充的数据结构
• 第 18 章 B 树
• 第 19 章 用于不相交集合的数据结构

第五部分 图算法（第 20–25 章）¶

• 第 20 章 基本的图算法
• 第 21 章 最小生成树
• 第 22 章 单源最短路径
• 第 23 章 所有结点对的最短路径
• 第 24 章 最大流
• 第 25 章 二分图中的匹配

第六部分 高级专题（第 26–31 章）¶

• 第 26 章 并行算法
• 第 27 章 在线算法
• 第 28 章 矩阵运算
• 第 29 章 线性规划
• 第 30 章 多项式与快速傅里叶变换（FFT）
• 第 31 章 数论算法

第七部分 应用与前沿（第 32–35 章）¶

• 第 32 章 字符串匹配
• 第 33 章 机器学习算法
• 第 34 章 NP 完全性
• 第 35 章 近似算法

第一部分：基础（第 1–5 章）¶

第 1 章 算法在计算中的作用（The Role of Algorithms in Computing）¶

教学目标¶

• 理解算法的严格定义、正确性概念及其在计算中的核心地位
• 建立”算法即技术”的价值观，理解效率的重要性

核心学习要点¶

1. 算法的定义与正确性¶

• 算法：任何良定义的（well-defined）计算过程，以某个值或值的集合作为输入，在有限时间内产生输出；是”将输入变换为输出”的计算步骤序列。
• 问题实例（instance）：问题陈述规定了期望的输入/输出关系，一个具体输入即为一个实例。
• 正确算法：对每一个输入实例，在有限时间内停机并输出正确解。不正确的算法有时也有用（如可控制错误率的随机算法，第 31 章的素性测试），但通常只研究正确算法。
• 排序问题示例：输入 n 个数的序列，输出非递减排列——引出全书的第一个经典问题。

2. 算法解决的实际问题类别：
   - 大规模数据处理（人类基因组计划、搜索引擎）
   - 路由与网络（最短路径，第 22 章）
   - 信息安全（公钥密码学与数字签名，第 31 章）
   - 资源配置（线性规划，第 29 章）
   - 图像识别（聚类，第 33 章）
   - 数据压缩（Huffman 编码，第 15 章）

1.2 算法作为一种技术¶

• 效率：算法的增长速率（order of growth）决定了其在大输入下的可用性；硬件速度无法替代渐近效率。
• 算法与其他技术的关系：与快速硬件、GUI、面向对象系统、网络等技术并列，是计算的核心技术之一。

1.3 困难问题与模型¶

• 并非所有问题都有高效算法：有些问题（如 NP 完全问题，第 34 章）很可能不存在多项式时间算法。
• 并行计算（第 26 章）、量子计算等替代计算模型可能改变效率的图景。

必须掌握的关键词¶

算法、问题实例、正确性、输入/输出规格、增长速率、困难问题、数据结构、算法设计技术、计算模型

第 2 章 起步：插入排序与归并排序（Getting Started）¶

教学目标¶

• 掌握插入排序（增量法）与归并排序（分治法）两个入门算法
• 学会用循环不变式证明算法正确性
• 理解算法分析的基本框架：最坏情形、平均情形、增长阶

2.1 插入排序¶

• 算法思想：增量式（incremental）——每次将一个元素插入到已排序子序列的正确位置，类似整理扑克牌。
• 伪代码约定：缩进表示块结构、数组下标从 1 开始、for/while/repeat 循环、A.length 等，需熟悉本书伪代码风格。
• 循环不变式（loop invariant）证明三要素：
  1. 初始化：循环开始前不变式为真；
  2. 保持：若某次迭代前为真，则迭代后仍为真；
  3. 终止：循环终止时，不变式提供有用性质以证明算法正确。
• 对插入排序：每次迭代开始时，子数组 A[0..j-1] 已有序（其中包含原 A[0..j-1] 的元素）。
• 复杂度：最好 Θ(n)（已有序），最坏 Θ(n²)，平均 Θ(n²)。

2.2 分析算法¶

• RAM 模型：随机存取机——单处理器、顺序执行、每条指令代价为常数；对算法分析是合适的抽象。
• 输入规模：多数问题为输入项的数目 n；也可用位数或二进制表示长度。
• 运行时间：基本操作步数；通常关注最坏情形运行时间 T(n)（保证上界、常出现）。
• 平均情形：对输入分布做假设（如等可能）；期望运行时间。
• 增长阶（order of growth）：忽略常数因子与低阶项，只关注主导项，如 Θ(n²) 表示运行时间随 n² 增长。

2.3 设计算法：分治策略¶

• 分治法三步骤：分解（Divide）→ 解决（Conquer，递归求解子问题）→ 合并（Combine）。
• 归并排序（merge sort）：分解为两个规模 n/2 的子数组，递归排序，线性时间合并（MERGE 过程，借助哨兵）。
• 归并排序运行时间：递归式 T(n) = 2T(n/2) + Θ(n)，解为 Θ(n log n)。
• 归并排序与插入排序的对比：n 很大时，Θ(n log n) 显著优于 Θ(n²)。

本章必须掌握¶

循环不变式、正确性证明、最坏情形与平均情形、增长阶、增量法 vs 分治法、插入排序、归并排序、MERGE 过程

第 3 章 刻画运行时间（Characterizing Running Times）¶

教学目标¶

• 精确定义五大渐近记号（O、Ω、Θ、o、ω）
• 掌握渐近记号的运算性质与常用数学函数

3.1 渐近记号（非正式理解）¶

• Θ-notation（渐近紧确界）：f(n) = Θ(g(n)) 表示 f 被 c₁g(n) 与 c₂g(n) 上下夹住（n ≥ n₀）。
• O-notation（渐近上界）：f(n) = O(g(n)) 表示 f 不超过 c·g(n)（最多差常数因子）。
• Ω-notation（渐近下界）：f(n) = Ω(g(n)) 表示 f 至少为 c·g(n)。
• 例：插入排序最坏情形运行时间 T(n) = Θ(n²)，但作为一般上界写作 O(n²)；所有情况均为 Ω(n)。

3.2 形式化定义与性质¶

• 精确数学定义（存在正常数 c、n₀ 使不等式对所有 n ≥ n₀ 成立）。
• o-notation（非紧上界）与 ω-notation（非紧下界）：类比 < 与 ≤ 的区别；如 2n = o(n²) 但 n² ≠ o(n²)。
• 渐近记号间的关系：f = Θ(g) ⇔ f = O(g) 且 f = Ω(g)（类比 f = g 与 f ≤ g、f ≥ g）。
• 运算性质：传递性、自反性、对称性（仅 Θ）；渐近记号用于等式中的含义（= 为”是”关系；等式右边存在某函数属于左侧集合）。

3.3 标准记号与常用函数¶

• 单调性、下取整 ⌊x⌋ 与上取整 ⌈x⌉ 的性质。
• 模运算：a mod n。
• 多项式：P(n) 为 d 次多项式 ⇒ P(n) = Θ(n^d)。
• 指数：所有底数 a>1 的指数函数增长都快于任何多项式。
• 对数：对数函数增长慢于任何正幂多项式；换底公式；lg、ln 记号。
• 阶乘 n!：n! = ω(2ⁿ)，n! = o(nⁿ)；斯特林近似 n! ≈ √(2πn)(n/e)ⁿ。
• 函数迭代 f⁽ᵏ⁾(n) 与重对数函数 lg* n（lg* n = min{i ≥ 0 : lg⁽ⁱ⁾ n ≤ 1}）。
• 斐波那契数：F₀=0, F₁=1，Fₙ = Fₙ₋₁+Fₙ₋₂，与黄金比例 φ 的关系 Fₙ = φⁿ/√5（取整）。

本章小结¶

五个渐近记号的定义与关系、渐近记号在等式中的使用约定、常用数学函数及其增长速率排序、迭代对数、斐波那契数

第 4 章 分治策略（Divide-and-Conquer）¶

教学目标¶

• 深入理解分治法，掌握三个例子：矩阵乘法（Strassen）、以及一般的递归式求解
• 熟练掌握三种求解递归式的方法：代换法、递归树法、主方法
• 进阶：Akra-Bazzi 方法

4.0 递归式基础¶

• 递归式（recurrence）：用更小规模自身描述运行时间的等式，如 T(n) = 2T(n/2) + Θ(n)。
• 分治递归式的一般形式：T(n) = aT(n/b) + f(n)（a 个子问题，规模 n/b，分解与合并代价 f(n)）。
• 关于边界条件、取整、技术细节的约定（可忽略 floor/ceil，通常不影响渐近界）。

4.1 矩阵乘法的分治算法¶

• 朴素分治：8 次 n/2 规模乘法，递归式 T(n) = 8T(n/2) + Θ(n²)，解为 Θ(n³)——与朴素三重循环相同。
• 说明简单的分治不一定更优，但为 Strassen 奠定基础。

4.2 Strassen 算法¶

• 核心思想：用 7 次递归乘法（而非 8 次）加 O(n²) 次加减法完成 2×2 矩阵乘法。
• 递归式 T(n) = 7T(n/2) + Θ(n²)，解为 Θ(n^lg7) ≈ Θ(n^2.81)。
• 是超越 Θ(n³) 的第一个矩阵乘法；需了解其 7 个辅助矩阵的定义与”不进则退”的常数开销（实际中通常只在 n 很大时采用）。

4.3 代换法（substitution method）¶

• 两步：猜测形式（如 T(n) = O(n log n)），归纳证明。
• 技巧：猜测时”减掉一个低阶项”（如 cn log n − dn）以规避归纳证明中的余项；
• 常见陷阱：错误猜测（过大/过小）、忽略渐近记号中的常数（须严格证明 T(n) ≤ cn log n）。
• 变量代换（如 n = 2^m 将 T(2^m) 化为 S(m)）也属于该法的变形。

4.4 递归树法（recursion-tree method）¶

• 把递归展开为树：每层代价相加，总代价 = 各层代价之和。
• 适用于产生猜测，再经代换法验证（树法本身不算严格证明，但直观）。
• 例子：T(n) = 3T(n/4) + Θ(n²) 的递归树——每层代价递减为等比，根为支配项。

4.5 主方法（master method）¶

• 主定理：若 T(n) = aT(n/b) + f(n)，其中 a ≥ 1, b > 1，f(n) 为渐进正函数，则：
  1. 若 f(n) = O(n^{log_b a − ε})（n^ε）则 T(n) = Θ(n^{log_b a})；
  2. 若 f(n) = Θ(n^{log_b a}) 则 T(n) = Θ(n^{log_b a} log n)；
  3. 若 f(n) = Ω(n^{log_b a + ε}) 且存在 c<1 使 a f(n/b) ≤ c f(n)（正则条件），则 T(n) = Θ(f(n))。
• 三种情况反映：叶子代价支配、每层代价相等、根代价支配。
• 注意主方法不适用的情形（如 f(n)/n^{log_b a} 不在多项式差距：如 f(n) = n log n 与 log_b a = 1）。

★ 4.6–4.7 进阶¶

• 连续主定理（continuous master theorem）及其证明思路（积分形式）。
• Akra-Bazzi 方法：处理 T(n) = Σ aᵢ T(bᵢ n) + f(n) 这类更一般的递归式，结果为 Θ(n^p (1 + ∫₀ⁿ f(x)/x^{p+1} dx))，其中 p 满足 Σ aᵢ bᵢ^p = 1。

本章小结¶

分治范式、矩阵乘法（朴素 vs Strassen）、递归式、代换法、递归树、主定理及其适用条件、Akra-Bazzi

第 5 章 概率分析与随机化算法（Probabilistic Analysis and Randomized Algorithms）¶

教学目标¶

• 区分最坏情形分析、概率分析与随机化算法
• 掌握指示器随机变量（indicator random variable）这一核心分析工具
• 通过招聘问题、生日悖论、球与盒子、掷硬币等经典例子建立概率直觉

5.1 招聘问题（the hiring problem）¶

• 问题描述：依次面试 n 个候选人，每次招”截至目前最好”者，成本 = 面试费 + 聘请费。
• 最坏情形分析：候选人按质量递增排列时，招聘 n 次，总代价 O(cₕ·n)。
• 概率分析：假设候选人出现顺序随机（n! 等可能），用指示变量求期望招聘次数。
• 随机化算法：先随机排列候选人（RANDOMIZED-HIRE-ASSISTANT），使输入分布无关——把”分布假设”从输入移到算法内部，避免”恶意输入”造成的坏情形。

5.2 指示器随机变量¶

• 定义：I{A} = 1 若事件 A 发生，否则 0；E[I{A}] = Pr{A}。
• 期望的线性性：E[X₁+…+Xₙ] = E[X₁]+…+E[Xₙ]（不要求独立性）——这是概率分析中最强大的工具。
• 应用：招聘问题期望招聘次数 = Σ 1/k = ln n + O(1)（第 k 个候选人被聘的概率为 1/k）。

5.3 随机化算法设计¶

• 随机置换数组的两种方法：给每个元素赋随机优先级后排序（PERMUTE-BY-SORTING）；原地随机置换（SWAP 逐个交换，RANDOMIZED 版本，可证明为均匀分布）。
• 随机化排序的效益：使期望运行时间与输入无关（为后续快速排序的随机化铺路）。

5.4 进一步的概率分析应用¶

• 生日悖论：m 个人中至少两人同生日概率 ≥ 1/2 时 m ≈ √(2n ln 2) ≈ 23（n=365）。用指示器变量求期望同生日对数 ≈ m(m−1)/(2n)。
• 球与盒子（balls and bins）：n 个球随机放入 n 个盒子，期望最大负载 ≈ (ln n)/(ln ln n)（Chernoff 界相关直觉）；空盒子期望数 n(1−1/n)ⁿ ≈ n/e。
• 抛硬币连续（streaks）：n 次硬币中连续正面最长的期望为 Θ(log n)（分块分析 + 指示变量）。
• 在线招聘问题：先拒绝前 k 个观察，再从 k+1 开始选第一个比观察期更好的人；最优 k ≈ n/e，成功概率约 1/e（秘书问题的变体）。

本章小结¶

概率分析 vs 随机化算法、指示器随机变量与线性期望、随机置换、生日悖论、球与盒子、连续与在线招聘，为后续随机化算法（快排、随机选择）与哈希分析打基础

第二部分：排序与顺序统计（第 6–9 章）¶

第 6 章 堆排序（Heapsort）¶

教学目标¶

• 掌握堆（优先队列）数据结构及其基本操作
• 理解堆排序算法与复杂度 Θ(n log n)
• 理解堆如何作为优先队列使用

6.1 堆¶

• 堆：近完全二叉树（所有层除最后一层外满，最后一层从左到右填充），用数组表示：PARENT(i)=⌊i/2⌋, LEFT(i)=2i, RIGHT(i)=2i+1。
• 最大堆性质：A[PARENT(i)] ≥ A[i]；最小堆反之。
• 堆高度：Θ(log n)；堆上的基本操作代价与高度成正比。

6.2 维护堆性质：MAX-HEAPIFY¶

• 输入：下标 i，假设左右子树已是最大堆；将 A[i] 与较大孩子交换并逐层下沉。
• 运行时间：T(n) ≤ T(2n/3) + Θ(1) = O(log n)（最坏情形为树高）。

6.3 建堆（BUILD-MAX-HEAP）¶

• 自底向上对 i = ⌊n/2⌋ 到 1 依次调用 MAX-HEAPIFY。
• 复杂度：各结点高度求和，O(n)（非 O(n log n)）——关键洞察：大多数结点高度很小。

6.4 堆排序（HEAPSORT）¶

• 流程：建堆 → 反复将 A[1]（最大值）与末尾交换、堆规模减 1、MAX-HEAPIFY(1)。
• 复杂度：O(n log n)，原地排序（in-place）。

6.5 优先队列¶

• 优先队列 = 支持插入、取最大/最小、增大/减小关键字、删除的堆应用。
• 操作：MAXIMUM（O(1)）、EXTRACT-MAX（O(log n)）、INCREASE-KEY（O(log n)）、INSERT（O(log n)）。
• 应用：事件模拟、任务调度、图算法（Dijkstra、Prim 等后续章节用到）。

本章小结¶

数组表示的二叉堆、MAX-HEAPIFY、BUILD-MAX-HEAP 的 O(n) 建堆、堆排序、优先队列；习题延伸：d 叉堆、Young 矩阵

第 7 章 快速排序（Quicksort）¶

教学目标¶

• 掌握快速排序的分治思想与划分过程
• 理解其最坏/期望运行时间的分析与随机化版本的必要性

7.1 算法描述¶

• 分治：选主元（pivot，通常取 A[r]）→ PARTITION 将数组划分为”≤pivot”与”>pivot”两段 → 递归排序两段。
• PARTITION 过程：一趟扫描，维护两个区间的指示器，将所有 ≤ x 的元素放到左侧；返回主元最终位置。
• 原地划分（in-place）是快排优势之一；不稳定但常数因子小。

7.2 性能分析¶

• 最坏情形：每次划分极端不平衡（如已有序输入取端点为 pivot），T(n) = T(n−1) + Θ(n) = Θ(n²)。
• 最佳情形：每次划分恰好 n/2 对半分，T(n) = 2T(n/2) + Θ(n) = Θ(n log n)。
• 平衡划分：即使 9:1 划分，递归树仍为 Θ(n log n)——常数比例划分即可达到 Θ(n log n)。
• 平均情形直觉：好的划分与坏的划分交替时，好划分主导，期望 Θ(n log n)。

7.3 随机化版本（RANDOMIZED-PARTITION）¶

• 随机选 pivot：使任何输入下期望运行时间为 Θ(n log n)，消除对输入分布/恶意输入的依赖。

7.4 严格分析¶

• 最坏情形 T(n) = Θ(n²)。
• 期望运行时间：通过指示器随机变量与比较次数计数，对每次划分中比较总次数求期望。
• 若按元素值排名的顺序 z₁,…,zₙ，定义 Xᵢⱼ 表示 zᵢ 与 zⱼ 是否被比较；Pr{zᵢ 与 zⱼ 比较} = 2/(j−i+1)。
• E[总比较次数] = Σ 2/(j−i+1) = O(n log n)。
• 结论：快速排序期望 O(n log n)，常数小、原地、缓存友好，实际中常优于堆排序。

本章小结¶

划分过程、最坏/最佳/期望分析、随机化 pivot、比较计数法证明期望 O(n log n)；习题涉及 Hoare 划分、三数取中、栈深度优化（尾递归）等工程细节

第 8 章 线性时间排序（Sorting in Linear Time）¶

教学目标¶

• 证明比较排序的下界 Ω(n log n)
• 掌握三种线性时间排序：计数排序、基数排序、桶排序（以及各自适用条件）

8.1 比较排序下界¶

• 决策树模型：每次比较一个分支，任何基于比较的排序算法对应一棵决策树；n! 个叶子 ⇒ 树高 ≥ ⌈lg(n!)⌉。
• 定理 8.1：任何比较排序在最坏情况下需要 Ω(n log n) 次比较（利用斯特林公式 lg(n!) = Θ(n log n)）。
• 结论：归并排序、堆排序的 O(n log n) 是渐近最优的比较排序。

8.2 计数排序（counting sort）¶

• 适用：元素为 0 到 k 范围内的小整数；不是比较排序，稳定（stable）。
• 思想：统计每个值的出现次数（C 数组）→ 前缀和 → 从后向前按稳定方式填入输出。
• 复杂度：O(n + k)；若 k = O(n) 则为 O(n)；需要额外空间 Θ(k)（辅助计数数组）与非比较性质。

8.3 基数排序（radix sort）¶

• 思想：对 d 位数字，从最低有效位到最高有效位依次做稳定排序（如计数排序）。
• 引理 8.3/8.4：对 b 位字、每轮 r 位、d = ⌈b/r⌉ 轮，总代价 O((b/r)(n + 2^r))；选取 r ≈ lg n 得 Θ((b/lg n)(n + 2^{lg n}))，即接近线性（当 b = O(lg n)）。
• 直观：稳定排序的”组合”才能保证正确性（先低后高）。

8.4 桶排序（bucket sort）¶

• 适用：输入在 [0,1) 区间均匀分布；将区间分为 n 个桶，元素入桶，各桶内排序（插入排序），再拼接。
• 期望运行时间 O(n)（若输入均匀分布，桶内元素少）；最坏情形（全落一桶）退化为 O(n²)。

本章小结¶

决策树下界、计数排序（O(n+k)）、基数排序（按位稳定排序）、桶排序（分布假设）、”何时线性排序可行”的判断——利用输入结构（小范围整数/有限基数/均匀分布）

第 9 章 中位数与顺序统计（Medians and Order Statistics）¶

教学目标¶

• 掌握在 O(n) 内求最小/最大/第 i 小元素的方法
• 理解随机化选择与最坏情形线性时间选择

9.1 最小值和最大值¶

• 求最小值：n−1 次比较即可（遍历）。
• 同时求最大和最小：成对比较法，每次 3 次比较，共 ≤ ⌈3n/2⌉−2 次。

9.2 期望线性时间选择（RANDOMIZED-SELECT）¶

• 基于随机化划分：按 pivot 划分后，判断第 i 小元素落在哪个区间，递归（仅一侧）。
• 期望时间 O(n)：T(n) ≤ O(n) + (1/n)Σ T(max(k−1, n−k))，由指示变量与分析得 E[T(n)] = O(n)。

9.3 最坏情形线性时间选择（SELECT）¶

• 关键三步：分组（每组 5 个）→ 找各组中位数 → 递归找中位数的中位数作为划分主元，保证划分至少 3n/10 的规模。
• 递归式：T(n) ≤ T(⌈n/5⌉) + T(7n/10 + 6) + O(n)，解为 T(n) = O(n)。
• 意义：即使最坏输入也能在 O(n) 内完成选择；但常数较大，实践中常用随机化版本。
• 延伸：中位数 → 也可用于求 top-k、加权中位数等。

本章小结¶

成对比较、随机化选择（期望 O(n)）、最坏情形线性时间（分组 5 元素 + 中位数的中位数）、如何由选择求中位数与顺序统计

第三部分：数据结构（第 10–13 章）¶

第 10 章 基本数据结构（Elementary Data Structures）¶

教学目标¶

• 掌握动态集合的基本操作（SEARCH、INSERT、DELETE、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR）
• 熟悉栈、队列、链表、树的数组/指针实现

10.1 数组、矩阵、栈、队列¶

• 栈（stack）：后进先出（LIFO）；PUSH/POP 均 O(1)；下溢/上溢处理。
• 队列（queue）：先进先出（FIFO）；用循环数组实现，ENQUEUE/DEQUEUE 均 O(1)。
• 数组与矩阵的行优先/列优先存储。

10.2 链表（linked lists）¶

• 单向/双向/循环链表；SEARCH/INSERT/DELETE 的代价分析（插入删除 O(1)，查找 O(n)）。
• 哨兵（sentinel）：哑结点简化边界处理，减少特殊分支（对某些操作使代码更简洁、常数更小）。

10.3 树的表示¶

• 二叉树：left/right/parent 指针（或数组下标）。
• 任意度数根树：左孩子右兄弟表示法（left-child, right-sibling）。
• 其他：如用父指针数组表示。

本章小结¶

动态集合操作、栈/队列的数组实现、双向链表与哨兵、树的多种表示，是后续所有数据结构（堆、哈希、BST、红黑树）的基础设施

第 11 章 散列表（Hash Tables）¶

教学目标¶

• 理解散列思想：直接寻址表 → 散列表 → 冲突解决（链接法、开放寻址）
• 掌握散列函数设计（除法、乘法、乘移法、全域散列）与期望性能分析

11.1 直接寻址表¶

• 当关键字全域 U 很小时，直接以关键字为下标——O(1) 的 SEARCH/INSERT/DELETE。
• 局限性：全域大时空间不可行 → 用散列函数压缩到 m 个槽。

11.2 散列表与冲突解决¶

• 散列表 T[0..m−1]，散列函数 h(k) 将关键字映射到槽。
• 简单一致散列（simple uniform hashing）假设：每个关键字等可能散列到每个槽，且相互独立。
• 链接法（chaining）：每个槽放一个链表。期望查找时间 Θ(1 + α)，α = n/m 为负载因子。
• 定理：成功查找期望时间 Θ(1+α)，平均 1+α/2；当 n = O(m) 时 Θ(1)。

11.3 散列函数¶

• 好的散列函数：近似均匀、独立、运算快；关键字可能是整数/向量/字符串。
• 静态散列：
• 除法散列：h(k) = k mod m（避免 m 为 2 的幂等坏选择，取素数为佳）。
• 乘法散列：h(k) = ⌊m(k·A mod 1)⌋，常用黄金比例 A ≈ 0.618。
• 乘移法（multiply-shift）：h(k) = (ak mod 2^w) >> (w−r)（利用字长截断，快速）。
• 随机散列：从全域散列函数族中随机选一个，使任何输入下期望冲突数都有界。
• 数论全域族：h_{ab}(k) = ((ak+b) mod p) mod m（定理 11.4：冲突概率 ≤ 1/m）。
• 乘移全域族：2/m-全域（定理 11.5）。
• 长输入（向量/字符串）：先组合成整数再散列，或用密码学散列（如 SHA 族）。

11.4 开放寻址（open addressing）¶

• 所有元素存在表内，无链表；探测序列 h(k,0), h(k,1), …
• 线性探测：h(k,i) = (h’(k) + i) mod m——简单但有聚类（primary clustering）。
• 双重散列：h(k,i) = (h₁(k) + i·h₂(k)) mod m——最佳（探测序列数为 m² 量级）。
• 性能（独立均匀探测假设）：成功期望探测数 ≈ (1/α) ln(1/(1−α))，失败 ≈ 1/(1−α)；负载因子 α < 1。
• 删除问题：开放寻址中删除需用”墓碑”（deleted）标记，不能直接置空。
• 线性探测分析（11.5）：均匀散列假设下（定理 11.9），插入期望代价 O(1/α)（实际工程常采用线性探测因其缓存友好）。

本章小结¶

直接寻址 → 链接法（期望 Θ(1+α)）→ 开放寻址（线性/双重探测）→ 全域散列（对抗恶意输入）→ 字符串散列与哈希的实用考量（层次内存、wee hash）

第 12 章 二叉搜索树（Binary Search Trees）¶

教学目标¶

• 掌握 BST 性质与基本操作（查询、插入、删除）
• 理解随机建树的高度期望

12.1 什么是二叉搜索树¶

• BST 性质：结点 x 的左子树中所有关键字 ≤ x.key ≤ 右子树中所有关键字。
• 中序遍历（inorder tree walk）输出有序序列，O(n)。

12.2 查询¶

• SEARCH（递归/迭代）、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR——均沿一条路径，O(h)。
• 后继（successor）：右子树非空取最左；否则向上找第一个”作为左孩子”的祖先。
• 定理：n 个结点的 BST，这些操作均 O(h)。

12.3 插入与删除¶

• 插入：沿搜索路径找到空位放入，O(h)。
• 删除三种情况：
  1. 无孩子：直接删除；
  2. 一个孩子：用孩子顶替；
  3. 两个孩子：找后继 y（右子树最小），用 y 替换 x，再删除 y（y 至多一个孩子）。
• 定理 12.3：插入删除均 O(h)。
• 期望高度：随机插入 n 个关键字构造的 BST 期望高度 O(log n)。

本章小结¶

BST 性质、中序有序、搜索/后继/前驱、插入/删除、随机 BST 高度；本章为红黑树（第 13 章）与扩充数据结构（第 17 章）做铺垫

第 13 章 红黑树（Red-Black Trees）¶

教学目标¶

• 掌握红黑树五条性质与”黑高”引理
• 理解旋转与插入/删除修复的各类情形，能手动模拟

13.1 红黑树性质¶

1. 每个结点为红色或黑色；
2. 根是黑色；
3. 每个叶（NIL）是黑色；
4. 红结点的两个子结点都是黑色（不能有两个连续红）；
5. 从任一结点到其每个叶子的所有简单路径上黑结点数目相同（黑高 bh 定义）。
   - 引理 13.1：n 个内结点的红黑树高度 ≤ 2 log₂(n+1)——由黑高与”红不连续”推出；故动态集合操作 O(log n)。

13.2 旋转（rotation）¶

• 左旋/右旋：保持 BST 性质的局部结构调整，O(1) 时间；是插入/删除修复的基本操作。

13.3 插入（RB-INSERT）¶

• 标准 BST 插入（新结点红）→ 逐种修复违反性质 4 的情况：
• Case 1：叔结点 y 为红——变色（z 的父、叔变黑，祖父变红，z 上移两代）；
• Case 2：叔为黑且 z 为右孩子——左旋转将 Case 2 变 Case 3；
• Case 3：叔为黑且 z 为左孩子——右旋 + 变色，修复完成。
• 最多两次旋转；总时间 O(log n)。

13.4 删除（RB-DELETE）¶

• 用”替换/移植”（TRANSPLANT）思想；若被删结点 y 为黑色则触发修复（引入”双黑”概念）。
• 四种 case（以 x 的兄弟 w 的颜色/子结点颜色分类）：
• Case 1：w 为红——变色 + 旋转，转为 Case 2/3/4；
• Case 2：w 为黑且两孩子黑——变色，x 上移；
• Case 3：w 为黑、左孩子红右孩子黑——旋转 + 变色，转 Case 4；
• Case 4：w 为黑、右孩子红——变色 + 旋转，终止。
• 时间复杂度 O(log n)，旋转次数至多 3 次。

本章小结¶

五性质与黑高、旋转、插入三 Case、删除四 Case、O(log n) 保证；红黑树是平衡搜索树的代表，也是第 17 章扩充结构与后续图算法优先队列的基础

第四部分：高级设计与分析技术（第 14–19 章）¶

第 14 章 动态规划（Dynamic Programming）¶

教学目标¶

• 掌握动态规划的两大要素：最优子结构与重叠子问题
• 掌握 DP 的四步设计流程与自顶向下（记忆化）/自底向上两种实现
• 通过钢条切割、矩阵链乘法、LCS、最优二叉搜索树四个经典例子深入理解

14.1 钢条切割（rod cutting）¶

• 问题：长度为 n 的钢条按价格表切割，求最大收益。
• 递归式：r_n = max(p_n, max(r_i + r_{n−i}))——最优子结构：最优解由子问题最优解组成。
• 朴素递归指数爆炸（重叠子问题）；记忆化（memoization） 或 自底向上（bottom-up） 均 O(n²)。
• 子问题图（subproblem graph）：结点为子问题，边为依赖——重叠子问题的图形刻画。

14.2 矩阵链乘法（matrix-chain multiplication）¶

• 问题：给定矩阵链 ⟨A₁,…,Aₙ⟩，求完全加括号方案使标量乘法次数最少。
• 结构：最优括号化在某个 k 处分裂为两个子链；
• 递归式：m[i,j] = min_{i≤k<j} { m[i,k] + m[k+1,j] + p_{i−1}p_k p_j }。
• 自底向上按链长填表，O(n³) 时间、O(n²) 空间；重建最优解用 s[i,j] 记录分裂点。

14.3 动态规划的原理¶

• 最优子结构（optimal substructure）：最优解包含子问题最优解；注意子问题独立。
• 重叠子问题（overlapping subproblems）：递归求解时反复遇到相同子问题——这是 DP 优于直接递归之处。
• 重构解：存储选择，最后回溯。
• 记忆化（memoization）：自顶向下 + 表格；与自底向上在渐近上等价。

14.4 最长公共子序列（LCS）¶

• 最优子结构（定理 14.1）：若 xₘ = yₙ，则 LCS 含该字符 + 前缀的 LCS；否则为两个前缀的 LCS 的较大者。
• 递归式与 LCS-LENGTH 表；输出 O(m+n) 空间可压缩（只存长度）。
• 应用：DNA 序列相似性、文件 diff。

14.5 最优二叉搜索树（optimal BST）¶

• 给定关键字（及失败结点的）频率，构造期望搜索代价最小的 BST。
• 结构：任一子树为连续关键字区间；递归式 e[i,j] = min_k { e[i,k−1] + e[k+1,j] + w(i,j) }，其中 w 为区间总概率。
• 运行时间 O(n³)（可优化到 O(n²) 因四边形不等式性质，习题延伸）。

本章小结¶

最优子结构 + 重叠子问题、自顶向下/自底向上、记忆化、子问题图；经典例题：钢切割、矩阵链、LCS、最优 BST、编辑距离、Viterbi 等（习题）

第 15 章 贪心算法（Greedy Algorithms）¶

教学目标¶

• 掌握贪心策略的要素：贪心选择性质与最优子结构
• 理解贪心 vs 动态规划：何时贪心成立，何时必须 DP
• 通过活动选择、Huffman 编码、离线缓存三个经典问题掌握贪心证明

15.1 活动选择问题（activity selection）¶

• 问题：最大相容活动集合（按结束时间）。
• 贪心选择：总是选择结束时间最早的相容活动——直观合理且正确（定理 15.1）。
• 递归/迭代贪心算法；复杂度 O(n log n)（按结束时间排序主导）或 O(n)。

15.2 贪心策略的要素¶

• 贪心选择性质（greedy-choice property）：每步的局部最优选择最终导致全局最优——通过交换论证（exchange argument）证明。
• 最优子结构：剩余子问题仍为最优。
• 贪心 vs DP：两者都需要最优子结构；贪心多做一步”贪心选择”而不再求解全部子问题（比较：0-1 背包需 DP，部分背包贪心即可）。

15.3 Huffman 编码¶

• 前缀码（prefix-free codes）与二叉树对应；最优前缀码 = Huffman 算法：每次合并频率最小的两棵树（借助最小堆）。
• 正确性：最优前缀码具有最优子结构（引理 15.3）+ 贪心选择性质（频率最小的两个字符作为最深兄弟，定理 15.4）。
• 应用：文件压缩；编码长度 = 叶子深度 × 频率。

15.4 离线缓存（offline caching）¶

• 缓存替换问题：已知未来访问序列时，最优策略是最远未来使用（furthest-in-future）。
• 证明要素：最优子结构 + 贪心选择性质（定理 15.5）。
• 意义：离线最优解作为在线缓存（第 27 章）竞比的基准（competitive ratio）。

本章小结¶

贪心选择性质（交换论证）、最优子结构、活动选择、Huffman 树、离线缓存；”贪心何时有效”的判断能力是本章核心

第 16 章 摊还分析（Amortized Analysis）¶

教学目标¶

• 掌握摊还分析的三种方法：聚合分析、记账法、势能法
• 理解”平均到每次操作”的含义，能分析动态表、栈、二进制计数器

16.1 聚合分析（aggregate analysis）¶

• 对所有操作的总代价求上界，再除以操作数得摊还代价。
• 例：栈的 MULTIPOP——总代价 O(n)（每个元素至多被压入/弹出一次），摊还 O(1)/操作。
• 例：二进制计数器 INCREMENT：总翻转次数 ≤ 2n，摊还 O(1)/操作。

16.2 记账法（accounting method）¶

• 给不同操作分配不同的摊还代价（可高于或低于实际代价）；”多付”的部分作为信用存储，用于支付后续”少付”操作。
• 栈：PUSH 记账 2，POP/MULTIPOP 记账 0（信用 = 元素存在）；计数器：置 0 记账 0，置 1 记账 2。
• 关键：任何操作序列的总摊还代价 ≥ 总实际代价（信用永不欠账）。

16.3 势能法（potential method）¶

• 定义势函数 Φ(D)：数据结构状态的函数；摊还代价 ĉ = 实际代价 + ΔΦ。
• 若 Φ(D₀) = 0 且 Φ 恒 ≥ 0，则总摊还代价 ≥ 总实际代价。
• 栈：Φ = 栈中元素数；计数器：Φ = 1 的个数（ΔΦ = 1 − t + … 推导摊还 2）。
• 势能法是三者中最通用、最强大，用于复杂分析（如第 19 章并查集）。

16.4 动态表（dynamic tables）¶

• 表扩张：满则翻倍（表扩大）；摊还代价 O(1)/插入（势 = 表大小 − 元素数）。
• 表收缩：元素少于 1/4 时减半（用 1/4 阈值避免抖动）。
• 摊还代价：插入 O(1)，删除 O(1)；摊还分析保证整体 O(n) 总代价。

本章小结¶

聚合、记账、势能三法等价；二进制计数器、栈、动态表的摊还 O(1)；势能法是后续并查集、树结构等分析的标准工具

第 17 章 扩充的数据结构（Augmenting Data Structures）¶

教学目标¶

• 掌握”在现有数据结构上增加信息”的四步扩充法
• 通过动态顺序统计与区间树两个完整例子掌握扩充技巧

17.1 动态顺序统计（dynamic order statistics）¶

• 在红黑树结点上增加 size（子树结点数）字段。
• OS-SELECT（按秩找元素）与 OS-RANK（求元素秩）均 O(log n)。
• 维护：旋转时 size 只需更新旋转涉及的两个结点——O(1) 局部更新保证整体 O(log n)。

17.2 扩充数据结构的四步法¶

1. 选择基础数据结构（如红黑树）；
2. 决定附加信息（如 size）；
3. 验证维护：基础操作（插入/删除/旋转）能否在 O(log n) 内维护附加信息；
4. 开发新操作（SELECT/RANK/INTERVAL-SEARCH）。
   - 定理 17.1：若结点字段 f 只依赖结点及其子树的信息，则红黑树插入/删除后可在 O(log n) 内维护。

17.3 区间树（interval trees）¶

• 目标：支持”查找与给定区间重叠的区间”。
• 四步：
  1. 基础结构：红黑树，按区间低端点排序；
  2. 附加信息：子树中最大高端点 max；
  3. 维护：max = max(low 自身的 low, 左右子树 max)——插入/删除 O(log n)；
  4. 新操作 INTERVAL-SEARCH：沿”max ≥ low[i]”的路径寻找重叠区间，O(log n)（定理 17.2）。

本章小结¶

扩充四步法、顺序统计树（size）、区间树（max）；可推广到更多附加信息（如习题最大重叠点、Josephus 排列）

第 18 章 B 树（B-Trees）¶

教学目标¶

• 理解 B 树作为磁盘/二级存储上的平衡搜索树的设计动机
• 掌握 B 树定义、高度、插入（分裂）与删除（合并）操作

18.0 磁盘与外存¶

• 磁盘访问远慢于内存：I/O 次数是主导代价；B 树通过大扇出（fan-out）降低树高，减少磁盘访问。

18.1 B 树定义¶

• 参数 t（最小度数）：每个非根结点含 [t−1, 2t−1] 个关键字（根可更少）；所有叶子同一深度。
• 结点最多 2t−1 个关键字 = 2t 个孩子（满结点）。
• 高度：引理：n ≥ 1 时高度 h ≤ log_t((n+1)/2)；大 t 值 → 低树高，适合磁盘。

18.2 基本操作¶

• 搜索：类似 BST，多路（结点内线性/二分），O(t log_t n) I/O。
• 插入：自顶向下沿路径遇到满结点即分裂——单趟完成，无需回溯；O(t log_t n)。
• 分裂（B-TREE-SPLIT-CHILD）：满结点中间关键字上移给父，左右两半成为两兄弟。

18.3 删除¶

• 若需要，先合并/借调（借用兄弟或合并），保证路径上结点不”过少”；
• 删除情况：叶子直接删；内结点用前驱/后继替换后删除；必要时下放合并。
• 复杂度 O(t log n) I/O。

本章小结¶

大扇出平衡树、B 树高度与 t 的关系、分裂/合并保证最低占用、单趟插入/删除；是数据库索引的基石，与红黑树（内存）相对照（磁盘）

第 19 章 用于不相交集合的数据结构（Data Structures for Disjoint Sets）¶

教学目标¶

• 掌握并查集（disjoint-set）的三种操作：MAKE-SET、FIND-SET、UNION
• 掌握两种实现（链表、森林）与两种启发式（按秩合并、路径压缩）
• 了解逆 Ackermann 函数的接近常数摊还复杂度

19.1 不相交集合操作¶

• 维护一组互不相交的集合；UNION 合并两集合（可用加权合并缩短链表）。
• 应用：连通分量 的动态维护（如求无向图的连通分量）。

19.2 链表表示¶

• 每个集合一个链表 + 尾指针；简单 UNION 总代价 O(n²)。
• 加权合并启发式（weighted-union heuristic）：总是把小集合合并进大集合——总代价 O(m log n)（定理 19.1）。

19.3 不相交集合森林（disjoint-set forests）¶

• 树表示集合（根为代表元素），两个启发式：
  1. 按秩合并（union by rank）：秩 = 树高上界，秩小树挂到秩大树；
  2. 路径压缩（path compression）：FIND-SET 时把路径上所有结点直接指向根。
• 两个启发式合用时，任意 m 个操作（n 个 MAKE-SET）的运行时间为 O(m α(n))，其中 α(n) 为 Ackermann 函数的逆，增长速度极慢（α(n) ≤ 4 对实际中一切 n）——实际线性。

19.4 分析（进阶）¶

• 引入”秩分组”与势函数，以抵消路径压缩的收益；
• 结论：逆 Ackermann 上界几乎线性，是现代算法分析中最精致的摊还分析。

本章小结¶

MAKE-SET/FIND-SET/UNION、加权合并、按秩合并、路径压缩、逆 Ackermann 界；应用于 Kruskal（21 章）、离线最小、最低公共祖先等

第五部分：图算法（第 20–25 章）¶

第 20 章 基本的图算法（Elementary Graph Algorithms）¶

教学目标¶

• 掌握图的两种表示（邻接表、邻接矩阵）及适用场景
• 熟练掌握广度优先搜索（BFS）与深度优先搜索（DFS）
• 掌握拓扑排序与强连通分量（Kosaraju 算法）

20.1 图的表示¶

• 邻接表：空间 Θ(V+E)，适合稀疏图；判断边 (u,v) 需 O(degree(u))。
• 邻接矩阵：空间 Θ(V²)，适合稠密图；判断边 O(1)。

20.2 广度优先搜索（BFS）¶

• 以源 s 为根构造广度优先树；用队列，访问距离递增的层。
• 每个顶点至多入队一次，时间 O(V + E)。
• 最短路径性质：BFS 算出的距离即无权图中的最短路径长度（引理 20.1–20.3，定理 20.5 正确性）。

20.3 深度优先搜索（DFS）¶

• 递归/显式栈；时间戳 d[u]（发现）、f[u]（完成） 形成括号结构。
• 括号定理（20.7）：后代区间嵌套于祖先区间。
• 白色路径定理（20.9）：DFS 树中的祖先关系可由白路径刻画。
• 边分类（在无向/有向图）：树边、后向边、前向边、横向边；
• 无向图无前向边/横向边；有向图存在后向边 ⇔ 有环。
• 复杂度 O(V+E)。

20.4 拓扑排序（topological sort）¶

• 定义：DAG 上所有边从前向后；DFS 完成时间的逆序即拓扑序（定理 20.12）。
• 应用：课程依赖、编译依赖、任务调度；O(V+E)。

20.5 强连通分量（strongly connected components）¶

• 算法（Kosaraju）：① 对 G 做 DFS 得完成时间；② 在转置图 Gᵀ 上按完成时间降序做 DFS；每个 DFS 森林的树即为一个 SCC。
• 理论基础：分量图（condensation graph）为 DAG；引理 20.13–20.15、定理 20.16。
• 复杂度 O(V+E)；应用：压缩图、2-SAT、网页排名相关分析。

本章小结¶

邻接表/矩阵、BFS（最短路、广度优先树）、DFS（时间戳、边分类）、拓扑排序、强连通分量；是后续所有图算法的基础工具

第 21 章 最小生成树（Minimum Spanning Trees）¶

教学目标¶

• 理解 MST 的安全边/割理论（生长一棵 MST 的一般方法）
• 掌握 Kruskal（并查集）与 Prim（优先队列）两种算法及复杂度

21.1 生长最小生成树¶

• 贪心框架 GENERIC-MST：不断加入”安全边”（安全 = 加入后仍属于某棵 MST）。
• 割定理（定理 21.1）：若边 (u,v) 是横跨割 (S, V−S) 的最轻边，且 A 无横跨该割的边，则 (u,v) 是安全边。
• 推论 21.2：森林中连接两个不同树的”最轻边”安全。

21.2 Kruskal 算法¶

• 按权排序边，用并查集判断端点是否已连通：不连通则加入（连成树）。
• 复杂度：O(E log E)（= O(E log V)），由排序主导；几乎线性的并查集部分使实际很快。

21.2 Prim 算法¶

• 从根出发扩展一棵树：每次选连接树与树外的最轻边（用优先队列/最小堆）。
• 复杂度：二叉堆 O(E log V)；斐波那契堆 O(E + V log V)（更优，但实现复杂）。

本章小结¶

割定理与安全边、Generic-MST、Kruskal（边视角 + 并查集）、Prim（顶点视角 + 堆）、二者均为贪心的正确性依赖”最轻边安全”

第 22 章 单源最短路径（Single-Source Shortest Paths）¶

教学目标¶

• 掌握松弛（relaxation）这一核心操作与最短路径性质
• 掌握三种算法及其适用条件：Bellman-Ford（负权、差分约束）、DAG 最短路径、Dijkstra（非负权）
• 理解最短路径与线性规划/差约束的联系

0 基础概念¶

• 最优子结构（引理 22.1）；负权边与负环（无最短路径）；前驱子图。
• 松弛：若 d[v] > d[u] + w(u,v)，更新 d[v] = d[u] + w(u,v)。
• 最短路径性质：三角不等式、上界性质、无路径性质、收敛性质、路径松弛性质、前驱子图性质（22.5 节汇总）。

22.1 Bellman-Ford 算法¶

• 对所有边做 n−1 轮松弛，最后再检查一轮是否存在可松弛边（检测负环）。
• 复杂度 O(VE)；适用：允许负权、检测负环；在无负环时正确（定理 22.4）。

22.2 DAG 最短路径¶

• 先拓扑排序，再按拓扑序逐顶点松弛所有出边。
• 复杂度 O(V+E)（线性！）；可处理负权（因 DAG 无环）。

22.3 Dijkstra 算法¶

• 贪心 + 优先队列：每次选当前 d 值最小的未确定顶点，松弛其出边。
• 要求边权非负（否则贪心失效）；复杂度：二叉堆 O(E log V)（+ V log V），斐波那契堆 O(E + V log V)。
• 正确性（定理 22.6）：每次选出的 u 的 d[u] 即为真正最短距离（三角不等式 + 归纳）。

22.4 差约束与最短路径¶

• 差分约束系统：形如 x_j − x_i ≤ b_k 的不等式组；可行域为凸区域。
• 转化为约束图：边 i→j 权 b_k；Bellman-Ford 求单源最短路给出可行解（定理 22.9）。
• 应用：调度、时限约束、VLSI 布局等；”系统不可行” ⇔ 约束图含负环。

本章小结¶

松弛范式、Bellman-Ford（O(VE)，负权/负环检测）、DAG 线性算法、Dijkstra（非负权、堆优化）、差约束建图；最短路径性质证明是后续所有最短路算法的理论基础

第 23 章 所有结点对的最短路径（All-Pairs Shortest Paths）¶

教学目标¶

• 掌握三种策略：矩阵乘法式 DP、Floyd-Warshall、Johnson（稀疏图）
• 理解输出矩阵与路径重构

23.1 最短路径与矩阵乘法¶

• DP：L⁽ᵐ⁾[i,j] = 至多 m 条边的最短路径；L⁽ᵐ⁾ = L⁽ᵐ⁻¹⁾ ⊗ W（”min-plus 矩阵乘法”）。
• 重复平方（squaring）技巧：计算 L⁽¹⁾, L⁽²⁾, L⁽⁴⁾, …（倍增）→ O(n³ log n)。

23.2 Floyd-Warshall 算法¶

• 按中间顶点编号动态规划：d⁽ᵏ⁾[i][j] = min(d⁽ᵏ⁻¹⁾[i][j], d⁽ᵏ⁻¹⁾[i][k] + d⁽ᵏ⁻¹⁾[k][j])。
• 三重循环 O(n³)；可处理负权（无负环）；前驱矩阵重构路径。
• 传递闭包：只关心”可达性”布尔矩阵，同样 DP，O(n³)（bitset 可加速）。

23.3 Johnson 算法（稀疏图）¶

• 思路：重新赋予权值（reweighting）使边权非负（h(v) 势函数：w’(u,v)=w(u,v)+h(u)−h(v)，由 Bellman-Ford 求 h），再对每个顶点运行 Dijkstra。
• 复杂度：O(VE + V² log V)（稀疏图优于 Floyd-Warshall 的 O(n³)）。
• 若存在负环，重新赋权可检测（Bellman-Ford 失败）。

本章小结¶

min-plus 矩阵乘法（倍增）、Floyd-Warshall（O(n³)）、Johnson（稀疏图 + 重新赋权）、闭包、路径重构；选择依据：稠密 → Floyd；稀疏 → Johnson

第 24 章 最大流（Maximum Flow）¶

教学目标¶

• 掌握流网络、残量网络、增广路径、割与最大流最小割定理
• 掌握 Ford-Fulkerson 方法与 Edmonds-Karp 改进
• 掌握最大二分匹配的流建模

24.1 流网络¶

• 定义：有向图 + 源 s + 汇 t + 容量 c(u,v)；流 f 满足容量约束与流量守恒。
• 建模技巧：多源多汇（加超级源/超级汇）；反平行边（拆结点）。

24.2 Ford-Fulkerson 方法¶

• 残量网络 G_f：剩余容量与反向边（用于”撤销/调整”流）；
• 增广路径：残量网络中的 s→t 路径；每次增广其瓶颈容量，直到无增广路径。
• 割与最小割：割的容量 = 从 S 到 T 的总容量；任意流 ≤ 任意割容量；
• 最大流最小割定理（定理 24.6）：以下等价——f 最大、无增广路径、存在割使 |f| = 容量。
• 复杂度：O(E|f*|)（依赖最大流量值；若容量为无理数甚至可能不终止）。
• Edmonds-Karp：总是选最短增广路径（BFS） → O(VE²)，独立于容量。

24.3 最大二分匹配¶

• 构建流网络：源→左部、左→右（容量 1）、右→汇；
• 积分性定理（定理 24.10）：最大流可取整数值 → 最大流 = 最大匹配（用匹配大小 m = |f|）。
• Ford-Fulkerson 在二分匹配图上复杂度 O(VE)。

本章小结¶

流与守恒、残量网络、增广路径、min-cut/max-flow 定理、Ford-Fulkerson、Edmonds-Karp（BFS 增广）、二分匹配转化；后续第 25 章将深化匹配

第 25 章 二分图中的匹配（Matchings in Bipartite Graphs）¶

教学目标¶

• 掌握二分匹配理论与增广路径（改进路径）的充要条件
• 掌握 Hopcroft-Karp 算法与稳定婚姻（Gale-Shapley）算法
• 了解匈牙利算法（指派问题）

25.1 最大二分匹配（重访）¶

• 增广路径（M-augmenting path）：起止于未匹配点的交替路径——翻转它可让匹配 +1。
• Berge 定理：匹配 M 最大 ⇔ 不存在 M-增广路径。
• Hall 定理（推论 25.4 相关）：完美匹配存在 ⇔ 对所有 X 子集 S 有 |N(S)| ≥ |S|。
• Hopcroft-Karp 算法：用 BFS 分层（最短增广路径）多路增广 + DFS 一次找出多增广路径；复杂度 O(√V · E)——显著快于朴素 O(VE)。

25.2 稳定婚姻问题（Gale-Shapley）¶

• 每个男人按偏好求婚，女人保留更优者（可”解除婚约”）——订婚算法。
• 保证：总是终止于稳定匹配（无不满意配对），且对求婚方为男优（man-optimal），对女方为最差（woman-pessimal）但仍有稳定匹配（定理 25.9–25.13）。

25.3 匈牙利算法（指派问题）¶

• 指派问题：完全二分图，边有权，求最小权重完美匹配。
• 思想：顶点标号（vertex labeling）+ 等子图（equality subgraph G_h）+ 交替树/匈牙利树；找到能扩展匹配的”临界”标号调整。
• 复杂度 O(n³)（本课程实现 O(n³) 进阶练习；朴素实现更高）。对稠密图实用。

25 小结¶

• 增广路径定理、Hall 定理、Hopcroft-Karp（O(√V·E)）、Gale-Shapley 稳定婚姻、匈牙利算法；匹配是网络流（24）的自然深化，也见之于调度/指派/拍卖等实际应用

第六部分：高级专题（第 26–31 章）¶

第 26 章 并行算法（Parallel Algorithms）¶

教学目标¶

• 掌握 fork-join 并行模型：工作量（work）与延展度（span）
• 掌握并行算法的分析（Brent 定理、贪心调度）与常用并行算法
• 能识别竞争条件（race）

26.1 fork-join 并行基础¶

• 关键字：spawn（派生）、sync（同步）——派生任务并行执行，sync 等待完成。
• 执行图（DAG）：结点 = 指令，边 = 依赖。
• 性能度量：
• 工作量 T₁：串行执行总步数；
• 延展 T∞：无限处理器下最短时间（关键路径长度）；
• 并行度 T₁/T∞（= 饱和所需处理器数）。
• Brent 定律：P 处理器时间 T_P ≥ max(T₁/P, T∞)；贪心调度器在 P 处理器上 T_P ≤ T₁/P + T∞（定理 26.1）。
• Corollary：贪心调度达到 T_P = O(T₁/P + T∞)；并行加速比 ≤ 并行度。
• 分析：T₁ = 串行运行时间；T∞ 反映可并行潜力。
• 并行循环：并行 for 的展开（递归分治）；竞争条件：两任务读写同一变量（无同步）→ 需用原子操作/分治避免（矩阵乘法、归并排序均有例子）。

26.2 并行矩阵乘法¶

• 并行三重循环：T∞ = O(log n)（每层并行求和树），T₁ = O(n³)；并行度高。
• 分治并行乘法（含 Strassen 并行化）与 cache 友好设计。

26.3 并行归并排序¶

• 并行归并（并行合并两有序数组）：T∞ = O(log² n)，T₁ = O(n)（用二分选划分点并行递归）；并行归并排序 T₁ = O(n log n)，T∞ = O(log³ n)。

26 小结¶

fork-join 模型、T₁/T∞/并行度/Brent、贪心调度、并行归并与归并排序、竞争条件；为后续并行图算法与并行矩阵算法打基础

第 27 章 在线算法（Online Algorithms）¶

教学目标¶

• 掌握竞争比（competitive ratio）这一在线算法分析框架
• 掌握滑雪租借（电梯等待）、搜索列表维护、在线缓存等经典问题

27.1 等待电梯（ski rental 变体）¶

• 在”不知何时到来”下权衡租/买：最优在线策略的竞争比为 2（买 vs 租的阈值策略）。
• 建立”在线决策无法回退”的直觉模型。

27.2 维护搜索列表（move-to-front）¶

• 线性搜索列表维护：未知访问序列；向前移动（move-to-front, MTF） 在线算法；
• 定理：MTF 的竞争比为 2——比”转置/频率计数”等启发式有最坏情形保证。

27.3 在线缓存¶

• 确定性缓存算法：竞争比下界 ≥ k（缓存大小）；最远未来/最少使用仅离线最优；
• 定理：任何确定性在线缓存算法的竞争比 ≥ k；LFU/LRU 等达到 2 竞争比？——分析见 27.3（LRU 竞争比 = k）。
• 随机化缓存：随机选择驱逐 → 竞争比可降为 O(log k)（如 RANDOM/Marking 类算法），说明随机化能改善最坏情形。

27 小结¶

在线 vs 离线、竞争比、move-to-front（2 竞争）、确定性缓存下界 k、随机化缓存的 O(log k)；在线算法是”竞比分析”的现代主题

第 28 章 矩阵运算（Matrix Operations）¶

教学目标¶

• 掌握 LUP 分解与线性方程组求解（前向/回代）
• 掌握矩阵求逆与矩阵乘法的关系（等价难易）
• 了解对称正定矩阵与最小二乘

28.1 求解线性方程组（LUP 分解）¶

• LUP 分解：A = LUP（下三角 L、上三角 U、置换 P），引入部分主元（数值稳定性）。
• 求解流程：解 Ly = Pb（前向代换）→ 解 Ux = y（回代）。
• 复杂度：分解 O(n³)，每次代换 O(n²)；多右端项只需分解一次。

28.2 矩阵求逆¶

• 由 LUP 分解对每列求解：求逆 O(n³)。
• 定理 28.1/28.2：矩阵乘法与矩阵求逆互不更难（乘法 ≥ 求逆 ≥ 乘法）——在多项式时间内等价。

28.3 对称正定矩阵与最小二乘¶

• 对称正定（SPD）：xᵀAx > 0 对所有 x≠0；性质（各主子式正定、Schur 补引理 28.5）→ 可用Cholesky 分解（LLᵀ）更高效求解。
• 最小二乘：解超定方程组 min ||Ax−b||²，正规方程 AᵀAx = Aᵀb（要求列满秩）。

本章小结¶

LUP 分解、前/回代、矩阵求逆与乘法等价性、SPD/Cholesky、最小二乘；为数值算法（线性规划内点法、机器学习梯度法）提供基础

第 29 章 线性规划（Linear Programming）¶

教学目标¶

• 掌握线性规划的标准形式与几何解释
• 掌握把问题（最短路、最大流、最小费用流）建模为 LP
• 理解对偶性（duality）与基本定理

29.1 线性规划形式¶

• 标准形：max cᵀx，约束 Ax ≤ b，x ≥ 0；可行域为凸多面体。
• 求解算法概览：单纯形法（实际高效、指数最坏）、椭球法（多项式但实际慢）、内点法（多项式、实际高效）。

29.2 把问题建模为 LP¶

• 最短路径（作为势差的约束）、最大流、最小费用流、多商品流（一般多商品流是整数规划，不可 LP 化）。
• 关键技巧：变量 + 线性约束描述流守恒/容量/费用；目标函数线性化。

29.3 对偶性¶

• 对偶问题：min cᵀx s.t. Ax ≤ b, x ≥ 0 的对偶为 max bᵀy s.t. Aᵀy ≥ c, y ≥ 0。
• 弱对偶（引理 29.1）：任何原始可行解 ≥ 任何对偶可行解——提供下界。
• Farkas 引理（29.3）：不可行性由对偶刻画。
• 强对偶（定理 29.4）：原与对偶同最优值（若两者均可行）。
• 基本定理（29.5）：LP 最优解出现在极点（顶点）——单纯形在顶点间移动的理由。

29 小结¶

标准形、几何（多面体/极点）、单纯形与内点法、建模（流/最短路/网络）、对偶（弱/强/互补松弛）、整数规划的 NP 难概述；为后续第 34、35 章（NP 完全与近似）提供线性规划放松的工具

第 30 章 多项式与快速傅里叶变换（Polynomials and the FFT）¶

教学目标¶

• 掌握多项式的两种表示（系数、点值）与互转
• 掌握 DFT/FFT 原理（单位复数根）与卷积
• 理解 FFT 的电路实现

30.1 多项式表示¶

• 系数表示：求值 O(n)，乘法卷积 O(n²)；
• 点值表示：乘法 O(n)（对应点相乘）；
• 插值唯一性（定理 30.1）：n+1 个点唯一确定 n 次多项式。
• 策略：系数 → 点值（求值）→ 逐点乘 → 插值回系数；用 FFT 使求值/插值均为 O(n log n)，从而多项式乘法 O(n log n)。

30.2 DFT 与 FFT¶

• n 次单位根：ωₙ = e^{2πi/n}；引理：相消引理（ω_{dn}^{dk}=ωₙᵏ）、半分引理（ωₙ^{2k}=ω_{n/2}^k）、求和引理（Σωₙ^{jk} = 0）。
• DFT：y_k = Σ a_j ωₙ^{kj}；
• FFT（Cooley-Tukey）：按奇偶分成 A^even/A^odd，递归 2 个 n/2 点 FFT，合并 O(n)：
• T(n) = 2T(n/2) + O(n) = O(n log n)。
• 插值 = 逆 DFT（用 ωₙ^{-1} 与 1/n），定理 30.7（DFT 求逆）。
• 卷积定理（30.8）：多项式乘积系数 = 两多项式系数的卷积；可 FFT 计算。

30.3 FFT 电路¶

• 蝶形运算（butterfly）：一次乘加 + 复用；递归电路 → 完整的 O(n log n) 深度 log n 的 FFT 网络；输入按位逆序排列。

30 小结¶

• 系数↔点值、单位根与引理、FFT 分治（O(n log n)）、卷积定理、电路实现；是信号处理与大数据乘法（大整数乘法）的基础

第 31 章 数论算法（Number-Theoretic Algorithms）¶

教学目标¶

• 掌握数论基础（整除、模、gcd、唯一分解）
• 掌握欧几里得算法与扩展欧几里得、模线性方程、中国剩余定理、幂模运算
• 掌握 RSA 公钥密码系统与素性测试（Miller-Rabin）

31.1 数论基础¶

• 整除性、除法定理（a = qn + r，0 ≤ r < n）、模等价、公约数与 gcd 性质（gcd 组合定理）。
• 唯一分解定理（算术基本定理）；互素与欧拉 φ 函数。

31.2 最大公约数¶

• 欧几里得算法（辗转相除）：EUCLID(a,b)，O(log min(a,b))（Lamé 定理：步数 ≤ 2 log φ(min)）。
• 扩展欧几里得：EXTENDED-EUCLID 求 (d, x, y) 使 ax + by = d。

31.3 模算术与群论基础¶

• 有限群 Z_n（加法群）与 Z_n（乘法群）；子群与 Lagrange 定理*（子群大小整除群大小）。
• 循环群与生成元（元素阶的性质）。

31.4 模线性方程¶

• 方程 ax ≡ b (mod n) 有解 ⇔ gcd(a,n) | b；解数 = gcd(a,n) 个（模 n）。
• 求解方法：先用扩展欧几里得求 ax ≡ d (mod n) 的特解，再加 n/d 的倍数。

31.5 中国剩余定理（CRT）¶

• 给定两两互素的模 n₁,…,n_k，系统 x ≡ aᵢ (mod nᵢ) 有唯一解模 N = Π nᵢ。
• 应用：大数运算分解为小模运算再重组（快速并行算术）。

31.6 元素的幂与反复平方¶

• Euler 定理：a^φ(n) ≡ 1 (mod n)（a 与 n 互素）；Fermat 小定理：a^{p−1} ≡ 1 (mod p)。
• 离散对数问题 与阶的性质（用于密码学）。
• 反复平方（MODULAR-EXPONENTIATION）：二进制展开指数，O(log n) 次乘法。

31.7 RSA 公钥密码¶

• 密钥生成：选大素数 p,q，n = pq，e 与 (p−1)(q−1) 互素，d = e⁻¹ mod φ(n)；公钥 (e,n)、私钥 (d,n)。
• 加密 c = mᵉ mod n，解密 m = cᵈ mod n（正确性依赖 Euler 定理，定理 31.36）。
• 安全性：破解 RSA 需要分解 n（大整数分解难题）；混合密码系统 = 对称密钥 + RSA 交换。

31.8 素性测试¶

• 素数定理：π(x) ≈ x/ln x（素数密度）。
• 伪素性测试（Fermat 测试）：a^{n−1} ≡ 1 的合数可能通过（Carmichael 数）；
• Miller-Rabin 随机测试：错误率 ≤ 1/4（可多次运行指数压低，定理 31.39/31.40）；是实践中寻找大素数（RSA 密钥）的标准工具。

31 小结¶

• 数论基础、Euclid/扩展欧几里得、模群与 Lagrange、模线性方程、CRT、Euler/Fermat、反复平方、RSA、Miller-Rabin；是密码学与信息安全的核心算法库

第七部分：应用与前沿（第 32–35 章）¶

第 32 章 字符串匹配（String Matching）¶

教学目标¶

• 掌握字符串匹配问题的各种算法及其思想
• 重点掌握 KMP 算法（前缀函数）与 Rabin-Karp（哈希）
• 了解有限自动机与后缀数组

32.0 记号¶

• 文本 T[1..n]、模式 P[1..m]；有效位移 s 使 T[s+1..s+m] = P；重叠后缀引理（32.1）是 KMP 的基础。

32.1 朴素算法¶

• 每个位移逐字符比较：最坏 O((n−m+1)·m)。

32.2 Rabin-Karp¶

• 把模式哈希为数值，滚动计算文本子串的哈希（模 q）；匹配则进一步验证。
• 期望 O(n+m)；最坏 O(nm)（哈希碰撞）；利用模 q 的小型随机性可期望线性。平均情形优秀。

32.3 有限自动机¶

• 由模式构造字符串匹配自动机（状态 = 已匹配前缀长度，转移函数 δ）；
• 匹配过程 O(n)，预处理 O(m·|Σ|)（三字符集）。
• 后缀函数递归引理（32.2/32.3）：δ(q, a) 由最长前缀后缀决定——是 KMP 的抽象。

32.4 Knuth-Morris-Pratt（KMP）¶

• 前缀函数 π：模式 P 中每个位置的最长”真前缀 = 后缀”长度；
• 匹配主循环不回溯文本指针：失配时按 π 回退模式——总时间 O(n + m)（文本只前进）。
• 正确性：前缀函数迭代引理（32.5）等；算法简洁，是字符串处理的核心工具。

32.5 后缀数组¶

• 文本所有后缀的字典序排序数组；配合 LCP 数组可支持 O(m + log n) 的子串匹配与许多字符串问题；
• 构造：倍增 + 基数排序 → O(n log n)。

32 小结¶

• 朴素 → Rabin-Karp（哈希）→ 有限自动机 → KMP（前缀函数，线性）→ 后缀数组；字符串匹配是文本处理、生物信息学的核心工具

第 33 章 机器学习算法（Machine-Learning Algorithms）¶

教学目标¶

• 掌握 k-means 聚类（Lloyd 算法）的迭代优化思路
• 掌握乘法权重算法（multiplicative weights）的在线学习框架
• 掌握梯度下降（含随机梯度下降）及其在机器学习中的应用

33.1 聚类（k-means / Lloyd 方法）¶

• 特征向量与相似度（距离）；k-means 目标：最小化簇内点到中心的平方距离和。
• Lloyd 过程：交替优化——固定簇 → 最优中心为均值（定理 33.1）；固定中心 → 每点分到最近中心（定理 33.2）；迭代直到收敛。
• 说明：Lloyd 收敛到局部最优（NP 难问题的启发式）；EM 思想的雏形；用于图像压缩、客户分群等。

33.2 乘法权重（multiplicative-weights）¶

• 框架：多个”专家”，每轮按权重分布选择，观察损失后按指数缩小坏专家权重；
• 定理 33.4（Hedge）：总损失 ≤ (1+ε)·最优专家损失 + O((ln N)/ε)——接近最优。
• 应用：在线学习、博弈、组合优化近似（如集合覆盖、L1 回归）。

33.3 梯度下降¶

• 无约束梯度下降：x ← x − η∇f(x)（凸函数保证收敛）；
• 对 α-强凸、β-光滑 函数：收敛率 O(1/ε²) 步或指数收敛（定理 33.8 等）。
• 约束梯度下降：投影步（projected gradient）保证可行域内（定理 33.11）。
• 应用：解线性方程组（最小二乘/正规方程）、机器学习训练损失函数最小化。
• 随机梯度下降（SGD）（习题 33-4）：每次用一个样本估计梯度——大数据规模下显著降成本（机器学习训练标配）。

33 小结¶

聚类（Lloyd/k-means）、乘法权重（在线学习竞比）、梯度下降（凸优化收敛性）、SGD；是现代机器学习算法的基础工具

第 34 章 NP 完全性（NP-Completeness）¶

教学目标¶

• 掌握 P、NP、NP 完全的形式化定义（语言/编码/归约）
• 掌握归约的方法与”证明一个问题是 NP 完全的”标准流程
• 熟悉经典 NP 完全问题谱系（电路可满足性 → SAT → 3-CNF → 团/顶点覆盖/哈密顿回路/TSP/子集和）

34.1 多项式时间¶

• 抽象问题 → 判定问题（语言）→ 编码；P = 可多项式时间判定的语言（图灵机模型；多项式时间 = 健壮（不依赖编码细节）——引理 34.1）。

34.2 多项式时间验证与 NP¶

• 验证器：证书（certificate）在多项式时间内验证；NP = 有多项式时间验证器的语言。
• 例：哈密顿回路问题（HAM-CYCLE）易验证（给回路）但未知可求解。

34.3 可归约性与 NP 完全¶

• 多项式时间归约 A ≤_P B：A 的实例映射到 B 的实例，保持答案（yes⇔yes）。
• NP 完全：∈ NP 且 NP 中所有问题可多项式归约到它（语言框架：引理 34.3，定理 34.4）。
• 第一个 NP 完全问题：电路可满足性（CIRCUIT-SAT）——Cook-Levin 思想：NP 语言的多项式验证器可编码为电路，故 NP ⊆ P 当且仅当 CIRCUIT-SAT ∈ P。

34.4 NP 完全性证明¶

• 标准流程：证明 L ∈ NP；选已知 NP 完全问题 A，构造 A ≤_P L（归约）。
• 公式可满足性 SAT ≤_P（从电路编码）；3-CNF-SAT（用”真值表/布尔公式等价”把 SAT 转为 3-CNF）。
• 归约设计策略（34.5.6）：从一般到特殊、利用原问题结构、找特例、设计构造部件（gadget）。

34.5 经典 NP 完全问题（归约链）¶

• CLIQUE（来自 3-CNF-SAT）；
• VERTEX-COVER（来自 CLIQUE）；
• HAMILTONIAN-CYCLE（来自 VERTEX-COVER，部件构造）；
• TSP（来自 HAM-CYCLE，加边权技巧）；
• SUBSET-SUM（来自 3-CNF-SAT）。
• 这些归约展示了”从一个结构到另一个结构”的典型手法，是学习归约设计的样板。

34 小结¶

P、NP、NP 完全、归约、验证与语言、电路-SAT→SAT→3-CNF→（团/顶点覆盖/哈密顿/TSP/子集和）；”看起来像 NP 难”的判断力与归约构造能力是本章核心技能

第 35 章 近似算法（Approximation Algorithms）¶

教学目标¶

• 掌握近似比与近似方案（PTAS/FPTAS）的定义
• 掌握几个经典问题的近似算法：顶点覆盖、TSP、集合覆盖、MAX-3-CNF、子集和
• 理解”NP 难优化问题如何妥协求近优”

35.0 性能比¶

• 近似比 ρ(n)：max{C/C, C/C} ≤ ρ(n)（C 算法解，C* 最优解）；最小化/最大化统一。
• 近似方案：对任意 ε>0 为 (1+ε)-近似；
• PTAS：固定 ε 时多项式时间；
• FPTAS：时间多项式于 n 与 1/ε（如 O((1/ε)² n³)）。

35.1 顶点覆盖（vertex cover）¶

• 贪心/极大匹配近似：选一条未覆盖边，两点都入覆盖——近似比 2（定理 35.1）。
• 证明思想：任一匹配边两顶点被覆盖，极大匹配大小 ≤ 最优 ≤ 2·匹配大小。

35.2 旅行商问题（TSP）¶

• 三角不等式 TSP：由 MST 深度优先遍历 + 跳跃（MST 双遍历）得近似比 2（定理 35.2）。
• 一般 TSP：若 P≠NP，则不存在任何常数比 ρ 近似（定理 35.3，把 HAM-CYCLE 归约构造）。
• 结论：近似算法依赖问题结构（三角不等式）——坏结构问题不可近似。

35.3 集合覆盖（set cover）¶

• 贪心算法：每次选覆盖最多未覆盖元素的新集合；
• 分析：代价 ≤ ln n 倍最优（对数近似比，定理 35.4）——利用分配/双计数证明。
• 集合覆盖是最小化的典型：比 2 更差但仍有界（且 (1−ε)ln n 近似不可改善，NP 假设下）。

35.4 随机化与线性规划¶

• MAX-3-CNF 可满足性：随机给每个变量独立赋真值——期望满足子句 ≥ 7/8，即 8/7-近似（定理 35.5）。
• 加权顶点覆盖：用 LP 松弛（变量 0≤x≤1 放松整数约束）→ 取 x≥1/2 圆整 → 2-近似（定理 35.6）。
• 展示了随机化与线性规划两种现代近似工具。

35.5 子集和（subset-sum）¶

• 指数精确算法（枚举合并表）；
• FPTAS：缩放/修剪（truncation + rounding 去掉多余子集）→ 对任何 ε 得到 (1+ε)-近似，时间多项式于 n 与 1/ε（定理 35.7）。
• 例：0-1 背包的近似模式（习题）。

35 小结¶

• 近似比/PTAS/FPTAS、2-顶点覆盖、2-TSP（三角不等式）、对数集合覆盖、8/7-MAX-3SAT、LP 松弛与随机化、子集和 FPTAS；近似算法是在 NP 难问题面前”工程可得性”的系统方法

结语与学习路径建议¶

全课程知识框架¶

1. 分析工具：渐近记号（3）、递归式（4）、概率/随机（5）、摊还（16）
2. 排序与顺序统计：插入/归并（2）、堆（6）、快排（7）、线性排序（8）、选择（9）
3. 数据结构：基础结构（10）、哈希（11）、BST（12）、红黑树（13）、B 树（18）、并查集（19）、扩充结构（17）
4. 设计技术：分治（2/4）、动态规划（14）、贪心（15）、随机化（5/7/9）
5. 图算法：BFS/DFS/拓扑/SCC（20）、MST（21）、最短路（22–23）、最大流（24）、匹配（25）
6. 高级主题：并行（26）、在线（27）、矩阵（28）、LP（29）、FFT（30）、数论（31）、字符串（32）、ML（33）
7. 复杂度与现代：NP 完全（34）、近似（35）

掌握程度自检建议¶

• 必会证明：循环不变式（2）、递归式主定理（4）、BFS/DFS 正确性（20）、Dijkstra/Bellman-Ford 正确性（22）、max-flow min-cut（24）、贪心正确性（15）、DP 最优子结构（14）、NP 归约（34）。
• 必会手算：插入/归并/堆/快排过程、红黑树插入删除、Floyd-Warshall 表、Ford-Fulkerson 增广、KMP 前缀函数、FFT 蝶形。
• 复杂度表（核心记忆）：
  | 算法 | 时间复杂度 |
  |—|—|
  | 插入排序 | O(n²) |
  | 归并/堆/快排（期望） | O(n log n) |
  | 计数/基数/桶（条件） | O(n) |
  | 选择（期望/最坏） | O(n) |
  | 哈希 | 期望 O(1) |
  | 红黑树/B 树 | O(log n) |
  | BFS/DFS/拓扑/SCC | O(V+E) |
  | Prim/Kruskal | O(E log V) |
  | Dijkstra | O(E log V) |
  | Bellman-Ford | O(VE) |
  | Floyd-Warshall | O(n³) |
  | Johnson | O(VE + V² log V) |
  | Ford-Fulkerson | O(E·f*) |
  | Edmonds-Karp | O(VE²) |
  | Hopcroft-Karp | O(√V·E) |
  | KMP/Rabin-Karp | O(n+m) |
  | FFT | O(n log n) |
  | Euclid | O(log n) |
  | 并查集（两个启发式） | O(m α(n)) |

教授寄语：算法导论的核心不是背算法，而是培养三种能力——严谨的证明能力（为什么正确）、精确的分析能力（为什么高效）、建模的能力（把实际问题转成已知算法问题）。每章学完后，建议亲手实现关键算法并用随机数据对拍验证，再回归本章”必须掌握的关键词”自测。

（本文档根据各章节 full.md 材料整理，覆盖第 1–35 章全部学习要点。）

AI生成

🗺️ 长汀古城两日游行程路线（高效不绕路）¶

上午动车/自驾出发。¶

• 中午 (12:00-13:30)：水东街觅食
  从卧龙书院出来，步行到本地人常去的水东街解决午餐。这里是品尝地道客家小吃的好地方。

• 下午 (13:30-17:30)：漫步古城精华

  • 13:30 八喜馆 & 大夫第：这两个景点相邻。八喜馆展示客家人“八大喜”民俗，有非遗表演；大夫第是清代官宅，木雕精美，被誉为“八闽第一雕花楼”。
  • 15:10 店头街：一条有千年历史的明清古街。青石板路两侧是各种传统手工作坊和特色小店，可以慢慢逛，感受古时商贸的繁荣。
  • 17:20 汀江古城墙漫步：从店头街出来，沿着唐代古城墙散步，这里是拍日落大片的绝佳位置。

• 晚上 (18:30-21:00)：沉醉汀江夜韵

  • 18:50 登济川门城楼：汀州最雄伟的城门，登高可俯瞰汀江夜景。每晚19:30左右有灯光秀。
  • 19:40 夜游汀江：在码头乘画舫游船（约60元/人），从水上欣赏两岸灯火。
  • 20:30 夜市与宵夜：下船后可以回到店头街或去小吃街，用一顿客家夜宵结束一天的行程。

• 次日上午 (8:30-12:00)：寻访历史文脉

  • 8:30 三元阁：从古城中心的唐代城门楼开始，清晨人少，适合拍照。
  • 9:00 汀州试院（长汀县博物馆）：凭身份证免费参观。这里是古代科举考场，院内有千年唐代古柏，也是了解客家历史和红色文化的好地方。
  • 10:10 卧龙书院：朱熹曾讲学的地方，徽派园林式建筑，非常清幽。二楼可免费体验笔墨纸砚。书院门口的木偶戏博物馆也值得一看。

🎫 门票信息¶

• 古城本身：免费进入。
• 内部景点：参观卧龙书院、济川门、八喜馆、大夫第等需要购票。推荐购买联票，价格在88元至98元之间，比单买划算。
• 长汀县博物馆：凭身份证免费参观。

🍜 美食推荐¶

长汀是客家美食之都，这些地道风味不容错过：

• 必吃小吃：泡猪腰（招牌，脆嫩无腥味）、芋子饺、灯盏糕、簸箕粄。
• 经典大菜：白斩河田鸡、客家酿豆腐。
• 推荐店铺：
  • 有间饭店：泡猪腰是一绝。
  • 城墙煎薯饼：煎薯饼和汆猪肉很受欢迎。
  • 醉春风：店面宽敞，盐酒鸡、泡猪腰都不错。
• 伴手礼：长汀豆腐干、客家米酒。

总览：高中语文核心素养与高考命题方向¶

一、四大核心素养（新课标）¶

二、2026高考语文命题六大核心变化（温儒敏解读）¶

1. 从”考知识”到”考素养”：告别碎片化考查（不再单独拆分字音、字形、病句），以语言运用为基础融合思维能力与审美能力，综合打包考查
2. 从”解题”到”解决问题”：设置真实情境（如采访提纲设计、活动方案策划），考查综合运用能力
3. 从”单一文本”到”多文本互证”：跨文本对比阅读成为常态，要求在不同材料间筛选、比较、评价
4. 从”套作模板”到”思维深度”：作文反套路，强调逻辑思辨，”答题模板通通失效”
5. 从”静态知识”到”动态运用”：文言文不再只考翻译，更考语境理解与活学活用
6. 从”封闭答题”到”开放表达”：答案不唯一，有理有据即可得分，鼓励个性化表达

三、2026高考语文全国卷分值结构（参考）¶

四、高中三年学习路径总览¶

第一学期：高一上（必修上册）¶

学习任务群分布¶

必会知识点（详细扩充）¶

一、古诗文必背篇目与逐篇鉴赏要点¶

二、文言文核心知识（详细分解）¶

1. 词类活用（七大类型+本册经典例句）¶

2. 特殊句式（八大类型+本册经典例句）¶

3. 虚词系统（本册重点5个精讲）¶

“而”的七种用法：
1. 并列关系（又，而且）：”蟹六跪而二螯”
2. 承接关系（就，才）：”学而时习之”
3. 转折关系（但是，却）：”而耻学于师”
4. 递进关系（而且）：”君子博学而日参省乎己”
5. 修饰关系（地）：”吾尝跂而望矣”
6. 假设关系（如果）：”人而无信，不知其可也”
7. 因果关系（因而）：”赂秦而力亏”

“之”的五种用法：
1. 代词（他/它/这）：”作《师说》以贻之”
2. 结构助词”的”：”古之学者必有师”
3. 助词，取消句子独立性：”师道之不传也久矣”
4. 宾语前置标志：”句读之不知”
5. 定语后置标志：”蚓无爪牙之利”

“其”的四种用法：
1. 代词（他的/它的/其中的）：”其闻道也固先乎吾”
2. 代词（那/那个）：”其孰能讥之乎”
3. 副词（大概/恐怕）：”其皆出于此乎”
4. 副词（难道/岂）：”其可怪也欤”

“以”的四种用法：
1. 介词”用/拿/凭”：”以五十步笑百步”
2. 介词”因为”：”不以物喜，不以己悲”
3. 连词”来/用来”：”作《师说》以贻之”
4. 连词”而”（表修饰）：”木欣欣以向荣”

“于”的四种用法：
1. 介词”在”：”而耻学于师”
2. 介词”对/对于”：”于其身也则耻师焉”
3. 介词”比”：”青，取之于蓝而青于蓝”
4. 介词”被”：”不拘于时”

4. 实词积累（本册120实词中的高频词）¶

三、文学常识（详细展开）¶

1. 诗词体裁体系¶

2. 词的发展脉络与两大流派¶

3. 散文分类体系¶

四、阅读与写作能力（详细展开）¶

1. 诗歌鉴赏四步法¶

第一步：读标题与作者 → 知人论世，初步定调
第二步：析意象与意境 → 逐联扫描，概括画面
第三步：判手法与技巧 → 修辞+表达技巧+结构技巧
第四步：明情感与主旨 → 概括情感层次（表层+深层）

2. 诗歌鉴赏术语体系¶

3. 小说阅读知识体系¶

4. 写作训练体系¶

记叙文写作（青春主题）：
- 素材来源：个人成长经历、身边的青春故事、课本中的人物启发
- 结构模型：线型叙事（起因→经过→高潮→结局）、对比式、片段组合式
- 技法重点：细节描写（动作/语言/心理/外貌）、环境烘托、虚实结合
- 升格要点：避免流水账，选取典型片段；以小见大，由事入理

议论文入门（学习之道）：
- 基本结构：引论（提出论点）→本论（分层论证）→结论（深化论点）
- 论证方法：举例论证、引用论证、对比论证、比喻论证
- 入格训练：每段必有分论点+论据+分析+小结
- 过渡衔接：使用逻辑关联词（首先/其次/再次/最后；然而/诚然/进而言之）

五、整本书阅读：《乡土中国》（详细展开）¶

1. 十四篇核心概念梳理¶

2. 阅读方法指导¶

• 圈点批注法：在概念定义处画线，在论述转折处批注疑问
• 概念地图法：以”差序格局”为中心，辐射关联概念
• 对比阅读法：将中国乡土社会与西方现代社会对比
• 高考化阅读法：将每篇提炼为”观点+论据+论证”三要素结构

3. 高考衔接训练¶

• 信息类文本：给出2~3段关于”差序格局”的学术材料，做对比阅读题
• 作文素材：以”乡土中国的现代转型”为话题的思辨作文

六、语言积累与梳理（第八单元详细展开）¶

1. 词语积累方法¶

2. 成语积累重点（本册关联）¶

第二学期：高一下（必修下册）¶

学习任务群分布¶

必会知识点（详细扩充）¶

一、古诗文必背篇目与逐篇鉴赏要点¶

二、文言文核心知识（详细分解）¶

1. 先秦诸子思想对比¶

2. 史传文叙事艺术精讲¶

《烛之武退秦师》叙事技法：
- 伏笔：佚之狐早有推荐→暗示郑国有人才
- 张弛：大军压境（紧张）→烛之武出使（舒缓）→说服退兵（高潮）
- 语言艺术：五层递进说辞（亡郑无益→亡郑有害→舍郑有益→历史恩怨→前景预测）
- 人物塑造：寥寥数笔刻画忠臣形象（”臣之壮也，犹不如人”的自嘲中含不平）

《鸿门宴》叙事技法：
- 结构艺术：宴会前的杀机→宴会上的明争暗斗→宴会后的余波
- 人物群像：

3. 文言实词扩展（本册重点）¶

三、文学常识（详细展开）¶

1. 中国古代小说发展脉络¶

2. 戏剧常识体系¶

3. 戏剧文本阅读方法¶

• 把握核心冲突→分析人物关系→品味关键对白→理解舞台说明→挖掘深层主题
• 窦娥”三桩誓愿”（血溅白练/六月飞雪/亢旱三年）的分析：誓愿层层递进→控诉力度加强
• 哈姆莱特”生存还是毁灭”独白分析：内心矛盾的本质（行动vs犹豫）

四、阅读与写作能力（详细展开）¶

1. 小说阅读升级：叙事技巧体系¶

2. 中外小说比较阅读¶

3. 写作训练体系¶

议论文深化（论点明确/论据充实/论证严密）：
- 分论点设置法：
- 并列式：从不同角度展开（个人/社会/国家）
- 递进式：层层深入（是什么→为什么→怎么办）
- 对比式：正反对比论证
- 论据运用技巧：
- 叙议结合：不能只摆事实不论理
- 一例多用：同一素材从不同角度解读
- 旧例新说：经典素材寻找新角度
- 逻辑链条构建：
- 概念界定→原因分析→影响评估→对策提出

演讲稿写作：
- 开场白：引子+论点
- 主体：分论点+论据+情感感染
- 结尾：号召与展望
- 语言特点：排比、设问、短句、呼告

五、整本书阅读：《红楼梦》（详细展开）¶

1. 人物谱系图¶

贾府
├── 荣国府
│   ├── 贾母（史太君）
│   ├── 贾政 — 王夫人
│   │   ├── 贾宝玉（核心）
│   │   ├── 贾珠（已亡）
│   │   └── 贾元春
│   └── 贾赦 — 邢夫人
│       └── 贾琏 — 王熙凤
└── 宁国府
    └── 贾珍

关键女性
├── 林黛玉（木石前盟）
├── 薛宝钗（金玉良缘）
├── 王熙凤（管理天才）
├── 贾探春（改革者）
└── 史湘云（名士风度）

2. 前五回纲领作用¶

3. 高考衔接¶

• 文学类文本阅读：从《红楼梦》选段出小说阅读题
• 作文素材：宝玉的反叛精神、探春的改革意识、刘姥姥的底层智慧

第三学期：高二上（选择性必修上册）¶

学习任务群分布¶

必会知识点（详细扩充）¶

一、古诗文必背篇目与逐篇鉴赏要点¶

二、文言文与传统文化核心知识¶

1. 诸子思想深化对比¶

2. 儒家”内圣外王”逻辑链¶

修身（明明德）
  ↓
齐家（亲民）
  ↓
治国（仁政/礼治）
  ↓
平天下（止于至善）

关键：从个人道德修养出发，向外扩展到社会治理。这一逻辑在高考作文中极为常用。

3. 道家”无用之用”辩证¶

• 《五石之瓠》核心辩证：大瓠→惠子以为无用（盛水/做瓢都不行）→庄子批判”有蓬之心”→说明”无用”实为”大用”
• 延伸思辨：无用之用方为大用→功利主义vs审美主义→现代社会中的反思

三、外国小说阅读体系（详细展开）¶

四大小说阅读方法对比：

四、逻辑思维能力（详细展开）¶

1. 形式逻辑核心知识¶

概念：
- 内涵：概念所反映的事物的特有属性
- 外延：概念所反映的对象的范围
- 关系：同一/包含/交叉/矛盾/反对

判断：
- 性质判断：所有S是P/有些S不是P
- 假言判断：如果P那么Q/只有P才Q
- 选言判断：或者P或者Q

推理：
- 演绎推理：三段论（大前提+小前提→结论）
- 归纳推理：完全归纳/不完全归纳
- 类比推理：A有a,b,c,d；B有a,b,c→B可能有d

2. 四大逻辑规律¶

3. 逻辑谬误识别（高考常见）¶

五、写作训练（详细展开）¶

1. 思辨性议论文结构模型¶

模型一：辩证推进式

引论：提出核心问题
├── 正面分析：合理性/价值
├── 反面审视：局限性/问题
├── 辩证综合：在更高层次上统一
└── 结论：提出建设性观点

模型二：让步驳论式

引论：亮出核心论点
├── 让步：承认对方观点的合理之处
├── 转折：指出其不足/局限
├── 深入：进一步论证自己的观点
└── 结论：升华论点

模型三：层递推进式

引论：提出论点
├── 是什么（现象界定）
├── 为什么（原因探究）
├── 怎么办（对策提出）
├── 会怎样（前景展望）
└── 结论：回扣论点

2. 传统文化主题作文素材库¶

第四学期：高二下（选择性必修中册）¶

学习任务群分布¶

必会知识点（详细扩充）¶

一、古诗文必背篇目与逐篇鉴赏要点¶

二、文言文核心知识（详细分解）¶

1. 政论文阅读体系：《过秦论》¶

论证结构图：

秦孝公据崤函之固（地利）
  → 商君佐之（人和）
    → 内立法度/外连横（策略）
      → 秦国崛起

惠文/惠武/昭襄
  → 南取/西举/东割/北收（扩张）
    → 六国合纵抗秦
      → 秦愈强六国愈弱

始皇
  → 振长策/执敲扑（武力统一）
    → 焚百家/隳名城（暴政）
      → 陈涉起义→秦亡

结论：仁义不施而攻守之势异也

高考命题角度：
- 对比论证的层次分析（九国之师 vs 陈涉 vs 秦朝自身）
- 铺叙的作用（渲染秦之强→反衬其亡之速）
- “攻守之势异也”的深层含义

2. 史论阅读体系：《伶官传序》¶

三重对比结构：
1. 盛衰对比（得天下之难 vs 失天下之易）
2. 人事对比（忧劳可以兴国 vs 逸豫可以亡身）
3. 天命vs人事（虽曰天命→岂非人事哉）

3. 边塞诗体系¶

4. 咏史怀古诗鉴赏框架¶

读标题 → 确定古迹/古人
析首联 → 把握所咏史实
品用典 → 理解典故含义
悟尾联 → 把握作者寄托
联作者 → 结合知人论世

常见主题：借古讽今/借古伤己/借古咏怀/怀古伤今

三、革命文学作品阅读（详细展开）¶

1. 鲁迅散文笔法¶

2. 三种革命小说风格对比¶

四、外国诗歌阅读（详细展开）¶

五、写作训练（详细展开）¶

1. 文学评论写作规范¶

基本结构：

引论：简述作品+亮出评论观点
├── 分析一：手法/语言/结构/意象
├── 分析二：人物/情感/主题/风格
├── 分析三：综合评价/比较延伸
└── 结论：总结评论观点

常见失误与纠正：
- 复述情节过多→应精简概述，重在分析
- 术语使用不当→确保术语准确（如”象征”vs”比喻”）
- 感想式评论→必须有理论支撑和文本证据
- 观点模糊→开篇即明确评论角度

2. 历史思辨作文素材¶

第五学期：高三上（选择性必修下册 + 高考一轮复习启动）¶

学习任务群分布¶

必会知识点（详细扩充）¶

一、古诗文必背篇目与逐篇鉴赏要点¶

二、文言文核心知识¶

1. 四篇抒情古文文体与写法对比¶

2. 《诗经》与楚辞比兴体系对比¶

3. 说理文言文两篇对比¶

三、现当代文学体系（详细展开）¶

四、高考一轮复习核心要点（详细展开）¶

1. 信息类文本阅读¶

答题四步法：

步骤一：速读全文，标划论点与论据
步骤二：审题定位，确定考查区间
步骤三：比较筛选，区分材料异同
步骤四：规范表述，分点作答

六大题型及应对：

2. 文学类文本阅读¶

小说阅读答题框架：

散文阅读答题框架：
- 形散神聚：找”形”（人/事/景/物）→找”神”（贯穿全文的情感线索）
- 语言赏析：用词精妙（叠词/动词/色彩）+句式特色（长短/整散/反复）+修辞效果

3. 文言文翻译六大原则¶

4. 古诗词鉴赏答题模板¶

常见题型公式：

5. 名篇名句默写策略¶

• 理解性默写为主流趋势，不再考查简单机械默写
• 情境化默写：给出特定语境，要求写出相关语句
• 备考策略：理解诗句含义→理解在全文中的作用→关联相似主题的诗句

6. 语言文字运用专题¶

第六学期：高三下（高考二轮复习 + 冲刺）¶

复习模块化详解¶

一、现代文阅读¶

1. 信息类文本阅读提分攻略¶

高频失分点与纠正：

2. 文学类文本阅读提分攻略¶

小说阅读五大高频题型深度攻略：

二、古代诗文阅读¶

1. 文言文断句六大标志¶

2. 文言文翻译增分技巧¶

• 得分点意识：每个翻译题有3~5个得分点（实词/虚词/句式/活用/通假）
• 踩分步骤：先翻译得分点→再组织成通顺句子→最后润色
• 常见失误：漏译、死译、乱译（随意发挥）

3. 古诗词鉴赏时间管理¶

• 建议用时：8~10分钟
• 阅读诗题+注释：2分钟
• 品读全诗：3分钟
• 组织答题：5分钟
• 每点1~2行，共3~4点

三、语言文字运用¶

1. 六大病句类型速判表¶

2. 2026新增趋势题型¶

采访提纲设计：
- 问题要有深度（非”是什么”而是”为什么/怎么样”）
- 问题之间要有逻辑递进
- 理由说明要基于文本内容
- 注意角色定位（你是记者，不是评论员）

情境化语言综合运用：
- 根据特定场景选择表达方式
- 注意对象意识（对老师/对同学/对公众语气不同）
- 格式规范（倡议书/感谢信/活动方案各有规范格式）

四、写作¶

1. 高考作文评分标准细则¶

2. 四类作文类型详解¶

任务驱动型作文：
- 核心要义：必须完成试题给定的”任务”
- 任务类型：给材料+给指令（”请谈谈你的看法”/”请就此写一篇…”）
- 失误点：不完成任务指令→严重扣分
- 应对：先圈画任务指令→全文围绕任务展开

思辨型作文：
- 核心要义：展现思维深度和辩证能力
- 常见命题：”有人说…也有人说…你怎么看？”
- 结构策略：让步→转折→深入→综合
- 失误点：单面论述、回避矛盾→缺乏思辨

实用类作文：
- 格式要求：

文学短评：
- 定义：对文学作品的手法、语言、主题进行专业评论
- 结构：观点+文本分析+理论支撑+评价
- 语言：使用文学批评术语（如”叙事视角”“意象体系”“互文性”）
- 失误：感想式/复述式→缺乏专业分析

3. 作文升格路径¶

基础等级（30分）
  → 论点明确 + 论据充实 + 论证基本合理

发展等级（+10分）
  → 分论点有层次 + 有辩证思维 + 语言流畅

特色等级（+10分）
  → 深刻独到 + 文采斐然 + 结构精巧

满分路径
  → 审题精准 + 立意高远 + 逻辑严密 + 语言出彩 + 书写工整

4. 2026高考作文热点预测方向¶

附录¶

附录一：高中全五册必背古诗文总清单（34篇核心）¶

注：实际高考默写范围以当年考试说明为准，总量约64篇（含初中篇目30篇）。

附录二：18个文言虚词用法详解表¶

1. 而¶

2. 之¶

3. 其¶

4. 以¶

5. 于¶

6~18. 其余13个虚词精要¶

附录三：高考语文答题规范与提分建议¶

答题规范¶

1. 分点作答：标明①②③，要点化、条理化，每点1~2行
2. 术语准确：如”借景抒情”不写”用景物表达感情”，”衬托”不写”对比”
3. 结合文本：每一点都要有文本依据（引用原文关键词句），”言必有据”
4. 审题精准：注意题干限制条件（”结合材料”“用自己的话”“从…角度”等）
5. 书写工整：高考阅卷电子扫描，书写清晰影响得分

提分建议（面向2027届考生）¶

1. 告别刷题套路：2026高考已证实模板答题失灵，要回归文本理解与素养积累
2. 强化逻辑训练：信息类文本的逻辑分析是拉分关键，日常训练关注论证方法与逻辑谬误
3. 注重跨文本对比：多文本阅读是常态，日常训练要有意识做2~3篇文章的对比阅读
4. 写作重思维深度：议论要层层推进，避免”观点+例子”的平面结构，学会让步与驳论
5. 文言文重语境理解：不背死翻译，训练根据上下文推断词义的能力
6. 名篇默写贵在坚持：每日10分钟滚动复习，考前强化情境化默写
7. 整本书阅读不可跳过：《乡土中国》《红楼梦》是信息类文本和作文素材的重要来源
8. 积累作文素材：按”科技/文化/青年/生态/文明”五大方向分类积累，每方向至少5个精准素材
9. 模拟实战训练：高三下学期至少做6套完整高考真题，严格计时150分钟
10. 重视书写卷面：练字是性价比最高的提分方式，至少保证清晰可辨认

附录四：高中语文学习时间规划建议¶

AI大模型在金融风控领域的应用案例（近30天）¶

检索时间范围：2026年7月中旬至8月上旬
数据来源：WAIC 2026世界人工智能大会、行业媒体公开报道

五大典型应用场景¶

趋势总结¶

1. 从单点工具到全流程嵌入：AI大模型已从辅助风控工具升级为贯穿贷前、贷中、贷后的全流程核心引擎
2. 多模态能力成为标配：身份证、营业执照、流水单、财报等非结构化材料的多模态识别与理解是落地突破口
3. 人机协同新范式：银行从”人防”走向”人机协同”，AI助手承担信息整理、初步研判，人工聚焦决策确认
4. 智能体（Agent）规模化落地：宁波银行部署风控中台智能体、预警智能体等多类型智能体，易鑫智能体自主交付占比达65%
5. 算力底座国产化：浦发银行联合华为昇腾构建千卡推理资源池，国产算力支撑大模型风控成为主流路径

本文由TeleAgent整理发布，数据截至2026年8月10日

AI生成

根据《义务教育语文课程标准（2022年版）》的学段要求，并结合统编版语文教材的习作安排，1-9年级作文主题可按年级整理如下：

第一学段（1-2年级）：写话

目标：对写话有兴趣，留心周围事物，写自己想说的话，写想象中的事物。

一年级

• 看图写话：单幅图、多幅图，写清图意
• 观察写话：季节变化、动植物、自然现象（一句话或几句话）
• 想象写话：续编故事、愿望表达
• 生活情境写话：介绍自己、家人、校园生活
• 应用类写话：简单留言、祝福语

二年级

• 看图写话：情节较复杂的多幅图，加入对话、心理
• 写人：我的好朋友、家人
• 记事：一件趣事、做手工、游戏
• 写景：家乡、校园一角、季节景色
• 状物：喜欢的玩具、小动物、植物
• 想象：童话续编、假如我会变
• 应用文：留言条、请假条（格式正确）

第二学段（3-4年级）：习作

目标：乐于书面表达，能不拘形式地写下见闻、感受和想象，能用简短的书信、便条交流。

三年级

• 写人：猜猜他是谁、身边有特点的人
• 记事：那次玩得真高兴、我做了一项小实验、多彩的活动
• 写景：这儿真美、身边的一处景物
• 状物：我的植物朋友、国宝大熊猫、静物观察
• 想象：我来编童话、奇妙的想象、这样想象真有趣
• 看图作文：看图画写场景、写事件
• 应用文：日记、通知

四年级

• 写人：我的“自画像”、我的家人、朋友
• 记事：生活万花筒、记一次游戏、我学会了______、成长故事
• 写景：推荐一个好地方、游______（按游览顺序）
• 状物：我的动物朋友、观察一种事物
• 想象：我和__过一天、故事新编、未来的____
• 应用文：书信、观察日记

第三学段（5-6年级）：习作

目标：能写简单的记实作文和想象作文，内容具体，感情真实；学写读书笔记，学写常见应用文。

五年级

• 写人：“漫画”老师、他______了、形形色色的人
• 记事：那一刻，我长大了、______让生活更美好、探险/惊险经历
• 写景：______即景（动态变化）
• 状物：我的心爱之物、介绍一种事物（说明性）
• 想象：二十年后的家乡、神奇的探险之旅、科幻故事
• 读后感：读______有感
• 介绍说明类：推荐一本书、中国的世界文化遗产
• 简单议论：漫画的启示、社会现象小评论

六年级

• 写人：有你，真好、我的同学/亲人
• 记事：多彩的活动、让真情自然流露、毕业季故事
• 想象：变形记、插上科学的翅膀飞（科幻）、虚构小说
• 应用文：倡议书、活动策划书、毕业赠言
• 作品加工：写作品梗概、学写说明书
• 话题作文：围绕中心意思选材（如“甜”“泪”）

第四学段（7-9年级）：写作

目标：写记叙性文章，表达意图明确，内容具体充实；写简单的说明性文章，做到明白清楚；写简单的议论性文章，观点明确，有理有据；能写常见应用文。

七年级

• 记叙文·写人记事：热爱生活热爱写作、学会记事、写人要抓住特点、写出人物精神、抓住细节、亲情与成长
• 写景抒情：学习抒情、调动感官描写景物、情景交融
• 想象作文：发挥联想和想象、寓言童话新编、科幻短文
• 方法论训练：思路要清晰、如何突出中心、怎样选材、文从字顺、语言简明
• 应用文：书信、倡议书等

八年级

• 说明文：说明事物要抓住特征、说明的顺序（时间、空间、逻辑）
• 传记：学写传记、人物小传
• 写景游记：学习描写景物、学写游记、情景结合
• 读后感：学写读后感（紧扣原作，联系实际）
• 应用文与表达：新闻写作、撰写演讲稿、表达要得体
• 故事创作：学写故事、情节设计
• 仿写改写：学习仿写、改写古诗文为散文

九年级

• 议论文：观点要明确、议论要言之有据、论证要合理、写简单的评论
• 创意表达：尝试创作诗歌、有创意地表达
• 作文技法：审题立意、布局谋篇、修改润色
• 形式变换：学习缩写、学习扩写、学习改写（改变文体或叙述角度）
• 综合运用：叙事类、议论类、实用类文章的综合写作，根据情景进行表达

一、写人¶

• 第一学段（1-2年级）
  用几句话或一段话简单介绍人物。写清“是谁”“什么样”，如《我的好朋友》《我的家人》，只需写出外貌或一个明显特点。

• 第二学段（3-4年级）
  能通过一件或几件事表现人物的突出特点。尝试描写外貌、语言、动作，如《猜猜他是谁》《身边有特点的人》，写出人物与众不同之处。

• 第三学段（5-6年级）
  运用具体事例刻画人物形象，写出人物的神态、心理和变化。能表现人物的精神品质或性格的多面性，如《“漫画”老师》《他______了》，把人物写“活”。

• 第四学段（7-9年级）
  抓住细节，写出人物精神和内在世界。在叙事中综合运用多种描写方法，表现人物的个性与精神风貌，如《写出人物精神》《回忆我的母亲》，要求内容充实，感情真挚。

二、记事¶

• 第一学段（1-2年级）
  写一件简单的小事，交代清楚时间、地点、人物和事情的大致经过，如《一件趣事》《那次玩得真高兴》，几句话写完整即可。

• 第二学段（3-4年级）
  按一定顺序把事情的经过写清楚，写出自己的感受。学会把事情的重点部分写具体，如《我学会了______》《生活万花筒》。

• 第三学段（5-6年级）
  记事有详有略，能写出事情发展过程中的情感变化和内心体验。力求表达真情实感，如《那一刻，我长大了》《让真情自然流露》，写出事件对自己的深刻影响。

• 第四学段（7-9年级）
  叙事思路清晰，能根据表达需要选择素材、突出中心。内容充实具体，能运用记叙、描写、抒情等多种表达方式，写出事件的深意和自己的思考，如《学会记事》《我们是一家人》。

三、写景¶

• 第一学段（1-2年级）
  观察身边的一处景物，用几句话写出最直观的样貌，如季节景色、校园一角，会使用简单形容词。

• 第二学段（3-4年级）
  按照一定顺序（如方位、时间）描写景物，能抓住景物的主要特点，如《这儿真美》《游______》，写出景色的“美”或“好”。

• 第三学段（5-6年级）
  写出景物的动态变化，在描写中融入自己的情感。能运用恰当的修辞手法使文字具有感染力，如《______即景》，借景抒情。

• 第四学段（7-9年级）
  调动多种感官多角度描写景物，做到情景交融，在写景中自然融入个人的体验与感悟，如《学习描写景物》《学写游记》，追求意境与神韵。

四、状物与说明¶

• 第一学段（1-2年级）
  描写自己喜欢的玩具、动植物等，简单写清外形、颜色等，表达喜爱之情，如《我喜欢的玩具》。

• 第二学段（3-4年级）
  有顺序地观察并写出事物的样子、习性、功能等，内容较为具体，如《我的植物朋友》《国宝大熊猫》，开始带有一定的说明色彩。

• 第三学段（5-6年级）
  使用常见的说明方法（列数字、打比方、作比较等）介绍一种事物，分条理写清楚主要特点，如《介绍一种事物》《中国的世界文化遗产》，学写说明性文章。

• 第四学段（7-9年级）
  写简单的说明文，能准确抓住事物的特征，根据说明目的合理安排说明顺序（时间、空间、逻辑），语言准确、明白清楚，如《说明事物要抓住特征》。

五、想象作文¶

• 第一学段（1-2年级）
  写想象中的事物，如续编童话故事、表达自己的愿望，鼓励大胆、无拘束的想象，如《我多想……》。

• 第二学段（3-4年级）
  不拘形式地写自己的见闻和想象，能创造简单的童话或设想未来的场景，想象情节基本合理，如《我来编童话》《故事新编》。

• 第三学段（5-6年级）
  写简单的想象作文，能构思相对完整的情节和场景，有科幻或探险等主题，如《二十年后的家乡》《插上科学的翅膀飞》，内容具体。

• 第四学段（7-9年级）
  运用联想和想象进行创意表达，可创作故事、诗歌或小小说，想象既要丰富又要合乎逻辑，并能承载一定的思想内涵，如《发挥联想和想象》《创作诗歌》。

六、常见应用文¶

• 第一学段（1-2年级）
  学写简单留言条、请假条、祝福语等，格式基本正确，用一两句话把要表达的事写清楚。

• 第二学段（3-4年级）
  学写日记、通知、书信（含感谢信等），注意格式的完整，内容真实、清楚。

• 第三学段（5-6年级）
  学写倡议书、活动策划书、书信等，能根据不同的对象和目的选用恰当的语言，内容有条理，格式规范。

• 第四学段（7-9年级）
  学写新闻稿、演讲稿、书信、总结等，表达得体，能根据场合与受众调整语气和表达方式，做到文从字顺、清晰有效。

七、读（观）后感¶

• 第一学段（1-2年级）
  能简单说出一两句话，表达自己读了某本书或文章后的心情或看法，以口头表达为主。

• 第二学段（3-4年级）
  能围绕阅读内容，用几句话写出自己的感受和想法，内容主要为复述加一点感想。

• 第三学段（5-6年级）
  正式学写读后感，能够概括原文主要内容，并围绕一个感受点联系自己的生活或经验来写，如《读______有感》。

• 第四学段（7-9年级）
  能紧扣原作的某个方面展开，写出自己的独到见解，做到“引、议、联、结”结构清晰，观点明确，内容充实。

八、议论文（简单议论）¶

• 第一、二学段
  不作要求。

• 第三学段（5-6年级）
  能对图片、现象等发表简单的看法，如从漫画中读出启示，尝试写一段有观点的文字，表达自己的态度和理由。

• 第四学段（7-9年级）
  写简单的议论文，能够提出明确的论点，选用恰当的论据进行合理论证，结构完整、逻辑清晰，如《观点要明确》《议论要言之有据》。

二年级（写话）¶

写作要求：写清时间、地点、看到了什么，几句话表达感受。

范文：

游云水谣

今天，爸爸妈妈带我去云水谣玩。

云水谣真美啊！我看到了很多很大很大的榕树，它们的树枝长长的，像一把把绿色的大伞。树下有一条小河，河水清清的，能看到水底的石头。河上有座小石桥，我和爸爸从桥上走过去，桥下的小鱼在游来游去。

最好看的是那些圆圆的土楼。它们像一个个大大的圆圈，墙壁是黄色的，窗户小小的。听妈妈说，以前有很多人住在里面，大家一起生活，真有意思。

在云水谣，我还吃到了好吃的糍粑，甜甜的、软软的。

这一天我玩得真开心，真想下次再来云水谣！

四年级（写景·游记）¶

写作要求：按游览顺序写，写出景物特点，融入感受。

范文：

云水谣游记

假期里，爸爸妈妈带我去了福建南靖的云水谣古镇。一下车，我就被眼前的景色迷住了。

沿着鹅卵石铺成的小路往前走，第一眼看到的就是那几棵古老的榕树。它们比我想象的要大得多，树干粗得要几个人才能合抱，枝叶茂密得像一片绿色的天空。树下的溪水哗啦啦地流淌，阳光透过树叶洒在水面上，波光粼粼的，像撒了一河的碎金子。我忍不住蹲下来摸了摸溪水，凉丝丝的，舒服极了。

过了石跳桥，我们来到了怀远楼。这是一座圆形的土楼，从外面看，它就像一座坚固的城堡。走进去，里面别有洞天。四层的楼房围成一个圆圈，中间是一个大院子，院子里有一口古井。站在院子中央抬头看，天空变成了一个圆圆的大蓝盘，真奇妙！我摸着斑驳的土墙，想像着几百年前的人们在这里生活的样子。

夕阳西下，我们依依不舍地离开了云水谣。回程的路上，那潺潺的溪水声好像还在耳边回响。云水谣，你真是一个让人流连忘返的好地方！

六年级（写景·情景交融）¶

写作要求：写出景物的动态变化，注重真情实感，有详有略。

范文：

漫步云水谣

有人说，云水谣是一个可以让人慢下来的地方。当我真正走进它，才发现这句话一点也不假。

清晨的云水谣，笼罩在一层薄薄的雾气中，远山近水都蒙上了轻纱，像一幅淡雅的水墨画。沿着溪边的小路慢慢走，脚下是被岁月磨得光滑圆润的鹅卵石，发出轻轻的声响。

溪边那几棵古榕，不知道已经站立了几百年。它们的根须像老爷爷的长胡子，从枝干上垂下来，有的已经扎进了泥土，长成了新的树干。微风吹过，树叶沙沙作响，像是在低声诉说着古老的故事。溪水绿得像一块翡翠，倒映着古榕、石桥和蓝天，偶尔有白鹭掠过水面，激起一圈圈涟漪，打破了这片刻的宁静。

走进和贵楼，我感受到了一种厚重的历史气息。这座建在沼泽地上的土楼，经历了两百多年的风雨，依然稳稳地矗立着。木质的楼梯发出吱呀的响声，每一声都像是历史的回音。站在楼上往下看，院子里的老人们坐在竹椅上闲聊，孩子们追逐嬉戏，生活在这里缓缓流淌，一如百年前。

离开的时候，我忍不住回头望了一眼。云水谣静静地躺在群山的怀抱里，安宁而从容。这次旅行，我不仅看到了美丽的风景，更感受到了一种远离喧嚣的宁静。或许，这就是旅行的意义——在别处，遇见不一样的时光。

八年级（游记·情景结合）¶

写作要求：调动多种感官多角度描写景物，情景交融，写出个人体验与感悟。

范文：

云水谣记

那个周末，我终于走进了向往已久的云水谣。车子在蜿蜒的山路上穿行，两侧是层层叠叠的翠绿茶山，空气中弥漫着泥土和青草的清香。

到云水谣时，正值午后。阳光穿过古榕浓密的枝叶，在青石路上洒下斑驳的光影。我沿着溪边的小径缓步而行，脚下是光滑的鹅卵石，溪水清澈见底，水草在流水中柔柔地摆动，一群小鱼在水中悠然穿行。溪水的声音时而叮咚轻响，时而哗哗作响，像一首永不停歇的曲子。我脱了鞋，赤脚踩在石头上，清凉的溪水漫过脚踝，那一瞬间，所有的疲惫都被冲刷得干干净净。

云水谣的灵魂，是那些沉默不语的土楼。站在怀远楼前，我感到了一种强烈的震撼。厚厚的土墙，小小的门窗，圆形的天井——这些朴素的建筑元素，却构筑起了一个坚固而温暖的家园。走进楼内，我仿佛穿越了时光。昏黄的光线从天井倾泻而下，照亮了院子中央的石井。我轻轻触摸着粗糙的土墙，感受着指尖传来的凉意。几百年来，客家人在这片土地上聚族而居，守望相助，土楼不仅是一座建筑，更是一种精神的象征。

夜幕降临，云水谣安静下来。溪水依旧潺潺地流着，灯笼在古榕树下亮起，发出温暖的红光。我坐在溪边的石凳上，看着远处土楼的轮廓渐渐融入夜色，心中涌起一种说不清的感动。

在云水谣，我触摸到了时光的纹理，感受到了山水与人文的交融。那些盘根错节的古榕，那些静默伫立的土楼，那潺潺流淌的溪水，都在提醒着我：有些美好，值得慢慢品味。

第一学段（1-2年级）：从“想说”到“会写”¶

核心目标：培养写话兴趣，建立书写自信，实现从口头表达到书面表达的过渡。

写话类（看图写话、观察写话）¶

• 先说后写法：先让孩子把看到的内容说一遍，说通了再写。这样可以降低书写门槛，保证思路流畅。
• 五要素训练法：教孩子记住“时间、地点、谁、干什么、结果”，每次写话先在心里过一遍这五个问题，写出来的话就完整了。
• 提问拓展法：家长或老师用“什么样？”“怎么做的？”“心里怎么想？”来追问，帮孩子把一句话变成一段话。比如“小鸟在飞”——“什么样的小鸟？”“怎么飞的？”“飞到哪里去？”
• 词语积累本：准备一个本子，分类积累学到的好词（颜色词、形状词、动作词），写话时可以翻看使用。

想象写话类¶

• 绘本续编法：用绘本作为素材，读到关键处停下来，让孩子猜想接下来会发生什么，先说后写。
• 角色扮演法：让孩子扮演故事中的角色，说说自己的想法和感受，再写下来。

应用文类（留言条、请假条）¶

• 格式歌诀法：把格式编成顺口溜，如“称呼顶格写，正文空两格，署名在右下，日期最后写”。
• 情境真实法：在真实生活中创造写留言条的机会，如给家人留言、给老师写请假条，让写作有意义。

第二学段（3-4年级）：从“写清楚”到“写具体”¶

核心目标：学习有顺序地表达，掌握基本构段方式，能写内容具体的片段。

写人类¶

• 特征聚焦法：写人前先问“这个人最大的特点是什么？”，想清楚再动笔，围绕一个特点来写。
• 事例支撑法：用一两件小事来证明人物的特点，每件事说清起因、经过、结果。
• 对话插入法：在叙述中加入人物的语言，让人物“开口说话”，形象立刻鲜活起来。

记事类¶

• 顺序梳理法：动笔前用“首先……接着……然后……最后……”梳理事情经过，保证叙事有条理。
• 放大镜法：把事情最精彩的部分“放大”来写，多问自己“当时看到了什么？听到了什么？心里怎么想？”，把一瞬间写成一长段。
• 感受添加法：在事情的结尾或关键处，加入一句自己的感受或想法，让文章有“我”在里面。

写景类¶

• 定点观察法：站在一个地方，按从远到近、从左到右或从上到下的顺序观察，写景时不跳来跳去。
• 移步换景法：游览类文章用“走到哪里—看到什么—它什么样子”的结构，一个地方一个地方地写清楚。
• 五感调动法：写景物时依次想一想：看到了什么颜色形状？听到了什么声音？闻到了什么气味？摸上去什么感觉？这样景物就立体了。

状物类¶

• 外形分解法：写一个物体或动植物时，按照从头到尾、从整体到部分的顺序，一样一样写清楚。
• 习性/功能挖掘法：写动物加上生活习性，写物品加上用途和玩法，内容就丰富了。

想象类¶

• 假设提问法：“假如我是……”“如果……会怎样？”用假设句开启想象，沿着一个假设往下编故事。
• 童话公式法：写童话可以套用“主人公遇到困难—想办法解决—收获道理”的结构，既有情节又有意义。

应用文类（日记、书信、通知）¶

• 日记“三有”法：有日期、有天气、有正文。正文可以写“今天最开心/最难忘/最后悔的一件事”。
• 书信“五要素”法：称呼、正文、祝语、署名、日期，每样写对位置。

第三学段（5-6年级）：从“写具体”到“写生动”¶

核心目标：写出真情实感，运用描写技巧，尝试多种文体，形成初步的文体意识。

写人类¶

• 细节刻画法：不再满足于“她很温柔”，而要写出她温柔时的一个动作、一句话、一个眼神，让人物“活在纸上”。
• 侧面烘托法：不光直接写这个人，还可以写别人的反应、环境的氛围来烘托人物。
• 变化展示法：写人物前后的变化（如从胆小到勇敢），在变化中体现成长。

记事类¶

• 真情触发法：选择让自己真正动情的事来写，问自己“那一刻我心里最强烈的感受是什么？”，围绕这个感受来组织内容。
• 波折设置法：事情的发展可以有一波三折，写出曲折感。如“以为……没想到……结果……”
• 首尾呼应法：开头和结尾互相关联、互相呼应，文章显得完整而有设计感。

写景类¶

• 动态捕捉法：重点写景物的变化过程，如日出、下雨、风吹过树叶，把静止的画面写出动态感。
• 情景交融法：写景时把自己的心情放进去，开心时景是明媚的，忧伤时景是灰暗的，做到“景中有我”。
• 修辞润色法：有意识地运用比喻、拟人、排比等修辞手法，让语言有感染力。

状物与说明类¶

• 资料搜集法：写之前查阅相关资料，了解事物的数据、历史、类别等，让文章有知识含量。
• 方法运用法：有意识地使用列数字、打比方、作比较、分类别等说明方法。
• 顺序清晰法：根据说明对象选择合适的说明顺序（空间顺序、时间顺序、逻辑顺序），用“首先、其次、此外”等词标示层次。

想象类¶

• 世界构建法：想象未来世界或奇幻世界时，先设定这个世界的规则（科技水平、自然环境、社会形态），再在这个规则下写故事。
• 逻辑自洽法：想象作文也讲逻辑，前因后果要合理，不能天马行空到前后矛盾。

读后感类¶

• “引—议—联—结”法：引述原文要点、议论自己感受最深的一点、联系自己的生活经验、总结收获与启示。

应用文类（倡议书、策划书）¶

• 对象意识法：写之前想清楚“给谁看的？希望对方做什么？”，根据对象调整语气和用词。
• 格式规范法：严格按照各类应用文的格式要求书写，养成规范意识。

第四学段（7-9年级）：从“写生动”到“写好文”¶

核心目标：能够根据写作目的和读者对象选择适当的文体和表达方式，写出有思想、有条理、有文采的文章。

记叙文类（写人记事）¶

• 选材精当法：面对众多素材，只选最能突出中心的一两件事重点写，与中心关系不大的大胆舍弃。
• 详略得当法：列提纲时标注“详写”“略写”，确保重点部分浓墨重彩，次要部分一笔带过。
• 多种表达融合法：记叙文中巧妙融入描写、抒情、议论，让文章既有故事，又有画面，还有思考。
• 线索贯穿法：设置一条贯穿全文的线索（一个物品、一句话、一种情感变化），把零散的事件串成整体。

说明文类¶

• 特征聚焦法：动笔前反复问自己：“这件事物最本质的特点是什么？”全文围绕这个特点展开。
• 顺序优选法：根据说明对象选择合适的顺序——建筑物用空间顺序，制作过程用时间顺序，事理说明用逻辑顺序。
• 语言精准法：说明文的语言要准确、客观、平实，少用修饰词，多用数据、术语、判断句。

议论文类¶

• 观点先行法：开篇明确亮出自己的观点，一句话说清楚自己的立场。
• 论据积累法：平时分类积累名言警句、名人故事、社会现象、数据案例，建立自己的“论据库”。
• 论证展开法：学习常见的论证方法——举例论证、道理论证、对比论证、比喻论证，写论证段落时有意识地使用。
• 结构完整法：掌握“引论—本论—结论”的基本结构，本论部分分层展开，逻辑严密。

游记与写景类¶

• 双线交织法：游踪（行踪线索）和感悟（情感线索）双线并行，既写所见的景，也写心中的思。
• 独特感受法：不写千篇一律的“好美”，而是写出自己独特、真实的感受与思考，写出“独属于我的风景”。

读后感与评论类¶

• 一点深入法：不面面俱到，只抓住自己感受最深的一个点深入挖掘，联系实际展开论述。
• 有理有据法：评论文要有观点、有依据，引用原文要准确，分析要有条理。

创意表达与诗歌类¶

• 意象凝练法：用具体的意象表达抽象的情感，如用“雨”写愁绪，用“光”写希望。
• 语言锤炼法：反复推敲用词，力求每一个字都有表现力，删去可有可无的词语。

各年级通用学习方法¶

小学1-6年级课外阅读清单及必考知识点¶

依据统编版语文教材”快乐读书吧”栏目及《义务教育语文课程标准（2022年版）》整理，涵盖小学阶段全部推荐阅读书目与对应必考知识点。

一年级¶

上册：和大人一起读¶

下册：读读童谣和儿歌¶

必考知识点¶

• 儿歌与童谣：能背诵教材中出现的经典童谣，理解押韵和节奏
• 古诗启蒙：
• 《咏鹅》骆宾王——“白毛浮绿水，红掌拨清波”（咏物诗）
• 《静夜思》李白——思乡之情
• 《春晓》孟浩然——春天景色
• 《悯农》李绅——珍惜粮食
• 成语故事：画蛇添足、守株待兔——理解寓意
• 阅读方法：和大人一起读，指读法，图文对照

二年级¶

上册：读读童话故事¶

下册：读读儿童故事¶

必考知识点¶

• 童话与寓言区别：童话偏想象，寓言含道理
• 《安徒生童话》：丑小鸭（成长蜕变）、皇帝的新装（讽刺虚伪）、卖火柴的小女孩（社会批判）
• 《伊索寓言》：龟兔赛跑（坚持不懈）、狐狸和葡萄（自欺欺人）、农夫和蛇（善恶不分）
• 修辞手法初识：
• 比喻——“月亮像小船”
• 拟人——“小鸟在唱歌”
• 古诗：
• 《村居》高鼎——“草长莺飞二月天”
• 《咏柳》贺知章——“不知细叶谁裁出”
• 《登鹳雀楼》王之涣——“欲穷千里目，更上一层楼”
• 阅读方法：学会看目录，了解书的基本结构

三年级¶

上册：读读童话¶

下册：读读寓言故事¶

必考知识点¶

• 叶圣陶与《稻草人》：中国现代童话开创之作，了解稻草人的善良与无奈
• 安徒生：”世界童话之王”，丹麦人，代表作必知：丑小鸭、海的女儿、拇指姑娘
• 格林童话：德国民间文学，代表篇目——白雪公主、灰姑娘、小红帽、汉赛尔与格莱特
• 寓言三大来源对比：
• 中国古代寓言——历史故事化，含治国修身之理（如守株待兔、滥竽充数、南辕北辙）
• 伊索寓言——动物拟人化，简洁生动（如龟兔赛跑、狼和小羊）
• 克雷洛夫寓言——诗体寓言，讽刺社会现实（如《狐狸和葡萄》《天鹅、梭鱼和大虾》）
• 修辞进阶：掌握比喻、拟人、排比、夸张
• 古诗：
• 《望天门山》李白——“两岸青山相对出”
• 《饮湖上初晴后雨》苏轼——“欲把西湖比西子”
• 《望洞庭》刘禹锡——“潭面无风镜未磨”
• 阅读方法：学会做阅读批注，摘抄好词好句

四年级¶

上册：读读神话故事¶

下册：读读科普读物¶

必考知识点¶

• 中国神话必考：
• 盘古开天辟地——身体化为万物
• 女娲补天——五色石补天
• 后羿射日——射落九个太阳
• 精卫填海——坚持不懈精神
• 夸父逐日——追求光明
• 大禹治水——三过家门而不入
• 希腊神话必考：
• 宙斯——众神之王
• 普罗米修斯——盗火受罚，英雄形象
• 赫拉克勒斯——大力神，十二项功绩
• 科普读物阅读方法：了解说明文基本特点（说明对象、说明方法、说明顺序）
• 说明方法：列数字、举例子、作比较、打比方
• 古诗：
• 《题西林壁》苏轼——“不识庐山真面目，只缘身在此山中”（哲理诗）
• 《暮江吟》白居易——“一道残阳铺水中”
• 《雪梅》卢梅坡——“梅须逊雪三分白，雪却输梅一段香”
• 阅读方法：学会提问，带着问题阅读科普类文本

五年级¶

上册：读读民间故事¶

下册：读读古典名著¶

必考知识点¶

民间故事¶

• 中国民间故事必考：
• 牛郎织女——七夕节来历
• 孟姜女哭长城——控诉暴政
• 梁山伯与祝英台——爱情悲剧
• 白蛇传——人妖之恋
• 民间故事特点：口耳相传、反映劳动人民愿望、善有善报

四大名著核心考点¶

《西游记》：
- 作者：吴承恩，明代
- 体裁：长篇神话小说
- 主角：孙悟空（机智勇敢、嫉恶如仇）、猪八戒（憨态可掬、好吃懒做）、沙僧（忠诚老实）、唐僧（慈悲为怀但有时不辨真假）
- 必考情节：大闹天宫、三打白骨精、三借芭蕉扇、真假美猴王、女儿国遇难、车迟国斗法
- 孙悟空名号变化：石猴→美猴王→弼马温→齐天大圣→孙行者→斗战胜佛

《三国演义》：
- 作者：罗贯中，元末明初
- 体裁：长篇历史演义小说
- 必考情节：桃园三结义、草船借箭、火烧赤壁、空城计、温酒斩华雄、三顾茅庐
- 核心人物：诸葛亮（神机妙算）、曹操（奸雄）、刘备（仁义）、关羽（忠义）、张飞（勇猛）
- 经典歇后语：周瑜打黄盖——一个愿打一个愿挨；司马昭之心——路人皆知

《水浒传》：
- 作者：施耐庵，元末明初
- 体裁：长篇章回体小说，中国第一部白话长篇小说
- 内容：描写北宋末年以宋江为首的108将梁山聚义
- 必考情节：武松打虎、鲁智深倒拔垂杨柳、林冲雪夜上梁山、智取生辰纲
- 人物绰号：及时雨宋江、豹子头林冲、花和尚鲁智深、行者武松、黑旋风李逵

《红楼梦》：
- 作者：曹雪芹，清代
- 体裁：长篇章回体小说，中国古典小说巅峰
- 核心情节：贾宝玉与林黛玉的爱情悲剧、四大家族兴衰
- 主要人物：贾宝玉（叛逆）、林黛玉（多愁善感）、薛宝钗（端庄大方）、王熙凤（精明泼辣）
- 必考知识：金陵十二钗、”贾史王薛”四大家族

• 古诗：
• 《示儿》陆游——“王师北定中原日，家祭无忘告乃翁”
• 《题临安邸》林升——“暖风熏得游人醉，直把杭州作汴州”
• 《己亥杂诗》龚自珍——“落红不是无情物，化作春泥更护花”
• 阅读方法：学会略读与精读结合，做读书笔记

六年级¶

上册：读读成长故事¶

下册：读读世界名著¶

必考知识点¶

成长故事类¶

《童年》：
- 作者：高尔基，苏联
- 体裁：自传体三部曲之一（另两部《在人间》《我的大学》）
- 主人公：阿廖沙（高尔基乳名）
- 核心人物：外祖母（慈爱善良）、外祖父（吝啬暴躁）
- 主题：在苦难中成长，黑暗中的人性之光

《爱的教育》：
- 作者：亚米契斯，意大利
- 体裁：日记体儿童小说
- 主人公：安利柯
- 主题：爱——祖国之爱、亲子之爱、师生之爱、朋友之爱

《小英雄雨来》：
- 作者：管桦
- 内容：抗日战争时期少年雨来与敌人斗争
- 主题：爱国与勇敢

世界名著类¶

《鲁滨逊漂流记》：
- 作者：丹尼尔·笛福，英国，”英国小说之父”
- 体裁：长篇冒险小说
- 核心情节：流落荒岛28年，靠智慧和毅力生存
- 主题：人与自然的抗争、自强不息的奋斗精神
- 必考：鲁滨逊在岛上养羊、种麦、建住所、救”星期五”

《汤姆·索亚历险记》：
- 作者：马克·吐温，美国
- 主人公：汤姆·索亚——聪明、调皮、勇敢、正义感
- 必考情节：山洞历险、墓地目击凶案、海盗冒险
- 主题：童年成长、正义与勇气

《骑鹅旅行记》：
- 作者：塞尔玛·拉格洛芙，瑞典，首位女性诺贝尔文学奖获得者
- 主人公：尼尔斯——从调皮捣蛋到勇敢善良的蜕变
- 主题：人与自然的和谐、成长与责任

《爱丽丝漫游奇境》：
- 作者：刘易斯·卡罗尔，英国
- 体裁：荒诞童话
- 必考情节：掉进兔子洞、疯茶会、红心王后的槌球场
- 主题：想象力的自由、逻辑与荒诞

• 古诗：
• 《石灰吟》于谦——“粉骨碎身浑不怕，要留清白在人间”
• 《竹石》郑燮——“咬定青山不放松，立根原在破岩中”
• 《马诗》李贺——“何当金络脑，快走踏清秋”
• 阅读方法：学会比较阅读，整本书阅读策略，做思维导图梳理人物关系

小学阶段通用文学常识必考汇总¶

一、中国古代文学常识¶

二、文学体裁常识¶

三、常见修辞手法¶

四、小学必背古诗词分类速查¶

阅读方法与能力进阶¶

说明：本文依据统编版小学语文教材”快乐读书吧”栏目及《义务教育语文课程标准（2022年版）》整理，书目以教材指定为必读，知识点覆盖常见考试考点。建议配合各年级教材同步阅读，每本书读后做知识梳理和人物关系图，效果更佳。

AI生成

初中九年级语文阅读要求及阅读能力提升技巧¶

引言¶

九年级是初中语文学习的收官之年，也是中考备考的关键冲刺期。本年度的阅读学习，既是对前两年所学阅读方法与技能的综合运用与深化，更是全面对标中考要求、实现阅读能力质的飞跃的重要阶段。

部编版九年级教材在文体覆盖上更为全面，上册涵盖诗歌、议论文、古文、小说等多种文体，下册进一步引入戏剧阅读和非连续性文本阅读，形成了从”学会阅读”到”运用阅读”的能力进阶路径。九年级阅读的核心目标可概括为：

1. 文体贯通：系统掌握诗歌、小说、散文、议论文、文言文、古诗词、戏剧、非连续性文本等各类文体的阅读方法与答题策略。
2. 方法迁移：将精读所学方法自觉迁移至略读和自读中，实现从”教读”到”自读”的真正独立。
3. 中考实战：全面对标中考阅读考查要求，熟练掌握各类考点与答题模板，做到规范、高效、不失分。
4. 素养提升：在应试能力提升的同时，深化对语言文字的感悟力、思辨力和审美力，为高中语文学习奠定坚实基础。

上册部分¶

第一单元 诗歌——吟诵与感悟¶

本单元课文篇目¶

阅读目标与要求¶

1. 感受诗歌的韵律之美，掌握诗歌朗诵的基本技巧，做到节奏分明、感情充沛。
2. 体会诗歌创设的意境，理解诗人通过意象传达的思想感情。
3. 学习从意象、语言、手法、情感四个维度赏析诗歌。
4. 了解现代自由诗与古体词的不同艺术特征。
5. 积累经典诗歌名句，丰富语言储备。

精读/略读/自读要求¶

精读要求（《沁园春·雪》《我爱这土地》《乡愁》）：
- 逐句品读，标注意象与关键词，分析意象的象征意义和情感内涵。
- 体会诗歌语言的音乐性，分析节奏、押韵和反复等手法的作用。
- 结合写作背景，深入理解诗人的情感表达。
- 练习有感情地朗读，注意语气、语调、停顿的处理。

自读要求（《你是人间的四月天》《我看》）：
- 运用精读所学方法，独立分析意象和情感。
- 比较两首诗在意象选择和情感表达上的异同。
- 尝试撰写简短的诗歌赏析笔记。

阅读重点技能¶

• 意象分析法：识别核心意象→分析意象特征→理解象征含义→把握情感指向。
• 朗诵技巧：划分节奏→确定重音→把握语调→控制速度→表达感情。
• 比较阅读法：从题材、意象、手法、情感等维度进行诗歌间的横向比较。

第二单元 议论文——观点与逻辑¶

本单元课文篇目¶

阅读目标与要求¶

1. 明确议论文的基本要素：论点、论据、论证，掌握其相互关系。
2. 学习梳理议论文的论证思路，分析文章的逻辑结构。
3. 辨别举例论证、道理论证、对比论证、比喻论证等常见论证方法，理解其作用。
4. 体会议论文语言的严密性和逻辑性。
5. 培养批判性思维，能对观点和论证进行独立评价。

精读/略读/自读要求¶

精读要求（《敬业与乐业》《就英法联军远征中国致巴特勒上尉的信》）：
- 准确找出中心论点和分论点，分析论点之间的关系。
- 逐一标注论据，判断论据类型（事实论据/道理论据），分析论据对论点的支撑作用。
- 逐段概括论证方法，分析每种论证方法的具体作用。
- 绘制论证思路图，把握全文逻辑脉络。
- 品味关键语句，体会议论文语言的准确性和严密性。

自读要求（《论教养》《精神的三间小屋》）：
- 独立找出论点，梳理论证思路。
- 比较两篇文章在论证方式上的异同（立论与比喻说理）。
- 思考文章观点的现实意义，形成自己的独立看法。

阅读重点技能¶

• 论点定位法：看标题→看开头→看结尾→看过渡句→归纳全文。
• 论据分析法：识别类型→判断真实性→分析与论点的关系→评价论据效力。
• 论证思路梳理法：逐段概括→划分层次→理清逻辑关系→绘制结构图。
• 语言品析法：关注限定词、关联词、语气词，分析语言的准确性和严密性。

第三单元 古文——山水抒怀¶

本单元课文篇目¶

阅读目标与要求¶

1. 积累文言重点实词、虚词，掌握一词多义、古今异义、词类活用等文言现象。
2. 理解文言特殊句式（判断句、省略句、倒装句、被动句），能准确翻译重点语句。
3. 把握文章的思想内涵，体会作者寄情山水背后的政治抱负和人生感悟。
4. 学习骈散结合、对偶工整等古文语言特色。
5. 背诵并默写全篇及诗歌，理解名句的深刻含义。

精读/略读/自读要求¶

精读要求（《岳阳楼记》《醉翁亭记》）：
- 逐字逐句翻译，标注重点实词、虚词用法。
- 分析文章结构，理解”先天下之忧而忧，后天下之乐而乐”的政治抱负和”与民同乐”的思想内涵。
- 赏析对偶、排比等修辞手法和骈散结合的语言特色。
- 比较两文在写景和抒情方式上的异同。
- 熟读成诵，准确默写。

自读要求（《湖心亭看雪》）：
- 独立翻译全文，关注”强饮”“痴”等关键词。
- 体会白描手法和”痴”的深层含义。
- 感受作者故国之思和清高自赏的情感。

诵读要求（三首诗词）：
- 了解写作背景，理解诗词主旨。
- 背诵默写，准确理解名句内涵。
- 体会诗人面对人生困境时的不同人生态度。

阅读重点技能¶

• 文言翻译五字法：留（保留）→删（删除）→补（补充）→换（替换）→调（调整）。
• 文意把握法：疏通文字→理解层意→把握主旨→联系背景深入体会。
• 古文结构分析法：找出过渡句→划分层次→概括层意→理清脉络。
• 名句理解法：理解字面义→把握深层义→联系背景→体会情感。

第四单元 小说——社会人生¶

本单元课文篇目¶

阅读目标与要求¶

1. 掌握小说阅读的基本方法：分析人物形象、梳理故事情节、理解环境描写、把握主题思想。
2. 学习从细节描写（动作、语言、神态、心理）入手分析人物性格和内心世界。
3. 理解环境描写对烘托人物、推动情节、深化主题的作用。
4. 体会小说中的对比手法和象征手法。
5. 培养对小说主题的多角度理解能力，能联系时代背景深入解读。

精读/略读/自读要求¶

精读要求（《故乡》《我的叔叔于勒》）：
- 梳理故事情节，绘制情节结构图（开端—发展—高潮—结局）。
- 找出所有人物描写（外貌、语言、动作、心理、神态），逐一分析人物形象特征。
- 标注环境描写片段，分析其烘托人物、暗示主题的作用。
- 重点分析对比手法：闰土的前后变化、菲利普夫妇对于勒态度的变化等。
- 联系时代背景，深入理解小说主题的深刻内涵。

自读要求（《孤独之旅》）：
- 独立分析杜小康这一人物形象及其成长历程。
- 体会环境描写在表现人物心理变化中的重要作用。
- 思考”孤独”的深层含义和成长的代价。

阅读重点技能¶

• 人物形象分析法：找描写→析手法→概括特征→理解意义→把握典型性。
• 环境描写作用分析法：交代背景→渲染氛围→烘托心情→推动情节→暗示主题。
• 对比分析法：找出对比→分析差异→理解用意→深化主题认识。
• 主题多元解读法：关注标题→关注结尾→关注反复出现的意象→联系时代背景→多角度归纳。

第五单元 议论文——思辨与创造¶

本单元课文篇目¶

阅读目标与要求¶

1. 学习驳论文的阅读方法，掌握”先破后立”的论证思路。
2. 辨析立论与驳论的区别，理解驳论文中”敌论—驳斥—立论”的结构模式。
3. 培养质疑精神，学会对论点、论据、论证进行批判性审视。
4. 理解创造性思维的内涵，培养创新意识。
5. 体会议论文中丰富多样的说理方式。

精读/略读/自读要求¶

精读要求（《中国人失掉自信力了吗》《怀疑与学问》）：
- 分析驳论文的结构：找准敌论→分析驳斥方式→理解作者立论。
- 体会鲁迅杂文的语言风格：犀利、幽默、讽刺。
- 理解”怀疑”在治学中的重要性，梳理论证链条。
- 辨别直接驳斥和间接驳斥的不同方式。
- 学习抓住关键词句分析论证逻辑的方法。

自读要求（《谈创造性思维》《创造宣言》）：
- 独立梳理论证思路，概括主要观点。
- 分析文章所用的论证方法及其作用。
- 思考创造性思维对个人成长的意义。

阅读重点技能¶

• 驳论文阅读法：识别敌论→分析驳论方式（驳论点/驳论据/驳论证）→理解作者立论→评价论证效力。
• 批判性阅读法：审视论据是否充分→检验论证是否严密→评估结论是否可靠→提出自己的见解。
• 论证语言分析法：关注反语、讽刺、设问、反问等语言手法的表达效果。

第六单元 古典小说——英雄与世态¶

本单元课文篇目¶

阅读目标与要求¶

1. 了解中国古典四大名著的基本概况，培养阅读整本书的兴趣。
2. 学习古典小说中通过言行描写塑造人物的方法。
3. 体会古典小说的叙事技巧：线索设置、情节波澜、伏笔照应等。
4. 理解古典小说反映的社会现实和文化内涵。
5. 比较不同古典小说在语言风格和人物塑造上的特色。

精读/略读/自读要求¶

精读要求（《智取生辰纲》《范进中举》）：
- 分析人物群像：吴用等人的智谋、杨志的精明与失算；范进的疯癫、众人的丑态。
- 理解叙事技巧：明暗双线、层层铺垫、跌宕起伏。
- 体会讽刺手法在《范进中举》中的运用，分析讽刺对象和讽刺效果。
- 联系原著，了解节选在全书中的地位和作用。
- 朗读精彩片段，感受古典白话小说的语言魅力。

自读要求（《三顾茅庐》《刘姥姥进大观园》）：
- 分析刘备求贤若渴的形象和刘姥姥的喜剧形象。
- 体会正面描写与侧面烘托相结合的手法。
- 感受《红楼梦》语言的细腻和精致。
- 激发阅读整本原著的兴趣。

诵读要求（诗词曲五首）：
- 背诵默写，理解各首诗词的主旨和情感。
- 体会不同体裁（诗、词、曲）的艺术特色。

阅读重点技能¶

• 古典小说人物分析法：言行描写入手→分析性格特征→理解社会意义→把握典型性。
• 叙事技巧分析法：线索梳理→伏笔照应→情节波澜→叙事节奏→叙事视角。
• 讽刺手法识别法：夸张→对比→反语→白描→理解讽刺对象和效果。
• 名著节选阅读法：了解原著背景→精读节选内容→联系全书理解→回归整本阅读。

九年级上册阅读能力提升技巧¶

一、议论文阅读技巧深度¶

（一）论点的寻找与概括¶

寻找论点的方法：
1. 看标题：标题本身就是论点的，如《敬业与乐业》。
2. 看开头：论点常出现在第一段或第二段末尾。
3. 看结尾：归纳式论点常出现在结尾段。
4. 看过渡段：承上启下的过渡句往往包含分论点。
5. 自行概括：当论点不明确时，需综合各段内容归纳。

概括论点的原则：
- 必须是完整的陈述句，不能用疑问句或短语。
- 必须明确表明作者的态度和观点。
- 不能过大（超出文章范围）或过小（只涵盖部分内容）。

（二）论据的类型与作用分析¶

论据类型：

分析论据作用的答题模式：

使用了_（事实/道理）论据，具体论证了（分论点），进而支撑了_（中心论点），使论证更加（具体/有力/权威）。

（三）论证方法的辨识与分析¶

四种常见论证方法及其作用：

答题模板：

运用了_论证方法，（具体分析如何论证），论证了_（论点），使论证（效果）。

（四）论证思路的梳理¶

梳理步骤：
1. 逐段概括段意（或层意）。
2. 划分逻辑层次：引论（提出问题）→本论（分析问题）→结论（解决问题）。
3. 标注各层之间的逻辑关系（并列、递进、对比、总分）。
4. 用”首先—其次—然后—最后”等词语连贯表述。

答题模板：

首先提出_的论点（或引出_的论题），然后运用_论证方法，从_角度论证了_，最后得出_的结论。

驳论文论证思路：

首先摆出敌论_，然后从_（论点/论据/论证）方面进行驳斥，最后树立自己的观点____。

二、文学作品阅读综合技巧¶

（一）小说阅读方法¶

1. 人物形象分析四步法
- 第一步：找出所有描写（外貌、语言、动作、心理、神态）。
- 第二步：分析描写手法（直接描写/间接描写/对比衬托）。
- 第三步：概括性格特征（用四字短语或短语概括）。
- 第四步：理解人物的典型意义和社会意义。

答题模板：

_是一个的人物形象。从文中”_”（具体描写）可以看出他/她_的性格特点。这一形象具有_的典型意义，反映了。

2. 情节分析技巧
- 梳理情节结构：开端→发展→高潮→结局。
- 分析情节安排技巧：悬念、伏笔、照应、巧合、突转。
- 理解情节对表现人物和主题的作用。

3. 环境描写作用分析

4. 小说主题的归纳方法
- 从人物命运看主题。
- 从情节发展看主题。
- 从环境描写看主题。
- 从关键语句（议论、抒情句）看主题。
- 联系作者和时代背景理解主题。

（二）散文阅读方法¶

1. 散文类型与阅读重点

2. 散文形散神聚的理解
- “形散”：取材广泛、手法多样、结构灵活。
- “神聚”：主题统一、情感统一、线索统一。
- 找”神”的方法：抓住文眼（中心句、抒情议论句）。

3. 散文语言赏析
- 词语赏析：换词比较法、语境分析法。
- 句子赏析：修辞手法+表达效果+情感内涵。
- 表达方式分析：叙述、描写、议论、抒情、说明的综合运用。

三、文言文阅读综合技巧¶

（一）文言实词积累法¶

1. 一词多义归纳法

以”之”为例：
| 用法 | 释义 | 例句 |
|------|------|------|
| 结构助词 | 的 | 予独爱莲之出淤泥而不染 |
| 代词 | 他/她/它/这 | 属予作文以记之 |
| 动词 | 往、到 | 辍耕之垄上 |
| 助词 | 主谓之间取消独立性 | 予独爱莲之出淤泥而不染 |
| 音节助词 | 无实义 | 怅恨久之 |

2. 古今异义辨析法

3. 词类活用识别法
- 名词用作动词
- 形容词用作动词
- 动词用作名词
- 使动用法
- 意动用法

（二）文言特殊句式¶

（三）文意把握方法¶

1. 借助注释通大意：先不看翻译，借助课下注释疏通大意。
2. 抓住关键词：关注核心实词和起关联作用的虚词。
3. 理清结构：划分层次，把握文章脉络。
4. 联系背景：了解写作背景和作者情况，深入理解文意。
5. 归纳主旨：用简洁语言概括文章中心。

（四）文言翻译五字法¶

• 留：保留人名、地名、官名、年号等专有名词。
• 删：删除无实在意义的虚词（发语词、语气词等）。
• 补：补出省略成分（主语、谓语、宾语等）。
• 换：将古词替换为现代词（”曰”→”说”，”走”→”跑”）。
• 调：调整特殊语序为正常语序。

四、古诗词鉴赏综合技巧¶

（一）炼字赏析¶

赏析角度：
1. 词语的含义（本义+语境义）。
2. 手法技巧（修辞、动静、感官等）。
3. 意境创设（描绘了怎样的画面）。
4. 情感表达（表达了怎样的情感）。

答题模板：

“_”字好在：该字原意为_，在句中的意思是_，运用了_手法，生动形象地写出了_（景物特点/人物情态），表达了_的情感，使诗句更具____的效果。

常见炼字类型：
- 动词：使画面灵动。
- 形容词：突出特征。
- 叠词：增强韵律、强调程度。
- 数量词：渲染氛围、营造意境。

（二）情感把握¶

常见情感类型：
| 类型 | 典型表现 |
|------|----------|
| 忧国忧民 | 关心国家命运，同情人民疾苦 |
| 壮志难酬 | 怀才不遇，报国无门 |
| 思乡怀人 | 羁旅之思，亲友之念 |
| 离愁别绪 | 送别之伤，离别之苦 |
| 归隐田园 | 厌倦官场，向往自然 |
| 伤春悲秋 | 感叹时光，嗟叹身世 |

把握方法：
1. 看标题（往往暗示情感）。
2. 看意象（特定意象传递特定情感）。
3. 看关键词（直接抒情的词句）。
4. 看作者（了解作者经历和风格）。
5. 看注释（背景信息提示情感）。

（三）手法分析¶

常见表现手法：

常见修辞手法：
比喻、拟人、对偶、夸张、设问、反问、反复、互文等。

答题模板：

运用了_手法/修辞，_（具体分析），表达了_的情感/达到了_的效果。