概率与计算 算法与数据分析中的随机化和概率技术 原书第2版PDF电子书下载

查看更多关于的内容

第1章 事件与概率 1

1.1 应用：验证多项式恒等式 1

1.2 概率论公理 2

1.3 应用：验证矩阵乘法 6

1.4 应用：朴素贝叶斯分类器 9

1.5 应用：最小割随机化算法 11

1.6 练习 13

第2章 离散型随机变量与期望 17

2.1 随机变量与期望 17

2.1.1 期望的线性性 18

2.1.2 詹森不等式 19

2.2 伯努利随机变量和二项随机变量 20

2.3 条件期望 21

2.4 几何分布 24

2.5 应用：快速排序的期望运行时间 27

2.6 练习 29

第3章 矩与离差 33

3.1 马尔可夫不等式 33

3.2 随机变量的方差和矩 33

3.3 切比雪夫不等式 36

3.4 中位数和平均值 38

3.5 应用：计算中位数的随机化算法 40

3.5.1 算法 40

3.5.2 算法分析 41

3.6 练习 44

第4章 切尔诺夫界与霍夫丁界 46

4.1 矩母函数 46

4.2 切尔诺夫界的导出和应用 47

4.2.1 泊松试验和的切尔诺夫界 47

4.2.2 例：投掷硬币 50

4.2.3 应用：估计参数 50

4.3 某些特殊情况下更好的界 51

4.4 应用：集合的均衡 53

4.5 霍夫丁界 54

4.6 应用：稀疏网络中的数据包路由选择 56

4.6.1 超立方体网络上排列的路由选择 56

4.6.2 蝶形网络上排列的路由选择 61

4.7 练习 65

第5章 球、箱子和随机图 69

5.1 例：生日悖论 69

5.2 球放进箱子 70

5.2.1 球和箱子模型 70

5.2.2 应用：桶排序 71

5.3 泊松分布 72

5.4 泊松近似 75

5.5 应用：散列法 81

5.5.1 链散列 81

5.5.2 散列：二进制数字串 82

5.5.3 Bloom过滤器 83

5.5.4 放弃对称性 85

5.6 随机图 85

5.6.1 随机图模型 85

5.6.2 应用：随机图中的哈密顿圈 87

5.7 练习 92

5.8 探索性作业 95

第6章 概率方法 97

6.1 基本计数论证 97

6.2 期望论证 99

6.2.1 应用：求最大割 99

6.2.2 应用：最大可满足性 100

6.3 利用条件期望消除随机化 101

6.4 抽样和修改 102

6.4.1 应用：独立集合 102

6.4.2 应用：有较大围长的图 103

6.5 二阶矩方法 103

6.6 条件期望不等式 105

6.7 洛瓦兹局部引理 107

6.7.1 应用：边不相交的路径 109

6.7.2 应用：可满足性 109

6.8 利用洛瓦兹局部引理的显式构造 110

6.9 洛瓦兹局部引理：一般情况 113

6.10 洛瓦兹算法局部引理 114

6.11 练习 118

第7章 马尔可夫链及随机游动 122

7.1 马尔可夫链：定义及表示 122

7.1.1 应用：2-可满足性的随机化算法 124

7.1.2 应用：3-可满足性的随机化算法 127

7.2 状态分类 130

7.3 平稳分布 133

7.4 无向图上的随机游动 138

7.5 Parrondo悖论 141

7.6 练习 144

第8章 连续分布与泊松过程 149

8.1 连续随机变量 149

8.1.1 R中的概率分布 149

8.1.2 联合分布与条件概率 150

8.2 均匀分布 152

8.3 指数分布 155

8.3.1 指数分布的其他性质 155

8.3.2 例：有反馈的球和箱子 157

8.4 泊松过程 159

8.4.1 到达间隔分布 161

8.4.2 组合与分解泊松过程 162

8.4.3 条件到达时间分布 163

8.5 连续时间马尔可夫过程 165

8.6 例：马尔可夫排队论 167

8.6.1 均衡的M/M/1排队 167

8.6.2 均衡的M/M/1/K排队 169

8.6.3 M/M/∞排队中的顾客数 170

8.7 练习 171

第9章 正态分布 176

9.1 正态分布 176

9.1.1 标准正态分布 176

9.1.2 一般单变量正态分布 177

9.1.3 矩母函数 179

9.2 二项分布的极限 180

9.3 中心极限定理 182

9.4 多维正态分布 184

9.5 应用：生成正态分布的随机值 187

9.6 最大似然点估计 189

9.7 应用：针对混合高斯分布的EM算法 192

9.8 练习 195

第10章 熵、随机性和信息 198

10.1 熵函数 198

10.2 熵和二项式系数 200

10.3 熵：随机性的测度 201

10.4 压缩 205

10.5 编码：香农定理 207

10.6 练习 213

第11章 蒙特卡罗方法 218

11.1 蒙特卡罗方法 218

11.2 应用：DNF计数问题 219

11.2.1 朴素算法 220

11.2.2 DNF计数问题的完全多项式随机方案 221

11.3 从近似抽样到近似计数 223

11.4 马尔可夫链蒙特卡罗方法 226

11.5 练习 229

11.6 最小支撑树的探索作业 231

第12章 马尔可夫链的耦合 232

12.1 变异距离和混合时间 232

12.2 耦合 234

12.2.1 例：洗牌 235

12.2.2 例：超立方体上的随机游动 235

12.2.3 例：固定大小的独立集合 236

12.3 应用：变异距离是不增的 237

12.4 几何收敛 239

12.5 应用：正常着色法的近似抽样 240

12.6 路径耦合 243

12.7 练习 246

第13章 鞅 250

13.1 鞅 250

13.2 停时 251

13.3 瓦尔德等式 254

13.4 鞅的尾部不等式 256

13.5 Azuma-Hoeffding不等式的应用 257

13.5.1 一般形式 257

13.5.2 应用：模式匹配 259

13.5.3 应用：球和箱子 260

13.5.4 应用：色数 260

13.6 练习 260

第14章 样本复杂度、VC维度以及拉德马赫复杂度 264

14.1 “学习”问题 265

14.2 VC维度 266

14.2.1 VC维度的其他例子 267

14.2.2 增长函数 268

14.2.3 VC维度的合成界 269

14.2.4 ε-网和ε-样本 270

14.3 ε-网定理 271

14.4 应用：PAC学习 274

14.5 ε-样本定理 276

14.5.1 应用：不可知学习 279

14.5.2 应用：数据挖掘 279

14.6 拉德马赫复杂度 281

14.6.1 拉德马赫复杂度和样本错误 283

14.6.2 估计拉德马赫复杂度 284

14.6.3 应用：二值分类的不可知学习 285

14.7 练习 286

第15章 两两独立及通用散列函数 288

15.1 两两独立 288

15.1.1 例：两两独立的二进制数字的构造 288

15.1.2 应用：消去最大割算法的随机性 289

15.1.3 例：构造关于一个素数模的两两独立的值 290

15.2 两两独立变量的切比雪夫不等式 291

15.3 通用散列函数族 293

15.3.1 例：一个2维通用散列函数族 295

15.3.2 例：强2维通用散列函数族 295

15.3.3 应用：完美散列 297

15.4 应用：在数据流中寻找重量级的源-终点 299

15.5 练习 302

第16章 幂律及相关的分布 305

16.1 幂律分布：基本定义和性质 305

16.2 语言中的幂律 307

16.2.1 Zipf定律和其他例子 307

16.2.2 语言优化 307

16.2.3 猴子随意打字 308

16.3 偏好链接 309

16.4 幂律在算法分析中的应用 312

16.5 其他相关的分布 314

16.5.1 对数正态分布 314

16.5.2 具有指数截断的幂律 315

16.6 练习 315

第17章 平衡分配和布谷鸟散列 318

17.1 两种选择的影响力 318

17.2 两种选择：下界 322

17.3 两种选择影响力的应用 324

17.3.1 散列法 324

17.3.2 动态资源分配 325

17.4 布谷鸟散列 325

17.5 布谷鸟散列的扩展 332

17.5.1 带删除的布谷鸟散列 332

17.5.2 处理故障 333

17.5.3 更多的选择和更大的箱子 334

17.6 练习 335

延伸阅读 339

查看更多关于的内容