随机算法(Randomized Algorithms)
点此进入淘宝搜索页搜索分類: 图书,科学与自然,数学,概率论与数理统计,
品牌: Rajeev Motwani
基本信息·出版社：高等教育出版社
·页码：452 页
·出版日期：2008年
·ISBN：9787040237238
·条形码：9787040237238
·包装版本：1版
·装帧：平装
·开本：16
·正文语种：中文
·外文书名：Randomized Algorithms
产品信息有问题吗？请帮我们更新产品信息。
内容简介《随机算法》是斯坦福-剑桥项目(Stanford-Cambridge ProSram)之一。对于许多应用，随机算法是最简单可行的，或者是最快的，或者两者兼得。《随机算法》由该领域两位著名专家写成，给出了随机算法设计和分析的基本概念，适用于接近研究生开始阶段的水平。《随机算法》的第一部分介绍了概率论的基本工具，以及在算法应用中经常使用的概率分析。为了说明每个工具的作用，在具体设置给出了一些算法示例。《随机算法》的第二部分为算法的应用，共包括七章，每一章集中在随机算法应用的一个重要领域，如数据结构、几何算法、图算法、数论、计数、并行算法及在线算法等。对于每个领域中的算法，做了全面并且具有代表性的选择。
编辑推荐《随机算法》基本按照教材写成，也可作为一本有价值的参考书供专业人员和研究者使用。
目录
序言.
第一部分工具与技巧
第1章概述
1.1最小切算法
1.2LasVegas和MonteCarlo
1.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随机Treap
8.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基本概率论
参考文献
索引
……[看更多目录]
