概率与计算(算法与数据分析中的随机化和概率技术原书第2版)/华章数学译丛

作者简介

迈克尔·米森马彻（Michael Mitzenmacher）是哈佛大学的计算机科学教授，他于1996年在加州大学伯克利分校获得博士学位。在1999年进入哈佛大学之前，他是PaloAlto数字系统研究实验室的研究员。他获得了NSF职业奖和艾尔弗雷德·P·斯隆研究奖学金。2002年，他因在纠错码方面的工作而获得IEEE信息理论学会“*佳论文”奖。 Eli Upfal是布朗大学计算机科学系的教授、系主任。他在以色列耶路撒冷的希伯来大学获得了博士学位，在1997年进入布朗大学之前，他是IBM研究部的研究员，以色列魏兹曼科学研究所的教授。 他的主要研究兴趣是随机计算与算法的概率分析及其在优化算法中的应用， 通信网络，并行和分布式计算，以及计算生物学等。

内容简介

本书是概率论与计算机科学相结合的完美教材。它系统地介绍了概率论、随机过程及样本复杂度、VC 维度和拉德马赫复杂度等理论知识，并介绍了使用本章理论去解决一些实际问题的算法设计技巧。 其目的在于帮助读者学会如何利用概率论理论及计算机求解实际问题。本书覆盖的知识面很广，全书共分为两部分，第壹部分介绍了随机抽样、期望、马尔可夫不等式、切比雪夫不等式、切尔诺夫界、球和箱子模型、概率技术和马尔可夫链等核心内容。第二部分主要研究连续概率、有限独立性的应用、熵、马尔可夫链蒙特卡罗方法、耦合、鞅及平衡配置等比较高深的内容。 本书可作为高年级本科生或低年级研究生的教材及教学参考书。 本书特色： ? 本书内容全面，结构严谨，几乎所有定理都给出了详细证明。 ?本书所选例题和现实中的问题紧密相关，且大部分案例都是目前相关学科（如计算机网络、图论、机器学习等）的热点问题。 ? 许多案例常常给出多种求解方案，并分析比较这些方案的时间效率和空间效率。 ? 本书的每一章都包含大量习题，且一些算法练习有可操作性的引导。