全部课程/CS70

CS70：离散数学与概率论

用证明、图论、模运算、可计算性、组合计数与概率论建立计算机科学的数学基础；收录 Spring 2023 本地 Discussion、Homework 及官方解答。

怎样把一个直觉命题变成可检查的证明，并在不确定性中量出它成立的概率？

加州大学伯克利分校Satish Rao、Babak Ayazifar2023 年春季14 讲官方课程 ↗

从这里开始

命题逻辑、集合与证明技术

已完成 0 / 14 讲 · 记录保存在当前浏览器
开始学习

学习进度

0 / 14讲义已完成

已完成 0 / 41 份实践
由你确认，不自动标记

课程地图

  1. 1逻辑与证明第 1–4 讲

    直觉怎样变成可检查的证明？

  2. 2代数与计算第 5–7 讲

    有限结构有哪些表达能力？

  3. 3计数与概率第 8–10 讲

    怎样定义并计算不确定性？

  4. 4随机变量与极限第 11–14 讲

    大量随机事件有哪些规律？

三种学习方式

学习

读讲义，理解原理与机制。
把量词、样本空间、图或随机变量的边界说清楚。

查看讲义

思考

做讨论题，自己推一遍。
每一步标注使用的定义、引理与不变量，避免跳过关键蕴含。

查看讨论

实践

用工作簿与实验验证方法。
主动构造最小反例，区分“看起来合理”和真的必然成立。

查看实践

课程讲义

逻辑与证明

直觉怎样变成可检查的证明？

  1. 01命题逻辑、集合与证明技术讲义
  2. 02数学归纳法讲义
  3. 03稳定匹配讲义
  4. 04图论讲义

代数与计算

有限结构有哪些表达能力？

  1. 05模运算与 RSA讲义
  2. 06多项式、秘密共享与纠错码讲义
  3. 07可数性、可计算性与计数讲义

计数与概率

怎样定义并计算不确定性？

  1. 08组合计数与容斥原理讲义
  2. 09概率基础、条件概率与独立性讲义
  3. 10离散随机变量及其分布讲义

随机变量与极限

大量随机事件有哪些规律？

  1. 11期望、方差、协方差、几何与泊松分布讲义
  2. 12协方差、大数定律与集中不等式讲义
  3. 13连续分布、PDF/CDF 与中心极限定理讲义
  4. 14连续随机变量、CLT 与估计讲义

思考 · 讨论工作簿

先预测，再动手推，最后对照解析。

  1. 01真值表、命题练习、逆/否/逆否命题与量词等价工作簿
  2. 02完全平方、聚会朋友数、卵石与集合运算保持工作簿
  3. 04Bernoulli 归纳、加强假设、二进制表示、斐波那契工作簿
  4. 06稳定匹配：运行、证明与判断工作簿
  5. 08欧拉迹/回路、树染色、奇度顶点工作簿
  6. 09树与连通分量、平面性、超立方体工作簿
  7. 11模末位、模杂题、模逆、斐波那契 GCD工作簿
  8. 12扩展欧几里得（递归与迭代）、CRT 练习、Baby Fermat工作簿
  9. 13RSA 预热、多密钥 RSA、演唱会门票 RSA工作簿
  10. 15GF(p) 多项式、Lagrange 插值、联合国秘密共享与破坏工作簿
  11. 16Berlekamp-Welch 预热、算法演练、少误差情形工作簿
  12. 18可数性判断、证明调试、笛卡尔积工作簿
  13. 19Hello World 可计算性、代码可达性、字符串计数工作簿
  14. 21农夫市场计数、容斥原理、组合恒等式工作簿
  15. 23Venn 图、掷币样本空间、有/无放回抽样工作簿
  16. 24扑克 Ace、弹珠盒、对决气象学家工作簿
  17. 26概率不等式、复活节彩蛋、中毒 Smarties（贝叶斯）工作簿
  18. 27Balls-and-Bins、二项分布（正面计数）、成对独立工作簿
  19. 29几何分布（正面计数 II）、家庭规划、抽球、期望线性性工作簿
  20. 30Beast Arcade 期望、方差、手牌多样化工作簿
  21. 32协方差、机场 Poisson 过程、Poisson 变量和工作簿
  22. 33数字游戏、条件 1 计数、联合分布、学生生活（洗衣）工作簿
  23. 35概率界、Vegas 估计器、大数定律工作簿
  24. 36连续入门（PDF/CDF）、均匀转盘、飞镖（均匀 vs 指数）工作簿
  25. 38高斯趣题、二项浓度、擦除与 CLT 界工作簿
  26. 39指数灯泡、高斯、事件条件化工作簿
  27. 40猜多项式、两信封悖论、飞机座位工作簿

实践 · 工作簿与实验

把理解落到可检查的推导、测试与实现证据。

  1. 03行政、Ed、学术诚信、命题逻辑、蕴含、量词、集合运算工作簿
  2. 05微积分复习、证明或反驳、有理/无理、孪生质数、机场归纳、不等式、AM-GM、硬币游戏工作簿
  3. 07全局偏好、部分匹配、合并稳定配对、积累错误、图证明、二分图工作簿
  4. 10平面性与图补、超立方体周游、二叉树、边染色、模运算练习、Wilson 定理工作簿
  5. 14Fermat 小定理、Euler φ 函数、Euler 定理、素数稀疏性、RSA 练习、RSA 变体工作簿
  6. 17GF(p) 多项式、单点插值、CRT 与 Lagrange、秘密共享、纠错码、Alice 与 Bob工作簿
  7. 20并/交可数性、无限图、可数性证明、不动点、Kolmogorov 复杂性、计数、Fermat 手链工作簿
  8. 22货运箱、网格路径与树、图计数与对称、组合证明、斐波那契时尚工作簿
  9. 25概率热身、Five Up、往昔概率化、随机图团、PIE 推广、独立补工作簿
  10. 28Monty Hall 复仇、说真话的人、Mario 硬币、对称弹珠、饼干罐、航模测试工作簿
  11. 31有损信道、选课、swap 与 cycle、掷飞盘、Balls-and-Bins、我能收到包裹吗工作簿
  12. 34协方差直觉、不可靠服务器、几何与泊松、优惠券收集方差、买概率书、骰子游戏工作簿
  13. 37Cantelli 不等式、优惠券收集方差、估计 π、连续简答、有用均匀、等公交工作簿
  14. 41鱼雨（Poisson 过程）、Noisy Love（高斯信道）、Chebyshev vs CLT、均匀估计工作簿