搜索
高级检索
高级搜索
书       名 :
著       者 :
出  版  社 :
I  S  B  N:
文献来源:
出版时间 :
随机算法
0.00    
图书来源: 浙江图书馆(由图书馆配书)
  • 配送范围:
    全国(除港澳台地区)
  • ISBN:
    9787040237238
  • 作      者:
    Rajeev Motwani,Prabhakar Raghavan著
  • 出 版 社 :
    高等教育出版社
  • 出版日期:
    2008
收藏
编辑推荐
    《随机算法》基本按照教材写成,也可作为一本有价值的参考书供专业人员和研究者使用。
展开
内容介绍
    《随机算法》是斯坦福-剑桥项目(Stanford-Cambridge ProSram)之一。对于许多应用,随机算法是最简单可行的,或者是最快的,或者两者兼得。《随机算法》由该领域两位著名专家写成,给出了随机算法设计和分析的基本概念,适用于接近研究生开始阶段的水平。《随机算法》的第一部分介绍了概率论的基本工具,以及在算法应用中经常使用的概率分析。为了说明每个工具的作用,在具体设置给出了一些算法示例。《随机算法》的第二部分为算法的应用,共包括七章,每一章集中在随机算法应用的一个重要领域,如数据结构、几何算法、图算法、数论、计数、并行算法及在线算法等。对于每个领域中的算法,做了全面并且具有代表性的选择。
展开
目录
    序言<br>第一部分 工具与技巧<br>第1章 概述<br>§1.1 最小切算法<br>§1.2 Las Vegas和Monte Carlo<br>§1.3 二分平面划分<br>§1.4 概率递归<br>§1.5 计算模型和复杂性类<br>注释<br>问题<br><br>第2章 博弈论技术<br>§2.1 博弈树估值<br>§2.2 最小化最大原则<br>§2.3 随机性与非均匀性<br>注释<br>问题<br><br>第3章 矩和偏差<br>§3.1 占有问题<br>§3.2 Markov和Chebyshev不等式<br>§3.3 随机选择<br>§3.4 两点采样<br>§3.5 稳定婚姻问题<br>§3.6 优惠券收集者问题<br>注释<br>问题<br><br>第4章 尾不等式<br>§4.1 Chernoff界<br>§4.2 并行计算机中的路由<br>§4.3 布线问题<br>§4.4 鞅(Martingale)<br>注释<br>问题<br><br>第5章 概率法<br>§5.1 概率法概论<br>§5.2 最大可满足性<br>§5.3 扩展图<br>§5.4 重审遗忘路由<br>§5.5 Lovasz局部引理<br>§5.6 条件概率法<br>注释<br>问题<br><br>第6章 Markov链和随机游动<br>§6.1 2-SAT问题<br>§6.2 Markov链<br>§6.3 图上的随机游动<br>§6.4 电路网络<br>§6.5 覆盖时间<br>§6.6 图的连通性<br>§6.7 扩展以及快速混合随机游动<br>§6.8 扩展上的随机游动得到概率放大<br>注释<br>问题<br><br>第7章 代数技术<br>§7.1 指纹和Freivalds技术<br>§7.2 验证多项式<br>§7.3 图的完美匹配<br>§7.4 验证串的相等<br>§7.5 指纹技术的比较<br>§7.6 模式识别<br>§7.7 交互证明系统<br>§7.8 PCP和有效证明验证<br>注释<br>问题<br><br>第二部分 应用<br>第8章 数据结构<br>§8.1 基础数据结构问题<br>§8.2 随机Treap<br>§8.3 跳表<br>§8.4 哈希表<br>§8.5 O(1)搜索时间的哈希<br>注释<br>问题<br><br>第9章 几何算法与线性规划<br>§9.1 随机增量构造<br>§9.2 平面上的凸包<br>§9.3 几何对偶<br>§9.4 半空间的交<br>§9.5 Delaunary三角划分<br>§9.6 梯形分解<br>§9.7 二分空间划分<br>§9.8 点集合的直径<br>§9.9 随机抽样<br>§9.1 0线性规划<br>注释<br>问题<br><br>第10章 图算法<br>§10.1 所有点对之间的最短路径问题<br>§10.2 最小切问题<br>§10.3 最小生成树<br>注释<br>问题<br><br>第11章 近似计数<br>§11.1 随机近似方案<br>§11.2 DNF计数问题<br>§11.3 近似积和式<br>§11.4 体积估计<br>注释<br>问题<br><br>第12章 并行分布式算法<br>§12.1 PRAM模型<br>§12.2 PRAM上的排序<br>§12.3 极大独立集<br>§12.4 完美匹配<br>§12.5 选择协调问题<br>§12.6 拜占庭协议<br>注释<br>问题<br><br>第13章 在线算法<br>§13.1 在线页面管理问题<br>§13.2 对手模型<br>§13.3 针对不经意对手的页面管理<br>§13.4 对手间的相关性<br>§13.5 适应性在线对手<br>§13.6 k-服务器问题<br>注释<br>问题<br><br>第14章 数论与代数<br>§14.1 准备知识<br>§14.2 群和域<br>§14.3 二次余数<br>§14.4 RSA加密<br>§14.5 多项式根及因式<br>§14.6 素数检测<br>注释<br>问题<br>附录A 符号索引<br>附录B 数学背景<br>附录C 基本概率论<br>参考文献<br>索引
展开
加入书架成功!
收藏图书成功!
我知道了(3)
发表书评
读者登录

请选择您读者所在的图书馆

选择图书馆
浙江图书馆
点击获取验证码
登录
没有读者证?在线办证