请输入您要查询的百科知识:

 

词条 概率与计算
释义

基本信息

书名:概率与计算

ISBN:711120805

作者:(美)Michael Mitzenmacher;Eli Upfal

出版社:机械工业出版社

定价:39

出版日期:1900-1-1

简介

本书详细地介绍了概率技术以及在概率算法与分析发展中使用过的范例。本书分两部分,第一部分介绍了随机抽样、期望、马尔可夫不等式、切比雪夫不等式、切尔诺夫界、球和箱子模型、概率技术和马尔可夫链等核心内容。第二部分主要研究连续概率、有限独立性的应用、熵、马尔可夫链蒙特卡罗方法、耦合、鞅和平衡配置等比较高深的课题。.

本书适合作为高等院校计算机科学和应用数学专业高年级本科生与低年级研究生的教材,也适合作为数学工作者和科技人员的参考书。..

随机化与概率技术在现代计算科学中起着重要的作用,其应用遍及组合优化、机器学习、通信网络以及安全协议等诸多领域。

本书详细地介绍了概率技术以及在概率算法与分析发展中使用过的范例。本书分两部分,第一部分介绍了随机抽样、期望、马尔可夫不等式、切比雪夫不等式、切尔诺夫界、球和箱子模型、概率技术和马尔可夫链等核心内容。第二部分主要研究连续概率、有限独立性的应用、熵、马尔可夫链蒙特卡罗方法、耦合、鞅和平衡配置等比较高深的课题。...

目录

译者序

前言.

第1章事件与概率

应用:验证多项式恒等式

概率论公理

应用:验证矩阵乘法

应用:最小割随机化算法

练习

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

随机变量与期望

期望的线性性

詹森不等式

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

条件期望

几何分布

例:赠券收集问题

应用:快速排序的期望运行时间

练习

第3章矩与离差

马尔可夫不等式

随机变量的方差和矩

例:二项随机变量的方差

切比雪夫不等式

例:赠券收集问题

应用:计算中位数的随机化算法

算法

算法分析

练习

第4章切尔诺夫界

矩母函数

切尔诺夫界的导出和应用

泊松试验和的切尔诺夫界

例:投掷硬币

应用:估计参数

某些特殊情况下更好的界

应用:集合的均衡

应用:稀疏网络中的数据包路由选择

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

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

练习

第5章球.c箱子和随机图

例:生日悖论

球和箱子模型

球和箱子模型

应用:桶排序

泊松分布

二项分布的极限

泊松近似

例:赠券收集问题再讨论

应用:散列法

链散列

散列:二进制数字串

Bloom过滤器

放弃对称性

随机图

随机图模型

应用:随机图中的哈密顿圈

练习

探索性作业

第6章概率方法

基本计数论证

期望论证

应用:求最大割

应用:最大可满足性

利用条件期望消除随机化

抽样和修改

应用:独立集合

应用:有较大围长的图

二阶矩方法

应用:随机图的阈性质

条件期望不等式

洛瓦兹局部引理

应用:边不相交的路径

应用:可满足性

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

应用:可满足性算法

洛瓦兹局部引理:一般情况

练习

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

马尔可夫链:定义及表示

应用: 可满足性的随机化算法

应用:可满足性的随机化算法

状态分类

例:赌徒的破产

平稳分布

例:简单的队列

无向图上的随机游动

应用:s-t连通性算法

Parrondo悖论

练习..

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

连续随机变量

R中的概率分布

联合分布与条件概率

均匀分布

均匀分布的其他性质

指数分布

指数分布的其他性质

例:有反馈的球和箱子

泊松过程

到达间隔分布

组合与分解泊松过程

条件到达时间分布

连续时间马尔可夫过程

例:马尔可夫排队论

均衡的M/M/1排队

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

M/M/∞排队中的顾客?

练习

第9章熵 随机性和信息

熵函数

熵和二项式系数

熵:随机性的测度

压缩

编码:香农定理

练习

第10章蒙特卡罗方法

蒙特卡罗方法

应用:DNF计数问题

朴素算法

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

从近似抽样到近似计数

马尔可夫链蒙特卡罗方法

Metropolis算法

练习

最小支撑树的探索性作业

第11章马尔可夫链的耦合

变异距离和混合时间

耦合

例:洗牌

例:超立方体上的随机游动

例:固定大小的独立集合

应用:变异距离是不增的

几何收敛

应用:正常着色法的近似抽样

路径耦合

练习

第12章鞅

停时

例:选举定理

瓦尔德方程

鞅的尾部不等式

Azuma-Hoeffding不等式的应用

一般形式

应用:模式匹配

应用:球和箱子

应用:色数

练习

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

两两独立

例:两两独立的二进制数字的构造

应用:消去最大割算法的随机性

例:构造关于一个素数模的两两独立的值

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

应用:利用少量随机二进制数字的抽样

通用散列函数族

例:一个2维通用散列函数族

例:一个2维强通用散列函数族

应用:完美散列

应用:在数据流中寻找重量级的源终点

练习

第14章平衡配置

两种选择的影响力

上界

两种选择:下界

两种选择影响力的应用

散列

动态资源配置

练习

进一步阅读材料

索引...

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/3/24 9:30:52