Ch13 §01 离散数学 · 讲解稿¶
章节定位: Ch13 数学基础。覆盖集合论 / 命题与谓词逻辑 / 证明方法 / 组合数学 / 图论基础 / 算法复杂度。 承接: Ch01 集合 → Ch13 §01 离散数学完整版; Ch14 数据结构 → Ch13 §01 复杂度理论 走向: §02 计算机架构 / §03 OS / §04 并发 / §05 编程语言 篇幅: ~4200 字 / 阅读 12 分钟 / 讲解 25-30 分钟
一 · 一句话总览¶
离散数学 = 计算机科学的数学语言: 集合 (数据) + 逻辑 (推理) + 证明 (验证) + 组合 (计数) + 图论 (关系) + 复杂度 (资源)。Ch13 §01 是 AI 工程师必学的基础。
二 · 心智模型¶
| 概念 | 编程对应 |
|---|---|
| 集合 | set / 列表 |
| 关系 | 函数 / 数据库 join |
| 证明 | 程序正确性 |
| 组合 | 概率采样 |
| 图论 | 网络 / GNN |
| 复杂度 | 算法选择 |
三 · 章节主线 (5 段)¶
第 1 段 · 集合论 (8 分钟)¶
3.1.1 基本运算¶
| 运算 | 符号 | 定义 |
|---|---|---|
| 并 | \(A \cup B\) | 任一集合的所有元素 |
| 交 | \(A \cap B\) | 两集合的公共元素 |
| 差 | \(A \setminus B\) | \(A\) 中不在 \(B\) 的元素 |
| 补 | \(\bar A\) | 全集 - \(A\) |
德摩根律: \(\overline{A \cup B} = \bar A \cap \bar B\), \(\overline{A \cap B} = \bar A \cup \bar B\)。
3.1.2 笛卡尔积与关系¶
\(A \times B = \{(a, b) : a \in A, b \in B\}\)
关系 \(R \subseteq A \times B\) 是 \(A \times B\) 的子集。函数 \(f: A \to B\) 是特殊关系 (每个 \(a\) 对应唯一 \(b\))。
3.1.3 幂集¶
例: \(S = \{1, 2, 3\}\) → \(|\mathcal{P}(S)| = 8\)。
第 2 段 · 命题逻辑与谓词逻辑 (8 分钟)¶
3.2.1 命题逻辑¶
命题 = 真或假的陈述句。用符号 \(\land, \lor, \neg, \to, \leftrightarrow\) 组合。
| 命题 | 例子 |
|---|---|
| \(P\) | 今天是周一 |
| \(P \land Q\) | 今天是周一且下雨 |
| \(P \to Q\) | 如果下雨, 地面湿 |
真值表: \(\neg(P \land Q) = \neg P \lor \neg Q\) (德摩根)。
3.2.2 谓词逻辑¶
谓词 \(P(x)\) = 含变量 \(x\) 的命题。\(\forall x P(x)\) 全称, \(\exists x P(x)\) 存在。
3.2.3 证明方法¶
| 方法 | 思路 |
|---|---|
| 直接 | 假设 → 推导 → 结论 |
| 反证 | 假设结论错 → 推出矛盾 |
| 归纳 | 基础 \(P(1)\) + 归纳 \(P(k) \to P(k+1)\) |
| 构造 | 显式构造对象证明存在 |
3.2.4 鸽巢原理¶
\(n\) 个鸽巢, \(n+1\) 只鸽子 → 至少一巢有 ≥ 2 只。
应用: 证明哈希冲突, 模运算, 子数组和。
第 3 段 · 组合数学 (8 分钟)¶
3.3.1 排列¶
\(P(n, k)\) = \(n\) 个中取 \(k\) 个有序:
\(P(5, 3) = 5 \cdot 4 \cdot 3 = 60\)。
3.3.2 组合¶
\(C(n, k)\) = \(n\) 个中取 \(k\) 个无序:
\(C(5, 3) = 10\)。
3.3.3 二项式定理¶
3.3.4 经典问题¶
| 问题 | 公式 |
|---|---|
| 错位排列 | \(D_n = n! \sum_{k=0}^n (-1)^k / k!\) |
| Catalan 数 | \(C_n = \frac{1}{n+1} \binom{2n}{n}\) |
| 球盒问题 | (球/盒是否可区分, 盒是否允许空) |
第 4 段 · 图论基础 (8 分钟)¶
(详细见 Ch12 §02, 此处复习)
| 概念 | 定义 |
|---|---|
| 节点 | \(V\), 边 \(E\) |
| 度 | \(d_v = \sum A_{uv}\) |
| 路径 | 节点序列, 邻接 |
| 圈 | 起点 = 终点 |
| 树 | 无圈连通, \(n-1\) 边 |
| 拉普拉斯 | \(L = D - A\) |
3.4.1 树的应用¶
- 文件系统 (ext4 inode 树)
- AST (抽象语法树, Ch13 §05)
- 决策树 (Ch05)
3.4.2 二叉树遍历¶
- 前序: 根 → 左 → 右
- 中序: 左 → 根 → 右
- 后序: 左 → 右 → 根
第 5 段 · 算法复杂度 (12 分钟)¶
3.5.1 大 O 记号¶
| 记号 | 含义 |
|---|---|
| \(O(f)\) | 上界 |
| \(\Omega(f)\) | 下界 |
| \(\Theta(f)\) | 紧界 |
3.5.2 常见复杂度¶
| 复杂度 | 算法 | 例子 |
|---|---|---|
| \(O(1)\) | 哈希查找 | dict[key] |
| \(O(\log n)\) | 二分查找 | bisect |
| \(O(n)\) | 线性扫描 | 数组求和 |
| \(O(n \log n)\) | 归并排序 | sort |
| \(O(n^2)\) | 冒泡 | bubble |
| \(O(2^n)\) | 子集枚举 | power set |
| \(O(n!)\) | 旅行商暴力 | TSP brute |
3.5.3 P / NP 完整¶
| 类别 | 含义 |
|---|---|
| P | 多项式时间内可解 |
| NP | 多项式时间内可验证 |
| NP 完整 | NP 中最难, 互为多项式归约 |
| P = NP? | 未解, 密码学假设 \(P \neq NP\) |
NP 完整例子: SAT, 旅行商, 团问题, 子集和。
3.5.4 Python 实测复杂度¶
import time
def measure(n):
# O(n)
t0 = time.perf_counter()
s = sum(range(n))
t1 = time.perf_counter()
print(f"O(n) n={n}: {t1-t0:.4f}s, sum={s}")
# O(n^2)
t0 = time.perf_counter()
s = 0
for i in range(n):
for j in range(n):
s += i * j
t1 = time.perf_counter()
print(f"O(n²) n={n}: {t1-t0:.4f}s, sum={s}")
# n=1000 vs n=10000, O(n²) 差距 100×
3.5.5 主定理 (Master Theorem)¶
递推 \(T(n) = a T(n/b) + f(n)\):
| 条件 | 复杂度 |
|---|---|
| \(f(n) = O(n^{\log_b a - \epsilon})\) | \(T(n) = \Theta(n^{\log_b a})\) |
| \(f(n) = \Theta(n^{\log_b a})\) | \(T(n) = \Theta(n^{\log_b a} \log n)\) |
| \(f(n) = \Omega(n^{\log_b a + \epsilon})\) | \(T(n) = \Theta(f(n))\) |
例: 归并排序 \(T(n) = 2T(n/2) + O(n)\) → \(T(n) = O(n \log n)\)。
四 · 易错点 (5 条)¶
- 大 O 不等于精确: \(O(n)\) 是上界, 实际 \(T(n)\) 可能更小。
- 鸽巢: 不要和"两个鸽巢一只鸽子"搞混。
- 排列 vs 组合: 有序用 \(P\), 无序用 \(C\)。
- P vs NP: \(P \subseteq NP\), 但 \(\neq\) 未证。
- 归纳法: 必须有基础步, 不能直接假设结论。
五 · 跨章连接¶
| 章节 | 关联 |
|---|---|
| Ch01 §01 集合 | 离散数学基础 |
| Ch02 §04 矩阵论 | 邻接 / 拉普拉斯 |
| Ch05 §04 贝叶斯 | 概率 = 组合计数 |
| Ch12 §02 图论 | 离散数学应用 |
| Ch14 §01 数据结构 | 复杂度分析 |
六 · 自测 5 题¶
- \(C(10, 5)\) 等于多少?
- 鸽巢原理: 13 人中至少几人生日同月?
- \(O(n \log n)\) 与 \(O(n^2)\) 在 \(n=10^6\) 时差距?
- P 类与 NP 类核心区别?
- 数学归纳法证明 \(1 + 2 + \dots + n = n(n+1)/2\)。
七 · 一句话总结¶
离散数学 = AI 系统的语言层。覆盖集合 (数据) / 逻辑 (推理) / 证明 (正确性) / 组合 (计数) / 图论 (关系) / 复杂度 (资源)。Ch13 §02-§05 都建立在 §01 的数学基础之上。
八 · 板书建议¶
[板书 1: 集合运算]
A∪B, A∩B, A\B, Ā
De Morgan: ¬(A∪B) = Ā ∩ B̄
[板书 2: 组合]
P(n,k) = n!/(n-k)! 有序
C(n,k) = n!/(k!(n-k)!) 无序
[板书 3: 大 O]
T(n) = O(f(n)) 上界
Ω, Θ
[板书 4: P vs NP]
P ⊆ NP, P =? NP
NP 完整: SAT, TSP, Clique
九 · 参考资料¶
- Rosen, "Discrete Mathematics and Its Applications" (经典教材)
- Ch01 §01 集合 (本套书)
- Ch12 §02 图论 (本套书)
- Sipser, "Introduction to the Theory of Computation" (P/NP)
- Cormen et al., "Introduction to Algorithms" (CLRS)