Cormen 等《Introduction to Algorithms》 · 第 6 部分

元信息：Cormen, Leiserson, Rivest, Stein《Introduction to Algorithms》（第 3 版）｜作者：T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein｜本笔记负责 PDF 第 1094–1313 页（原书页码 p.1073 起，PDF 页码 = 原书页码 + 21）。覆盖：第 34 章 NP 完全性后半（34.3 末尾起）、第 35 章近似算法、第 VIII 部分附录 A–D（求和、集合等、计数与概率、矩阵）、参考文献、索引。

第 34 章 NP 完全性（NP-Completeness）（接上一块）

34.3 NP 完全性与可归约性（续）：电路可满足性是 NP 完全的（PDF p.1094–1099）

（接上一块）前文已定义布尔组合电路（boolean combinational circuit）、电路可满足性问题 CIRCUIT-SAT、多项式时间归约 $L_1 \le_P L_2$、NP-hard 与 NP-complete（NPC）。本块从“CIRCUIT-SAT 的朴素算法”结尾开始：对 $k$ 个输入的电路 $C$，枚举 $2^k$ 种赋值，每种检查要多项式时间，所以总时间 $\Omega(2^k)$，对电路规模是超多项式的。脚注 9 提醒：若电路规模本身是 $\Theta(2^k)$，那么 $O(2^k)$ 的算法关于输入规模就是多项式的；即使 P ≠ NP，这也不矛盾——特例存在多项式算法不意味着一般情形存在。

引理 34.5：CIRCUIT-SAT ∈ NP。证明：构造两输入验证算法 $A(x, y)$，$x$ 为电路 $C$ 的标准编码，证书（certificate）$y$ 为电路中每条导线的布尔取值。$A$ 对每个逻辑门检查其输出导线值是否等于其输入导线值经门函数计算的结果，再检查整个电路输出是否为 1。可满足电路必存在多项式长度证书使 $A$ 输出 1；不可满足电路无论给什么证书都不会被“骗过”。良好实现下线性时间即可。（习题 34.3-4 指出也可只用输入赋值作证书。）

引理 34.6：CIRCUIT-SAT 是 NP-hard 的。（证明是“草图”，依赖对计算机硬件的理解。）

背景概念：程序以指令序列存在内存中；程序计数器（program counter, PC）指示下一条指令；任一时刻内存（含程序本身、PC、工作存储、各种簿记状态位）的整体状态称为一个格局（configuration）。执行一条指令就是把一个格局映射到下一个格局，实现这一映射的硬件可以视为一个布尔组合电路 $M$。
设 $L \in NP$，存在多项式时间验证算法 $A$；设 $T(n)=O(n^k)$ 为 $A$ 在长度 $n$ 输入上的最坏运行时间，且证书长度也是 $O(n^k)$（$k\ge1$ 为常数）。
把 $A$ 的计算表示为格局序列 $c_0, c_1, \dots, c_{T(n)}$（图 34.9）：每个格局包含程序 $A$、PC 与辅助机器状态、输入 $x$、证书 $y$、工作存储；$M$ 把 $c_i$ 映射为 $c_{i+1}$。$A$ 结束时把输出位 0/1 写到指定位置，此后不再改变，所以输出是 $c_{T(n)}$ 中的某一位。
归约算法 $F$：给定 $x$，计算 $n=|x|$，把 $T(n)$ 个 $M$ 串接成电路 $C'$（第 $i$ 个副本的输出直接接到第 $i+1$ 个副本的输入，格局不存在内存里而是“活在导线上”）。然后把 $C'$ 中对应程序 $A$、初始 PC、输入 $x$、初始内存的输入端直接接成已知常数，只剩证书 $y$ 对应的输入端是自由的；输出端只保留 $c_{T(n)}$ 中对应 $A$ 输出的那一位。于是得到电路 $C=f(x)$，对任意长度 $O(n^k)$ 的 $y$ 有 $C(y)=A(x,y)$。
正确性：若存在证书 $y$ 使 $A(x,y)=1$，把 $y$ 输入 $C$ 得 $C(y)=1$，$C$ 可满足；反之若 $C$ 可满足，存在 $y$ 使 $C(y)=1$，即 $A(x,y)=1$。
多项式时间：格局位数是 $n$ 的多项式（程序常数大小，输入 $n$，证书 $O(n^k)$，运行至多 $O(n^k)$ 步故工作存储也是多项式）；$M$ 的规模是格局长度的多项式（主要是内存系统逻辑）；$C$ 至多 $O(n^k)$ 个 $M$ 副本，故规模为多项式，构造也是多项式时间。（此处假设工作存储连续，习题 34.3-5 要求去掉这一假设。）

定理 34.7：CIRCUIT-SAT 是 NP 完全的。由引理 34.5、34.6 和 NPC 定义直接得出。

习题 34.3 概览：34.3-1 验证图 34.8(b) 电路不可满足；34.3-2 证明 $\le_P$ 具有传递性；34.3-3 证明 $L\le_P \bar L$ 当且仅当 $\bar L \le_P L$；34.3-4 用输入赋值作证书重新证明引理 34.5，比较哪个更简单；34.3-5 工作存储连续假设用在何处、为何不失一般性；34.3-6 定义“对类 $\mathcal C$ 完全”，证明 $\emptyset$ 与 $\{0,1\}^*$ 是 P 中仅有的不是 P-完全的语言；34.3-7 $L$ 对 NP 完全当且仅当 $\bar L$ 对 co-NP 完全；34.3-8 Sartre 教授质疑 $F$ 只知道 $A$、$k$ 存在而不知其值——指出其推理漏洞（归约只需存在性，$F$ 本身随 $L$ 而定）。

34.4 NP 完全性证明（NP-completeness proofs）（PDF p.1099–1107）

引理 34.8：若存在 $L' \in NPC$ 使 $L' \le_P L$，则 $L$ 是 NP-hard；若再有 $L\in NP$，则 $L \in NPC$。证明：对任意 $L''\in NP$ 有 $L''\le_P L'$，由传递性 $L''\le_P L$。

证明一个语言 $L$ 是 NP 完全的标准五步法：

证明 $L\in NP$；
选一个已知 NP 完全语言 $L'$；
给出计算函数 $f$ 的算法，把 $L'$ 的每个实例 $x\in\{0,1\}^*$ 映射为 $L$ 的实例 $f(x)$；
证明对所有 $x$：$x\in L' \iff f(x)\in L$；
证明计算 $f$ 的算法是多项式时间。（第 2–5 步证明 NP-hard。）CIRCUIT-SAT ∈ NPC 是“敲门砖（foot in the door）”，此后已知 NPC 问题目录越大，可选的归约源越多。常见误区：归约方向必须是“从已知难题归约到新问题”，反过来不能证明新问题难。

公式可满足性 SAT

SAT 实例：布尔公式 $\phi$，由 $n$ 个布尔变量 $x_1,\dots,x_n$、$m$ 个布尔联结词（任何一元或二元布尔函数，如 ∧ AND、∨ OR、¬ NOT、→ 蕴含、↔ 等价）及括号组成（假设无冗余括号，每个联结词至多一对括号）。编码长度是 $n+m$ 的多项式。
真值赋值（truth assignment）、满足赋值（satisfying assignment）、可满足公式（satisfiable formula）定义同电路。$\text{SAT}=\{\langle\phi\rangle : \phi \text{ 是可满足的布尔公式}\}$。
例：$\phi=((x_1\to x_2)\vee\neg((\neg x_1\leftrightarrow x_3)\vee x_4))\wedge\neg x_2$，赋值 $\langle x_1=0,x_2=0,x_3=1,x_4=1\rangle$ 使 $\phi=((0\to0)\vee\neg((\neg0\leftrightarrow1)\vee1))\wedge\neg0=(1\vee\neg(1\vee1))\wedge1=(1\vee0)\wedge1=1. \quad (34.2)$
朴素算法枚举 $2^n$ 个赋值，$\Omega(2^n)$ 时间，关于 $|\langle\phi\rangle|$ 超多项式。SAT 有“史上第一个被证明 NP 完全的问题”这一历史地位。

定理 34.9：SAT 是 NP 完全的。

SAT ∈ NP：证书为满足赋值，代入求值即可多项式时间验证。
CIRCUIT-SAT $\le_P$ SAT：朴素做法是从输出门开始递归把每个门的输入展开成公式；但扇出（fan-out）≥2 的门会使共享子公式被反复复制，公式规模可能指数增长（习题 34.4-1）。正确做法（图 34.10）：给电路每条导线 $x_i$ 一个变量，每个门写成一个小公式（称为子句 clause），如输出 AND 门写成 $x_{10}\leftrightarrow(x_7\wedge x_8\wedge x_9)$。最终公式是电路输出变量与所有门子句的合取： $\phi = x_{10}\wedge(x_4\leftrightarrow\neg x_3)\wedge(x_5\leftrightarrow(x_1\vee x_2))\wedge(x_6\leftrightarrow\neg x_4)\wedge(x_7\leftrightarrow(x_1\wedge x_2\wedge x_4))\wedge(x_8\leftrightarrow(x_5\vee x_6))\wedge(x_9\leftrightarrow(x_6\vee x_7))\wedge(x_{10}\leftrightarrow(x_7\wedge x_8\wedge x_9)).$ 构造显然多项式时间。电路可满足 ⇒ 各导线取值良定且输出为 1，代入后每个子句为 1；反之亦然。

3-CNF 可满足性 3-CNF-SAT

定义：文字（literal）是变量或其否定的一次出现；合取范式（conjunctive normal form, CNF）是若干子句的 AND，每个子句是一个或多个文字的 OR；3-CNF 要求每个子句恰好 3 个不同文字。例：$(x_1\vee\neg x_1\vee\neg x_2)\wedge(x_3\vee x_2\vee x_4)\wedge(\neg x_1\vee\neg x_3\vee\neg x_4)$。
动机：从受限语言出发归约，需要考虑的情形少；但不能限制得太狠以致变成多项式可解（如 2-CNF-SAT ∈ P，见习题 34.4-7；DNF 可满足性 ∈ P，见习题 34.4-5）。

定理 34.10：3-CNF-SAT 是 NP 完全的。证明 SAT $\le_P$ 3-CNF-SAT，分三步：

建二叉语法树（parse tree）：叶为文字，内部结点为联结词；多元 OR 用结合律完全加括号，使每个内部结点 1 或 2 个孩子（图 34.11）。为每个内部结点的输出引入新变量 $y_i$，把公式改写为“根变量 ∧ 各结点子句”。对式 (34.3) 得 $\phi'=y_1\wedge(y_1\leftrightarrow(y_2\wedge\neg x_2))\wedge(y_2\leftrightarrow(y_3\vee y_4))\wedge(y_3\leftrightarrow(x_1\to x_2))\wedge(y_4\leftrightarrow\neg y_5)\wedge(y_5\leftrightarrow(y_6\vee x_4))\wedge(y_6\leftrightarrow(\neg x_1\leftrightarrow x_3)).$ 每个子句 $\phi'_i$ 至多 3 个文字，但还不是 OR 形式。
每个子句转 CNF：对 $\phi'_i$ 列真值表（至多 $2^3=8$ 行）；用取值为 0 的行写出等价于 $\neg\phi'_i$ 的析取范式（disjunctive normal form, DNF，OR of ANDs）；再取否定并用 De Morgan 律 $\neg(a\wedge b)=\neg a\vee\neg b$、$\neg(a\vee b)=\neg a\wedge\neg b$ 得到 CNF $\phi''_i$。例：$\phi'_1=(y_1\leftrightarrow(y_2\wedge\neg x_2))$ 的真值表（图 34.12）中值为 0 的行给出 $\neg\phi'_1 \equiv (y_1\wedge y_2\wedge x_2)\vee(y_1\wedge\neg y_2\wedge x_2)\vee(y_1\wedge\neg y_2\wedge\neg x_2)\vee(\neg y_1\wedge y_2\wedge\neg x_2),$ $\phi''_1=(\neg y_1\vee\neg y_2\vee\neg x_2)\wedge(\neg y_1\vee y_2\vee\neg x_2)\wedge(\neg y_1\vee y_2\vee x_2)\wedge(y_1\vee\neg y_2\vee x_2).$
补足到恰好 3 个文字：引入两个辅助变量 $p,q$。对 $\phi''$ 的每个子句 $C_i$：3 个不同文字则原样保留；2 个文字 $(l_1\vee l_2)$ 换成 $(l_1\vee l_2\vee p)\wedge(l_1\vee l_2\vee\neg p)$；1 个文字 $l$ 换成 $(l\vee p\vee q)\wedge(l\vee p\vee\neg q)\wedge(l\vee\neg p\vee q)\wedge(l\vee\neg p\vee\neg q)$。无论 $p,q$ 取何值，恰有一个子句等价于原子句，其余为 1（AND 的单位元）。

正确性：第 1 步保持可满足性；第 2 步代数等价；第 3 步对任意 $p,q$ 取值都与 $\phi''$ 代数等价。
规模：第 1 步每个联结词至多加 1 个变量和 1 个子句；第 2 步每个子句至多产生 8 个子句；第 3 步每个子句至多变 4 个。总规模关于原公式长度是多项式。

习题 34.4 概览：34.4-1 构造规模 $n$ 的电路使朴素转换得到指数规模公式；34.4-2 对式 (34.3) 写出完整 3-CNF；34.4-3 Jagger 教授只用整式真值表法——说明真值表有 $2^n$ 行，不是多项式归约；34.4-4 重言式（tautology）判定是 co-NP 完全的；34.4-5 DNF 可满足性多项式可解（只需某一合取项不含互补文字）；34.4-6 用 SAT 判定黑盒在多项式时间内构造满足赋值（逐个变量固定取值的自归约 self-reduction）；34.4-7 2-CNF-SAT ∈ P：把 $x\vee y$ 视为 $\neg x\to y$ 与 $\neg y\to x$ 建蕴含有向图，用强连通分量判定（$x$ 与 $\neg x$ 在同一 SCC 则不可满足），线性时间。

34.5 NP 完全问题（NP-complete problems）（PDF p.1107–1122）

NP 完全问题遍布布尔逻辑、图、算术、网络设计、集合与划分、存储与检索、排序与调度、数学规划、代数与数论、博弈与谜题、自动机与语言、程序优化、生物、化学、物理等领域。本节的归约结构（图 34.13）： CIRCUIT-SAT → SAT → 3-CNF-SAT → {CLIQUE → VERTEX-COVER → HAM-CYCLE → TSP；SUBSET-SUM}。

34.5.1 团问题（The clique problem）（PDF p.1107–1110）

无向图 $G=(V,E)$ 中的团（clique）是顶点子集 $V'\subseteq V$，其中任两点之间都有边，即完全子图；规模为顶点数。优化问题求最大团；判定版本：$\text{CLIQUE}=\{\langle G,k\rangle: G \text{ 含规模为 } k \text{ 的团}\}$。
朴素算法枚举所有 $k$-子集：$\Omega\!\left(k^2\binom{|V|}{k}\right)$；$k$ 为常数时多项式，但 $k\approx|V|/2$ 时超多项式。

定理 34.11：CLIQUE 是 NP 完全的。

∈NP：证书为顶点集 $V'$，逐对检查边是否在 $E$ 中。
3-CNF-SAT $\le_P$ CLIQUE：设 $\phi=C_1\wedge\cdots\wedge C_k$，每个 $C_r=(l^r_1\vee l^r_2\vee l^r_3)$。对每个子句放三个顶点 $v^r_1,v^r_2,v^r_3$（一个“三元组”）；在 $v^r_i$ 与 $v^s_j$ 之间连边当且仅当 (i) $r\ne s$（不同三元组）且 (ii) 两文字一致（$l^r_i$ 不是 $l^s_j$ 的否定）。
⇒：满足赋值下每个子句至少有一个真文字，各取一个得 $k$ 个顶点；任两个来自不同三元组且都为真，不可能互补，因此有边，构成 $k$-团。
⇐：同一三元组内无边，所以 $k$-团恰含每个三元组一个顶点；把这些文字设为 1，不会冲突（不一致文字间无边）；每个子句被满足；团外变量任意设。
例（图 34.14）：$\phi=(x_1\vee\neg x_2\vee\neg x_3)\wedge(\neg x_1\vee x_2\vee x_3)\wedge(x_1\vee x_2\vee x_3)$，满足赋值 $x_2=0,x_3=1$，$x_1$ 任意；对应团为第一子句的 $\neg x_2$、第二、三子句的 $x_3$。
方法论要点：(1) 我们只证明了在“特殊结构图”（三元组、组内无边）上 CLIQUE 是 NP-hard 的，但这足以推出一般图上 NP-hard——一般图算法自然能解特殊图；反之，把“特殊结构的 3-CNF-SAT 实例”归约到一般 CLIQUE 则不够，因为那些特殊实例可能是简单的。(2) 归约只能用实例本身，不能用它的解（不能依赖知道 $\phi$ 是否可满足）。

34.5.2 顶点覆盖问题（The vertex-cover problem）（PDF p.1110–1112）

顶点覆盖（vertex cover）：$V'\subseteq V$，使每条边 $(u,v)$ 至少一个端点在 $V'$ 中。$\text{VERTEX-COVER}=\{\langle G,k\rangle: G \text{ 有规模为 } k \text{ 的顶点覆盖}\}$。例：图 34.15(b) 有覆盖 $\{w,z\}$。

定理 34.12：VERTEX-COVER 是 NP 完全的。

∈NP：证书为 $V'$，检查 $|V'|=k$ 及每条边被覆盖。
CLIQUE $\le_P$ VERTEX-COVER：用补图（complement）$\bar G=(V,\bar E)$，$\bar E=\{(u,v):u,v\in V,u\ne v,(u,v)\notin E\}$。把 $\langle G,k\rangle$ 映射为 $\langle\bar G,|V|-k\rangle$。
⇒：$V'$ 是 $G$ 的 $k$-团，则 $V-V'$ 覆盖 $\bar G$：任一 $(u,v)\in\bar E$ 不在 $E$ 中，故 $u,v$ 不能同在 $V'$，至少一个在 $V-V'$。
⇐：$V'$ 是 $\bar G$ 的规模 $|V|-k$ 的覆盖，则对任意 $u,v$，若 $u,v\notin V'$ 则 $(u,v)\in E$（逆否命题），即 $V-V'$ 是 $G$ 中规模 $k$ 的团。
引出第 35 章：虽然 NP 完全，但 35.1 节有多项式时间 2-近似算法，“问题 NP 完全不代表应放弃”。

34.5.3 哈密顿回路问题（The hamiltonian-cycle problem）（PDF p.1112–1117）

定理 34.13：HAM-CYCLE 是 NP 完全的。

∈NP：证书为 $|V|$ 个顶点的序列，检查每个顶点恰好出现一次、相邻顶点（含首尾）之间有边。
VERTEX-COVER $\le_P$ HAM-CYCLE：给定 $G=(V,E)$ 和 $k$，构造 $G'=(V',E')$ 使 $G'$ 有哈密顿回路当且仅当 $G$ 有规模 $k$ 的顶点覆盖。
部件（widget） $W_{uv}$（图 34.16）：对每条边 $(u,v)$ 一个，含 12 个顶点 $[u,v,i]$、$[v,u,i]$（$1\le i\le6$）和 14 条边。只有 $[u,v,1],[u,v,6],[v,u,1],[v,u,6]$ 与部件外相连。任意哈密顿回路穿过它只有三种方式：从 $[u,v,1]$ 进则从 $[u,v,6]$ 出，要么一次走完全部 12 个顶点（图 b），要么只走 $[u,v,1..6]$ 六个顶点（图 c，此时必须另一条路径再进来走 $[v,u,1..6]$）；从 $[v,u,1]$ 进类似（图 d）。不可能用两条不相交路径分别连 $[u,v,1]\to[v,u,6]$、$[v,u,1]\to[u,v,6]$ 覆盖全部顶点。
选择顶点（selector vertices） $s_1,\dots,s_k$：用来“选出”覆盖中的 $k$ 个顶点。
额外边：(1) 对每个 $u\in V$，把与 $u$ 关联的边对应的部件串成一条路径：将 $u$ 的邻居任意排序为 $u^{(1)},\dots,u^{(\text{degree}(u))}$，加边 $\{([u,u^{(i)},6],[u,u^{(i+1)},1]):1\le i\le\text{degree}(u)-1\}$。例：$w$ 的邻居排为 $x,y,z$，则加 $([w,x,6],[w,y,1])$、$([w,y,6],[w,z,1])$。(2) 每条这样路径的首点 $[u,u^{(1)},1]$ 和尾点 $[u,u^{(\text{degree}(u))},6]$ 都与每个选择顶点 $s_j$ 相连。
规模：$|V'|=12|E|+k\le12|E|+|V|$；$|E'|=14|E|+(2|E|-|V|)+2k|V|=16|E|+(2k-1)|V|\le16|E|+(2|V|-1)|V|$（利用 $\sum_u(\text{degree}(u)-1)=2|E|-|V|$）。故多项式时间可构造。
⇒：覆盖 $V^*=\{u_1,\dots,u_k\}$，回路从 $s_1$ 出发，走遍 $u_1$ 的所有部件，到 $s_2$，再走遍 $u_2$ 的部件……最后回到 $s_1$。具体边：各 $u_j$ 的串联边、部件内部边（视边被一个还是两个覆盖点覆盖而选图 b–d 的走法）、$\{(s_j,[u_j,u_j^{(1)},1])\}$、$\{(s_{j+1},[u_j,u_j^{(\deg)},6]):1\le j\le k-1\}$、$(s_1,[u_k,u_k^{(\deg)},6])$。因 $V^*$ 是覆盖，每个部件都被访问（一次或两次），每个选择顶点也被访问，故为哈密顿回路。（脚注 10：此处以边集描述回路属记号滥用。）
⇐：定义 $V^*=\{u\in V:(s_j,[u,u^{(1)},1])\in C \text{ 对某个 } j\}$ (34.4)。把回路切成以选择顶点为端点的极大“覆盖路径（cover path）”$p_u$：它从某 $s_i$ 走边 $(s_i,[u,u^{(1)},1])$，穿过所有与 $u$ 关联边的部件，到达某 $s_j$。每个部件被一或两条覆盖路径访问：一条则该边被 $u$ 覆盖；两条则另一条是 $p_v$，边被 $u,v$ 同时覆盖。每个部件顶点都被访问，故每条边都被 $V^*$ 覆盖。

34.5.4 旅行商问题（The traveling-salesman problem）（PDF p.1117–1118）

完全图上 $n$ 个城市，非负整数代价 $c(i,j)$，求总代价最小的巡回（tour，即哈密顿回路）。例（图 34.18）：最小巡回 $\langle u,w,v,x,u\rangle$ 代价 7。
判定版本：$\text{TSP}=\{\langle G,c,k\rangle: G \text{ 完全图}, c:V\times V\to\mathbb N, k\in\mathbb N, G \text{ 有代价} \le k \text{ 的巡回}\}$。

定理 34.14：TSP 是 NP 完全的。

∈NP：证书为 $n$ 个顶点的序列，检查每点恰出现一次、求和比较 $k$。
HAM-CYCLE $\le_P$ TSP：由 $G=(V,E)$ 构造完全图 $G'=(V,E')$，代价 $c(i,j)=0$ 若 $(i,j)\in E$，否则为 1；实例为 $\langle G',c,0\rangle$。$G$ 有哈密顿回路 ⇔ $G'$ 有代价 ≤0 的巡回（代价只有 0/1，代价 0 意味着全用原图边）。

34.5.5 子集和问题（The subset-sum problem）（PDF p.1118–1122）

给定正整数有限集 $S$ 和目标 $t>0$，问是否存在 $S'\subseteq S$ 使元素和为 $t$。$\text{SUBSET-SUM}=\{\langle S,t\rangle:\exists S'\subseteq S, t=\sum_{s\in S'}s\}$。例：$S=\{1,2,7,14,49,98,343,686,2409,2793,16808,17206,117705,117993\}$，$t=138457$，解 $S'=\{1,2,7,98,343,686,2409,17206,117705\}$。
关键前提：整数用二进制编码。若 $t$ 用一进制表示则多项式可解（习题 34.5-4，即动态规划 $O(n t)$ 是伪多项式时间 pseudo-polynomial）。

定理 34.15：SUBSET-SUM 是 NP 完全的。

∈NP：证书为 $S'$，求和比较。
3-CNF-SAT $\le_P$ SUBSET-SUM：公式 $\phi$ 有变量 $x_1..x_n$、子句 $C_1..C_k$（每个恰 3 个不同文字）。不失一般性假设：没有子句同时含 $x_i$ 与 $\neg x_i$；每个变量至少出现在一个子句中。
构造十进制数，每个数 $n+k$ 位：高 $n$ 位对应变量，低 $k$ 位对应子句。
- 目标 $t$：变量位全为 1，子句位全为 4。
- 对每个变量 $x_i$ 造 $v_i$、$v'_i$：在 $x_i$ 位为 1、其他变量位为 0；若 $x_i$ 出现在 $C_j$ 中则 $v_i$ 的 $C_j$ 位为 1；若 $\neg x_i$ 出现在 $C_j$ 中则 $v'_i$ 的 $C_j$ 位为 1。由两条假设，所有 $v_i,v'_i$ 互不相同。
- 对每个子句 $C_j$ 造松弛变量（slack variables）$s_j$、$s'_j$：只有 $C_j$ 位非零，分别为 1 和 2。
- 任一位上数字和最大为 6（子句位：三个文字的 1 加上 1+2），十进制下不会进位。（脚注 11：任何底数 $b\ge7$ 都行；开头的例子正是图 34.19 的实例按 7 进制解释并排序。）
例（图 34.19）：$C_1=(x_1\vee\neg x_2\vee\neg x_3)$，$C_2=(\neg x_1\vee\neg x_2\vee\neg x_3)$，$C_3=(\neg x_1\vee\neg x_2\vee x_3)$，$C_4=(x_1\vee x_2\vee x_3)$，满足赋值 $x_1=0,x_2=0,x_3=1$。$S=\{1001001,1000110,100001,101110,10011,11100,1000,2000,100,200,10,20,1,2\}$，$t=1114444$。$S'$ 含 $v'_1,v'_2,v_3$ 及 $s_1,s'_1,s'_2,s_3,s_4,s'_4$。
规模：$|S|=2n+2k$，每个数 $n+k$ 位，多项式时间。
⇒：$x_i=1$ 取 $v_i$，否则取 $v'_i$。变量位和为 1；每个子句至少一个真文字，子句位从 $v$ 们得到 1、2 或 3，再用 $\{s_j,s'_j\}$ 的适当非空子集补到 4（例中 $C_1,C_4$ 得 1，$C_2$ 得 2，$C_3$ 得 3）。无进位，所以和为 $t$。
⇐：变量位和为 1 迫使每个 $i$ 恰选 $v_i$ 或 $v'_i$ 之一，据此定赋值；子句位要达到 4，而松弛变量最多贡献 3，所以至少有一个 $v_i$ 或 $v'_i$ 在 $C_j$ 位为 1，对应文字为真，子句被满足。

习题 34.5 概览：34.5-1 子图同构 NP 完全；34.5-2 0-1 整数规划（$Ax\le b$，$x\in\{0,1\}^n$）NP 完全（从 3-CNF-SAT 归约）；34.5-3 一般整数线性规划 NP 完全；34.5-4 $t$ 为一进制时子集和多项式可解；34.5-5 集合划分（set-partition，两半和相等）NP 完全；34.5-6 哈密顿路径 NP 完全；34.5-7 最长简单回路的判定版本 NP 完全；34.5-8 “半 3-CNF 可满足”（恰一半子句为真）NP 完全。

第 34 章思考题与章注（PDF p.1121–1126）

34-1 独立集（independent set）：(a) 判定版本 NP 完全（从团归约：$G$ 的独立集即 $\bar G$ 的团）；(b) 给判定黑盒，用多项式次查询求最大独立集；(c) 每个顶点度为 2（图是若干不相交回路）时的高效算法；(d) 二部图上用最大匹配/最大流（26.3 节，König 定理）求解。
34-2 Bonnie 和 Clyde 分赃：(a) 只有两种面值 $x,y$ 的硬币，平分——多项式（枚举）；(b) 面值都是 2 的幂——多项式（贪心）；(c) 任意金额支票平分——即集合划分，NP 完全；(d) 允许差额不超过 100 美元——仍 NP 完全。
34-3 图着色（graph coloring）：$k$-着色 $c:V\to\{1..k\}$，相邻顶点不同色。(a) 2-着色可用 BFS 判二部图；(b) 写出判定版本并证明与优化版本多项式等价；(c) 若 3-COLOR NP 完全则一般判定版本也是；(d)–(f) 从 3-CNF-SAT 归约到 3-COLOR：变量顶点、否定顶点、每子句 5 个顶点、3 个特殊顶点 TRUE/FALSE/RED；“文字边”在特殊顶点间和每个 $\{x_i,\neg x_i,\text{RED}\}$ 上形成三角形，迫使变量与其否定一个着 TRUE 色一个着 FALSE 色；子句部件（图 34.20）保证当且仅当至少一个文字着 TRUE 色时可 3-着色。
34-4 带利润与截止期的调度：单机、$n$ 个任务，加工时间 $t_j$、利润 $p_j$、截止期 $d_j$，不可中断，按时完成才得利润。(a) 写判定版本；(b) 证明 NP 完全（可从子集和归约）；(c)(d) 加工时间为 1..n 的整数时用动态规划给出多项式算法。
章注：Garey & Johnson [129] 是 NP 完全性经典指南（1979 年的问题目录，定理 34.13 的证明取自该书）；Johnson 在 Journal of Algorithms 上 1981–1992 年连载 23 篇专栏。P 类由 Cobham（1964）与 Edmonds（1965）独立提出，Edmonds 还提出 NP 类并猜想 P≠NP；Cook（1971）提出 NP 完全概念并证明 SAT、3-CNF-SAT；Levin 独立发现（铺砖问题）；Karp（1972）引入归约方法并证明团、顶点覆盖、哈密顿回路等。Papadimitriou 1995 年称每年约 6000 篇论文的标题/摘要/关键词含“NP-complete”。近年的 PCP（probabilistically checkable proofs）理论表明许多问题（团、顶点覆盖、满足三角不等式的 TSP 等）求好的近似解也是 NP-hard 的。

第 34 章本章要点

NP 完全性理论的核心工具是多项式时间归约；Cook–Levin 定理（此书以 CIRCUIT-SAT 的形式给出）利用“把验证算法的计算展开成电路”证明一切 NP 问题可归约到电路可满足性。
证明新问题 NP 完全的五步法：属于 NP + 从已知 NPC 问题归约（构造、双向正确性、多项式时间）。
经典归约链：CIRCUIT-SAT → SAT → 3-CNF-SAT → CLIQUE → VERTEX-COVER → HAM-CYCLE → TSP，以及 3-CNF-SAT → SUBSET-SUM。归约技巧包括：为中间量引入新变量避免指数膨胀、真值表+De Morgan、填充辅助变量、补图、部件（widget）、按位编码且防进位。
子集和的 NP 完全依赖二进制编码；一进制下可伪多项式求解——“数值大小”与“输入长度”需区分。
2-CNF-SAT、DNF-SAT、二部图独立集等特例是多项式可解的。

第 34 章与量化交易的关联

组合优化的难度判断：带基数约束的组合优化（如“从 N 只股票中恰选 K 只使跟踪误差最小”）、带最小交易单位/整手约束的组合再平衡、0-1 选股，本质上是整数规划，属 NP-hard（习题 34.5-2、34.5-3）。知道这一点，就会主动采用 MIQP 求解器的分支定界、松弛+取整、贪心或启发式，而不是寻找“精确多项式算法”。
子集和/背包与伪多项式：订单拆分凑目标金额、按整手凑仓位，若金额以“最小变动单位”离散化且范围不大，可用 $O(nt)$ 动态规划，这正是“一进制可解”的实际意义。
调度类问题（思考题 34-4）：交易任务在截止期前执行以获取收益，与执行算法中的订单调度、回测集群任务排程结构相似。
理论证明细节（电路构造、部件）与日常量化工作没有直接关系，教材中可只保留结论与归约思想。

第 34 章推荐习题

34.4-6（用判定黑盒构造解，自归约思想）；34.4-7（2-SAT 线性时间算法，蕴含图 + 强连通分量）；34.5-2、34.5-3（0-1/整数规划 NP 完全，与组合优化直接相关）；34.5-4（子集和的伪多项式 DP）；34.5-5（集合划分）；思考题 34-1（独立集各特例）；思考题 34-4（带截止期调度，DP 求解）。

第 35 章近似算法（Approximation Algorithms）（PDF p.1127–1161）

35.0 引言：性能比与近似方案（PDF p.1127–1129）

面对 NP 完全问题至少有三条出路：(1) 输入规模小时指数算法也可接受；(2) 找出多项式可解的重要特例；(3) 在多项式时间内（最坏或期望意义下）求近似最优解。返回近似最优解的算法称为近似算法（approximation algorithm）。
近似比（approximation ratio） $\rho(n)$：对任意规模 $n$ 的输入，算法解的代价 $C$ 与最优代价 $C^*$ 满足 $\max\left(\frac{C}{C^*},\frac{C^*}{C}\right)\le\rho(n). \quad (35.1)$ 达到该比值的算法称 $\rho(n)$-近似算法。对最大化问题 $0<C\le C^*$，看 $C^*/C$；对最小化问题 $0<C^*\le C$，看 $C/C^*$。假设所有解代价为正，比值良定且总 $\ge1$；1-近似即最优。脚注：比值与 $n$ 无关时直接说“近似比 $\rho$”“$\rho$-近似算法”。
有的问题有小常数近似比；有的最好已知近似比随 $n$ 增长（如集合覆盖）。
近似方案（approximation scheme）：输入除实例外还有 $\epsilon>0$，对任意固定 $\epsilon$ 是 $(1+\epsilon)$-近似算法。多项式时间近似方案（PTAS）：对任意固定 $\epsilon$，运行时间是 $n$ 的多项式（如 $O(n^{2/\epsilon})$，$\epsilon$ 变小时时间可能暴涨）。完全多项式时间近似方案（FPTAS）：运行时间关于 $1/\epsilon$ 和 $n$ 都是多项式（如 $O((1/\epsilon)^2n^3)$），$\epsilon$ 按常数倍减小只让时间按常数倍增加。
本章路线：35.1 顶点覆盖 2-近似；35.2 满足三角不等式的 TSP 2-近似，一般 TSP 不可常数近似（除非 P=NP）；35.3 集合覆盖贪心，对数近似比；35.4 MAX-3-CNF 随机 8/7-近似、加权顶点覆盖 LP 舍入 2-近似；35.5 子集和 FPTAS。

35.1 顶点覆盖问题（The vertex-cover problem）（PDF p.1129–1132）

最优顶点覆盖（optimal vertex cover）：规模最小的顶点覆盖。

算法 APPROX-VERTEX-COVER(G)（Python 风格）：

def approx_vertex_cover(G):
    C = set()
    E1 = set(G.E)                     # 边集副本
    while E1:
        (u, v) = any_edge(E1)         # 任取一条边
        C |= {u, v}                   # 两个端点都加入
        E1 -= {e for e in E1 if u in e or v in e}  # 删去所有被 u 或 v 覆盖的边
    return C

复杂度：用邻接表表示 $E'$，时间 $O(V+E)$，空间 $O(V+E)$。
例（图 35.1）：7 顶点 8 边的图，依次选边 $(b,c)$、$(e,f)$、$(d,g)$，得 $C=\{b,c,d,e,f,g\}$ 共 6 个顶点；最优覆盖只需 3 个：$\{b,d,e\}$。

定理 35.1：APPROX-VERTEX-COVER 是多项式时间 2-近似算法。证明：设 $A$ 为第 4 行选中的边集。任何覆盖（包括最优 $C^*$）都必须含 $A$ 中每条边的至少一个端点；$A$ 中任两条边无公共端点（选边后会删去所有相邻边），故 $|C^*|\ge|A|$ (35.2)。每次选的边两个端点都不在 $C$ 中，所以 $|C|=2|A|$ (35.3)。于是 $|C|=2|A|\le2|C^*|$。

方法论：不知道最优值也能证近似比——关键是找一个最优值的下界（这里是极大匹配 maximal matching 的大小：不是任何其他匹配真子集的匹配），再证明算法解不超过下界的若干倍。后续各节反复使用这一套路。

习题概览：35.1-1 给出总得到次优解的图；35.1-2 证明所选边集是极大匹配；35.1-3 “每次选最高度顶点”的启发式没有近似比 2（用左侧度均匀、右侧度不等的二部图构造反例）；35.1-4 树上线性时间求最优顶点覆盖的贪心（选叶子的父结点）；35.1-5 顶点覆盖与团互补，但这不意味着团有常数近似比（补关系对比值不保持）。

35.2 旅行商问题（The traveling-salesman problem）（PDF p.1131–1138）

记 $c(A)=\sum_{(u,v)\in A}c(u,v)$。代价函数满足三角不等式（triangle inequality）：对所有 $u,v,w$，$c(u,w)\le c(u,v)+c(v,w)$（跳过中间站不会更贵）；平面欧氏距离自然满足。即使满足三角不等式，TSP 仍是 NP 完全的（习题 35.2-2）。

35.2.1 满足三角不等式的 TSP

思路：先求一个结构——最小生成树（minimum spanning tree, MST），其权是最优巡回的下界；再用它构造代价不超过 MST 两倍的巡回。

算法 APPROX-TSP-TOUR(G, c)：

def approx_tsp_tour(G, c):
    r = any_vertex(G.V)                 # 选根
    T = mst_prim(G, c, r)               # 第 23 章 Prim 算法
    H = preorder_walk(T, r)             # 前序遍历中首次访问的顺序
    return H + [H[0]]                   # 作为哈密顿回路

复杂度：完全图上即使用简单的 Prim 实现，时间 $\Theta(V^2)$（习题 23.2-2）；空间 $O(V^2)$（存完全图）或 $O(V)$（按需计算距离）。
例（图 35.2）：8 个格点，欧氏距离，根 $a$；完整遍历（full walk）顺序 $a,b,c,b,h,b,a,d,e,f,e,g,e,d,a$；前序遍历 $a,b,c,h,d,e,f,g$；所得巡回代价约 19.074，最优巡回约 14.715（短约 23%）。

定理 35.2：APPROX-TSP-TOUR 是满足三角不等式 TSP 的多项式时间 2-近似算法。证明：设最优巡回 $H^*$。从巡回删去任一边得到生成树，边权非负，故 $c(T)\le c(H^*)$ (35.4)。完整遍历 $W$ 恰好经过树的每条边两次：$c(W)=2c(T)$ (35.5)，故 $c(W)\le2c(H^*)$ (35.6)。$W$ 不是巡回（重复访问顶点），但由三角不等式，删去对某顶点的一次访问（从 $u$ 直接走到 $w$）不增加代价；反复删除只保留首次访问，即得前序序列 $H$，$c(H)\le c(W)$ (35.7)。合并得 $c(H)\le2c(H^*)$。

实践中此算法通常不是最佳选择，其他近似算法效果好得多（见章注：Christofides 的 3/2-近似）。

35.2.2 一般 TSP

定理 35.3：若 P≠NP，则对任意常数 $\rho\ge1$，一般 TSP 不存在多项式时间 $\rho$-近似算法。证明（反证）：设有 $\rho$-近似算法 $A$（不妨 $\rho$ 为整数）。对 HAM-CYCLE 实例 $G=(V,E)$ 构造完全图 $G'$，代价 $c(u,v)=1$ 若 $(u,v)\in E$，否则 $\rho|V|+1$。若 $G$ 有哈密顿回路，$G'$ 有代价 $|V|$ 的巡回；否则任何巡回至少用一条非 $E$ 边，代价至少 $(\rho|V|+1)+(|V|-1)=\rho|V|+|V|>\rho|V|$。由于“间隙（gap）”，$A$ 在有哈密顿回路时必返回它（代价 ≤ $\rho|V|$），否则返回代价 $>\rho|V|$ 的巡回，于是可多项式时间判定 HAM-CYCLE，推出 P=NP，矛盾。

一般技巧（gap reduction）：若能把 NP-hard 问题 X 多项式变换为最小化问题 Y，使 X 的“是”实例对应 Y 的值 ≤ $k$，“否”实例对应值 > $\rho k$，则除非 P=NP，Y 没有多项式 $\rho$-近似算法。

习题概览：35.2-1 满足三角不等式且至少 3 个顶点时 $c(u,v)\ge0$；35.2-2 把一般 TSP 多项式变换为满足三角不等式的实例且最优巡回集合相同（给每条边加大常数），解释为何不与定理 35.3 矛盾（近似比不保持）；35.2-3 最近点插入启发式（closest-point heuristic）是 2-近似；35.2-4 瓶颈 TSP（最小化最大边）在三角不等式下有 3-近似（瓶颈生成树+跳点不超过两个连续中间点）；35.2-5 平面欧氏 TSP 最优巡回不自交。

35.3 集合覆盖问题（The set-covering problem）（PDF p.1137–1143）

实例 $(X,\mathcal F)$：有限集 $X$ 与 $X$ 的子集族 $\mathcal F$，且 $X=\bigcup_{S\in\mathcal F}S$。求最小规模子族 $\mathcal C\subseteq\mathcal F$ 覆盖 $X$：$X=\bigcup_{S\in\mathcal C}S$ (35.8)。规模指所含集合个数。它推广了顶点覆盖，因此 NP-hard；判定版本 NP 完全（习题 35.3-2）。
例：$X$ 是解决问题所需技能，组建人数最少的委员会使每项技能至少有一人具备。图 35.3：12 个点、6 个集合，最小覆盖 $\{S_3,S_4,S_5\}$ 规模 3，贪心得到规模 4（依次 $S_1,S_4,S_5$，再 $S_3$ 或 $S_6$）。

算法 GREEDY-SET-COVER(X, F)：

def greedy_set_cover(X, F):
    U = set(X)            # 尚未覆盖的元素
    C = []
    while U:
        S = max(F, key=lambda S: len(S & U))   # 覆盖最多未覆盖元素的集合，平局任意
        U -= S
        C.append(S)
    return C

复杂度：循环次数 ≤ $\min(|X|,|\mathcal F|)$，循环体 $O(|X||\mathcal F|)$，简单实现总时间 $O(|X||\mathcal F|\min(|X|,|\mathcal F|))$；习题 35.3-3 要求做到 $O(\sum_{S\in\mathcal F}|S|)$（按“新覆盖元素数”分桶维护）。

记调和数 $H(d)=H_d=\sum_{i=1}^d1/i$，约定 $H(0)=0$。

定理 35.4：GREEDY-SET-COVER 是多项式时间 $\rho(n)$-近似算法，$\rho(n)=H(\max\{|S|:S\in\mathcal F\})$。证明（代价分摊法）：每选一个集合 $S_i$ 付代价 1，把它平均分给首次被 $S_i$ 覆盖的元素：若 $x$ 首次被 $S_i$ 覆盖，$c_x=\dfrac{1}{|S_i-(S_1\cup\cdots\cup S_{i-1})|}$。于是 $|\mathcal C|=\sum_{x\in X}c_x$ (35.9)。最优覆盖 $\mathcal C^*$ 中每个元素至少出现一次，故 $\sum_{S\in\mathcal C^*}\sum_{x\in S}c_x\ge\sum_xc_x$ (35.10)，得 $|\mathcal C|\le\sum_{S\in\mathcal C^*}\sum_{x\in S}c_x$ (35.11)。关键不等式：对任意 $S\in\mathcal F$，

\sum_{x\in S}c_x\le H(|S|). \quad (35.12)

由此 $|\mathcal C|\le\sum_{S\in\mathcal C^*}H(|S|)\le|\mathcal C^*|\cdot H(\max|S|)$。 (35.12) 的证明：令 $u_i=|S-(S_1\cup\cdots\cup S_i)|$，$u_0=|S|$，$k$ 为使 $u_k=0$ 的最小下标。第 $i$ 步 $S$ 中有 $u_{i-1}-u_i$ 个元素首次被覆盖。贪心选择保证 $|S_i-(S_1\cup\cdots\cup S_{i-1})|\ge|S-(S_1\cup\cdots\cup S_{i-1})|=u_{i-1}$。于是

\sum_{x\in S}c_x\le\sum_{i=1}^k(u_{i-1}-u_i)\frac1{u_{i-1}}=\sum_{i=1}^k\sum_{j=u_i+1}^{u_{i-1}}\frac1{u_{i-1}}\le\sum_{i=1}^k\sum_{j=u_i+1}^{u_{i-1}}\frac1j=\sum_{i=1}^k(H(u_{i-1})-H(u_i))=H(u_0)-H(u_k)=H(|S|).

（望远镜求和 telescoping。）

推论 35.5：GREEDY-SET-COVER 是多项式时间 $(\ln|X|+1)$-近似算法（由 $H_n\le\ln n+1$，式 A.14）。

当 $\max|S|$ 是小常数时近似比也是小常数。例：最大度 ≤3 的图上求顶点覆盖（每个顶点视为覆盖其关联边的集合），贪心比值 ≤ $H(3)=11/6$，略好于 APPROX-VERTEX-COVER 的 2。

习题概览：35.3-1 用单词字母集合 {arid, dash, drain, heard, lost, nose, shun, slate, snare, thread} 手算贪心（平局取字典序靠前）；35.3-2 从顶点覆盖归约证明集合覆盖判定版 NP 完全；35.3-3 线性时间实现；35.3-4 平凡的弱界 $|\mathcal C|\le|\mathcal C^*|\max|S|$；35.3-5 构造实例使不同平局规则下贪心可能返回指数多种不同解。

35.4 随机化与线性规划（Randomization and linear programming）（PDF p.1144–1149）

MAX-3-CNF 可满足性的随机近似算法

随机近似比：对规模 $n$ 的输入，随机算法解的期望代价 $C$ 满足 $\max(C/C^*,C^*/C)\le\rho(n)$ (35.13)，称随机 $\rho(n)$-近似算法。
MAX-3-CNF：输入同 3-CNF-SAT（每子句恰 3 个不同文字，且假设不含变量及其否定），求满足子句数最多的赋值。

定理 35.6：$n$ 个变量、$m$ 个子句，独立地以 1/2 概率把每个变量设为 1 或 0，是随机 8/7-近似算法。证明：指示随机变量 $Y_i=I\{\text{子句 } i \text{ 被满足}\}$。三个文字取值独立，子句不满足当且仅当三个文字都为 0，概率 $(1/2)^3=1/8$，故 $E[Y_i]=7/8$（引理 5.1）。由期望线性性 $E[Y]=\sum E[Y_i]=7m/8$。最优值至多 $m$，比值 ≤ $m/(7m/8)=8/7$。

复杂度：$O(n+m)$ 时间。

用线性规划近似最小权顶点覆盖

最小权顶点覆盖（minimum-weight vertex cover）：每个顶点有正权 $w(v)$，覆盖权 $w(V')=\sum_{v\in V'}w(v)$，求最小权覆盖。无权算法与随机解都可能离最优很远。
0-1 整数规划： $\min\sum_{v\in V}w(v)x(v)\quad\text{s.t. } x(u)+x(v)\ge1\ \forall(u,v)\in E,\quad x(v)\in\{0,1\}\ \forall v. \quad(35.14\text{–}35.16)$ （全部权为 1 时即 NP-hard 的顶点覆盖优化版。）
线性规划松弛（linear-programming relaxation）：把 $x(v)\in\{0,1\}$ 换成 $0\le x(v)\le1$ (35.17–35.20)。整数规划可行解都是 LP 可行解，故 LP 最优值是最小权覆盖的下界。

算法 APPROX-MIN-WEIGHT-VC(G, w)：

def approx_min_weight_vc(G, w):
    x_bar = solve_lp_relaxation(G, w)     # 式 (35.17)-(35.20) 的最优解
    return {v for v in G.V if x_bar[v] >= 0.5}   # 以 1/2 为阈值舍入（rounding）

复杂度：LP 可多项式时间求解（如椭球法/内点法，第 29 章），舍入 $O(V)$。

定理 35.7：APPROX-MIN-WEIGHT-VC 是多项式时间 2-近似算法。证明：设 $z^*$ 为 LP 最优值，$C^*$ 为最优覆盖，则 $z^*\le w(C^*)$ (35.21)。$C$ 是覆盖：每条边 $\bar x(u)+\bar x(v)\ge1$，至少一个 ≥1/2。权重：

z^*=\sum_vw(v)\bar x(v)\ge\sum_{v:\bar x(v)\ge1/2}w(v)\bar x(v)\ge\sum_{v\in C}w(v)\cdot\tfrac12=\tfrac12w(C). \quad(35.22)

故 $w(C)\le2z^*\le2w(C^*)$。

习题概览：35.4-1 允许子句含变量及其否定时随机算法仍是 8/7-近似；35.4-2 MAX-CNF（子句文字数不限）的随机 2-近似；35.4-3 MAX-CUT 随机把每个顶点放进 $S$ 或 $V-S$ 是随机 2-近似（每条边被切的概率 1/2）；35.4-4 约束 $x(v)\le1$ 是冗余的。

35.5 子集和问题（The subset-sum problem）（PDF p.1149–1155）

优化版本：$S=\{x_1,\dots,x_n\}$ 为正整数，求和不超过 $t$ 的最大子集和。例：卡车载重上限 $t$ 磅，$n$ 个箱子重 $x_i$，尽量装重。

指数时间精确算法

记号：$L+x$ 表示把列表每个元素加 $x$（如 $\langle1,2,3,5,9\rangle+2=\langle3,4,5,7,11\rangle$），集合同理 $S+x=\{s+x:s\in S\}$。MERGE-LISTS$(L,L')$ 归并两个有序表并去重，$O(|L|+|L'|)$。

def exact_subset_sum(S, t):
    L = [0]
    for x in S:
        L = merge_lists(L, [y + x for y in L])   # 有序归并并去重
        L = [y for y in L if y <= t]              # 超过 t 的和不可能扩展成最优解
    return max(L)

记 $P_i$ 为 $\{x_1..x_i\}$ 所有子集和的集合，如 $S=\{1,4,5\}$：$P_1=\{0,1\}$，$P_2=\{0,1,4,5\}$，$P_3=\{0,1,4,5,6,9,10\}$。恒等式 $P_i=P_{i-1}\cup(P_{i-1}+x_i)$ (35.23)；归纳可证 $L_i$ 是 $P_i$ 中 ≤ $t$ 元素的有序表。
复杂度：$|L_i|$ 可达 $2^i$，一般为指数时间；但 $|L_i|\le t+1$，所以时间 $O(n\cdot\min(2^n,t))$——当 $t$ 或所有 $x_i$ 被 $|S|$ 的多项式界住时是多项式（伪多项式）。

完全多项式时间近似方案（FPTAS）

修剪（trimming）：参数 $0<\delta<1$。修剪后的 $L'$ 满足：每个被删的 $y$ 都有保留的 $z$ 使 $\frac{y}{1+\delta}\le z\le y. \quad(35.24)$ 例：$\delta=0.1$，$L=\langle10,11,12,15,20,21,22,23,24,29\rangle$ 修剪为 $\langle10,12,15,20,23,29\rangle$（11 由 10 代表，21、22 由 20 代表，24 由 23 代表）。

def trim(L, delta):               # L 已升序
    out = [L[0]]
    last = L[0]
    for y in L[1:]:
        if y > last * (1 + delta):    # last 无法代表 y
            out.append(y)
            last = y
    return out

TRIM 时间 $\Theta(m)$，空间 $O(m)$。

def approx_subset_sum(S, t, eps):     # 0 < eps < 1
    n = len(S)
    L = [0]
    for x in S:
        L = merge_lists(L, [y + x for y in L])
        L = trim(L, eps / (2 * n))
        L = [y for y in L if y <= t]
    return max(L)

例：$S=\langle104,102,201,101\rangle$，$t=308$，$\epsilon=0.40$，$\delta=\epsilon/8=0.05$。逐步：$L_1=\langle0,104\rangle$；$L_2$ 合并得 $\langle0,102,104,206\rangle$，修剪为 $\langle0,102,206\rangle$；$L_3$ 合并得 $\langle0,102,201,206,303,407\rangle$，修剪为 $\langle0,102,201,303,407\rangle$，去掉 >308 得 $\langle0,102,201,303\rangle$；$L_4$ 合并得 $\langle0,101,102,201,203,302,303,404\rangle$，修剪为 $\langle0,101,201,302,404\rangle$，去掉 >308 得 $\langle0,101,201,302\rangle$。返回 $z^*=302$，最优为 $307=104+102+101$，误差约 2%，远小于 40%。

定理 35.8：APPROX-SUBSET-SUM 是子集和问题的 FPTAS。证明要点：

修剪和删除只删元素，$L_i\subseteq P_i$，所以返回值 $z^*$ 是某子集之和，且 $z^*\le y^*$（$y^*$ 为最优）。
对每个 $y\in P_i$、$y\le t$，存在 $z\in L_i$ 使 $\dfrac{y}{(1+\epsilon/2n)^i}\le z\le y$ (35.26)（对 $i$ 归纳，习题 35.5-2）。取 $i=n$、$y=y^*$，并且 $z^*$ 是 $L_n$ 最大值，故 $\dfrac{y^*}{z^*}\le(1+\epsilon/2n)^n$ (35.28)。
$(1+\epsilon/2n)^n$ 关于 $n$ 单调增（习题 35.5-3，式 35.29），极限为 $e^{\epsilon/2}$，所以 $\left(1+\frac{\epsilon}{2n}\right)^n\le e^{\epsilon/2}\le1+\frac\epsilon2+\left(\frac\epsilon2\right)^2\le1+\epsilon \quad(35.30)$ （第二步用 $e^x\le1+x+x^2$（$|x|\le1$，式 3.13），第三步用 $0<\epsilon<1$。）
列表长度：修剪后相邻元素之比 $>1+\epsilon/2n$，所以每个表含 0、可能含 1、外加至多 $\lfloor\log_{1+\epsilon/2n}t\rfloor$ 个值，元素数至多 $\log_{1+\epsilon/2n}t+2=\frac{\ln t}{\ln(1+\epsilon/2n)}+2\le\frac{2n(1+\epsilon/2n)\ln t}{\epsilon}+2<\frac{3n\ln t}{\epsilon}+2$ （用 $\ln(1+x)\ge x/(1+x)$，式 3.17）。这是输入规模（$\lg t$ 加上表示 $S$ 的位数）和 $1/\epsilon$ 的多项式。

复杂度：每轮 $O(|L_i|)$，总时间 $O\!\left(n\cdot\frac{n\ln t}{\epsilon}\right)=O\!\left(\frac{n^2\ln t}{\epsilon}\right)$，空间 $O\!\left(\frac{n\ln t}{\epsilon}\right)$。

习题概览：35.5-1 证明式 (35.23) 及 $L_i$ 的性质；35.5-2 归纳证明 (35.26)；35.5-3 证明 (35.29)；35.5-4 改造为求“不小于 $t$ 的最小子集和”的近似；35.5-5 让 APPROX-SUBSET-SUM 同时返回取到 $z^*$ 的子集（保存回溯指针）。

第 35 章思考题与章注（PDF p.1155–1161）

35-1 装箱（bin packing）：$n$ 个物体大小 $0<s_i<1$，装入最少的单位容量箱。(a) NP-hard（从子集和归约）；(b) 最优箱数 ≥ $\lceil S\rceil$，$S=\sum s_i$；(c) 首次适配（first-fit）至多一个箱不足半满；(d) 首次适配用箱数 ≤ $\lceil2S\rceil$；(e) 由此近似比 2；(f) 高效实现（如用平衡树/线段树维护剩余容量，$O(n\lg n)$）。
35-2 最大团规模近似：定义 $G^{(k)}$：顶点为有序 $k$ 元组，两元组相邻当且仅当每个分量相邻或相等。(a) $G^{(k)}$ 最大团规模是 $G$ 最大团规模的 $k$ 次方；(b) 若最大团有常数近似比算法，则有 PTAS（放大技巧：取 $k$ 次方后开 $k$ 次根，比值变为 $\rho^{1/k}$）。
35-3 加权集合覆盖：每个集合有权 $w_i$，按“单位新覆盖元素的权最小”贪心，证明近似比 $H(d)$，$d$ 为最大集合大小。
35-4 最大匹配：(a) 极大匹配不一定是最大匹配（4 顶点路径例）；(b) $O(E)$ 贪心求极大匹配；(c) 最大匹配大小是任意顶点覆盖大小的下界；(d) 极大匹配 $M$ 的端点集 $T$ 之外的顶点之间无边（诱导子图无边）；(e) 故 $2|M|$ 是一个顶点覆盖的大小；(f) 贪心极大匹配是最大匹配的 2-近似（线性时间）。
35-5 并行机调度（parallel machine scheduling）：$n$ 个作业处理时间 $p_k$，$m$ 台相同机器，最小化完工时间跨度（makespan）$C_{\max}=\max_jC_j$。例：两台机，$p=(2,12,4,5)$，一种调度 $C_{\max}=14$，最优为 $J_2$ 单独一台、其余在另一台，$C_{\max}=12$。(a) $C^*_{\max}\ge\max_kp_k$；(b) $C^*_{\max}\ge\frac1m\sum_kp_k$；(c) 写出“有机器空闲就分配任一未调度作业”的贪心（list scheduling），用优先队列 $O(n\lg m)$；(d) 贪心满足 $C_{\max}\le\frac1m\sum_kp_k+\max_kp_k$，因此是 2-近似。
35-6 最大生成树近似：边权互异，$\max(v)$ 为与 $v$ 关联的最大权边，$S_G=\{\max(v)\}$，$T_G$ 为最大权生成树。(a)(b) 举 $S_G=T_G$ 与 $S_G\ne T_G$ 的例；(c) $S_G\subseteq T_G$；(d) $w(S_G)\ge w(T_G)/2$；(e) 给出 $O(V+E)$ 的最大生成树 2-近似。
35-7 0-1 背包的 2-近似：价值 $v_1\ge v_2\ge\cdots\ge v_n$，重量 $w_i\le W$。受限实例 $I_j$：删去物品 $1..j-1$ 且必须含物品 $j$；$P_j$ 为 0-1 最优、$Q_j$ 为分数背包最优。(a) 原问题最优解是某个 $P_j$；(b) $Q_j$ 可由“先放 $j$，再按单位重量价值 $v_i/w_i$ 贪心”得到；(c) 存在至多一个物品取分数的 $Q_j$；(d) 删去分数物品得 $R_j$，有 $v(R_j)\ge v(Q_j)/2\ge v(P_j)/2$（因被删物品价值 ≤ $v_j$，而 $v_j$ 已在解中）；(e) 取 $R_1..R_n$ 中最大者得多项式 2-近似。
章注：近似算法概念由 Garey、Graham、Ullman 与 Johnson 形式化，首个此类算法常归于 Graham（并行机调度）。专著有 Ausiello 等、Hochbaum、Vazirani；综述 Shmoys、Klein & Young 等。APPROX-VERTEX-COVER 归于 Gavril 与 Yannakakis；顶点覆盖已知近似比均 ≥ $2-o(1)$。APPROX-TSP-TOUR 来自 Rosenkrantz–Stearns–Lewis；Christofides 给出满足三角不等式 TSP 的 3/2-近似；Arora 与 Mitchell 证明欧氏平面 TSP 有 PTAS；定理 35.3 属于 Sahni & Gonzalez。集合覆盖贪心分析仿照 Chvátal，基本结果属于 Johnson 与 Lovász。APPROX-SUBSET-SUM 仿照 Ibarra & Kim 的背包 FPTAS。思考题 35-7 来自 Bienstock & McClosky。MAX-3-CNF 随机算法隐含于 Johnson 的工作；加权顶点覆盖 LP 算法属于 Hochbaum。随机化+LP 结合产生随机舍入（randomized rounding）（Raghavan & Thompson）：解 LP 松弛，把变量值当作概率来引导整数解。其他重要思想：原始-对偶方法（primal-dual）、稀疏割、半定规划（semidefinite programming，如 MAX-CUT 的 Goemans–Williamson 算法）。PCP 结果给出许多问题的不可近似下界。

第 35 章本章要点

近似比定义统一处理最大化与最小化；PTAS 与 FPTAS 的区别在于运行时间是否对 $1/\epsilon$ 也是多项式。
证明近似比的通用套路：找到可计算的最优值下界（极大匹配、MST、LP 松弛最优值、所有子句数 $m$ 作为上界），再把算法解与该界联系起来。
具体结果：顶点覆盖 2-近似（$O(V+E)$）；三角不等式 TSP 2-近似（MST + 前序遍历 + 抄近路，$\Theta(V^2)$）；一般 TSP 不可常数近似（gap 归约）；集合覆盖贪心 $H(\max|S|)\le\ln|X|+1$（代价分摊证明）；MAX-3-CNF 随机 8/7（期望线性性）；加权顶点覆盖 LP 松弛 + 1/2 阈值舍入 2-近似；子集和 FPTAS（列表修剪，$O(n^2\ln t/\epsilon)$）。
常见误区：近似比是最坏情况保证，实际表现可能远好（如子集和例中 2% vs 40%）；APPROX-TSP-TOUR 理论好但实践中不是最优选择。

第 35 章与量化交易的关联

组合优化中的 LP 松弛与舍入：带基数约束/整手约束的组合构建，常见做法正是“解连续松弛 → 舍入/修复”，35.4 的 LP 下界思想可直接用于评估启发式解离最优还有多远（对偶间隙 gap）。随机舍入也用于离散化权重。
背包与子集和的 FPTAS：资金约束下选择交易机会（每个机会占用资金、带预期收益）就是 0-1 背包；列表修剪（按相对误差 $\delta$ 合并相近值）是控制 DP 状态数的实用技巧，也适用于整手订单凑目标金额。思考题 35-7 的“分数背包贪心后去掉分数物品”是可解释的快速近似。
集合覆盖：用最少的因子/资产/对冲工具覆盖所需的风险暴露类别、用最少的数据源覆盖全部所需标的，可用贪心集合覆盖并有 $\ln n+1$ 的质量保证。
调度：思考题 35-5 的 list scheduling 2-近似可用于回测/因子计算任务在多核/多机上的分配（最小化 makespan），是系统实现层面的直接应用。
TSP、顶点覆盖本身与量化交易关系不大，但其“下界+构造”的证明方法有借鉴价值。

第 35 章推荐习题

35.1-2（极大匹配下界）；35.2-2（变换满足三角不等式但不保近似比，理解近似比的脆弱性）；35.3-3（贪心集合覆盖线性实现）；35.4-3（MAX-CUT 随机 2-近似）；35.5-2、35.5-5（FPTAS 的归纳证明与解的回溯）；思考题 35-5（并行机调度）、35-7（0-1 背包 2-近似）、35-1（装箱首次适配）。

第 VIII 部分附录：数学背景（Appendix: Mathematical Background）引言（PDF p.1162–1165）

PDF p.1162 为空白页，p.1163 为部分扉页。引言说明：分析算法需要一系列数学工具，第 I 部分已讲渐近记号和递归式，本附录汇编其余概念方法，作参考材料使用，并配有习题。附录 A：求和式的求值与界（多见于微积分教材，集中整理便于查阅）；附录 B：集合、关系、函数、图、树的基本定义、记号与性质；附录 C：计数（排列、组合等）及基础概率——书中多数算法分析不需要概率，初读可跳过后半部分，遇到概率分析时再查；附录 D：矩阵定义、运算及基本性质，统一本书的记号与定义。

附录 A 求和（Summations）（PDF p.1166–1178）

动机：循环结构的运行时间是各次迭代时间之和。例如插入排序第 $j$ 次迭代最坏耗时与 $j$ 成正比，总和 $\sum_{j=2}^nj$ 给出 $\Theta(n^2)$。A.1 列公式（多数不证），A.2 讲求界技巧。

A.1 求和公式与性质（Summation formulas and properties）（PDF p.1166–1170）

有限和：$\sum_{k=1}^na_k=a_1+\cdots+a_n$，$n=0$ 时定义为 0；有限和的值总是良定的，可按任意顺序相加。
无穷级数：$\sum_{k=1}^\infty a_k:=\lim_{n\to\infty}\sum_{k=1}^na_k$；极限不存在称发散（diverge），否则收敛（converge）。收敛级数不一定可以任意重排；绝对收敛（absolutely convergent，即 $\sum|a_k|$ 收敛）的级数可以重排。
线性性（linearity）：$\sum_{k=1}^n(ca_k+b_k)=c\sum a_k+\sum b_k$，对收敛无穷级数也成立。可用于渐近记号：$\sum_{k=1}^n\Theta(f(k))=\Theta\!\left(\sum_{k=1}^nf(k)\right)$——注意左边的 $\Theta$ 作用于变量 $k$，右边作用于 $n$。
算术级数（arithmetic series）： $\sum_{k=1}^nk=\frac12n(n+1)\ \ (A.1)\ =\Theta(n^2)\ \ (A.2).$
平方和与立方和： $\sum_{k=0}^nk^2=\frac{n(n+1)(2n+1)}{6}\ \ (A.3),\qquad\sum_{k=0}^nk^3=\frac{n^2(n+1)^2}{4}\ \ (A.4).$
几何级数（geometric / exponential series）：实数 $x\ne1$ 时 $\sum_{k=0}^nx^k=\frac{x^{n+1}-1}{x-1}\ \ (A.5);\qquad|x|<1\text{ 时 }\sum_{k=0}^\infty x^k=\frac1{1-x}\ \ (A.6).$ 约定 $0^0=1$，所以 $x=0$ 时公式也适用。
调和级数（harmonic series）：第 $n$ 个调和数 $H_n=1+\frac12+\cdots+\frac1n=\sum_{k=1}^n\frac1k=\ln n+O(1)\ \ (A.7).$
对级数积分与微分：对 (A.6) 两边求导再乘 $x$： $\sum_{k=0}^\infty kx^k=\frac{x}{(1-x)^2},\quad|x|<1\ \ (A.8).$
望远镜级数（telescoping series）：$\sum_{k=1}^n(a_k-a_{k-1})=a_n-a_0$ (A.9)，同理 $\sum_{k=0}^{n-1}(a_k-a_{k+1})=a_0-a_n$。例：$\dfrac1{k(k+1)}=\dfrac1k-\dfrac1{k+1}$，故 $\sum_{k=1}^{n-1}\dfrac1{k(k+1)}=1-\dfrac1n$。
乘积：$\prod_{k=1}^na_k$，$n=0$ 时定义为 1；可用 $\lg\left(\prod a_k\right)=\sum\lg a_k$ 把乘积转为求和。

习题 A.1 概览：A.1-1 $\sum(2k-1)=n^2$；A.1-2 $\sum_{k=1}^n1/(2k-1)=\ln\sqrt n+O(1)$（用 $H_{2n}-\frac12H_n$）；A.1-3 $\sum k^2x^k=x(1+x)/(1-x)^3$；A.1-4 $\sum_{k\ge0}(k-1)/2^k=0$；A.1-5 求 $\sum_{k\ge1}(2k+1)x^{2k}$；A.1-6 用线性性证 $\sum O(f_k(i))=O(\sum f_k(i))$；A.1-7 求 $\prod_{k=1}^n2\cdot4^k=2^{n(n+2)}$；A.1-8 $\prod_{k=2}^n(1-1/k^2)=\frac{n+1}{2n}$（望远镜乘积）。

A.2 求和的界（Bounding summations）（PDF p.1170–1178）

1. 数学归纳法（mathematical induction）

证精确值：$\sum_{k=1}^{n+1}k=\frac12n(n+1)+(n+1)=\frac12(n+1)(n+2)$。
证上界（不必知道精确值）：证 $\sum_{k=0}^n3^k\le c3^n$。基例 $n=0$：$1\le c$。归纳：$\sum_{k=0}^{n+1}3^k\le c3^n+3^{n+1}=\left(\frac13+\frac1c\right)c3^{n+1}\le c3^{n+1}$，只要 $c\ge3/2$。故 $O(3^n)$。
常见错误：“证明”$\sum_{k=1}^nk=O(n)$：$\sum_{k=1}^{n+1}k=O(n)+(n+1)=O(n+1)$——错！大 O 里隐藏的“常数”随 $n$ 增长，并没有证明同一个常数对所有 $n$ 成立。用归纳证渐近界时必须写出显式常数。

2. 逐项放大（bounding the terms）

用最大项界住所有项：$\sum_{k=1}^nk\le\sum n=n^2$；一般地 $\sum_{k=1}^na_k\le n\cdot a_{\max}$。
若级数可被几何级数控制，这种方法太弱。若对所有 $k\ge0$ 有 $a_{k+1}/a_k\le r$，$0<r<1$ 为常数，则 $a_k\le a_0r^k$， $\sum_{k=0}^na_k\le\sum_{k=0}^\infty a_0r^k=\frac{a_0}{1-r}.$
例：$\sum_{k=1}^\infty k/3^k=\sum_{k=0}^\infty(k+1)/3^{k+1}$，$a_0=1/3$，比值 $\frac13\cdot\frac{k+2}{k+1}\le\frac23$，所以和 $\le\frac13\cdot\frac1{1-2/3}=1$。
常见错误：只证明相邻项比值 <1 就套几何级数。反例：调和级数比值 $k/(k+1)<1$，但 $\sum_{k=1}^\infty1/k=\lim\Theta(\lg n)=\infty$ 发散。必须存在常数 $r<1$ 使所有比值都 ≤ $r$；调和级数的比值可任意接近 1。

3. 拆分求和（splitting summations）

求 $\sum_{k=1}^nk$ 的下界：用最小项只得 $n$。拆成两半（设 $n$ 偶）： $\sum_{k=1}^nk=\sum_{k=1}^{n/2}k+\sum_{k=n/2+1}^nk\ge\sum_{k=1}^{n/2}0+\sum_{k=n/2+1}^n\frac n2=\left(\frac n2\right)^2=\Omega(n^2),$ 与上界 $O(n^2)$ 合起来是紧界。
忽略前常数项：若每项 $a_k$ 与 $n$ 无关，则对常数 $k_0$，$\sum_{k=0}^na_k=\Theta(1)+\sum_{k=k_0}^na_k$。例：$\sum_{k=0}^\infty k^2/2^k$，相邻项比 $\frac{(k+1)^2}{2k^2}\le\frac89$（当 $k\ge3$），故 $\sum_{k=0}^\infty\frac{k^2}{2^k}\le\sum_{k=0}^2\frac{k^2}{2^k}+\frac98\sum_{k=0}^\infty\left(\frac89\right)^k=O(1).$
调和级数的 $O(\lg n)$ 上界：把 $1..n$ 分成 $\lfloor\lg n\rfloor+1$ 段，第 $i$ 段为 $1/2^i$ 到 $1/2^{i+1}$（不含），每段至多 $2^i$ 项、每项 ≤ $1/2^i$，贡献 ≤1： $\sum_{k=1}^n\frac1k\le\sum_{i=0}^{\lfloor\lg n\rfloor}\sum_{j=0}^{2^i-1}\frac1{2^i+j}\le\sum_{i=0}^{\lfloor\lg n\rfloor}\sum_{j=0}^{2^i-1}\frac1{2^i}=\sum_{i=0}^{\lfloor\lg n\rfloor}1\le\lg n+1.\quad(A.10)$

4. 积分近似（approximation by integrals）

$f$ 单调递增时： $\int_{m-1}^nf(x)\,dx\le\sum_{k=m}^nf(k)\le\int_m^{n+1}f(x)\,dx.\quad(A.11)$
$f$ 单调递减时： $\int_m^{n+1}f(x)\,dx\le\sum_{k=m}^nf(k)\le\int_{m-1}^nf(x)\,dx.\quad(A.12)$
图 A.1 的直观：和是一排宽 1 的矩形面积，积分是曲线下面积；比较面积得一侧不等式，把矩形整体右移一个单位得另一侧。
调和数的紧估计：下界 $\sum_{k=1}^n\frac1k\ge\int_1^{n+1}\frac{dx}x=\ln(n+1)$ (A.13)；上界先拿掉第一项，$\sum_{k=2}^n\frac1k\le\int_1^n\frac{dx}x=\ln n$，得 $\sum_{k=1}^n\frac1k\le\ln n+1.\quad(A.14)$ （习题 A.2-5 问为何不直接对 $\sum_{k=1}^n1/k$ 用 (A.12) 上界：会出现 $\int_0^n dx/x$ 发散。）

习题与思考题概览：A.2-1 $\sum1/k^2$ 有常数上界；A.2-2 $\sum_{k=0}^{\lfloor\lg n\rfloor}\lceil n/2^k\rceil=O(n)$；A.2-3 用拆分证 $H_n=\Omega(\lg n)$；A.2-4 用积分近似 $\sum k^3$（约 $n^4/4$）；A.2-5 见上。思考题 A-1：求 $\sum_{k=1}^nk^r=\Theta(n^{r+1})$、$\sum\lg^sk=\Theta(n\lg^sn)$、$\sum k^r\lg^sk=\Theta(n^{r+1}\lg^sn)$ 的紧界（$r,s\ge0$ 为常数）。

附录注：Knuth [209] 是很好的参考；级数基本性质见 Apostol [18] 或 Thomas 等 [334] 的微积分教材。

附录 A 本章要点

必背公式：算术级数、平方/立方和、有限与无限几何级数、$\sum kx^k=x/(1-x)^2$、调和数 $\ln(n+1)\le H_n\le\ln n+1$、望远镜求和。
求界四法：归纳（写出显式常数）、逐项放大（最大项或几何比值界——比值须被常数 $r<1$ 界住）、拆分（丢弃前若干常数项、对半拆求下界、按 2 的幂分段）、积分近似（单调性决定方向）。

附录 A 与量化交易的关联

几何级数是贴现、年金、指数加权移动平均（EWMA）权重和的基础：衰减因子 $\lambda$ 的 EWMA 权重和为 $\sum\lambda^k=1/(1-\lambda)$，有效窗口长度、半衰期都由它推出；$\sum k\lambda^k=\lambda/(1-\lambda)^2$ 给出加权平均滞后（平均“年龄”），常用于评估信号滞后与因子衰减。
调和数 $H_n\approx\ln n$ 出现在集合覆盖贪心近似比、随机算法期望分析中；积分近似常用于把离散的成本、冲击累积近似为连续积分（如分段执行的累计冲击成本）。
望远镜求和对应累计收益/PnL 的分解（逐期差分求和等于首尾差）。
求界技巧本身主要用于算法复杂度分析，对回测系统、撮合引擎等的性能估算有用。

附录 A 推荐习题

A.1-3（$\sum k^2x^k$，矩计算常用）；A.1-8（望远镜乘积）；A.2-3（拆分求下界）；A.2-5（积分近似的边界陷阱）；思考题 A-1（多项式×对数求和的紧界，复杂度分析常用）。

附录 B 集合等（Sets, Etc.）（PDF p.1179–1203）

本附录复习离散数学中集合、关系、函数、图、树的记号、定义与基本性质。

B.1 集合（Sets）（PDF p.1179–1184）

集合（set）：可区分对象的汇集，对象称成员/元素（member/element），$x\in S$、$x\notin S$。列举表示如 $S=\{1,2,3\}$。集合中同一对象不能出现多次（允许重复的称多重集 multiset），元素无序：$\{1,2,3,1\}=\{1,2,3\}=\{3,2,1\}$。
特殊集合：$\emptyset$ 空集；$\mathbb Z$ 整数；$\mathbb R$ 实数；$\mathbb N=\{0,1,2,\dots\}$ 自然数（本书从 0 开始，有些作者从 1 开始）。
子集：$A\subseteq B$；真子集（proper subset）$A\subset B$ 即 $A\subseteq B$ 且 $A\ne B$（有的作者用 $\subset$ 表示普通子集）。性质：$A\subseteq A$；$A=B\iff A\subseteq B\wedge B\subseteq A$；子集关系传递；$\emptyset\subseteq A$。
描述法：$\{x:x\in\mathbb Z\text{ 且 }x/2\text{ 是整数}\}$，冒号读作“使得（such that）”，有的作者用竖线。
运算：交 $A\cap B$、并 $A\cup B$、差 $A-B=\{x:x\in A,x\notin B\}$。
运算律：空集律 $A\cap\emptyset=\emptyset$，$A\cup\emptyset=A$；幂等律；交换律；结合律；分配律 $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$，$A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$ (B.1)；吸收律 $A\cap(A\cup B)=A$，$A\cup(A\cap B)=A$；De Morgan 律 $A-(B\cap C)=(A-B)\cup(A-C)$，$A-(B\cup C)=(A-B)\cap(A-C)$ (B.2)（图 B.1 用 Venn 图说明）。
全集（universe） $U$ 与补集（complement）$\bar A=U-A$：$\bar{\bar A}=A$，$A\cap\bar A=\emptyset$，$A\cup\bar A=U$；De Morgan 律的补集形式 $\overline{B\cap C}=\bar B\cup\bar C$，$\overline{B\cup C}=\bar B\cap\bar C$。
不相交（disjoint）：$A\cap B=\emptyset$。非空集合族 $\mathcal S=\{S_i\}$ 是 $S$ 的划分（partition）：两两不相交且并为 $S$，即 $S$ 每个元素恰在一个 $S_i$ 中。
基数（cardinality）$|S|$：元素个数；两集合可一一对应则基数相同；$|\emptyset|=0$。基数为自然数的是有限集，否则无限集；能与 $\mathbb N$ 一一对应的是可数无限（countably infinite），否则不可数（uncountable）；$\mathbb Z$ 可数，$\mathbb R$ 不可数。
$|A\cup B|=|A|+|B|-|A\cap B|$ (B.3)，故 $|A\cup B|\le|A|+|B|$；不相交时取等号；$A\subseteq B\Rightarrow|A|\le|B|$。
$n$ 元集称 $n$-set，1 元集称单元素集（singleton），$k$ 个元素的子集称 $k$-subset。
幂集（power set） $2^S$：$S$ 所有子集（含 $\emptyset$ 和 $S$）的集合，如 $2^{\{a,b\}}=\{\emptyset,\{a\},\{b\},\{a,b\}\}$，$|2^S|=2^{|S|}$。
有序对（ordered pair） $(a,b)$ 形式定义为 $\{a,\{a,b\}\}$，$(a,b)\ne(b,a)$。笛卡儿积（Cartesian product） $A\times B=\{(a,b):a\in A,b\in B\}$，如 $\{a,b\}\times\{a,b,c\}$ 有 6 个有序对；$|A\times B|=|A|\cdot|B|$ (B.4)。$n$ 个集合的积是 $n$ 元组（n-tuple）集合，$|A_1\times\cdots\times A_n|=\prod|A_i|$；$A^n$ 为 $n$ 重积，$|A^n|=|A|^n$。$n$ 元组也可视为长度 $n$ 的有限序列。

习题概览：B.1-1 画分配律 Venn 图；B.1-2 推广 De Morgan 律到 $n$ 个集合；B.1-3 容斥原理（principle of inclusion and exclusion）：

|A_1\cup\cdots\cup A_n|=\sum|A_i|-\sum_{i<j}|A_i\cap A_j|+\sum_{i<j<k}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{n-1}|A_1\cap\cdots\cap A_n|;

B.1-4 奇自然数可数；B.1-5 幂集有 $2^{|S|}$ 个元素；B.1-6 用有序对递归定义 $n$ 元组。

B.2 关系（Relations）（PDF p.1184–1187）

二元关系（binary relation） $R$：$A\times B$ 的子集，$(a,b)\in R$ 记作 $aRb$；“$A$ 上的关系”指 $R\subseteq A\times A$。例：$\mathbb N$ 上的“小于”关系 $\{(a,b):a<b\}$。$n$ 元关系是 $A_1\times\cdots\times A_n$ 的子集。
性质：自反（reflexive） $aRa$（“=”“≤”自反，“<”不是）；对称（symmetric） $aRb\Rightarrow bRa$（“=”对称，“<”“≤”不是）；传递（transitive） $aRb\wedge bRc\Rightarrow aRc$（“<”“≤”“=”传递；$\{(a,b):a=b-1\}$ 不传递，$3R4$、$4R5$ 推不出 $3R5$）。
等价关系（equivalence relation）：自反+对称+传递。等价类 $[a]=\{b\in A:aRb\}$。例：$R=\{(a,b):a+b\text{ 为偶数}\}$ 是等价关系，$[4]=\{0,2,4,\dots\}$，$[3]=\{1,3,5,\dots\}$。
定理 B.1（等价关系即划分）：$A$ 上任一等价关系的等价类构成 $A$ 的划分；反之 $A$ 的任一划分确定一个以划分块为等价类的等价关系。证明：自反性使 $a\in[a]$，等价类非空且并为 $A$；若 $[a]$、$[b]$ 有公共元 $c$，则 $aRc$、$bRc$，由对称 $cRb$，由传递 $aRb$，进而 $[a]\subseteq[b]$ 且反之，故 $[a]=[b]$。反向：定义 $R=\{(a,b):\exists i, a,b\in A_i\}$，验证三条性质，且划分块就是等价类。
反对称（antisymmetric）：$aRb\wedge bRa\Rightarrow a=b$（如“≤”）。偏序（partial order）：自反+反对称+传递，定义了偏序的集合称偏序集（partially ordered set）。例：“是……的后代”（视个人为自身后代）。偏序集可能没有唯一“最大”元，但可以有多个极大元（maximal element）：不存在 $b\ne a$ 使 $aRb$。例：一堆大小不同的盒子，可能有多个装不进任何别的盒子的极大盒，却没有能装下所有盒子的最大盒（脚注：需把盒子视为能装进自身才构成偏序）。
全关系（total relation）：任意 $a,b$ 有 $aRb$ 或 $bRa$。既是偏序又是全关系的称全序/线性序（total/linear order），如 $\mathbb N$ 上的“≤”；“后代”关系不是全序。传递的全关系（不要求自反、反对称）称全预序（total preorder）。

习题概览：B.2-1 $\mathbb Z$ 子集上的“⊆”是偏序不是全序；B.2-2 模 $n$ 同余 $a\equiv b\pmod n$（存在整数 $q$ 使 $a-b=qn$）是等价关系，划分为 $n$ 个剩余类；B.2-3 分别举“自反对称不传递”“自反传递不对称”“对称传递不自反”的例子；B.2-4 有限集上既是等价关系又反对称，则等价类都是单元素集；B.2-5 Narcissus 教授称对称+传递 ⇒ 自反——错误，因为若 $a$ 与任何元素都无关系，就推不出 $aRa$（如空关系）。

B.3 函数（Functions）（PDF p.1187–1189）

函数（function） $f:A\to B$：$A$、$B$ 上的二元关系，对每个 $a\in A$ 恰有一个 $b\in B$ 使 $(a,b)\in f$，记 $b=f(a)$。$A$ 为定义域（domain），$B$ 为陪域（codomain）。不同的 $a$ 可映到同一 $b$，但一个 $a$ 不能映到两个 $b$。例：$f=\{(a,b):b=a\bmod2\}$ 是 $\mathbb N\to\{0,1\}$ 的函数；$g=\{(a,b):a+b\text{ 为偶数}\}$ 不是函数（$(1,3)$ 与 $(1,5)$ 都在其中）。
$a$ 为自变量（argument），$b$ 为在 $a$ 处的值（value）。两函数相等：定义域、陪域相同且处处取值相同。
有限序列：定义域为 $\{0,1,\dots,n-1\}$ 的函数，记 $\langle f(0),\dots,f(n-1)\rangle$；无限序列：定义域为 $\mathbb N$，如 Fibonacci 序列 $\langle0,1,1,2,3,5,8,13,21,\dots\rangle$。
定义域是笛卡儿积时省略多余括号：$f(a_1,\dots,a_n)$，各 $a_i$ 也称参数。
像（image）：$b=f(a)$ 是 $a$ 的像；$A'\subseteq A$ 的像 $f(A')=\{b:b=f(a),a\in A'\}$。**值域（range）**为 $f(A)$，如 $f(n)=2n$ 的值域是非负偶数。
满射（surjection / onto）：值域等于陪域。$f(n)=\lfloor n/2\rfloor$ 是 $\mathbb N\to\mathbb N$ 的满射；$f(n)=2n$ 不是（取不到 3），但它是 $\mathbb N\to$ 偶数的满射。
单射（injection / one-to-one）：$a\ne a'\Rightarrow f(a)\ne f(a')$。$f(n)=2n$ 是单射；$\lfloor n/2\rfloor$ 不是（2、3 都映到 1）。
双射（bijection / one-to-one correspondence）：既单又满。例：$f(n)=(-1)^n\lceil n/2\rceil$ 是 $\mathbb N\to\mathbb Z$ 的双射：$0\to0,1\to-1,2\to1,3\to-2,4\to2,\dots$。集合到自身的双射称置换（permutation）。双射有逆函数 $f^{-1}(b)=a\iff f(a)=b$；上例的逆为 $f^{-1}(m)=2m$（$m\ge0$），$-2m-1$（$m<0$）。

习题概览：B.3-1 有限集上单射 ⇒ $|A|\le|B|$，满射 ⇒ $|A|\ge|B|$；B.3-2 $f(x)=x+1$ 在 $\mathbb N$ 上不是双射（取不到 0），在 $\mathbb Z$ 上是；B.3-3 定义关系的逆使其与双射函数的逆一致；B.3-4 构造 $\mathbb Z\to\mathbb Z\times\mathbb Z$ 的双射。

B.4 图（Graphs）（PDF p.1188–1194）

有向图（directed graph / digraph） $G=(V,E)$：$V$ 为有限顶点集（vertex set），$E$ 为 $V$ 上的二元关系（边集 edge set）；允许自环（self-loop）。图 B.2(a)：$V=\{1,..,6\}$，$E=\{(1,2),(2,2),(2,4),(2,5),(4,1),(4,5),(5,4),(6,3)\}$，$(2,2)$ 是自环。
无向图（undirected graph）：边是无序对 $\{u,v\}$，$u\ne v$，习惯仍写 $(u,v)$，$(u,v)$ 与 $(v,u)$ 是同一条边；禁止自环。图 B.2(b)：$E=\{(1,2),(1,5),(2,5),(3,6)\}$，顶点 4 孤立。
关联：有向边 $(u,v)$ 离开（incident from / leaves） $u$、进入（incident to / enters） $v$；无向边关联于（incident on） $u,v$。邻接（adjacent）：$(u,v)\in E$ 则 $v$ 邻接于 $u$，无向图中对称，有向图中不一定，有向时记 $u\to v$。
度（degree）：无向图中关联边数；度为 0 称孤立（isolated）。有向图有出度（out-degree）、入度（in-degree），度=入度+出度（图 B.2(a) 顶点 2：入度 2、出度 3、度 5）。
路径（path）：长度 $k$ 的路径是顶点序列 $\langle v_0,\dots,v_k\rangle$，$(v_{i-1},v_i)\in E$；长度为边数；总有从 $u$ 到 $u$ 的 0 长路径。$u'$ 经 $p$ 从 $u$ 可达（reachable），有向时记 $u\overset{p}{\leadsto}u'$。简单路径（simple path）：顶点互异。（脚注：有的作者把这里的 path 叫 walk，把 simple path 叫 path。）子路径（subpath）：连续子序列。
回路/环（cycle）：有向图中 $v_0=v_k$ 且至少一条边；简单回路要求 $v_1..v_k$ 互异；自环是长度 1 的回路；循环移位得到的是同一回路（$\langle1,2,4,1\rangle$、$\langle2,4,1,2\rangle$、$\langle4,1,2,4\rangle$ 是同一回路）。无自环的有向图称简单有向图。无向图中回路要求 $k>0$、$v_0=v_k$ 且所有边互异，简单回路要求 $v_1..v_k$ 互异（如 $\langle1,2,5,1\rangle$）。无简单回路的图称无环（acyclic）。
连通（connected）：无向图中任意顶点互相可达；**连通分量（connected components）**是“可达”关系的等价类（图 B.2(b) 有 $\{1,2,5\},\{3,6\},\{4\}$ 三个）。强连通（strongly connected）：有向图任两点互相可达；强连通分量是“相互可达”关系的等价类（图 B.2(a) 有 $\{1,2,4,5\},\{3\},\{6\}$；$\{3,6\}$ 不是，因为从 3 到不了 6）。
同构（isomorphic）：存在双射 $f:V\to V'$ 使 $(u,v)\in E\iff(f(u),f(v))\in E'$（图 B.3(a)）；图 B.3(b) 两图都有 5 顶点 7 边，但一个有度 4 顶点另一个没有，故不同构。
子图（subgraph）：$V'\subseteq V$、$E'\subseteq E$。由 $V'$ 诱导的子图（induced subgraph）：$E'=\{(u,v)\in E:u,v\in V'\}$；图 B.2(a) 中 $\{1,2,3,6\}$ 诱导出边集 $\{(1,2),(2,2),(6,3)\}$。
无向图的有向版本：每条无向边换成两条反向有向边。有向图的无向版本：去方向、去自环、去重。有向图中 $v$ 是 $u$ 的邻居（neighbor）：$u\ne v$ 且 $(u,v)$ 或 $(v,u)\in E$。
特殊图：**完全图（complete graph）**任两点相邻；**二部图（bipartite graph）**顶点可分成 $V_1,V_2$ 使所有边跨两部分；**森林（forest）无环无向图；（自由）树（free tree）**连通无环无向图；DAG（directed acyclic graph）有向无环图。变体：**多重图（multigraph）**允许重边和自环；**超图（hypergraph）**每条超边连接任意顶点子集。
收缩（contraction）：无向图按边 $e=(u,v)$ 收缩，$V'=V-\{u,v\}\cup\{x\}$，删去 $(u,v)$，把与 $u$ 或 $v$ 相邻的 $w$ 改连到新顶点 $x$。

习题概览：B.4-1 握手引理（handshaking lemma）$\sum_{v}\text{degree}(v)=2|E|$；B.4-2 有路径必有简单路径，有向图有回路必有简单回路；B.4-3 连通无向图 $|E|\ge|V|-1$；B.4-4 无向图中可达是等价关系，有向图中只保证自反和传递；B.4-5 写出图 B.2 的无向/有向版本；B.4-6 超图可用二部图表示（一侧为顶点，一侧为超边，关联即相邻）。

B.5 树（Trees）（PDF p.1194–1203）

B.5.1 自由树（Free trees）

自由树：连通、无环的无向图（常省略“自由”）；无环但可能不连通的无向图是森林（forest）。图 B.4：(a) 自由树，(b) 森林（不连通故非树），(c) 含回路的连通图，既非树也非森林。

定理 B.2（自由树的性质）：对无向图 $G=(V,E)$，以下六条等价：

$G$ 是自由树；
任两顶点之间有唯一简单路径；
$G$ 连通，但去掉任一条边就不连通；
$G$ 连通，且 $|E|=|V|-1$；
$G$ 无环，且 $|E|=|V|-1$；
$G$ 无环，但加任一条边就产生回路。

证明链：

(1)⇒(2)：连通故至少一条简单路径。若有两条不同简单路径 $p_1,p_2$，设 $w$ 为第一次分叉点（在 $p_1$ 上后继为 $x$、在 $p_2$ 上后继为 $y$，$x\ne y$），$z$ 为 $w$ 之后第一次重新汇合点；$p_1$ 上 $w\to x\to z$ 的子路径 $p'$ 与 $p_2$ 上 $w\to y\to z$ 的子路径 $p''$ 只共享端点，$p'$ 接 $p''$ 的反向构成回路，矛盾（图 B.5）。
(2)⇒(3)：唯一路径蕴含连通；任一边 $(u,v)$ 本身就是 $u$ 到 $v$ 的唯一路径，去掉它 $u,v$ 不连通。
(3)⇒(4)：连通推出 $|E|\ge|V|-1$（习题 B.4-3）。对 $n$ 归纳证 $|E|\le|V|-1$：$n=1,2$ 时成立；$n\ge3$ 时去掉任一边把图分成 $k\ge2$ 个（实际 $k=2$）连通分量，每个分量仍满足 (3)，由归纳 $|E_i|\le|V_i|-1$，合计 ≤ $|V|-k\le|V|-2$，加回去掉的边得 $|E|\le|V|-1$。
(4)⇒(5)：设有含 $k$ 个顶点的简单回路，子图 $G_k$ 有 $|V_k|=|E_k|=k$。若 $k<|V|$，由连通性存在 $V-V_k$ 中顶点 $v_{k+1}$ 与某 $v_i\in V_k$ 相邻，加入后仍有 $|V_{k+1}|=|E_{k+1}|=k+1$；持续扩展到 $G_n$，$|E_n|=|V|$，于是 $|E|\ge|V|$，与 $|E|=|V|-1$ 矛盾。
(5)⇒(6)：设有 $k$ 个连通分量，每个都是自由树，由 (1)⇒(5) 总边数 $|V|-k$，故 $k=1$，$G$ 是树；由 (1)⇒(2) 任两点有唯一简单路径，加边必成回路。
(6)⇒(1)：对任意不相邻的 $u,v$，加边 $(u,v)$ 产生回路，回路除该边外都在 $G$ 中，所以 $G$ 中有 $u$ 到 $v$ 的路径，$G$ 连通。

B.5.2 有根树与有序树（Rooted and ordered trees）

有根树（rooted tree）：指定一个顶点为根（root）的自由树；其顶点称结点（node）（脚注：图论中 node 常与 vertex 同义，本书只用 node 指有根树的顶点）。图 B.6(a)：12 个结点，根为 7。
从根 $r$ 到 $x$ 的唯一简单路径上的任一结点 $y$ 是 $x$ 的祖先（ancestor），$x$ 是 $y$ 的后代（descendant）；每个结点是自身的祖先和后代；$y\ne x$ 时称真祖先/真后代（proper）。以 $x$ 为根的**子树（subtree）**是 $x$ 的后代诱导的树（图中以 8 为根的子树含 8、6、5、9）。
路径最后一条边为 $(y,x)$，则 $y$ 是 $x$ 的父结点（parent），$x$ 是 $y$ 的孩子（child）；根是唯一没有父结点的结点；同父的结点是兄弟（siblings）；无孩子的结点是叶（leaf）/外部结点（external node），否则是内部结点（internal node）。
有根树中结点的度是孩子数（脚注：与自由树中“相邻顶点数”不同，父结点不计入）。深度（depth）：根到 $x$ 的简单路径长度。层（level）：同一深度的所有结点。结点的高度（height）：从该结点向下到叶的最长简单路径的边数；树高为根的高度，也等于最大结点深度（图 B.6(a) 树高 4）。
有序树（ordered tree）：每个结点的孩子有先后次序。图 B.6(a)(b) 作为有根树相同，作为有序树不同（结点 3 的孩子顺序不同）。

B.5.3 二叉树与位置树（Binary and positional trees）

二叉树（binary tree）递归定义：要么不含结点（空树 empty tree / null tree，记 NIL），要么由三部分不相交结点集组成：根、称为左子树的二叉树、称为右子树的二叉树。非空左子树的根是左孩子（left child），右子树类似；子树为 NIL 时称该孩子缺失（absent/missing）。
二叉树不只是“每个结点度 ≤2 的有序树”：只有一个孩子时，它是左孩子还是右孩子是有区别的（图 B.7(a)(b) 作为有序树相同，作为二叉树不同：(a) 中结点 7 的左孩子是 5，(b) 中右孩子是 5）。
用**满二叉树（full binary tree）**表示位置信息：把每个缺失的孩子补成一个无孩子的结点（图中方形叶），得到每个结点要么是叶要么度恰为 2 的有序树（图 B.7(c)）。
位置树（positional tree）：孩子以互异正整数标号，第 $i$ 个孩子缺失即无标号 $i$ 的孩子。$k$ 叉树（k-ary tree）：标号大于 $k$ 的孩子都缺失；二叉树即 $k=2$。
完全 $k$ 叉树（complete k-ary tree）：所有叶深度相同、所有内部结点度为 $k$（图 B.8：高 3 的完全二叉树，8 个叶、7 个内部结点）。高为 $h$ 时叶数 $k^h$；$n$ 个叶时高为 $\log_kn$；内部结点数 $1+k+\cdots+k^{h-1}=\sum_{i=0}^{h-1}k^i=\frac{k^h-1}{k-1},$ 完全二叉树有 $2^h-1$ 个内部结点。

习题概览：B.5-1 画出 3 个顶点 $x,y,z$ 的所有自由树、以 $x$ 为根的所有有根树、有序树、二叉树；B.5-2 DAG 中若某点 $v_0$ 到每个顶点都有唯一路径，则其无向版本是树；B.5-3 非空二叉树中度为 2 的结点比叶少 1，由此满二叉树内部结点数比叶少 1；B.5-4 $n$ 结点非空二叉树高度 ≥ $\lfloor\lg n\rfloor$；B.5-5 满二叉树外部路径长度 $e$ = 内部路径长度 $i$ + $2n$（$n$ 为内部结点数）；B.5-6 Kraft 不等式：深度 $d$ 的叶赋权 $2^{-d}$，所有叶权和 ≤1；B.5-7 $L\ge2$ 个叶的二叉树必有一棵子树叶数在 $[L/3,2L/3]$ 之间。

附录 B 思考题与附录注

B-1 图着色：$k$-着色 $c:V\to\{0..k-1\}$。(a) 任何树可 2-着色；(b) 二部图 ⇔ 可 2-着色 ⇔ 无奇数长回路；(c) 最大度为 $d$ 的图可用 $d+1$ 色着色（贪心）；(d) 边数 $O(|V|)$ 的图可用 $O(\sqrt{|V|})$ 色着色。
B-2 友谊图（友谊对称、不自反）：(a) 至少两人的群体中必有两人在群内朋友数相同（鸽巢原理）；(b) 任 6 人中必有 3 人互为朋友或 3 人互不相识（Ramsey 数 $R(3,3)=6$）；(c) 任何群体可分成两组，使每人至少一半朋友在另一组（局部翻转论证/最大割）；(d) 若每人是至少一半人的朋友，则可围桌而坐使每人两侧都是朋友（Dirac 定理：哈密顿回路存在）。
B-3 树的二分：(a) 任意 $n$ 顶点二叉树去掉一条边可把顶点分为 $|A|,|B|\le3n/4$ 两部分；(b) 常数 3/4 在最坏情况下最优；(c) 去掉至多 $O(\lg n)$ 条边可分成恰为 $\lfloor n/2\rfloor$ 和 $\lceil n/2\rceil$ 的两部分。
附录注：Boole 在 1854 年的书中开创符号逻辑并引入许多集合记号；Cantor 1874–1895 年创立现代集合论（主要研究无限基数）；“函数”一词归于 Leibniz；图论起源于 1736 年 Euler 证明哥尼斯堡七桥不可能各走一次回到起点。Harary [160] 是图论定义和结果的有用汇编。

附录 B 本章要点

集合运算律（分配律、吸收律、De Morgan 律）、容斥原理、幂集基数 $2^{|S|}$、笛卡儿积基数相乘。
关系三性质（自反、对称、传递）定义等价关系；等价关系与划分一一对应（定理 B.1）；反对称 → 偏序；全关系 → 全序；极大元 vs 最大元。
函数的单射、满射、双射与逆；有限/无限序列作为函数。
图的基本术语（有向/无向、度、路径、简单路径、回路、连通与强连通分量、同构、诱导子图、二部图、DAG、多重图、超图、收缩），握手引理。
自由树六条等价刻画（定理 B.2），尤其 $|E|=|V|-1$；有根树、有序树、二叉树、位置树、$k$ 叉树的区别；完全 $k$ 叉树叶数 $k^h$、内部结点 $(k^h-1)/(k-1)$。

附录 B 与量化交易的关联

等价关系与划分：行业分类、风格分组、板块聚类本质上是对股票集合的划分；分组中性化（行业中性、市值分组中性）就是在等价类内做去均值/标准化。
偏序：多目标比较（收益更高且回撤更小）只构成偏序，Pareto 前沿就是“极大元”集合，而不存在唯一最大元——参数寻优与策略筛选时要理解这一点。
图：相关性网络、最小生成树（股票相关性 MST 聚类）、强连通分量（交易对手/持股关系网络）、二部图（基金—持仓、订单—成交匹配）、DAG（因子计算依赖、任务调度流水线）都直接使用本附录的术语；连通分量与等价类对应。
树：决策树/梯度提升树模型、层次聚类树（HRP 风险平价中的树形结构）、订单簿的平衡树实现都依赖这些定义。
集合基数与容斥原理用于事件计数（如多个信号同时触发的样本统计）。

附录 B 推荐习题

B.1-3（容斥原理）；B.2-5（对称+传递不能推出自反，经典陷阱）；B.4-1（握手引理）；B.5-3、B.5-6（二叉树叶数关系与 Kraft 不等式，后者与编码/信息论相关）；思考题 B-1(b)（二部图三种等价刻画）、B-2(b)（Ramsey 论证）。

附录 C 计数与概率（Counting and Probability）（PDF p.1204–1237）

本附录复习初等组合与概率论。多数章节不需要概率，但部分章节必不可少。C.1 计数（排列、组合）；C.2 概率公理与分布；C.3 随机变量、期望、方差；C.4 伯努利试验导出的几何分布与二项分布；C.5（进阶）二项分布的尾部。

C.1 计数（Counting）（PDF p.1204–1210）

计数理论回答“有多少”而不实际枚举，如“有多少个不同的 $n$ 位数”“$n$ 个不同元素有多少种排列”。

加法法则（rule of sum）：从两个不相交集合之一选一个元素的方式数是两集合基数之和，$|A\cup B|=|A|+|B|$（由 B.3）。例：车牌每位可以是字母或数字，$26+10=36$ 种。
乘法法则（rule of product）：选有序对的方式数是两者方式数之积，$|A\times B|=|A|\cdot|B|$（即 B.4）。例：28 种口味冰淇淋、4 种配料，一球一料的圣代有 $28\times4=112$ 种。
串（string）：有限集 $S$ 上的元素序列。长度 3 的二进制串有 8 个：000,…,111。长度 $k$ 的串称 $k$-串（k-string）；**子串（substring）**是连续元素的有序序列，长度 $k$ 的称 $k$-子串（如 010 是 01101001 从第 4 位开始的 3-子串，111 不是其子串）。$S$ 上的 $k$-串可视为 $S^k$ 的元素，共 $|S|^k$ 个；$n$-集上的 $k$-串有 $n^k$ 个，二进制 $k$-串有 $2^k$ 个。
排列（permutation）：有限集所有元素的有序序列，每个恰出现一次。$\{a,b,c\}$ 有 6 个排列 abc, acb, bac, bca, cab, cba；$n$ 个元素有 $n!$ 个排列。
$k$-排列（k-permutation）：取 $k$ 个不重复元素的有序序列。$\{a,b,c,d\}$ 的 2-排列有 12 个。$n$-集的 $k$-排列数： $n(n-1)(n-2)\cdots(n-k+1)=\frac{n!}{(n-k)!}.\quad(C.1)$
$k$-组合（k-combination）：$n$-集的 $k$-子集。$\{a,b,c,d\}$ 有 6 个 2-组合 ab, ac, ad, bc, bd, cd。每个 $k$-组合恰对应 $k!$ 个 $k$-排列，所以 $k$-组合数为 $\frac{n!}{k!(n-k)!}.\quad(C.2)$ $k=0$ 时为 1（不是 0），因为 $0!=1$。
二项式系数（binomial coefficients） $\binom nk$（读作 “n choose k”）$=\dfrac{n!}{k!(n-k)!}$，对称性 $\binom nk=\binom n{n-k}$ (C.3)。来自二项式展开： $(x+y)^n=\sum_{k=0}^n\binom nkx^ky^{n-k}.\quad(C.4)$ 特例 $x=y=1$：$2^n=\sum_{k=0}^n\binom nk$，对应按 1 的个数给 $2^n$ 个二进制 $n$-串分类（含恰 $k$ 个 1 的有 $\binom nk$ 个）。
二项式系数的界：
- 下界（$1\le k\le n$）：$\binom nk=\dfrac nk\cdot\dfrac{n-1}{k-1}\cdots\dfrac{n-k+1}1\ge\left(\dfrac nk\right)^k$。
- 上界：由 Stirling 近似推出 $k!\ge(k/e)^k$，故 $\binom nk\le\dfrac{n^k}{k!}\le\left(\dfrac{en}k\right)^k$ (C.5)。
- 对 $0\le k\le n$（约定 $0^0=1$）：$\binom nk\le\dfrac{n^n}{k^k(n-k)^{n-k}}$ (C.6)。令 $k=\lambda n$，$0\le\lambda\le1$： $\binom n{\lambda n}\le\left(\left(\frac1\lambda\right)^\lambda\left(\frac1{1-\lambda}\right)^{1-\lambda}\right)^n=2^{nH(\lambda)},$ 其中二元熵函数（binary entropy function） $H(\lambda)=-\lambda\lg\lambda-(1-\lambda)\lg(1-\lambda)$ (C.7)，约定 $0\lg0=0$，故 $H(0)=H(1)=0$。

习题概览：C.1-1 $n$-串的 $k$-子串数 $n-k+1$，子串总数 $n(n+1)/2$（不计空串）；C.1-2 $n$ 输入 1 输出布尔函数有 $2^{2^n}$ 个，$m$ 输出有 $2^{m2^n}$ 个；C.1-3 $n$ 人围圆桌（旋转视为相同）有 $(n-1)!$ 种；C.1-4 从 1..99 选三个不同数使和为偶数的方式数；C.1-5 $\binom nk=\frac nk\binom{n-1}{k-1}$ (C.8)；C.1-6 $\binom nk=\frac n{n-k}\binom{n-1}k$；C.1-7 Pascal 恒等式 $\binom nk=\binom{n-1}k+\binom{n-1}{k-1}$（按某个特定元素是否被选分类）；C.1-8 画 $n=0..6$ 的 Pascal 三角；C.1-9 $\sum_{i=1}^ni=\binom{n+1}2$；C.1-10 $\binom nk$ 在 $k=\lfloor n/2\rfloor$ 或 $\lceil n/2\rceil$ 取最大；C.1-11 $\binom n{j+k}\le\binom nj\binom{n-j}k$ (C.9)，给代数证明和组合论证及不等的例子；C.1-12 归纳证明 (C.6)；C.1-13 用 Stirling 证 $\binom{2n}n=\dfrac{2^{2n}}{\sqrt{\pi n}}(1+O(1/n))$ (C.10)；C.1-14 求导证 $H(\lambda)$ 在 $\lambda=1/2$ 取最大值 $H(1/2)=1$；C.1-15 $\sum_{k=0}^n\binom nkk=n2^{n-1}$ (C.11)。

C.2 概率（Probability）（PDF p.1210–1217）

样本空间（sample space） $S$：其元素称基本事件（elementary events），可看作试验的可能结果。抛两枚可区分硬币：$S=\{HH,HT,TH,TT\}$。
事件（event）：$S$ 的子集（脚注：一般分布中并非所有子集都是事件，常见于不可数样本空间；事件集须对补、可数并、可数交封闭；本书多为有限或可数样本空间，视所有子集为事件，连续均匀分布是例外）。“一正一反”事件为 $\{HT,TH\}$。$S$ 为必然事件（certain event），$\emptyset$ 为空事件（null event）；$A\cap B=\emptyset$ 称互斥（mutually exclusive）；基本事件两两互斥。
概率公理（probability axioms）：概率分布 $\Pr\{\cdot\}$ 是从事件到实数的映射，满足
1. $\Pr\{A\}\ge0$；
2. $\Pr\{S\}=1$（归一化，选 1 只是自然方便）；
3. 对互斥事件 $\Pr\{A\cup B\}=\Pr\{A\}+\Pr\{B\}$；更一般地，对有限或可数无穷个两两互斥事件 $\Pr\{\bigcup_iA_i\}=\sum_i\Pr\{A_i\}$。
推论：$\Pr\{\emptyset\}=0$；$A\subseteq B\Rightarrow\Pr\{A\}\le\Pr\{B\}$；$\Pr\{\bar A\}=1-\Pr\{A\}$； $\Pr\{A\cup B\}=\Pr\{A\}+\Pr\{B\}-\Pr\{A\cap B\}\ (C.12)\ \le\Pr\{A\}+\Pr\{B\}\ (C.13).$ 例：四个基本事件各 1/4，至少一个正面的概率 $\Pr\{HH,HT,TH\}=3/4$，或 $1-\Pr\{TT\}=3/4$。
离散概率分布（discrete）：定义在有限或可数无穷样本空间上，$\Pr\{A\}=\sum_{s\in A}\Pr\{s\}$。有限 $S$ 上每个基本事件概率 $1/|S|$ 即均匀分布（uniform probability distribution），也说“从 $S$ 中随机选取一个元素”。例：公平硬币抛 $n$ 次，$S=\{H,T\}^n$，$|S|=2^n$，每个串概率 $1/2^n$；“恰 $k$ 次正面”事件大小 $\binom nk$，概率 $\binom nk/2^n$。
连续均匀分布（continuous uniform probability distribution）：定义在闭区间 $[a,b]$（$a<b$）上。不可数个点无法每点都赋相同正概率（与公理 2、3 冲突），所以只对部分子集定义概率：对 $a\le c\le d\le b$，$\Pr\{[c,d]\}=\dfrac{d-c}{b-a}$。单点概率为 0；去掉端点得开区间 $(c,d)$，由 $[c,d]=[c,c]\cup(c,d)\cup[d,d]$ 及公理 3 得 $\Pr\{[c,d]\}=\Pr\{(c,d)\}$。事件集包含有限或可数个开、闭区间之并及某些更复杂集合。
条件概率（conditional probability）：例：朋友抛两枚公平硬币并告诉你至少一枚正面，两枚都是正面的概率为 1/3（排除 TT 后剩三种等可能）。定义 $\Pr\{A\mid B\}=\frac{\Pr\{A\cap B\}}{\Pr\{B\}},\quad\Pr\{B\}\ne0.\quad(C.14)$ 直观：已知 $B$ 发生，把 $B$ 中基本事件的概率除以 $\Pr\{B\}$ 归一化。上例 $\Pr\{A\mid B\}=(1/4)/(3/4)=1/3$。
独立（independent）：$\Pr\{A\cap B\}=\Pr\{A\}\Pr\{B\}$ (C.15)，若 $\Pr\{B\}\ne0$ 等价于 $\Pr\{A\mid B\}=\Pr\{A\}$。例：两枚独立公平硬币，“第一枚正面”与“两枚不同”各 1/2、同时发生 1/4，因此独立——尽管直觉上二者都依赖第一枚。反例：两枚焊在一起（同正或同反，各 1/2），各自正面概率 1/2，但同时正面概率 $1/2\ne1/4$，不独立。
两两独立（pairwise independent）：所有 $i<j$ 有 $\Pr\{A_i\cap A_j\}=\Pr\{A_i\}\Pr\{A_j\}$。（相互）独立（mutually independent）：任意 $k$ 个（$2\le k\le n$）的交的概率等于概率之积。例：$A_1$ 第一枚正面、$A_2$ 第二枚正面、$A_3$ 两枚不同，各 1/2，两两交各 1/4，所以两两独立；但 $\Pr\{A_1\cap A_2\cap A_3\}=0\ne1/8$，不相互独立。常见误区：两两独立不等于相互独立。
Bayes 定理（Bayes's theorem）：由 $\Pr\{A\cap B\}=\Pr\{B\}\Pr\{A\mid B\}=\Pr\{A\}\Pr\{B\mid A\}$ (C.16) 得 $\Pr\{A\mid B\}=\frac{\Pr\{A\}\Pr\{B\mid A\}}{\Pr\{B\}}.\quad(C.17)$ 分母是归一化常数，由 $B=(B\cap A)\cup(B\cap\bar A)$（互斥）得 $\Pr\{B\}=\Pr\{A\}\Pr\{B\mid A\}+\Pr\{\bar A\}\Pr\{B\mid\bar A\}$，于是 $\Pr\{A\mid B\}=\frac{\Pr\{A\}\Pr\{B\mid A\}}{\Pr\{A\}\Pr\{B\mid A\}+\Pr\{\bar A\}\Pr\{B\mid\bar A\}}.\quad(C.18)$ 例：一枚公平硬币、一枚总出正面的偏硬币，随机选一枚抛两次，都为正面，求选中偏硬币的概率。$\Pr\{A\}=1/2$，$\Pr\{B\mid A\}=1$，$\Pr\{\bar A\}=1/2$，$\Pr\{B\mid\bar A\}=1/4$， $\Pr\{A\mid B\}=\frac{(1/2)\cdot1}{(1/2)\cdot1+(1/2)\cdot(1/4)}=\frac45.$

习题概览：C.2-1 Rosencrantz 抛 1 次、Guildenstern 抛 2 次，前者正面更多的概率（=1/4）；C.2-2 Boole 不等式（union bound）$\Pr\{A_1\cup A_2\cup\cdots\}\le\sum\Pr\{A_i\}$ (C.19)；C.2-3 10 张牌洗匀后依次取 3 张恰为递增的概率（1/6）；C.2-4 $\Pr\{A\mid B\}+\Pr\{\bar A\mid B\}=1$；C.2-5 链式法则 $\Pr\{A_1\cap\cdots\cap A_n\}=\Pr\{A_1\}\Pr\{A_2\mid A_1\}\cdots\Pr\{A_n\mid A_1\cap\cdots\cap A_{n-1}\}$；C.2-6 用公平硬币以概率 $a/b$ 产生正面（按 $a/b$ 的二进制展开逐位比较，期望 $O(1)$ 次抛掷）；C.2-7 构造 $n$ 个两两独立但任意 $k>2$ 个都不相互独立的事件；C.2-8 条件独立（conditionally independent） $\Pr\{A\cap B\mid C\}=\Pr\{A\mid C\}\Pr\{B\mid C\}$，举不独立但条件独立的例子；C.2-9 Monty Hall 问题（换门中奖概率从 1/3 升到 2/3）；C.2-10 三囚犯问题（X 的生还概率仍为 1/3）。

C.3 离散随机变量（Discrete random variables）（PDF p.1217–1222）

（离散）随机变量（random variable） $X$：从有限或可数无穷样本空间到实数的函数。事件 $X=x$ 即 $\{s\in S:X(s)=x\}$，$\Pr\{X=x\}=\sum_{s:X(s)=x}\Pr\{s\}$。$f(x)=\Pr\{X=x\}$ 称概率密度函数（probability density function）（离散情形即概率质量函数），$\Pr\{X=x\}\ge0$，$\sum_x\Pr\{X=x\}=1$。
例：掷两颗六面骰，36 个等可能基本事件，$X$ 为两数最大值，$\Pr\{X=3\}=5/36$（(1,3),(2,3),(3,3),(3,2),(3,1)）。
联合概率密度函数（joint pdf） $f(x,y)=\Pr\{X=x\text{ 且 }Y=y\}$；边缘：$\Pr\{Y=y\}=\sum_x\Pr\{X=x,Y=y\}$，$\Pr\{X=x\}=\sum_y\Pr\{X=x,Y=y\}$；条件：$\Pr\{X=x\mid Y=y\}=\dfrac{\Pr\{X=x,Y=y\}}{\Pr\{Y=y\}}$。
$X$、$Y$ 独立：对所有 $x,y$，$\Pr\{X=x,Y=y\}=\Pr\{X=x\}\Pr\{Y=y\}$。同一样本空间上的随机变量的和、积及其他函数也是随机变量。
期望（expected value / expectation / mean）： $E[X]=\sum_xx\Pr\{X=x\},\quad(C.20)$ 在和有限或绝对收敛时良定，也记 $\mu_X$ 或 $\mu$。例：抛两枚公平硬币，每个正面赚 3 美元、每个反面亏 2 美元，$E[X]=6\cdot\frac14+1\cdot\frac12-4\cdot\frac14=1$。
期望线性性（linearity of expectation）：$E[X+Y]=E[X]+E[Y]$ (C.21)，即使不独立也成立，可推广到有限和与绝对收敛的和；这是用指示随机变量做概率分析的关键（5.2 节）。$E[g(X)]=\sum_xg(x)\Pr\{X=x\}$；$E[aX]=aE[X]$ (C.22)；$E[aX+Y]=aE[X]+E[Y]$ (C.23)。
独立时 $E[XY]=E[X]E[Y]$（推导：$\sum_x\sum_yxy\Pr\{X=x\}\Pr\{Y=y\}$ 分解为两个和之积）；$n$ 个相互独立时 $E[X_1\cdots X_n]=E[X_1]\cdots E[X_n]$ (C.24)。
取值于 $\mathbb N$ 的随机变量的尾和公式： $E[X]=\sum_{i=0}^\infty i\Pr\{X=i\}=\sum_{i=0}^\infty i(\Pr\{X\ge i\}-\Pr\{X\ge i+1\})=\sum_{i=1}^\infty\Pr\{X\ge i\},\quad(C.25)$ 因为每个 $\Pr\{X\ge i\}$ 被加 $i$ 次、减 $i-1$ 次（$\Pr\{X\ge0\}$ 加 0 次）。
Jensen 不等式：凸函数 $f$（对所有 $x,y$ 和 $0\le\lambda\le1$ 有 $f(\lambda x+(1-\lambda)y)\le\lambda f(x)+(1-\lambda)f(y)$）满足 $E[f(X)]\ge f(E[X])$ (C.26)（期望存在且有限时）。
方差（variance）：期望不反映离散程度。例：$X$ 等概率取 1/4、3/4，$Y$ 等概率取 0、1，期望都是 1/2，但 $Y$ 离均值更远。 $\mathrm{Var}[X]=E[(X-E[X])^2]=E[X^2-2XE[X]+E^2[X]]=E[X^2]-2E^2[X]+E^2[X]=E[X^2]-E^2[X].\quad(C.27)$ （$E[X]$ 是实数而非随机变量，所以 $E[E^2[X]]=E^2[X]$，$E[XE[X]]=E^2[X]$ 由 (C.22)。）改写得 $E[X^2]=\mathrm{Var}[X]+E^2[X]$ (C.28)。$\mathrm{Var}[aX]=a^2\mathrm{Var}[X]$；$X,Y$ 独立时 $\mathrm{Var}[X+Y]=\mathrm{Var}[X]+\mathrm{Var}[Y]$；一般地，$n$ 个两两独立的随机变量 $\mathrm{Var}[\sum X_i]=\sum\mathrm{Var}[X_i]$ (C.29)（注意只需两两独立）。
标准差（standard deviation） $\sigma_X$：方差的非负平方根，方差记 $\sigma^2$。

习题概览：C.3-1 两骰之和的期望 7、最大值的期望 $161/36$；C.3-2 随机排列数组中最大元、最小元下标的期望均为 $(n+1)/2$；C.3-3 三骰赌博游戏（押中 $k$ 个骰赢 $k$ 美元，否则输 1 美元）期望收益为 $-17/216$；C.3-4 非负随机变量 $E[\max(X,Y)]\le E[X]+E[Y]$；C.3-5 $X,Y$ 独立则 $f(X),g(Y)$ 独立；C.3-6 Markov 不等式 $\Pr\{X\ge t\}\le E[X]/t$（$X\ge0$，$t>0$）(C.30)；C.3-7 若处处 $X(s)\ge X'(s)$，则 $\Pr\{X\ge t\}\ge\Pr\{X'\ge t\}$；C.3-8 $E[X^2]\ge E^2[X]$（方差非负）；C.3-9 0-1 变量 $\mathrm{Var}[X]=E[X]E[1-X]$；C.3-10 证明 $\mathrm{Var}[aX]=a^2\mathrm{Var}[X]$。

C.4 几何分布与二项分布（The geometric and binomial distributions）（PDF p.1222–1229）

伯努利试验（Bernoulli trial）：只有两种结果的试验，成功概率 $p$，失败概率 $q=1-p$。说“一组伯努利试验”时默认相互独立且成功概率都为 $p$。

几何分布（geometric distribution）

$X$ 为获得首次成功所需的试验次数，取值 $\{1,2,\dots\}$： $\Pr\{X=k\}=q^{k-1}p,\quad k\ge1.\quad(C.31)$ （前 $k-1$ 次失败、第 $k$ 次成功。）图 C.1：$p=1/3$ 的几何分布，期望 3。
期望（$q<1$，用 A.8）： $E[X]=\sum_{k=1}^\infty kq^{k-1}p=\frac pq\sum_{k=0}^\infty kq^k=\frac pq\cdot\frac q{(1-q)^2}=\frac pq\cdot\frac q{p^2}=\frac1p.\quad(C.32)$ 直观：平均要 $1/p$ 次才成功。方差（用习题 A.1-3）：$\mathrm{Var}[X]=q/p^2$ (C.33)。
例：反复掷两颗骰子直到点数和为 7 或 11。36 种结果中 6 种为 7、2 种为 11，$p=8/36=2/9$，平均需掷 $9/2=4.5$ 次。

二项分布（binomial distribution）

$n$ 次伯努利试验中成功次数 $X$，取值 $0..n$： $\Pr\{X=k\}=\binom nkp^kq^{n-k}.\quad(C.34)$ 记 $b(k;n,p)=\binom nkp^k(1-p)^{n-k}$ (C.35)。“二项”之名来自它是 $(p+q)^n$ 展开的第 $k$ 项，故 $\sum_{k=0}^nb(k;n,p)=1$ (C.36)。图 C.2：$b(k;15,1/3)$，期望 $np=5$。
期望的两种算法：
- 代数法（用 C.8 $k\binom nk=n\binom{n-1}{k-1}$ 和 C.36）：$E[X]=\sum_kk\binom nkp^kq^{n-k}=np\sum_{k=1}^n\binom{n-1}{k-1}p^{k-1}q^{n-k}=np\sum_{k=0}^{n-1}b(k;n-1,p)=np$ (C.37)。
- 期望线性性（简得多）：$X_i$ 为第 $i$ 次试验的成功数，$E[X_i]=p\cdot1+q\cdot0=p$，$E[X]=\sum E[X_i]=np$ (C.38)。
方差：$X_i\in\{0,1\}$ 故 $X_i^2=X_i$，$E[X_i^2]=p$，$\mathrm{Var}[X_i]=p-p^2=pq$ (C.39)；由独立性和 (C.29)，$\mathrm{Var}[X]=npq$ (C.40)。
单峰性：相邻项之比 $\frac{b(k;n,p)}{b(k-1;n,p)}=\frac{\binom nkp^kq^{n-k}}{\binom n{k-1}p^{k-1}q^{n-k+1}}=\frac{(n-k+1)p}{kq}=1+\frac{(n+1)p-k}{kq}.\quad(C.41)$ 比值 >1 当且仅当 $(n+1)p-k>0$：$k<(n+1)p$ 时递增，$k>(n+1)p$ 时递减。若 $(n+1)p$ 是整数，则在 $k=(n+1)p$ 和 $k-1=np-q$ 两处同取最大；否则在满足 $np-q<k<(n+1)p$ 的唯一整数处取最大。

引理 C.1：$n\ge0$，$0<p<1$，$q=1-p$，$0\le k\le n$，则

b(k;n,p)\le\left(\frac{np}k\right)^k\left(\frac{nq}{n-k}\right)^{n-k}.

证明：由 (C.6)，$b(k;n,p)\le\left(\frac nk\right)^k\left(\frac n{n-k}\right)^{n-k}p^kq^{n-k}$，整理即得。

习题概览：C.4-1 验证几何分布满足公理 2；C.4-2 每次抛 6 枚公平硬币，平均抛几轮才能得到 3 正 3 反（成功概率 $\binom63/64=20/64$，期望 $3.2$ 轮）；C.4-3 $b(k;n,p)=b(n-k;n,q)$；C.4-4 二项分布最大值约为 $1/\sqrt{2\pi npq}$；C.4-5 $p=1/n$ 时 $n$ 次试验无成功、恰一次成功的概率都约为 $1/e$；C.4-6 两人各抛 $n$ 次，正面数相同的概率为 $\binom{2n}n/4^n$，并推出 $\sum_k\binom nk^2=\binom{2n}n$；C.4-7 $b(k;n,1/2)\le2^{nH(k/n)-n}$；C.4-8 各次成功概率 $p_i\le p$ 时 $\Pr\{X<k\}\ge\sum_{i=0}^{k-1}b(i;n,p)$；C.4-9 $p'_i\ge p_i$ 时 $\Pr\{X'\ge k\}\ge\Pr\{X\ge k\}$（耦合论证，用习题 C.3-7）。

C.5 二项分布的尾部（The tails of the binomial distribution）（带星号的进阶节）（PDF p.1229–1237）

比起“恰好 $k$ 次成功”，“至少/至多 $k$ 次成功”的概率往往更有用。尾部指远离均值 $np$ 的两个区域。右尾界可通过交换成功与失败的角色得到左尾界。

定理 C.2：$n$ 次成功概率为 $p$ 的伯努利试验，$X$ 为成功次数，$0\le k\le n$，

\Pr\{X\ge k\}=\sum_{i=k}^nb(i;n,p)\le\binom nkp^k.

证明：对 $S\subseteq\{1..n\}$，令 $A_S$ 为“$S$ 中所有试验成功”，$|S|=k$ 时 $\Pr\{A_S\}=p^k$。$\Pr\{X\ge k\}=\Pr\{\bigcup_{|S|=k}A_S\}\le\sum_{|S|=k}\Pr\{A_S\}=\binom nkp^k$（Boole 不等式 C.19）。

推论 C.3（左尾版本）：$\Pr\{X\le k\}=\sum_{i=0}^kb(i;n,p)\le\binom n{n-k}(1-p)^{n-k}=\binom nk(1-p)^{n-k}$。

定理 C.4（左尾远离均值时指数下降）：$0<k<np$ 时

\Pr\{X<k\}=\sum_{i=0}^{k-1}b(i;n,p)<\frac{kq}{np-k}b(k;n,p).

证明：用 A.2 节“几何级数界”技巧。由 (C.41)，对 $i=1..k$，

\frac{b(i-1;n,p)}{b(i;n,p)}=\frac{iq}{(n-i+1)p}<\frac{iq}{(n-i)p}\le\frac{kq}{(n-k)p}=:x.

而 $x<\frac{kq}{(n-np)p}=\frac{kq}{nqp}=\frac k{np}<1$。于是 $b(i-1)<x\,b(i)$，迭代得 $b(i)<x^{k-i}b(k)$（$0\le i<k$），

\sum_{i=0}^{k-1}b(i;n,p)<b(k;n,p)\sum_{i=1}^\infty x^i=\frac x{1-x}b(k;n,p)=\frac{kq}{np-k}b(k;n,p).

推论 C.5：$0<k\le np/2$ 时，少于 $k$ 次成功的概率小于少于 $k+1$ 次成功概率的一半。证明：$\frac{kq}{np-k}\le\frac{(np/2)q}{np/2}\le1$ (C.42)，由定理 C.4 得 $\sum_{i<k}b(i)<b(k)$，所以 $\frac{\Pr\{X<k\}}{\Pr\{X<k+1\}}=\frac{\sum_{i<k}b(i)}{\sum_{i<k}b(i)+b(k)}<\frac12$。

推论 C.6（右尾）：$np<k<n$ 时 $\Pr\{X>k\}=\sum_{i=k+1}^nb(i;n,p)<\dfrac{(n-k)p}{k-np}b(k;n,p)$。 推论 C.7：$(np+n)/2<k<n$ 时，多于 $k$ 次成功的概率小于多于 $k-1$ 次成功概率的一半。（C.6、C.7 的证明留作习题 C.5-2。）

定理 C.8（Chernoff 型界，成功概率可不同）：第 $i$ 次试验成功概率 $p_i$、失败 $q_i=1-p_i$，$X$ 为成功总数，$\mu=E[X]$。对 $r>\mu$，

\Pr\{X-\mu\ge r\}\le\left(\frac{\mu e}r\right)^r.

证明（矩母函数 + Markov 不等式的标准套路）：

对任意 $\alpha>0$，$e^{\alpha x}$ 严格增，$\Pr\{X-\mu\ge r\}=\Pr\{e^{\alpha(X-\mu)}\ge e^{\alpha r}\}$ (C.43)；由 Markov 不等式 (C.30) $\le E[e^{\alpha(X-\mu)}]e^{-\alpha r}$ (C.44)。
指示变量 $X_i=I\{\text{第 } i \text{ 次成功}\}$，$X=\sum X_i$，$\mu=\sum p_i$，$X-\mu=\sum(X_i-p_i)$。由相互独立（$e^{\alpha(X_i-p_i)}$ 也相互独立，习题 C.3-5）和 (C.24)：$E[e^{\alpha(X-\mu)}]=\prod_iE[e^{\alpha(X_i-p_i)}]$。
单项： $E[e^{\alpha(X_i-p_i)}]=e^{\alpha(1-p_i)}p_i+e^{\alpha(0-p_i)}q_i=p_ie^{\alpha q_i}+q_ie^{-\alpha p_i}\le p_ie^\alpha+1\le\exp(p_ie^\alpha)\quad(C.45)$ （用 $\alpha>0$、$q_i\le1$ 故 $e^{\alpha q_i}\le e^\alpha$，$e^{-\alpha p_i}\le1$；最后一步用 $1+x\le e^x$，式 3.12）。
乘起来：$E[e^{\alpha(X-\mu)}]\le\prod\exp(p_ie^\alpha)=\exp(\mu e^\alpha)$ (C.46)，所以 $\Pr\{X-\mu\ge r\}\le\exp(\mu e^\alpha-\alpha r)$ (C.47)。
取 $\alpha=\ln(r/\mu)$（使右边最小，习题 C.5-7）：$\exp(\mu\cdot r/\mu-r\ln(r/\mu))=\dfrac{e^r}{(r/\mu)^r}=\left(\dfrac{\mu e}r\right)^r$。

推论 C.9：各次成功概率均为 $p$，$r>np$ 时

\Pr\{X-np\ge r\}=\sum_{k=\lceil np+r\rceil}^nb(k;n,p)\le\left(\frac{npe}r\right)^r.

（因 $\mu=np$，由 C.37。）

习题概览：C.5-1 比较“抛 $n$ 次无正面”与“抛 $4n$ 次少于 $n$ 次正面”哪个更不可能；C.5-2 证推论 C.6、C.7；C.5-3 $\sum_{i=0}^{k-1}\binom nia^i<(a+1)^n\frac k{na-k(a+1)}b(k;n,a/(a+1))$；C.5-4 $\sum_{i<k}p^iq^{n-i}<\frac{kq}{np-k}\left(\frac{np}k\right)^k\left(\frac{nq}{n-k}\right)^{n-k}$；C.5-5 左尾的 Chernoff 型界 $\Pr\{\mu-X\ge r\}\le\left(\frac{(n-\mu)e}r\right)^r$ 及 $\Pr\{np-X\ge r\}\le\left(\frac{nqe}r\right)^r$；C.5-6 Hoeffding 型界 $\Pr\{X-\mu\ge r\}\le e^{-r^2/2n}$（提示：先证 $p_ie^{\alpha q_i}+q_ie^{-\alpha p_i}\le e^{\alpha^2/2}$）；C.5-7 证明 $\alpha=\ln(r/\mu)$ 使 (C.47) 右端最小。

附录 C 思考题与附录注

C-1 球与箱（balls and bins）：$n$ 个球放入 $b$ 个不同箱子。(a) 球互异、箱内无序：$b^n$；(b) 球互异、箱内有序：$(b+n-1)!/(b-1)!$（$n$ 个不同球与 $b-1$ 根相同隔板排成一列）；(c) 球相同：$\binom{b+n-1}n$（隔板法）；(d) 球相同且每箱至多一球（$n\le b$）：$\binom bn$；(e) 球相同且不允许空箱（$n\ge b$）：$\binom{n-1}{b-1}$。
附录注：Pascal 与 Fermat 1654 年的通信、Huygens 1657 年的书首次讨论求解概率问题的一般方法；严格概率论始于 J. Bernoulli（1713）与 De Moivre（1730）；Laplace、Poisson、Gauss 继续发展；随机变量之和最初由 Chebyshev 与 Markov 研究；Kolmogorov 1933 年公理化概率论；Chernoff [66] 与 Hoeffding [173] 给出分布尾部界；Erdős 开创随机组合结构研究。参考：Knuth [209]、Liu [237]（组合计数）；Billingsley、Chung、Drake、Feller、Rozanov（概率论教材）。

附录 C 本章要点

计数：加法、乘法法则；$k$-串 $n^k$；排列 $n!$；$k$-排列 $n!/(n-k)!$；组合 $\binom nk$；二项式定理；界 $(n/k)^k\le\binom nk\le(en/k)^k$，$\binom n{\lambda n}\le2^{nH(\lambda)}$。
概率：公理化定义、离散与连续均匀分布、条件概率、独立（两两独立 ≠ 相互独立）、Bayes 定理（含全概率分母形式）、Boole 不等式（union bound）。
随机变量：pdf、联合与边缘分布、期望（线性性不要求独立）、独立时乘积期望可分解、$\mathbb N$ 值变量的尾和公式、Jensen 不等式、方差 $E[X^2]-E^2[X]$、两两独立即可使方差可加、Markov 不等式。
分布：几何分布 $E=1/p$、$\mathrm{Var}=q/p^2$；二项分布 $E=np$、$\mathrm{Var}=npq$、单峰、众数在 $(np-q,(n+1)p)$。
尾界：$\Pr\{X\ge k\}\le\binom nkp^k$；远离均值时左/右尾被几何级数控制（推论 C.5、C.7 “每远一步概率至少减半”）；Chernoff 界 $\Pr\{X-\mu\ge r\}\le(\mu e/r)^r$ 与 Hoeffding 型界 $e^{-r^2/2n}$。

附录 C 与量化交易的关联

Bayes 定理：信号可信度更新（已知某指标发出信号，真实处于上涨状态的后验概率）、状态切换模型的滤波、贝叶斯收缩估计都以 (C.17)(C.18) 为基础；硬币例是理解“先验×似然/证据”的最佳教学例。
期望线性性与方差可加性：组合收益期望是各资产期望的加权和（无需独立）；而方差可加需要（两两）独立/不相关——这正是组合风险中协方差项不可忽视的原因。
二项分布与胜率检验：策略 $n$ 笔交易中盈利笔数服从二项分布（若独立），可用 $np$、$\sqrt{npq}$ 判断胜率是否显著高于 50%；尾界（定理 C.2、Chernoff/Hoeffding）给出“策略靠运气获得高胜率”的概率上界，与多重检验、过拟合检测相关。注意交易收益常不独立、不同分布，定理 C.8 允许 $p_i$ 不同，但仍要求独立。
几何分布：等待首次成交/首次触发的次数、限价单在每个时间片成交概率为 $p$ 时的期望等待时间 $1/p$。
Markov 不等式与 Jensen 不等式：前者给出无分布假设的尾部风险粗界；后者解释凸收益（期权）的期望大于期望价格的收益（凸性价值）、几何平均收益 ≤ 算术平均收益（对数是凹函数）。
熵函数 $H(\lambda)$ 出现在 Kelly 准则、信息论度量和组合计数界中。
连续均匀分布与随机数生成：蒙特卡洛模拟的基础。

附录 C 推荐习题

C.1-7、C.1-13（Pascal 恒等式与中心二项式系数渐近）；C.2-2（union bound）；C.2-6（用公平硬币模拟任意有理概率，随机数生成思想）；C.2-7、C.2-8（两两独立 vs 相互独立、条件独立）；C.2-9（Monty Hall，Bayes 直觉训练）；C.3-6（Markov 不等式）；C.4-2、C.4-5（几何分布应用、泊松极限 $1/e$）；C.5-6（Hoeffding 型界，用于胜率显著性和集中不等式）；思考题 C-1（球与箱的各种计数）。

附录 D 矩阵（Matrices）（PDF p.1238–1250）

矩阵广泛出现在科学计算等应用中。D.1 讲基本定义与运算，D.2 讲基本性质。

D.1 矩阵与矩阵运算（Matrices and matrix operations）（PDF p.1238–1243）

矩阵（matrix）：数的矩形阵列。例： $A=\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\end{pmatrix}=\begin{pmatrix}1&2&3\\4&5&6\end{pmatrix}\quad(D.1)$ 是 $2\times3$ 矩阵 $A=(a_{ij})$。大写字母表示矩阵、对应小写带下标表示元素。$\mathbb R^{m\times n}$ 为实 $m\times n$ 矩阵全体，一般 $S^{m\times n}$。
转置（transpose） $A^T$：行列互换，上例 $A^T=\begin{pmatrix}1&4\\2&5\\3&6\end{pmatrix}$。
向量（vector）：一维数组，如 $x=(2,3,5)^T$ 为大小 3 的向量（$n$-vector）。标准形式是列向量（等价于 $n\times1$ 矩阵），行向量为其转置 $x^T=(2\ 3\ 5)$。单位向量（unit vector） $e_i$：第 $i$ 个元素为 1、其余为 0。**零矩阵（zero matrix）**记 $0$，大小由上下文确定。
**方阵（square matrices）**的特殊类型：
1. 对角矩阵（diagonal matrix）：$i\ne j$ 时 $a_{ij}=0$，记 $\mathrm{diag}(a_{11},\dots,a_{nn})$；
2. 单位矩阵（identity matrix） $I_n=\mathrm{diag}(1,\dots,1)$，其第 $i$ 列是 $e_i$；
3. 三对角矩阵（tridiagonal matrix）：$|i-j|>1$ 时 $t_{ij}=0$，非零元只在主对角线及其上下相邻对角线；
4. 上三角矩阵（upper-triangular） $U$：$i>j$ 时 $u_{ij}=0$；对角线全为 1 称单位上三角；
5. 下三角矩阵（lower-triangular） $L$：$i<j$ 时 $l_{ij}=0$；对角线全为 1 称单位下三角；
6. 置换矩阵（permutation matrix） $P$：每行每列恰一个 1，其余为 0；用它乘向量相当于重排向量元素（书中给出一个 $5\times5$ 例子）；
7. 对称矩阵（symmetric matrix）：$A=A^T$，如 $\begin{pmatrix}1&2&3\\2&6&4\\3&4&5\end{pmatrix}$。
基本运算：元素取自某数系（实数、复数、模素数整数），数系决定加法与乘法。
- 矩阵加法：同型 $m\times n$ 矩阵逐元素相加 $c_{ij}=a_{ij}+b_{ij}$；零矩阵是加法单位元 $A+0=A=0+A$。
- 数乘（scalar multiple） $\lambda A=(\lambda a_{ij})$；负矩阵 $-A=-1\cdot A$，$A+(-A)=0$；减法 $A-B=A+(-B)$。
- 矩阵乘法：$A$ 的列数等于 $B$ 的行数时相容（compatible）（写 $AB$ 即默认相容）。$A$ 为 $m\times n$、$B$ 为 $n\times p$，则 $C=AB$ 为 $m\times p$： $c_{ij}=\sum_{k=1}^na_{ik}b_{kj}.\quad(D.2)$ 4.2 节的 SQUARE-MATRIX-MULTIPLY 按此直接实现，$n\times n$ 时做 $n^3$ 次乘法与 $n^2(n-1)$ 次加法，时间 $\Theta(n^3)$。

def square_matrix_multiply(A, B):      # n x n
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]
    return C                            # 时间 Θ(n^3)，额外空间 Θ(n^2)

代数性质：$I_mA=AI_n=A$；$A\cdot0=0$；结合律 $A(BC)=(AB)C$；分配律 $A(B+C)=AB+AC$，$(B+C)D=BD+CD$；$n>1$ 时不满足交换律，例 $A=\begin{pmatrix}0&1\\0&0\end{pmatrix}$、$B=\begin{pmatrix}0&0\\1&0\end{pmatrix}$，$AB=\begin{pmatrix}1&0\\0&0\end{pmatrix}$，$BA=\begin{pmatrix}0&0\\0&1\end{pmatrix}$。
矩阵-向量积、向量-向量积把向量当作 $n\times1$（或行向量 $1\times n$）矩阵：$A$ 为 $m\times n$、$x$ 为 $n$-向量，$Ax$ 为 $m$-向量。内积（inner product） $x^Ty=\sum_{i=1}^nx_iy_i$（一个数，严格说是 $1\times1$ 矩阵）；外积（outer product） $xy^T$ 为 $n\times n$ 矩阵 $Z$，$z_{ij}=x_iy_j$。（欧氏）范数（euclidean norm） $\|x\|=(x_1^2+\cdots+x_n^2)^{1/2}=(x^Tx)^{1/2}$，即 $n$ 维欧氏空间中的长度。

习题概览：D.1-1 对称矩阵的和、差仍对称；D.1-2 $(AB)^T=B^TA^T$，$A^TA$ 总是对称；D.1-3 两个下三角矩阵之积是下三角；D.1-4 $PA$ 是 $A$ 的行置换、$AP$ 是列置换，置换矩阵之积仍是置换矩阵。

D.2 基本矩阵性质（Basic matrix properties）（PDF p.1243–1250）

逆矩阵（inverse）：$n\times n$ 矩阵 $A^{-1}$ 满足 $AA^{-1}=I_n=A^{-1}A$。例 $\begin{pmatrix}1&1\\1&0\end{pmatrix}^{-1}=\begin{pmatrix}0&1\\1&-1\end{pmatrix}$。许多非零方阵没有逆：无逆称不可逆/奇异（noninvertible / singular），如 $\begin{pmatrix}1&0\\1&0\end{pmatrix}$；有逆称可逆/非奇异（invertible / nonsingular）。逆若存在则唯一（习题 D.2-1）。$(BA)^{-1}=A^{-1}B^{-1}$；$(A^{-1})^T=(A^T)^{-1}$。
线性相关（linearly dependent）：存在不全为零的 $c_i$ 使 $c_1x_1+\cdots+c_nx_n=0$。例：行向量 $x_1=(1\ 2\ 3)$、$x_2=(2\ 6\ 4)$、$x_3=(4\ 11\ 9)$ 满足 $2x_1+3x_2-2x_3=0$，线性相关。否则线性无关（linearly independent），如单位矩阵的各列。
秩（rank）：非零 $m\times n$ 矩阵的列秩为最大线性无关列组的大小，行秩同理；基本事实：行秩 = 列秩，统称秩，取值 $0..\min(m,n)$（零矩阵秩 0，$I_n$ 秩 $n$）。等价且常更有用的定义：秩是使 $A=BC$（$B$ 为 $m\times r$、$C$ 为 $r\times n$）成立的最小 $r$。方阵秩为 $n$ 称满秩（full rank）；$m\times n$ 矩阵秩为 $n$ 称列满秩（full column rank）。

定理 D.1：方阵满秩当且仅当非奇异。

零向量（null vector）：使 $Ax=0$ 的非零向量 $x$。 定理 D.2：$A$ 列满秩当且仅当没有零向量（证明为习题 D.2-7）。 推论 D.3：方阵 $A$ 奇异当且仅当有零向量。
余子式与行列式：$n>1$ 时 $A$ 的第 $ij$ 子式矩阵（minor） $A_{[ij]}$ 是删去第 $i$ 行第 $j$ 列后的 $(n-1)\times(n-1)$ 矩阵。行列式递归定义（按第一行展开）：
$\det(A)=\begin{cases}a_{11},&n=1,\\\sum_{j=1}^n(-1)^{1+j}a_{1j}\det(A_{[1j]}),&n>1.\end{cases}$ $(-1)^{i+j}\det(A_{[ij]})$ 称元素 $a_{ij}$ 的代数余子式（cofactor）。

定理 D.4（行列式性质）：

任一行或任一列全零 ⇒ $\det(A)=0$；
某一行（或列）全部乘以 $\lambda$ ⇒ 行列式乘以 $\lambda$；
把一行（列）加到另一行（列）上 ⇒ 行列式不变；
$\det(A)=\det(A^T)$；
交换两行（或两列）⇒ 行列式变号；
$\det(AB)=\det(A)\det(B)$。

定理 D.5：$n\times n$ 矩阵奇异当且仅当 $\det(A)=0$。

正定矩阵（positive-definite）：对所有非零 $x$ 有 $x^TAx>0$。例：$I_n$ 正定，因为 $x^TI_nx=x^Tx=\sum x_i^2>0$。

定理 D.6：若 $A$ 列满秩，则 $A^TA$ 正定。证明：$x^T(A^TA)x=(Ax)^T(Ax)=\|Ax\|^2\ge0$（用 D.1-2）。若 $\|Ax\|^2=0$ 则 $Ax=0$，由列满秩和定理 D.2 得 $x=0$。故对非零 $x$ 严格大于 0。（28.3 节讨论正定矩阵的更多性质，如最小二乘。）

习题概览：D.2-1 逆矩阵唯一；D.2-2 三角矩阵行列式等于对角元乘积，下三角矩阵的逆（若存在）仍是下三角；D.2-3 置换矩阵可逆且 $P^{-1}=P^T$，$P^T$ 也是置换矩阵；D.2-4 若 $AB=I$，把 $A$ 的第 $j$ 行加到第 $i$ 行得 $A'$，则把 $B$ 的第 $j$ 列减去第 $i$ 列得 $A'$ 的逆；D.2-5 非奇异复矩阵的逆全为实数当且仅当原矩阵全为实数；D.2-6 非奇异对称矩阵的逆对称，$BAB^T$ 对称；D.2-7 证定理 D.2（把某列由其余列线性表示写成矩阵-向量方程）；D.2-8 $\mathrm{rank}(AB)\le\min(\mathrm{rank}(A),\mathrm{rank}(B))$，$A$ 或 $B$ 为非奇异方阵时取等号（用 $A=BC$ 的秩定义）。

附录 D 思考题与附录注

D-1 Vandermonde 矩阵： $V(x_0,\dots,x_{n-1})=\begin{pmatrix}1&x_0&x_0^2&\cdots&x_0^{n-1}\\1&x_1&x_1^2&\cdots&x_1^{n-1}\\\vdots&&&&\vdots\\1&x_{n-1}&x_{n-1}^2&\cdots&x_{n-1}^{n-1}\end{pmatrix},\qquad\det V=\prod_{0\le j<k\le n-1}(x_k-x_j).$ 提示：对 $i=n-1,\dots,1$ 把第 $i$ 列乘 $-x_0$ 加到第 $i+1$ 列，再归纳。（与多项式插值、FFT 相关。）
D-2 GF(2) 上矩阵-向量乘法定义的置换：$S_n=\{0,\dots,2^n-1\}$，把 $x$ 视为 $n$ 位二进制向量（$x=\sum x_i2^i$），$n\times n$ 0-1 矩阵 $A$ 定义映射 $x\mapsto Ax$，运算在 GF(2) 上进行（$1+1=0$，即只保留最低位）。例：$A=\begin{pmatrix}1&0\\1&1\end{pmatrix}$ 给出 $\pi_A(0)=0,\pi_A(1)=3,\pi_A(2)=2,\pi_A(3)=1$。秩在 GF(2) 上定义；值域 $R(A)=\{Ax\}$。(a) 秩为 $r$ 则 $|R(A)|=2^r$，故仅满秩时是置换；(b) 原像 $P(A,y)=\{x:Ax=y\}$ 大小为 $2^{n-r}$；(c) 把 $S_n$ 分成大小 $2^m$ 的连续块，若 $A$ 左下 $(n-m)\times m$ 子矩阵秩为 $r$，则任一块的像落在 $2^r$ 个块中，每个块恰接收 $2^{m-r}$ 个数；扩展为 $x\mapsto Ax+c$ 的线性置换（linear permutation），例 $c=(0,1)^T$ 时 $\pi_{A,c}(0)=2,\pi_{A,c}(1)=1,\pi_{A,c}(2)=0,\pi_{A,c}(3)=3$；(d) 计数论证：线性置换数（至多 $2^{n^2+n}$）远少于 $(2^n)!$；(e) 举出不能由线性置换实现的置换（考虑矩阵乘单位向量即取列）。
附录注：线性代数教材提供大量矩阵背景，Strang [323, 324] 尤佳。

附录 D 本章要点

记号：矩阵/向量/转置/单位向量/零矩阵；特殊方阵（对角、单位、三对角、上下三角、置换、对称）。
运算：加法、数乘、乘法（$\Theta(n^3)$ 朴素算法）、结合律、分配律、不交换；内积、外积、欧氏范数。
性质：逆的唯一性与 $(BA)^{-1}=A^{-1}B^{-1}$；线性相关/无关；秩（行秩=列秩，最小分解维数定义）；满秩 ⇔ 非奇异 ⇔ 无零向量 ⇔ $\det\ne0$；行列式递归定义及性质；正定矩阵，列满秩 ⇒ $A^TA$ 正定。

附录 D 与量化交易的关联

协方差矩阵：资产收益协方差矩阵是对称半正定矩阵；若收益矩阵 $R$（$T\times N$，去均值后）列满秩，则 $R^TR$ 正定（定理 D.6），这保证了均值-方差优化中可求逆、最优解唯一。$T<N$（样本少于资产数）时列不满秩，样本协方差奇异，必须做收缩（shrinkage）或因子模型——这是秩概念在风险建模中最直接的应用。
最小二乘与因子回归：$X^TX$ 正定（设计矩阵列满秩）是 OLS 估计 $\hat\beta=(X^TX)^{-1}X^Ty$ 存在唯一的条件；因子共线性即接近列不满秩，导致行列式接近 0、估计不稳定。
秩的分解定义 $A=BC$ 对应因子模型的低秩结构：$N\times N$ 协方差矩阵 ≈ $B\Sigma_fB^T+D$，$B$ 为 $N\times K$ 暴露矩阵。
置换矩阵：资产重排序、排序因子（rank）构造可以用置换矩阵表示。三角矩阵：Cholesky 分解（下三角）用于相关随机数生成（蒙特卡洛模拟）。
范数与内积：组合权重的 $L_2$ 范数、跟踪误差 $\sqrt{(w-w_b)^T\Sigma(w-w_b)}$、因子暴露的内积计算。
行列式与逆的公式本身在数值计算中通常不直接使用（用 LU/Cholesky 分解更稳定），教材中可提示这一点。

附录 D 推荐习题

D.1-2（$(AB)^T=B^TA^T$，$A^TA$ 对称）；D.1-4、D.2-3（置换矩阵性质）；D.2-6（$BAB^T$ 对称，组合风险 $w^T\Sigma w$ 的矩阵版本）；D.2-7（列满秩 ⇔ 无零向量）；D.2-8（乘积的秩不等式，理解低秩因子模型）；思考题 D-1（Vandermonde 行列式，插值与多项式拟合）。

参考文献（Bibliography）（PDF p.1252–1271）

PDF p.1251 为空白页。参考文献共 362 条（[1] Abramowitz & Stegun《Handbook of Mathematical Functions》至 [362] Zwillinger《CRC Standard Mathematical Tables and Formulae》），按第一作者姓氏字母排序，正文中以方括号编号引用。内容大致分几类：

经典教材与工具书：Knuth《The Art of Computer Programming》卷 1–3 [209–211]；Aho–Hopcroft–Ullman [5, 6]；Garey & Johnson《Computers and Intractability》[129]；Papadimitriou & Steiglitz《Combinatorial Optimization》[271]；Tarjan《Data Structures and Network Algorithms》[330]；Golub & Van Loan《Matrix Computations》[144]；Press 等《Numerical Recipes》[283, 284]；Strang 线性代数 [323, 324]；Feller、Billingsley、Chung 概率论 [104, 46, 67]；Graham–Knuth–Patashnik《Concrete Mathematics》[152]；Kleinberg & Tardos [208]；Dasgupta–Papadimitriou–Vazirani [82]；Motwani & Raghavan《Randomized Algorithms》[262]；Vazirani《Approximation Algorithms》[345]；Hochbaum 编《Approximation Algorithms for NP-Hard Problems》[172]；Chvátal、Karloff、Schrijver、Vanderbei、Ye 的线性规划/内点法著作 [69, 197, 303, 344, 361]。
奠基性论文：Cook（1971，NP 完全）[75]、Karp（1972，归约）[199]、Levin [234]、Edmonds（1965）[100]、Cobham（1964）[72]；Dijkstra（1959）[88]、Bellman（1958）[38]、Floyd（1962）[105]、Warshall [349]、Prim [285]、Kruskal [222]；Ford & Fulkerson [109]、Edmonds & Karp [102]、Goldberg & Tarjan [140]；Hoare 快速排序 [169, 170]、Williams 堆排序 [357]；Huffman 编码 [185]；Cooley & Tukey FFT [76]；Strassen 矩阵乘法 [325]、Coppersmith & Winograd [78]；Knuth–Morris–Pratt [214]、Karp–Rabin [201]；RSA [296]、Diffie & Hellman [87]；Miller [255]、Rabin [289] 素性测试，AKS “PRIMES is in P” [4]；Fredman & Tarjan 斐波那契堆 [114]；van Emde Boas [339–341]；Karmarkar 内点法 [198]；Spielman & Teng 平滑分析 [322]。
与本块（第 34、35 章、附录）直接相关的文献：Garey–Graham–Ullman [128]、Johnson [190, 191]、Graham [149]（近似算法起源）；Rosenkrantz–Stearns–Lewis [298]（APPROX-TSP-TOUR）；Sahni & Gonzalez [301]（定理 35.3）；Arora [20–22]、Arora & Lund [23]、Mitchell [257]（PCP 与欧氏 TSP 的 PTAS）；Chvátal [68]、Lovász [238]（集合覆盖）；Ibarra & Kim [187]（子集和/背包 FPTAS）；Hochbaum [171]（加权顶点覆盖）；Raghavan & Thompson [290]（随机舍入）；Goemans & Williamson [134, 135]（半定规划、原始-对偶）；Bienstock & McClosky [45]（思考题 35-7）；Chernoff [66]、Hoeffding [173]（尾界）；Lawler 等编《The Traveling Salesman Problem》[225]。
另有多线程/并行计算（Cilk [51, 71, 118]、Blumofe & Leiserson 工作窃取 [52]、OpenMP [59]、TBB [292]）、计算几何（Graham 扫描 [150]、Jarvis [189]、Preparata & Shamos [282]）、字符串与计算生物学（Gusfield [156]、Pevzner [275]）、图像处理（Avidan & Shamir 接缝裁剪 [27]）等文献。

对量化教材编写者有参考价值的条目：Golub & Van Loan [144]（矩阵计算）、Press 等 [283, 284]（数值方法）、线性规划/内点法 [69, 197, 198, 303, 344, 361]、Motwani & Raghavan [262]（随机算法）、Chernoff/Hoeffding 尾界 [66, 173]、Feller [104]（概率论）。

索引（Index）（PDF p.1272–1313）

索引约 42 页，约定：数字按英文拼写排序（如 “2-3-4 tree” 按 “two-three-four tree” 排）；页码后标签 ex. 表示习题、pr. 表示思考题、fig. 表示图、n. 表示脚注；带标签的页码通常指习题/思考题起始页。索引页码为原书页码（PDF 页码 = 原书页码 + 21）。开头是符号索引（$\alpha(n)$、黄金分割 $\phi$、Euler $\phi$ 函数、各类渐近记号 $o,O,\omega,\Omega,\Theta$ 及 $\tilde O$ 等、集合符号、$\binom nk$、范数、阶乘、上下取整、$\sum$、$\prod$、可达关系、AND/OR/NOT、$\le_P$ 等），随后按字母从 “AA-tree” 到 “zonk” 排列，涵盖算法名（如 APPROX-TSP-TOUR p.1112、GREEDY-SET-COVER p.1119、TRIM p.1130）、数据结构、定理、术语。

与量化相关、便于编写者回查的索引条目（原书页码）：arbitrage 套利 679pr.（第 24 章思考题 24-3，用 Bellman-Ford 检测货币兑换负权回路）；currency exchange 390ex., 679pr.；least-squares approximation 最小二乘 835–839；linear programming 线性规划 843–897（含对偶 879–886、单纯形 864–879）；0-1 integer programming 1100ex., 1125；symmetric positive-definite matrix 832–835；LUP decomposition 815–825；matrix inversion 827–831；fast Fourier transform 898–925、convolution 901；median/order statistics 213–227、weighted median 225pr.、quantile 223ex.；streaks 连续成功 135–139；random sampling 129ex., 179；random permutation 124–128；Viterbi algorithm 408pr.；inventory planning 411pr.；priority queue 162–166；interval tree 348–354；order-statistic tree 339–345；knapsack problem 425–428, 1137pr.；scheduling 443–446, 1104pr., 1136pr.；Markov's inequality 1201ex.；Jensen's inequality 1199；Bayes's theorem 1194；binomial distribution tails 1208–1215。

（索引末尾的 “zonk, 1195ex.” 指 Monty Hall 问题习题 C.2-9 所在页，属于作者的小幽默。）