| 序言.第一部分 工具与技巧第1章 概述1.1最小切算法1.2LasVegas和MonteCarlo1.3二分平面划分1.4概率递归1.5计算模型和复杂性类注释问题第2章 博弈论技术2.1博弈树估值2.2最小化最大原则2.3随机性与非均匀性注释问题第3章 矩和偏差3.1占有问题3.2Markov和Chebyshev不等式3.3随机选择3.4两点采样3.5稳定婚姻问题3.6优惠券收集者问题注释问题第4章 尾不等式4.1Chernoff界4.2并行计算机中的路由4.3布线问题4.4鞅(Martingale)注释问题第5章 概率法5.1概率法概论5.2最大可满足性5.3扩展图5.4重审遗忘路由5.5Lovasz局部引理5.6条件概率法注释问题第6章 Markov链和随机游动6.12-SAT问题6.2Markov链6.3图上的随机游动6.4电路网络6.5覆盖时间6.6图的连通性6.7扩展以及快速混合随机游动6.8扩展上的随机游动得到概率放大注释问题第7章 代数技术7.1指纹和Freivalds技术7.2验证多项式7.3图的完美匹配7.4验证串的相等7.5指纹技术的比较7.6模式识别7.7交互证明系统7.8PCP和有效证明验证注释问题第二部分 应用..第8章 数据结构8.1基础数据结构问题8.2随机Treap8.3跳表8.4哈希表8.5O(1)搜索时间的哈希注释问题第9章 几何算法与线性规划9.1随机增量构造9.2平面上的凸包9.3几何对偶9.4半空间的交9.5Delaunary三角划分9.6梯形分解9.7分空间划分9.8点集合的直径9.9随机抽样9.10线性规划注释问题第10章 图算法10.1所有点对之间的最短路径问题10.2最小切问题10.3最小生成树注释问题第11章 近似计数11.1随机近似方案11.2DNF计数问题11.3近似积和式11.4体积估计注释问题第12章 并行分布式算法12.1PRAM模型12.2PRAM上的排序12.3极大独立集12.4完美匹配12.5选择协调问题12.6拜占庭协议注释问题第13章 在线算法13.1在线页面管理问题13.2对手模型13.3针对不经意对手的页面管理13.4对手间的相关性13.5适应性在线对手13.6k-服务器问题注释问题第14章 数论与代数14.1准备知识14.2群和域14.3二次余数14.4RSA加密14.5多项式根及因式14.6素数检测注释问题附录A符号索引附录B数学背景附录C基本概率论参考文献索引 |
内容加载中，请稍后...
商品评论（0条）