Probability and Computing 第一章笔记
最近看 Probability and Computing, 在此记录一些重要结论和有趣算法.
Polynomial Identities
多项式次数为d,则x在[0,100d]随机取值,仅有$\frac{1}{100}$概率错误(根据代数基本定理,f-g最多有d个根).
一些基本定义和引理:
概率定义
容斥原理
事件的独立性
条件概率 $\Pr(E|F)=\frac{\Pr(E\cap F)}{\Pr(F)}$
Veryfying Matrix Multiplication
给定三个方阵 A,B,C 快速验证 $A\times B=C$?
随机算法 随机...