UC Berkeley CS70 离散数学与概率论 · 开篇与课程概览
课程：CS70 — Discrete Mathematics and Probability Theory，UC Berkeley，Fall 2026 授课：Josh Hug、Manuel Sabin ｜ 讲座时间：周二/周四 15:30–17:00，Li Ka Shing 245 官方主页：https://www.eecs70.org/ 资料基础：本笔记以 CS70 官方公开讲义 Notes 为核心依据 —— Fall 2026 现行 Notes（Note 0–7，已随学期发布）以及 Berkeley 官方归档的完整 Notes 体系（Fall 2020 / Spring 2021，Note 0–22）。课程主页的讲座日程、Quiz 安排、评分政策亦已核对。 版权与用途声明：官方材料 © UC Berkeley / CS70 课程组，受版权保护。本文档是自学整理笔记：按 Fall 2026 讲次顺序重新组织内容，讲解、证明书写、示例构造均为原创中文表述，未逐字翻译或转载任何官方讲义。所有数值算例均经脚本验算。 使用方法：每讲先读「概述」把握定位，再读「核心概念的直观解释」建立直觉，然后动手把「完整证明与推导」在纸上重写一遍，最后用「思考题」自测。CS70 的官方学习建议是：“study the notes until you were able to comfortably reproduce all of the proofs” —— 能默写证明，才算真正掌握。
课程概览
一、这门课到底在教什么？
CS70 是伯克利计算机科学专业的数学基础核心课，它不教编程，教的是计算机科学背后的数学思维方式。课程的官方定位写得很直白：目标是培养 mathematical maturity（数学成熟度），即在面对一个从未见过的命题时，你知道该从哪个角度切入、用哪种证明技巧、写下什么样的严格论证。
课程内容分为两大模块，各 14 个子主题（官方原文 “Each half has fourteen subtopics”）：
| 模块一：离散数学 (Discrete Mathematics) | 模块二：概率论 (Probability Theory) |
|---|---|
| Propositional Logic（命题逻辑） | Counting（计数） |
| Direct Proofs（直接证明） | Probability Foundations（概率公理基础） |
| Proof Techniques（证明技巧） | Combinatorial Proofs（组合证明） |
| Induction（归纳法） | Conditional Probability & Bayes（条件概率与贝叶斯） |
| Modular Arithmetic（模运算） | Independence & Combination of Events（独立性与事件组合） |
| CRT（中国剩余定理） | Random Variables & Discrete Distributions（随机变量与离散分布） |
| RSA（RSA 公钥密码） | Expectations & Linearity（期望与线性性） |
| Polynomials（多项式） | Joint Distributions & Independence of RVs（联合分布） |
| Secret Sharing & ECCs（秘密共享与纠错码） | Variance & Covariance（方差与协方差） |
| Graphs（图论） | Concentration Inequalities（集中不等式） |
| Graph Induction（图上的归纳法） | Continuous Probability & Distributions（连续概率） |
| Stable Matching（稳定匹配） | Gaussian Distribution & CLT（高斯分布与中心极限定理） |
| Countability（可数性） | Markov Chains & Conditional Expectation（马尔可夫链与条件期望） |
| Computability（可计算性） | （最后一讲随学期调整） |
为什么是这个顺序？ 这不是任意排列，而是一条严格的逻辑链：
【离散数学模块】—— 从「怎么证明」到「什么不能被证明」
证明工具箱 §L00-L03 直接证明 → 命题逻辑 → 逆否/反证/分情形 → 归纳法
│ （没有这套工具，后面的一切都无法书写）
▼
数论与密码 §L04-L06 模运算 → 欧几里得/FLT/CRT → RSA
│ （同余语言 → 逆元与快速幂 → 真实工业级加密）
▼
代数与编码 §L07-L08 多项式 → 秘密共享 & 纠错码
│ （多项式插值：从「点唯一确定多项式」出发）
▼
图与匹配 §L09-L11 图论 → 平面图/欧拉/树 → 稳定匹配
│ （离散结构的建模语言 + 算法正确性证明）
▼
极限与不可能 §L12-L13 可数性 → 可计算性
（对角线方法 → 停机问题不可判定）
【概率论模块】—— 从「怎么数」到「怎么预测」
计数与测度 §L14-L15 计数 → 概率公理
│ （把「随机」装进集合论框架）
▼
信息更新 §L16-L18 组合证明 → 条件概率/贝叶斯 → 独立性
│ （观察到证据后如何修正信念）
▼
随机变量 §L19-L22 随机变量 → 期望线性性 → 联合分布 → 方差协方差
│ （把「随机」压缩成数字，再用线性性绕开相关性）
▼
极限定理 §L23-L25 集中不等式 → 连续分布 → 高斯与 CLT
│ （为什么大量独立随机性必然「聚拢」成钟形）
▼
动态随机过程 §L26 马尔可夫链与条件期望
（无记忆的演化：稳态、吸收、首步分析）
二、两个模块各自的核心思想
模块一的一句话总结：离散数学研究”能被有限步骤验证的真理”。 它的主线是证明技巧的进化：直接证明遇到困难 → 换逆否命题 → 再不行就反证 → 涉及”所有自然数”就上归纳 → 涉及”无穷”就上对角线方法。每引入一种新技巧，都是因为旧技巧在某类问题上碰壁。而模运算、多项式、图论这三块”具体数学”，则是证明技巧的练兵场，同时也各自通向真实应用（RSA、纠错码、稳定匹配）。
模块二的一句话总结：概率论研究”在信息不完全时如何做出可辩护的判断”。 它的主线是抽象层级的递进：先是事件（集合）→ 然后是随机变量（函数）→ 然后是数字特征（期望、方差）→ 最后是极限定理（大量随机性的宏观规律）。每一步都用上一层的工具，而期望的线性性（L20）是整门课最锋利的”免费午餐”：它不需要独立性，却能让你绕开所有复杂的联合分布计算。
三、学习方法建议（结合 CS70 的考核机制）
CS70 的考核方式很特殊：每周五 Quiz + 期中 + 期末，且按”主题通过制”（topic-based pass/fail）评分。每个主题在 Quiz 上出现一次；没通过可以在期中/期末再考一次。这意味着：
- 不要攒着学。每个主题只有一次（最多两次）机会，必须当周掌握。
- 证明要能默写。官方明确建议”把笔记读到能舒服地复现所有证明”。本笔记的每一讲都给出「证明策略 → 逐步推导 → 证明机制解说」三段式，正是为了让你能内化证明的生成过程，而不只是记住结论。
- 区分”看懂”和”会写”。看懂一个证明只需被动接受逻辑；会写一个证明需要你主动决定用什么技巧、基础情形取什么、归纳假设假设什么。本笔记每讲的「思考题」用来检验后者。
- 留意「常见误区」小节。CS70 的失分大多不是不会，而是踩了固定的坑（忘了基础情形、混淆 $P(A\mid B)$ 与 $P(B\mid A)$、把互斥当独立……）。这些坑在每讲末尾被明确列出。
- 把交叉引用当作复习线索。CS70 的考点经常跨主题（例如”用期望线性性证明哈希的 $O(1)$ 查找”），本笔记每讲的「与其他讲次的关联」小节专门标出这些纽带。
四、本笔记的结构
- 按 Lecture 0 → Lecture 26 顺序排列，与 Fall 2026 官方讲座日程严格对齐。
- 每一讲采用固定八段式：概述 → 核心概念的直观解释 → 完整证明与推导 → 与经典问题的联系 → 与其他讲次的关联 → 关键要点 → 常见误区与注意事项 → 思考题（带答案）。
- 文档末尾附 「核心定理与证明技巧速查表」，按证明技巧、数论与密码、代数与编码、图论与匹配、可计算性、计数与概率、随机变量与极限定理七大类别速查。
📌 关于讲次编号
本笔记的讲次编号（Lecture 0–26）遵循 Fall 2026 官方日程。官方 Notes 的编号与之并不一致（例如 Fall 2026 的 Lecture 0 “Direct Proofs” 对应 Note 0 与 Note 1 两份笔记；Lecture 11 “Stable Matching” 对应官方 Note 12）。阅读官方 Note 时请以主题名而非编号为准。