华章数学译丛概率与计算:算法与数据分析中的随机化和概率技术(原书第2版)/(美)迈克尔.米森马彻

译者序
第2版前言
第1版前言

第1章 事件与概率
1．1 应用：验证多项式恒等式
1．2 概率论公理
1．3 应用：验证矩阵乘法
1．4 应用：朴素贝叶斯分类器
1．5 应用：*小割随机化算法
1．6 练习

第2章 离散型随机变量与期望
2．1 随机变量与期望
2．1．1 期望的线性性
2．1．2 詹森不等式
2．2 伯努利随机变量和二项随机变量
2．3 条件期望
2．4 几何分布
2．5 应用：快速排序的期望运行时间
2．6 练习

第3章 矩与离差
3．1 马尔可夫不等式
3．2 随机变量的方差和矩
3．3 切比雪夫不等式
3．4 中位数和平均值
3．5 应用：计算中位数的随机化算法
3．5．1 算法
3．5．2 算法分析
3．6 练习

第4章 切尔诺夫界与霍夫丁界
4．1 矩母函数
4．2 切尔诺夫界的导出和应用
4．2．1 泊松试验和的切尔诺夫界
4．2．2 例：投掷硬币
4．2．3 应用：估计参数
4．3 某些特殊情况下更好的界
4．4 应用：集合的均衡
4．5 霍夫丁界
*4．6 应用：稀疏网络中的数据包路由选择
4．6．1 超立方体网络上排列的路由选择
4．6．2 蝶形网络上排列的路由选择
4．7 练习

第5章 球、箱子和随机图
5．1 例：生日悖论
5．2 球放进箱子
5．2．1 球和箱子模型
5．2．2 应用：桶排序
5．3 泊松分布
5．4 泊松近似
5．5 应用：散列法
5．5．1 链散列
5．5．2 散列：二进制数字串
5．5．3 Bloom过滤器
5．5．4 放弃对称性
5．6 随机图
5．6．1 随机图模型
5．6．2 应用：随机图中的哈密顿圈
5．7 练习
5．8 探索性作业

第6章 概率方法
6．1 基本计数论证
6．2 期望论证
6．2．1 应用：求*大割
6．2．2 应用：*大可满足性
6．3 利用条件期望消除随机化
6．4 抽样和修改
6．4．1 应用：独立集合
6．4．2 应用：有较大围长的图
6．5 二阶矩方法
6．6 条件期望不等式
6．7 洛瓦兹局部引理
6．7．1 应用：边不相交的路径
6．7．2 应用：可满足性
*6．8 利用洛瓦兹局部引理的显式构造
6．9 洛瓦兹局部引理：一般情况
*6．10 洛瓦兹算法局部引理
6．11 练习
……

第7章 马尔可夫链及随机游动
第8章 连续分布与泊松过程
第9章 正态分布
第10章 熵、随机性和信息
第11章 蒙特卡罗方法
第12章 马尔可夫链的耦合
第13章 鞅
第14章 样本复杂度、VC维度以及拉德马赫复杂度
第15章 两两独立及通用散列函数
第16章 幂律及相关的分布
第17章 平衡分配和布谷鸟散列
延伸阅读