---------------------------概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）---------------------------
第2版前言
本书的初版已经过了10年，随着大数据分析、机器学习和数据挖掘的重要性越来越突出，概率方法对于计算机科学来说也变得越来越核心．许多相关领域的应用成果，其算法和思路都是建立在对概率与统计的成熟理解基础之上的，要想正确地使用这些工具，对于这些数学概念的透彻理解是必不可少的．而第2版新增的主要内容就是着重于这些概念的介绍．
近年来，诸如万维网、社交网络、基因数据等使得我们能够产生、收集和存储大量的样本数据集，这对我们建立模型和分析这些数据的结构提出了新的挑战．熟练掌握一些标准的分布可以给建立和分析模型打下一个好的基础，新增的第9章包含了绝大多数常见的统计分布，同时也像之前一样，会强调这些分布在计算机科学中如何应用，比如确定分布的尾界等．然而，诸如万维网和社交网络等现代数据集有着一个奇妙的现象，在其中我们往往见不到正态分布，取而代之的是一种有着非常不同性质的、很少见的、特征明显的重尾分布．例如，在万维网中，一些页面经常会有大量的网页链接它们，其被链接的数量要高过平均水平一个数量级．第2版新增的第16章将包含对于建模和理解这种现代数据集来说非常重要的那些特殊分布．
机器学习是近年来计算机科学领域的重大成果之一，它提供了许多高效的工具来建模、理解和预测大数据．但是预测的准确性，特别是准确性和样本容量的关系这一点却常常被人忽略．第2版中新增的第14章将会对这些重要的内容进行详细的介绍．
在新版中，我们也对之前的部分内容进行了充实和更新．例如，我们介绍了重要的洛瓦兹局部引理的算法变化的一些新进展，也新增了一小节用来介绍布谷鸟散列这种享誉盛名且越来越实用的散列法．最后，除了这些新增内容，新版也包括了修正、勘误和许多新习题．
我们对几年来向我们发送了诸多勘误的读者表示由衷的感谢，可惜人数过于众多，我们在此不一一列出了，还望海涵．
第1版前言
为什么要研究随机性
计算机科学家为什么要研究和使用随机性呢?这是因为计算机出现了太多不可预见的状况!加入随机性似乎是一个缺点,它使得有效地使用计算机这种已经具有挑战性的工作变得更加复杂．
从20世纪开始,科学研究已经将随机性视为建模和分析中的基本组成部分．例如,在物理学上,牛顿定律使人们相信宇宙的位置是确定的:如果有一个足够大的计算工具和合适的初始条件,人们可以确定若干年后行星的位置．然而量子理论的发展却提出了不同的观点:宇宙仍旧按照自然法则运转,但是这些自然法则的核心是随机性的．“上帝不会同宇宙玩骰子”，这是爱因斯坦用来反驳现代量子力学的一句名言．然而,当代亚微粒子物理学的主要理论仍然是建立在随机现象和统计规律基础之上的,并且在从生物学的遗传与进化到自由市场经济的价格波动模型等几乎所有其他科学领域中,随机性都起着非常重要的作用．
计算机科学也不例外，从一些概率定理证明的高深理论到个人计算机以太网卡的实用性设计,随机性和概率方法在现代计算机科学中都扮演了关键角色．过去20年以来,概率论在计算中的应用得到了巨大的发展,越来越高级、越来越复杂的概率技术已经被应用于更加广泛和更富挑战性的计算机科学应用中．在本书中,我们主要研究随机性应用于计算机科学的基本方法:随机化算法和算法的概率分析．
随机化算法:随机化算法是执行过程中要求作随机选择的算法．实际上,随机化程序会使用由随机数发生器产生的数值,从若干执行分支中决定下一步执行哪个分支．例如,以太网卡协议用随机数决定何时试图访问共享的以太网通信介质．随机性在打破对称性、防止不同的以太网卡同时重复访问介质方面是非常有用的．随机化算法的其他常见应用还包括蒙特卡罗模拟和密码学中的初始检验．在这些以及其他重要应用中,随机化算法比最有名的确定性方法更有效,并且在大多数情况下更简单,更容易编写程序．
当然，这些优点也是需要付出一定代价的,问题的答案在一定的概率下是不正确的,或者只以某个概率保证有效．虽然设计一个有可能错误的算法似乎有点奇怪,但是如果错误发生的概率很小,那么提高运行速度和减少占用的内存是有价值的．
算法的概率分析:复杂性理论根据计算的复杂性对问题进行分类,尤其是区分简单问题和有难度的问题．例如,复杂性理论认为流动推销员问题是一个NP难题．如果城市数量以次指数增长,那么不可能存在可以解决流动推销员问题的任何一个实用的算法．对于经典的最坏情况复杂性理论,一个令人困惑的现象是,在分类上属于有难度的计算问题,实际上却很容易解决，概率分析对这种现象给出了理论上的解释．虽然对某些不合理的输入数据,问题难以解决,但对大多数输入(尤其是在日常的应用中),这些问题实际上却容易解决．更确切地说,如果我们认为输入是随机选择的结果,而随机选择是根据所有可能输入数据集上的某个概率分布作出的,就很有可能得到一个易于解答的问题实例,而这些实例不能求解的概率是相对较小的．算法的概率分析是研究当输入来自某一适当定义的概率空间时算法如何运行的一种方法．书中我们将会看到,即使是NP难题,也会有对于几乎所有输入都极其有效的算法．
. 关于本书
本书可以作为计算机科学和应用数学专业高年级本科生或低年级研究生一至两个学期的课程教材．在众多较好的大学中,随机化和概率技术已经从高年级研究生讨论班的主题变为高年级本科生和低年级研究生的正式课程．在这方面有大量相当高深的、研究性的著作,但仍然需要一本介绍性的教科书,我们希望本书能起到这方面的作用．
本书的内容是从近几年在布朗大学(CS 155)和哈佛大学(CS 223)讲授计算机科学中的概率方法这类课程发展而来的．这些课程和本书强调的是概率技术以及具体的范例,而非特定的应用领域．每章介绍一种方法或者技术,通过一些随机化算法分析或基于随机输入算法的概率分析例子来阐述．其中许多例子来自网络中的问题,反映了网络领域的主要趋势(和作者的兴趣)．
本书第1版共有14章,可分成两部分,第一部分(第1～7章)是核心内容．本书只要求读者具备基本的概率论知识,相当于计算机科学专业的离散数学课程包含的内容．第1～3章复习初等概率论,并介绍一些有意义的应用,内容包括随机抽样、期望、马尔可夫不等式、方差和切比雪夫不等式．如果教学班有充分的概率论背景,那么这几章可以很快地讲过去,但是建议读者不要跳过这些章节,因为这里介绍了随机化算法和算法的概率分析概念,并且还有一些贯穿全书的例子．
第4～7章介绍高级课题,包括切尔诺夫界、球和箱子模型、概率方法和马尔可夫链．同前面几章相比,这几章介绍的内容更具有挑战性．难度特别大的章节书中标有星号(教师可以根据需要考虑是否跳过这部分内容)．根据教学进度,前7章介绍的核心内容可以作为四分之一学年或半学年的课程．
本书第二部分(第8章、第10～13章、第15章、第17章)介绍另外一些高级内容,这些内容既可以作为基本课程的必要补充,也可以作为另一门更高级的课程．这些章节是各自独立的,教师可以选择最适合学生的内容来讲授．将连续概率和熵这两章纳入基本课程中可能是比较好的选择．对连续概率(第8章)的介绍主要集中在均匀分布和指数分布,其中还包括一些排队论的例子,对熵(第10章)的介绍包括如何度量随机性,以及在随机提取、压缩和编码中，熵是如何自然地产生的．
第11章和第12章分别介绍了蒙特卡罗方法和耦合,这两章是密切相关的,最好放在一起学习；第13章是关于鞅的知识,包含了如何处理相关随机变量的各种重要问题；而第15章则从不同的思路继续研究两两独立和消去随机性的进展；最后一章(第17章)讨论了均衡配置问题,介绍了作者的一些想法,该章与第5章的球和箱子问题密切相关．
本书各个章节的顺序,尤其是第一部分的顺序,是根据它们在算法中的相对重要性安排的,例如,我们先介绍切尔诺夫界,而其他一些基本的概率知识(如马尔可夫链)则放在后面,但是,教师在讲授时可以按照不同顺序进行．在更强调一般随机过程的课程中,可以在第1～3章后直接讲授马尔可夫链(第7章),随后讲授球、箱子和随机图(第5章,略去哈密顿圈的例子），接下来可以跳过第6章关于概率方法的内容,而讲授连续概率和泊松过程(第8章)．本书其余大部分内容都会用到第4章中关于切尔诺夫界的知识．
书中的大部分练习都是理论性的,但我们也选取了一些编程练习——包括两个需要编程的探索性作业．我们发现偶尔的编程练习,对于加强本书的思想和增添课程的多样性很有帮助．
我们将本书的内容严格限制在数学分析的方法和技术之内,除去一些特殊情况,本书的所有定理都给出了完整的证明．显然,许多相当有用的概率方法并不在这种严格的限制之内．例如,在蒙特卡罗方法的重要领域中,大多数实际解具有启发性,从而证实了试验估计比严格数学分析更有效．我们认为,为了很好地应用和理解启发性方法的优缺点,扎实地掌握基础概率理论和本书给出的严格技术是十分必要的,我们希望读者在学完本书之后能够喜欢这种处理方式．
致谢
首先我们要感谢许多曾经研究本书选取的极好题材的概率论专家和计算机科学家．我们没有把大量原始论文作为参考文献放入书中,只是提供一些优秀的参考书目作为本书各章的背景材料和更进一步的讨论依据．
书中许多内容来自布朗大学CS 155课程和哈佛大学CS 223课程的学生和老师的建议和反馈,我们特别要感谢Aris Anagnostopoulos、Eden Hochbaum、Rob Hunter和Adam Kirsch,他们阅读了本书的初稿,并提出了修改意见．
我们尤其要感谢Dick Karp,2003年秋季,他在伯克利大学授课(CS 174)期间,使用了本教材的初稿,他的早期建议和修改意见对改进教材是非常有价值的．Peter Bartlett在2004年春季于伯克利大学授课(CS 174)期间,也提出了很多有用的建议和修改意见．
感谢在本书编写过程中认真读过部分初稿的同事,他们在内容及表达方面指出许多错误,提出重要的改进意见．他们是:Artur Czumaj、Alan Frieze、Claire Kenyon、Joe Marks、Salil Vadhan、Eric Vigoda．另外,感谢为出版社审稿的一些不知道姓名的评审者．
感谢Rajeev Motwani和Prabhakar Raghavan同意我们引用他们优秀的著作《Randomized Algorithms》中的某些练习．
最后感谢剑桥大学出版社的Lauren Cowles,她在本书的准备和组织过程中提供了很多编辑方面的帮助和意见．
本书的写作得到了美国国家科学基金会信息技术研究基金(授权号CCR-0121154)的部分资助．
---------------------------初等数论及其应用（原书第6版）---------------------------
我编著本书的目的是想写一本关于数论的入门级读物.起初我的想法是制作一个教学上的有效工具，希望能展示数论这一数学分支中丰富的题材以及出乎意料的实用性.数论既是经典的又是现代的，同时它既是理论化的又是实用化的.在本书中，我力求抓住这一对立面，并最大限度地将它们糅合在一起.
本书是本科阶段理想的数论教材. 除了一些必要的数学素养和大学代数知识外不需要别的预备知识.本书也可以作为初等数论的资料读物，既可作为计算机科学类课程的有益补充，也可作为有兴趣学习数论和密码学进展的读者的初级读物.由于它的广泛性，它既可作为教科书，也可作为初等数论及其广泛应用的长期参考书.
本版的发行正好是庆祝该书的银质纪年. 在过去的25年里，前面的版本大约被十万名学生学习过. 本书每个成功的版本都得益于许多师生及审稿者的反馈与建议.本次新版延续了前面版本的基本框架，但有许多补充与改进.希望对本书不熟悉的教师或没有读过前面几版的读者仔细通读这一新的第6版，相信你们会喜欢本书中丰富的习题、有趣的人物传记和历史注记、最新进展的跟踪、缜密的证明、有用的例子、丰富的应用、对数学计算软件（例如Maple和Mathematica）的支持以及网络上的大量资源.
第6版的变化第6版的改动是为了使本书更易于教学和更有趣味性，以及尽可能及时更新诸多进展.许多改动是应第5版的读者和审阅者的要求而进行的.下面列出了本版的一些改动之处.
·新的发现本版追踪了数值计算和理论证明这两方面的最新发现. 这其中包括四个新的梅森素数的发现以及许多未解决猜想的新证据，还有证明了任意长度的素数级数存在性的 Tao-Green定理，这是本版收集的最新的理论证明方面的成果之一.
·人物传记和历史注记
我们在原来的丰富的人物传记基础上新添加了Terence Tao（陶哲轩）、Etienne Bezout、Norman MacLeod Ferrers、Clifford Cocks和Waclaw Sierpiński等人的小传，也增添了在Rivest、Shamir、Adleman等人的工作之前英国密码学上令人惊讶的秘密发现.
·猜想
新增了不少初等数论当中的猜想，特别是关于素数和丢番图方程的问题，这些问题中有的已经解决，而有的仍然悬而未决.
·组合数论新增了一节关于拆分的介绍性内容，这是组合数论中很有意思的分支. 这一节中介绍了比较重要的概念，例如费勒斯图、 拆分恒等式、拉马努扬在同余上的工作等. 在该节中，对于一些拆分恒等式，包括欧拉的重要工作，我们分别使用了母函数和建立双射对应来给出证明.
·同余数与椭圆曲线
新增了一节讲述鼎鼎有名的同余数问题，同余数问题是指判断哪些正整数是边长为有理数的三角形的面积.该节有椭圆曲线的简单介绍以及如何将同余数问题和特定的椭圆曲线上的有理点联系起来的内容，同时也有将同余数问题与三平方算术级数联系在一起的内容.
·几何推导
本版介绍了利用几何推导来研究丢番图问题的方法. 特别地，新增内容表明了找出单位圆周上的有理点对应于找出毕达哥拉斯三元组，找出以指定整数为面积的有理三角形等价于找出相应的椭圆曲线上的有理点.
·密码学
本版删去了RSA密码系统中待加密明文需与密钥中模互素这一不必要的限制.
·最大公因子
最大公因子和两整数互素都在第1章中引入. 本书也引入了Bezout 系数这一概念.
·雅可比符号
给出雅可比符号实用性的动机,特别是给出了利用雅可比符号来计算勒让德符号的讨论.
·改进的习题
对习题的改进我们做了大量的工作，添加了从一般性的到有挑战性的数百道新习题， 而且在计算和研究部分也有新习题.
·准确性
为本书的准确性我们付出了不少努力. 两个独立的审阅者分别检查了全部正文以及习题答案.
·网站www.pearsonhighered.com/rosen
本版的网站也进行了大幅扩充， 师生们可以在此找到许多与本书关联的资料. 新内容包括扩充的小应用程序列表、使用数学软件研究数论的手册以及一个专门刊发数论新闻的网页.
习题部分
鉴于习题的重要性，我在修改习题上花费了大量的时间. 学生应该记住学习数学的最好方法就是尽可能地多做习题.下面我将简短地介绍本书中习题的类型以及答案的出处.
·普通习题
一般性的习题按照适当的次序排序，着重于训练基本的技能，奇偶号习题都有这种类型的题目.大量中等难度的习题帮助学生将诸多概念融合在一起得出新的结果，也有很多习题是为了发展一些新的概念.
·有难度的习题
本书中有不少具有挑战性的习题，用“*”标记的是较难的习题，用“**”标记的是很难的习题.有些习题的结论在后面章节中会被用到，这些习题用手形“”标记，这部分习题应该在教师的指定下去尝试.
·习题答案
本书的后面提供了所有奇数号习题的答案限于篇幅，习题答案未出现在中文版中，有需要者可从华章网站（www.hzbook.com）下载.——编辑注.更完整的习题答案可在英文书网站上的“Student’s Solutions Manual”部分找到.所有答案都被多次检查以保证准确性.
·计算类习题
每节后附有计算和研究题，需要用诸如Maple、 Mathematica、 PARI/GP或者Sage 之类的软件或学生自己编写的程序来完成.有些常规的习题可以让学生熟悉一些基本的命令(附录D中有关于Maple、Mathemaica的命令，PARI/GP和Sage的命令可在英文书网站上找到)，而更多开放性的习题是为实验和激发创造性而设计的.每节后还附有程序设计题，学生可以选用一种编程语言或一种程序来完成. 英文书网站上的“Student’s Manual to Computations and Explorations ”部分提供了答案或提示以帮助学生完成这些习题.
网站
学生和教师可以在www.pearsonhighered.com/rosen上找到各种类型的资源. 在www.pearsonhighered.com/irc上可以找到专门为教师提供的资源，这些资源的获取需要从Pearson那里获取密码.
·外部链接
该网站列有到许多与数论相关的网站的带说明的链接.这些网站与书中相关材料的讨论关系密切. 附录D中列出了与数论相关的最重要的一些网址.
·数论新闻
该网站有一个专门刊登最新数论发现的页面.
·学生解题手册
学生解题手册包含所有奇数号习题的答案以及试题样本.
·学生计算和研究题手册
该手册为计算和研究题提供帮助，对此类习题提供完全或部分答案，或者给出提示.该手册在不同程度上支持各种计算平台，包括Maple、Mathematica以及PARI/GP.
·应用小程序
该网站上有大量的应用小程序. 学生可以利用这些程序来进行数论上一般性的计算以及加深对概念的理解和研究未解决的猜想.除了数论中的计算性算法程序外，我们也提供了密码学上的应用小程序，包括解密、加密、密码分析以及密码协议，兼顾了经典密码和RSA密码系统.这些密码学上的应用小程序可被个人或组织使用，也可用于教学.
·建议性项目
该网站上有一批建议性项目，这些项目可用于学生或是学生小组的期末作业.
·教师手册
含有所有习题的答案，包括偶数号习题，也有大量不对学生开放的各种资源，包括课程表样本、课程范围的建议以及试题库等.
如何使用本书
本书可用作侧重点不同的各种级别的初等数论课程的教科书. 因此，教师用本书来安排课程有相当大的自由度. 对多数教师而言，第1章、2.1节、第3章、4.1～4.3节、第6章、7.1～7.3节、9.1～9.2节的主要内容是必需的.
教师可以用感兴趣的部分来充实自己的课程表. 一般而言，所有内容可粗略分为理论性和应用性两部分.理论性部分有莫比乌斯反演（7.4节）、整数的拆分（7.5节）、 原根（第9章）、连分数（第12章）、 丢番图方程（第13章）、 高斯整数（第14章）等.
有些教师也许想加入一些易于接受的应用，例如整除性检验、万年历、校验位（第5章）. 而想侧重计算机应用和密码学的教师可以加入第2章和第8章，也可继续加入9.3节、9.4节、第10章、11.5节等.
在选好想要讲授的章节后，教师可参考下图所示的各章间的依赖关系：
虽然第2章在不需要时可省略，但其中解释了描述算法复杂度的贯穿全书的大O符号. 除了定理12.4依赖于第9章的内容外，第12章只依赖于第1章.第13章中只有13.4节依赖于第12章. 若9.1节中有关原根的可选注释被略去，则可以不用学完第9章而学习第11章.14.3节应与13.3节一同被采用.
此外，教师可参阅网站上教师手册中侧重点不同的课程表.
致谢
感谢Pearson和Addison-Wesley的编辑 Bill Hoffman和Pearson数学分部的主任 Greg Tobin一如既往的热情支持， Bill Hoffman是我在Pearson合作最多的编辑. 特别感谢我的助理编辑Caroline Celano, 在她的协助下本版得以出版. 感谢本书幕后的整个编辑、生产、营销和媒体团队，他们是Pearson的Beth Houston(生产项目经理)、Maureen Raymond(插图编辑)、Carl Cottrell(媒体设计师)、Jeff Weidenaar(市场营销经理)、Kendra Bassi(营销助理)、Beth Paquin（设计师）以及Windfall Software 的Paul Anagnostopoulos（项目经理）、Jacqui Scarlott(排版)、Rick Camp(文字编辑和校对)、Laurel Muller(美工).再次感谢为本书前五版提供支持的所有人，包括以前Addison-Wesley 的许多编辑以及AT&T贝尔实验室的管理层(以及相关人员).
特别感谢Bart Goddard, 本书所有习题的答案均由他给出，同时他也审阅了本书.感谢Jean-Claude Evard 和Roger Lipsett一遍遍地检查了全部手稿，包括习题的答案.感谢David Wright对本书网站所做的贡献，包括关于PARI/GP的材料、数论和密码学上的应用小程序、计算和研究手册和建议的作业. 感谢Larry Washington和Keith Conrad 在同余数及椭圆曲线方面的建议.
审阅人
我从本书前几版读者的深思熟虑的评论和建议中受益匪浅，他们的许多想法已体现在这一版中.在此特别感谢为第6版提供帮助的审阅人：
Jennifer Beineke, 西部新英格兰学院
David Bradley, 缅因阿让诺大学
Flavia Colonna, 乔治梅森大学
Keith Conrad, 康涅狄格大学
Pavel Guerzhoy, 夏威夷大学
Paul E. Gunnells, 马萨诸塞大学阿默斯特分校
Charles Parry, 弗吉尼亚理工学院和州立大学
Holly Swisher, 俄勒冈州立大学
Lawrence Sze, 加州理工大学Pomona分校
在此也感谢前几版的大约50位审阅人,他们一直为改进本书提供着帮助. 最后，提前感谢以后给我发送建议和勘误的读者，相关内容可由math@pearson.com转发给我.
Kenneth H. Rosen
于新泽西州米德尔顿
![[套装书]概率与计算：算法与数据分析中的随机化和概率技术（原书第2版）+初等数论及其应用（原书第6版）（2册）](http://images.china-pub.com/ebook8065001-8070000/8067231/zcover.jpg)
