随机算法PDF电子书下载

序言 1

第一部分 工具与技巧 9

第1章 概述 9

§1.1最小切算法 12

§1.2Las Vegas和Monte Carlo 14

§1.3二分平面划分 15

§1.4概率递归 19

§1.5计算模型和复杂性类 21

注释 27

问题 28

第2章 博弈论技术 31

§2.1博弈树估值 31

§2.2最小化最大原则 33

§2.3随机性与非均匀性 39

注释 42

问题 42

第3章 矩和偏差 45

§3.1占有问题 45

§3.2Markov和Chebyshev不等式 47

§3.3随机选择 49

§3.4两点采样 52

§3.5稳定婚姻问题 55

§3.6优惠券收集者问题 58

注释 64

问题 64

第4章 尾不等式 68

§4.1Chernoff界 68

§4.2并行计算机中的路由 74

§4.3布线问题 79

§4.4鞅（Martingale） 83

注释 94

问题 96

第5章 概率法 100

§5.1概率法概论 100

§5.2最大可满足性 102

§5.3扩展图 106

§5.4重审遗忘路由 110

§5.5Lovász局部引理 112

§5.6条件概率法 117

注释 119

问题 120

第6章 Markov链和随机游动 124

§6.12-SAT问题 125

§6.2Markov链 126

§6.3图上的随机游动 128

§6.4电路网络 130

§6.5覆盖时间 132

§6.6图的连通性 134

§6.7扩展以及快速混合随机游动 137

§6.8扩展上的随机游动得到概率放大 145

注释 148

问题 149

第7章 代数技术 154

§7.1指纹和Freivalds技术 155

§7.2验证多项式 156

§7.3图的完美匹配 159

§7.4验证串的相等 160

§7.5指纹技术的比较 161

§7.6模式识别 162

§7.7交互证明系统 164

§7.8PCP和有效证明验证 170

注释 176

问题 178

第二部分 应用 187

第8章 数据结构 187

§8.1基础数据结构问题 187

§8.2随机Treap 190

§8.3跳表 197

§8.4哈希表 201

§8.5 O（1）搜索时间的哈希 209

注释 216

问题 216

第9章 几何算法与线性规划 221

§9.1随机增量构造 221

§9.2平面上的凸包 222

§9.3几何对偶 225

§9.4半空间的交 227

§9.5Delaunary三角划分 230

§9.6梯形分解 233

§9.7二分空间划分 237

§9.8点集合的直径 240

§9.9随机抽样 241

§9.10线性规划 245

注释 256

问题 258

第10章 图算法 261

§10.1所有点对之间的最短路径问题 261

§10.2最小切问题 270

§10.3最小生成树 276

注释 281

问题 283

第11章 近似计数 286

§11.1随机近似方案 287

§11.2DNF计数问题 289

§11.3近似积和式 294

§11.4体积估计 307

注释 308

问题 309

第12章 并行分布式算法 312

§12.1PRAM模型 312

§12.2PRAM上的排序 314

§12.3极大独立集 318

§12.4完美匹配 322

§12.5选择协调问题 329

§12.6拜占庭协议 332

注释 334

问题 336

第13章 在线算法 341

§13.1在线页面管理问题 341

§13.2对手模型 344

§13.3针对不经意对手的页面管理 346

§13.4对手间的相关性 349

§13.5适应性在线对手 353

§13.6k-服务器问题 355

注释 358

问题 360

第14章 数论与代数 363

§14.1准备知识 363

§14.2群和域 365

§14.3二次余数 372

§14.4RSA加密 379

§14.5多项式根及因式 381

§14.6素数检测 385

注释 393

问题 394

附录A符号索引 396

附录B数学背景 400

附录C基本概率论 405

参考文献 413

索引 441