首页 > 代码库 > 中科院随机算法课程(孙晓明主讲)topic list

中科院随机算法课程(孙晓明主讲)topic list

如题,列出《随机算法》课程的topic list,以记录和供有兴趣的朋友研究。

Lession1:生日悖论、生日攻击、两个常用数学工具(马尔科夫不等式、切比雪夫不等式)

Lession2:radom quick sort(hw)、矩阵乘法判定、min(max())=max(min())、复杂性类(BPP/RP/CORP/ZPP)

Lession3:证明BPP2/3=BPP0.99、ZPP<=RP^CORP、Game Tree

Lession4:Balls and Bins

Lession5:Chernoff Bound

      · bit-fixing算法及其randome版本

Lession6:概率方法

      · 素数定理、Ramsey、最大割、cligque问题

Lession7:MAX set问题