课程概述
算法设计与分析专题之随机算法。
证书要求
证书规则将在开课前发布
预备知识
集合论图论，高等数学，数据结构与算法。
授课大纲
算法设计与分析之随机算法篇
第一周 随机算法概述
1-1 什么是随机算法
1-2 随机算法的分类
1-3 随机算法的思想
第二周 概率基础
2-1 概率与验证
2-2 随机变量与数学期望
2-3 二项分布与几何分布
第三周 矩与离差
3-1马尔可夫不等式
3-2 随机变量的方差和矩
3-3 切比雪夫不等式
3-4 中位数的随机化算法
第四周 切尔诺夫界
4-1 切尔诺夫界
4-2 参数估计
4-3 集合的均衡
第五周 球和箱子
5-1 球和箱子模型
5-2散列法
5-3 随机图
第六周 概率方法
6-1 最大可满足性问题
6-2 最大割问题
6-3 抽样方法
参考资料
殷建平, 徐云, 王刚, 刘晓光, 苏明, 邹恒明, 王宏志 (译). 算法导论. 机械工业出版社, 2012. 12.
