最大流算法：

1. majority算法
2. Misra-Gries算法

贝尔曼最优化方法

动态规划问题的理论基础：多阶段决策过程具有这样的性质，即不管过去的过程如何，只从当前的状态和系统的最优化要求出发，作出下一步的最优决策

1. 问题中的状态必须满足最优化原理；
2. 问题中的状态必须满足无后效性。

马尔可夫不等式：

$$Pr(x \geq a)\leq\frac{E(x)}$$

切比雪夫：

$$Pr(|x-E(x)| \geq k)\leq\frac{Var(x)}{E^2}$$

切尔诺夫不等式

$$ Pr(x \geq (1+\delta)\mu)\leq\exp(-\delta^{2\mu/3) $$
$$ Pr(x \leq (1+\delta)\mu)\leq\exp(-\delta}2\mu/2) $$

simple count(randomised algorithm)

tidemark(improved

randomised algorithm)