新書推薦：
《
突破不可能：用特工思维提升领导力
》
售價：HK$
77.3
《
王阳明大传：知行合一的心学智慧（精装典藏版）
》
售價：HK$
221.8
《
失衡与重塑——百年变局下的中国与世界经济
》
售價：HK$
132.2
《
不被定义的年龄：积极年龄观让我们更快乐、健康、长寿
》
售價：HK$
77.3
《
南方谈话：邓小平在1992
》
售價：HK$
80.6
《
纷纭万端 ： 近代中国的思想与社会
》
售價：HK$
109.8
《
中国古代文体形态研究（第四版）（中华当代学术著作辑要）
》
售價：HK$
168.0
《
朋党之争与北宋政治·大学问
》
售價：HK$
99.7
|
| 編輯推薦： |
本书是概率论与计算机科学相结合的完美教材。它系统地介绍了概率论、随机过程及样本复杂度、VC 维度和拉德马赫复杂度等理论知识，并介绍了使用本章理论去解决一些实际问题的算法设计技巧。 其目的在于帮助读者学会如何利用概率论理论及计算机求解实际问题。本书覆盖的知识面很广，全书共分为两部分，第壹部分介绍了随机抽样、期望、马尔可夫不等式、切比雪夫不等式、切尔诺夫界、球和箱子模型、概率技术和马尔可夫链等核心内容。第二部分主要研究连续概率、有限独立性的应用、熵、马尔可夫链蒙特卡罗方法、耦合、鞅及平衡配置等比较高深的内容。
本书可作为高年级本科生或低年级研究生的教材及教学参考书。
本书特色：
•本书内容全面，结构严谨，几乎所有定理都给出了详细证明。
•本书所选例题和现实中的问题紧密相关，且大部分案例都是目前相关学科（如计算机网络、图论、机器学习等）的热点问题。
• 许多案例常常给出多种求解方案，并分析比较这些方案的时间效率和空间效率。
• 本书的每一章都包含大量习题，且一些算法练习有可操作性的引导。
|
| 內容簡介： |
本书详细地介绍了概率技术以及在概率算法与分析发展中使用过的范例。本书分两部分，第壹部分介绍了随机抽样、期望、马尔可夫不等式、切比雪夫不等式、切尔诺夫界、球和箱子模型、概率技术和马尔可夫链等核心内容。第二部分主要研究连续概率、有限独立性的应用、熵、马尔可夫链蒙特卡罗方法、耦合、鞅和平衡配置等比较高深的课题。
本书适合作为高等院校计算机科学和应用数学专业高年级本科生与低年级研究生的教材，也适合作为数学工作者和科技人员的参考书。
|
| 關於作者： |
迈克尔·米森马彻（Michael Mitzenmacher）是哈佛大学的计算机科学教授，他于1996年在加州大学伯克利分校获得博士学位。在1999年进入哈佛大学之前，他是PaloAlto数字系统研究实验室的研究员。他获得了NSF职业奖和艾尔弗雷德·P·斯隆研究奖学金。2002年，他因在纠错码方面的工作而获得IEEE信息理论学会“*佳论文”奖。
Eli Upfal是布朗大学计算机科学系的教授、系主任。他在以色列耶路撒冷的希伯来大学获得了博士学位，在1997年进入布朗大学之前，他是IBM研究部的研究员，以色列魏兹曼科学研究所的教授。 他的主要研究兴趣是随机计算与算法的概率分析及其在优化算法中的应用， 通信网络，并行和分布式计算，以及计算生物学等。
|
| 目錄：
|
译者序
第2版前言
第1版前言
第1章 事件与概率1
1.1 应用：验证多项式恒等式1
1.2 概率论公理2
1.3 应用：验证矩阵乘法6
1.4 应用：朴素贝叶斯分类器9
1.5 应用：最小割随机化算法11
1.6 练习13
第2章 离散型随机变量与期望17
2.1 随机变量与期望17
2.1.1 期望的线性性18
2.1.2 詹森不等式19
2.2 伯努利随机变量和二项随机变量20
2.3 条件期望21
2.4 几何分布24
2.5 应用：快速排序的期望运行时间27
2.6 练习29
第3章 矩与离差33
3.1 马尔可夫不等式33
3.2 随机变量的方差和矩33
3.3 切比雪夫不等式36
3.4 中位数和平均值38
3.5 应用：计算中位数的随机化算法40
3.5.1 算法40
3.5.2 算法分析41
3.6 练习44
第4章 切尔诺夫界与霍夫丁界46
4.1 矩母函数46
4.2 切尔诺夫界的导出和应用47
4.2.1 泊松试验和的切尔诺夫界47
4.2.2 例：投掷硬币50
4.2.3 应用：估计参数50
4.3 某些特殊情况下更好的界51
4.4 应用：集合的均衡53
4.5 霍夫丁界54
* 4.6 应用：稀疏网络中的数据包路由选择56
4.6.1 超立方体网络上排列的路由选择56
4.6.2 蝶形网络上排列的路由选择61
4.7 练习65
第5章 球、箱子和随机图69
5.1 例：生日悖论69
5.2 球放进箱子70
5.2.1 球和箱子模型70
5.2.2 应用：桶排序71
5.3 泊松分布72
5.4 泊松近似75
5.5 应用：散列法81
5.5.1 链散列81
5.5.2 散列：二进制数字串82
5.5.3 Bloom过滤器83
5.5.4 放弃对称性85
5.6 随机图85
5.6.1 随机图模型85
5.6.2 应用：随机图中的哈密顿圈87
5.7 练习92
5.8 探索性作业95
第6章 概率方法97
6.1 基本计数论证97
6.2 期望论证99
6.2.1 应用：求最大割99
6.2.2 应用：最大可满足性100
6.3 利用条件期望消除随机化101
6.4 抽样和修改102
6.4.1 应用：独立集合102
6.4.2 应用：有较大围长的图103
6.5 二阶矩方法103
6.6 条件期望不等式105
6.7 洛瓦兹局部引理107
6.7.1 应用：边不相交的路径109
6.7.2 应用：可满足性109
* 6.8 利用洛瓦兹局部引理的显式构造110
6.9 洛瓦兹局部引理：一般情况113
* 6.10 洛瓦兹算法局部引理114
6.11 练习118
第7章 马尔可夫链及随机游动122
7.1 马尔可夫链：定义及表示122
7.1.1 应用：2可满足性的随机化算法124
7.1.2 应用：3可满足性的随机化算法127
7.2 状态分类130
7.3 平稳分布133
7.4 无向图上的随机游动138
7.5 Parrondo悖论141
7.6 练习144
第8章 连续分布与泊松过程149
8.1 连续随机变量149
8.1.1 R中的概率分布149
8.1.2 联合分布与条件概率150
8.2 均匀分布152
8.3 指数分布155
8.3.1 指数分布的其他性质155
* 8.3.2 例：有反馈的球和箱子157
8.4 泊松过程159
8.4.1 到达间隔分布161
8.4.2 组合与分解泊松过程162
8.4.3 条件到达时间分布163
8.5 连续时间马尔可夫过程165
8.6 例：马尔可夫排队论167
8.6.1 均衡的MM1排队167
8.6.2 均衡的MM1K排队169
8.6.3 MM∞排队中的顾客数170
8.7 练习171
第9章 正态分布176
9.1 正态分布176
9.1.1 标准正态分布176
9.1.2 一般单变量正态分布177
9.1.3 矩母函数179
* 9.2 二项分布的极限180
9.3 中心极限定理182
* 9.4 多维正态分布184
9.5 应用：生成正态分布的随机值187
9.6 最大似然点估计189
9.7 应用：针对混合高斯分布的EM算法192
9.8 练习195
第10章 熵、随机性和信息198
10.1 熵函数198
10.2 熵和二项式系数200
10.3 熵：随机性的测度201
10.4 压缩205
* 10.5 编码：香农定理207
10.6 练习213
第11章 蒙特卡罗方法218
11.1 蒙特卡罗方法218
11.2 应用：DNF计数问题219
11.2.1 朴素算法220
11.2.2 DNF计数问题的完全多项式随机方案221
11.3 从近似抽样到近似计数223
11.4 马尔可夫链蒙特卡罗方法226
11.5 练习229
11.6 最小支撑树的探索作业231
*第12章 马尔可夫链的耦合232
12.1 变异距离和混合时间232
12.2 耦合234
12.2.1 例：洗牌235
12.2.2 例：超立方体上的随机游动235
12.2.3 例：固定大小的独立集合236
12.3 应用：变异距离是不增的237
12.4 几何收敛239
12.5 应用：正常着色法的近似抽样240
12.6 路径耦合243
12.7 练习246
第13章 鞅250
13.1 鞅250
13.2 停时251
13.3 瓦尔德等式254
13.4 鞅的尾部不等式256
13.5 Azuma-Hoeffding不等式的应用257
13.5.1 一般形式257
13.5.2 应用：模式匹配259
13.5.3 应用：球和箱子260
13.5.4 应用：色数260
13.6 练习260
第14章 样本复杂度、VC维度以及拉德马赫复杂度264
14.1 “学习”问题265
14.2 VC维度266
14.2.1 VC维度的其他例子267
14.2.2 增长函数268
14.2.3 VC维度的合成界269
14.2.4 ε-网和ε-样本270
14.3 ε-网定理271
14.4 应用：PAC学习274
14.5 ε-样本定理276
14.5.1 应用：不可知学习279
14.5.2 应用：数据挖掘279
14.6 拉德马赫复杂度281
14.6.1 拉德马赫复杂度和样本错误283
14.6.2 估计拉德马赫复杂度284
14.6.3 应用：二值分类的不可知学习285
14.7 练习286
第15章 两两独立及通用散列函数288
15.1 两两独立288
15.1.1 例：两两独立的二进制数字的构造288
15.1.2 应用：消去最大割算法的随机性289
15.1.3 例：构造关于一个素数模的两两独立的值290
15.2 两两独立变量的切比雪夫不等式291
15.3 通用散列函数族293
15.3.1 例：一个2维通用散列函数族295
15.3.2 例：强2维通用散列函数族295
15.3.3 应用：完美散列297
15.4 应用：在数据流中寻找重量级的源终点299
15.5 练习302
第16章 幂律及相关的分布305
16.1 幂律分布：基本定义和性质305
16.2 语言中的幂律307
16.2.1 Zipf定律和其他例子307
16.2.2 语言优化307
16.2.3 猴子随意打字308
16.3 偏好链接309
16.4 幂律在算法分析中的应用312
16.5 其他相关的分布314
16.5.1 对数正态分布314
16.5.2 具有指数截断的幂律315
16.6 练习315
第17章 平衡分配和布谷鸟散列318
17.1 两种选择的影响力318
17.2 两种选择：下界322
17.3 两种选择影响力的应用324
17.3.1 散列法324
17.3.2 动态资源分配325
17.4 布谷鸟散列325
17.5 布谷鸟散列的扩展332
17.5.1 带删除的布谷鸟散列332
17.5.2 处理故障333
17.5.3 更多的选择和更大的箱子334
17.6 练习335
延伸阅读339
|
| 內容試閱：
|
第2版前言
本书的初版已经过了10年，随着大数据分析、机器学习和数据挖掘的重要性越来越突出，概率方法对于计算机科学来说也变得越来越核心．许多相关领域的应用成果，其算法和思路都是建立在对概率与统计的成熟理解基础之上的，要想正确地使用这些工具，对于这些数学概念的透彻理解是必不可少的．而第2版新增的主要内容就是着重于这些概念的介绍．
近年来，诸如万维网、社交网络、基因数据等使得我们能够产生、收集和存储大量的样本数据集，这对我们建立模型和分析这些数据的结构提出了新的挑战．熟练掌握一些标准的分布可以给建立和分析模型打下一个好的基础，新增的第9章包含了绝大多数常见的统计分布，同时也像之前一样，会强调这些分布在计算机科学中如何应用，比如确定分布的尾界等．然而，诸如万维网和社交网络等现代数据集有着一个奇妙的现象，在其中我们往往见不到正态分布，取而代之的是一种有着非常不同性质的、很少见的、特征明显的重尾分布．例如，在万维网中，一些页面经常会有大量的网页链接它们，其被链接的数量要高过平均水平一个数量级．第2版新增的第16章将包含对于建模和理解这种现代数据集来说非常重要的那些特殊分布．
机器学习是近年来计算机科学领域的重大成果之一，它提供了许多高效的工具来建模、理解和预测大数据．但是预测的准确性，特别是准确性和样本容量的关系这一点却常常被人忽略．第2版中新增的第14章将会对这些重要的内容进行详细的介绍．
在新版中，我们也对之前的部分内容进行了充实和更新．例如，我们介绍了重要的洛瓦兹局部引理的算法变化的一些新进展，也新增了一小节用来介绍布谷鸟散列这种享誉盛名且越来越实用的散列法．最后，除了这些新增内容，新版也包括了修正、勘误和许多新习题．
我们对几年来向我们发送了诸多勘误的读者表示由衷的感谢，可惜人数过于众多，我们在此不一一列出了，还望海涵．
第1版前言
为什么要研究随机性
计算机科学家为什么要研究和使用随机性呢?这是因为计算机出现了太多不可预见的状况!加入随机性似乎是一个缺点,它使得有效地使用计算机这种已经具有挑战性的工作变得更加复杂．
从20世纪开始,科学研究已经将随机性视为建模和分析中的基本组成部分．例如,在物理学上,牛顿定律使人们相信宇宙的位置是确定的：如果有一个足够大的计算工具和合适的初始条件,人们可以确定若干年后行星的位置．然而量子理论的发展却提出了不同的观点：宇宙仍旧按照自然法则运转,但是这些自然法则的核心是随机性的．“上帝不会同宇宙玩骰子”，这是爱因斯坦用来反驳现代量子力学的一句名言．然而,当代亚微粒子物理学的主要理论仍然是建立在随机现象和统计规律基础之上的,并且在从生物学的遗传与进化到自由市场经济的价格波动模型等几乎所有其他科学领域中,随机性都起着非常重要的作用．
计算机科学也不例外，从一些概率定理证明的高深理论到个人计算机以太网卡的实用性设计,随机性和概率方法在现代计算机科学中都扮演了关键角色．过去20年以来,概率论在计算中的应用得到了巨大的发展,越来越高级、越来越复杂的概率技术已经被应用于更加广泛和更富挑战性的计算机科学应用中．在本书中,我们主要研究随机性应用于计算机科学的基本方法：随机化算法和算法的概率分析．
随机化算法：随机化算法是执行过程中要求作随机选择的算法．实际上,随机化程序会使用由随机数发生器产生的数值,从若干执行分支中决定下一步执行哪个分支．例如,以太网卡协议用随机数决定何时试图访问共享的以太网通信介质．随机性在打破对称性、防止不同的以太网卡同时重复访问介质方面是非常有用的．随机化算法的其他常见应用还包括蒙特卡罗模拟和密码学中的初始检验．在这些以及其他重要应用中,随机化算法比最有名的确定性方法更有效,并且在大多数情况下更简单,更容易编写程序．
当然，这些优点也是需要付出一定代价的,问题的答案在一定的概率下是不正确的,或者只以某个概率保证有效．虽然设计一个有可能错误的算法似乎有点奇怪,但是如果错误发生的概率很小,那么提高运行速度和减少占用的内存是有价值的．
算法的概率分析：复杂性理论根据计算的复杂性对问题进行分类,尤其是区分简单问题和有难度的问题．例如,复杂性理论认为流动推销员问题是一个NP难题．如果城市数量以次指数增长,那么不可能存在可以解决流动推销员问题的任何一个实用的算法．对于经典的最坏情况复杂性理论,一个令人困惑的现象是,在分类上属于有难度的计算问题,实际上却很容易解决，概率分析对这种现象给出了理论上的解释．虽然对某些不合理的输入数据,问题难以解决,但对大多数输入尤其是在日常的应用中,这些问题实际上却容易解决．更确切地说,如果我们认为输入是随机选择的结果,而随机选择是根据所有可能输入数据集上的某个概率分布作出的,就很有可能得到一个易于解答的问题实例,而这些实例不能求解的概率是相对较小的．算法的概率分析是研究当输入来自某一适当定义的概率空间时算法如何运行的一种方法．书中我们将会看到,即使是NP难题,也会有对于几乎所有输入都极其有效的算法．
关于本书
本书可以
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
