编辑推荐
随机化和概率技术在现代计算机科学中发挥着重要作用, 其应用范围从组合优化与机器学习到通信网络与安全协议。
本书是概率论与计算机科学相结合的完美教材，系统地介绍概率论、随机过程及样本复杂度、VC维度和拉德马赫复杂度等理论知识，以及一些解决实际问题的算法设计技巧，旨在帮助你学会如何利用概率理论及计算机求解实际问题。你仅需有离散数学的基础知识就能阅读本书, 书中包含大量的实例和应用，其内容严谨，并有较好的可读性。
内容简介
《概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）》详细地介绍了概率技术以及在概率算法与分析发展中使用过的范例。
《概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）》分两部分，第一部分介绍了随机抽样、期望、马尔可夫不等式、切比雪夫不等式、切尔诺夫界、球和箱子模型、概率技术和马尔可夫链等核心内容.第二部分主要研究连续概率、有限独立性的应用、熵、马尔可夫链、蒙特卡罗方法、耦合、鞅和平衡配置等比较高深的课题。
《概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）》适合作为高等院校计算机科学和应用数学专业高年级本科生与低年级研究生的教材，也适合作为数学工作者和科技人员的参考书。
作者简介
迈克尔·米森马彻（Michael Mitzenmacher），哈佛大学的计算机科学教授，他于1996年在加州大学伯克利分校获得博士学位。在1999年进入哈佛大学之前，他是PaIoAlto数字系统研究实验室的研究员。他获得了NSF职业奖和艾尔弗雷德-P.斯隆研究奖学金。2002年，他因在纠错码方面的工作而获得IEEE信息理论学会“论文”奖。
伊莱·阿法尔（Eli Upfal），布朗大学计算机科学系的教授、系主任。他在以色列耶路撒冷的希伯来大学获得了博士学位，在1997年进入布朗大学之前，他是IBM研究部的研究员、以色列魏兹曼科学研究所的教授。他的主要研究兴趣是随机计算与算法的概率分析及其在优化算法中的应用、通信网络、并行和分布式计算，以及计算生物学等。
章节目录
译者序
第2版前言
第1版前言
第1章 事件与概率
1．1 应用：验证多项式恒等式
1．2 概率论公理
1．3 应用：验证矩阵乘法
1．4 应用：朴素贝叶斯分类器
1．5 应用：最小割随机化算法
1．6 练习
第2章 离散型随机变量与期望
2．1 随机变量与期望
2．1．1 期望的线性性
2．1．2 詹森不等式
2．2 伯努利随机变量和二项随机变量
2．3 条件期望
2．4 几何分布
2．5 应用：快速排序的期望运行时间
2．6 练习
第3章 矩与离差
3．1 马尔可夫不等式
3．2 随机变量的方差和矩
3．3 切比雪夫不等式
3．4 中位数和平均值
3．5 应用：计算中位数的随机化算法
3．5．1 算法
3．5．2 算法分析
3．6 练习
第4章 切尔诺夫界与霍夫丁界
4．1 矩母函数
4．2 切尔诺夫界的导出和应用
4．2．1 泊松试验和的切尔诺夫界
4．2．2 例：投掷硬币
4．2．3 应用：估计参数
4．3 某些特殊情况下更好的界
4．4 应用：集合的均衡
4．5 霍夫丁界
4．6 应用：稀疏网络中的数据包路由选择
4．6．1 超立方体网络上排列的路由选择
4．6．2 蝶形网络上排列的路由选择
4．7 练习
第5章 球、箱子和随机图
5．1 例：生日悖论
5．2 球放进箱子
5．2．1 球和箱子模型
5．2．2 应用：桶排序
5．3 泊松分布
5．4 泊松近似
5．5 应用：散列法
5．5．1 链散列
5．5．2 散列：二进制数字串
5．5．3 Bloom过滤器
5．5．4 放弃对称性
5．6 随机图
5．6．1 随机图模型
5．6．2 应用：随机图中的哈密顿圈
5．7 练习
5．8 探索性作业
第6章 概率方法
6．1 基本计数论证
6．2 期望论证
6．2．1 应用：求最大割
6．2．2 应用：最大可满足性
6．3 利用条件期望消除随机化
6．4 抽样和修改
6．4．1 应用：独立集合
6．4．2 应用：有较大围长的图
6．5 二阶矩方法
6．6 条件期望不等式
6．7 洛瓦兹局部引理
6．7．1 应用：边不相交的路径
6．7．2 应用：可满足性
6．8 利用洛瓦兹局部引理的显式构造
6．9 洛瓦兹局部引理：一般情况
6．10 洛瓦兹算法局部引理
6．11 练习
……
第7章 马尔可夫链及随机游动
第8章 连续分布与泊松过程
第9章 正态分布
第10章 熵、随机性和信息
第11章 蒙特卡罗方法
第12章 马尔可夫链的耦合
第13章 鞅
第14章 样本复杂度、VC维度以及拉德马赫复杂度
第15章 两两独立及通用散列函数
第16章 幂律及相关的分布
第17章 平衡分配和布谷鸟散列
延伸阅读
概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）是2020年由机械工业出版社出版,作者迈克尔·米森马彻。
得书感谢您对《概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）》关注和支持，如本书内容有不良信息或侵权等情形的，请联系本网站。
