数学与泛型编程:高效编程的奥秘.html.pdf
《数学与泛型编程:高效编程的奥秘.html.pdf》由会员分享,可在线阅读,更多相关《数学与泛型编程:高效编程的奥秘.html.pdf(289页珍藏版)》请在三一文库上搜索。
1、译者序 本书是从数学到泛型编程的一次精彩之旅。 书中讲解了与乘法、素数及最大公约数有关的古老算法,并展示了历代数学家对这些算法所做的探索。他们既想对求解的方 法做推广,以扩大其适用范围,又想对计算的步骤做简化,以提升其运算效率。 就前一方面来看,近代数学的发展(尤其是数论与抽象代数这两个分支)为算法的推广提供了很大的帮助。数论令人更加深 刻地了解到数字中的奥妙,并给高速计算提供了灵感,而抽象代数则使得那些本来只能处理整数的算法,逐渐变得可以处理分 数、实数、复数,乃至多项式。这种泛化还发生在数据之间的运算上面,比方说,通过连加可以实现求积,然而如果把其中的运 算由加法换为乘法,那么效果就会从求
2、积变成求幂。 就后一方面来看,计算机的出现使得算法的效率有了很大的提升空间。我们可以根据运算步骤及数据所具备的特征来发挥电 脑硬件与软件所拥有的特性。 作为全书主题的泛型编程体现了上述两个方面的融合。它既借鉴了数学中的抽象思维及知识整理办法,又利用了计算机编程 语言所提供的泛型与优化机制。这使得某些因实际问题而起的原始算法,在经过千百年的深化和抽象之后,终于可以变得更加普 适、更加高效。 作者把这些对泛型编程有益的思维与技术提炼成许多条原则,并通过严谨的数学证明来培养读者的逻辑推理能力。此外,书 中还有几篇简明的学者传记,使大家能够了解数学史及计算机技术的发展脉络。将这些内容与公钥加密系统等有
3、趣的实例结合起 来,可以指导我们把数学知识更好地转化为泛型编程的成果。 在翻译过程中,我得到了机械工业出版社华章公司诸位工作人员的帮助,在此深表谢意。 由于译者水平有限,书中难免出现错误与疏漏之处,请大家发邮件至,或访 问 爱飞翔 2017年4月 致谢 笔者要感谢令本书得以面世的每一个人。我们在A的管理团队从一开始就积极协助这个项目。Bill Stasior曾提议设立 一门课程,并从我们所给出的选项中挑出了一些话题,本书正是以该课程为基础而撰写的。Brian Pinkerton不仅出席了该课 程,而且还强烈鼓励我们把课程素材写成一本书。感谢Mat Marcus,他于20042005年同Alex
4、合作,在Adobe开设了类似的 课程。 Fundamental Data Structures and Algorithms for Search团队的其他成员在成书过程中扮演了重要的角色。Anil Gangolli帮我们确定了课程的内容,Ryan Ernst对基础编程环境的搭建工作出力很多,Paramjit Oberoi在我们写书时给出了宝 贵的建议。笔者喜欢与他们一起工作,并感谢他们所提出的意见。 感谢我们的编辑Peter Gordon及Greg Doench,也感谢Addison-Wesley所召集的专家团队,其中包括经理编辑John Fuller、制作编辑Mary Kesel Wils
5、on、文稿编辑Jill Hobbs以及排版员/LaTeX专家Lori Hughes,他们通过努力的工作把笔者的 草稿制作成了精美的书籍。 还要感谢朋友及家人,同时感谢阅读本书初稿或给我们提供评论、修正、建议、意见或其他帮助的同事:Gaper Aman、 John Banning、Cynthia Dwork、Hernan Epelman、Ryan Ernst、Anil Gangolli、Susan Gruber、Jon Kalb、Robert Lehr、Dmitry Leshchiner、Tom London、Mark Manasse、Paul McJones、Nicolas Nicolov、G
6、or Nishanov、Paramjit Oberoi、Sean Parent、Fernando Pelliccioni、John Reiser、Robert Rose、Stefan Vargyas及Adam Young。他们的努 力,令本书的品质大有提升。 最后,感谢许多细心的读者报告了阅读本书时所发现的错误,他们是:Abutalib Aghayev、Vladimir Burenkov、Greg Ives、Nitin Kumar、John Lakos、Andy Lawman、Jeremy Murphy、Anil Pal、Miguel Pinkas、Daniel Roldn、 Alexande
7、r Slinkin、Saul Tamari和Boris Vassilev。如果你发现了错误可以发送邮件至。可以在以下网址 下载本书的勘误: 作者简介 亚历山大A.斯捷潘诺夫(Alexander A.Stepanov)于19671972年在莫斯科国立大学(Moscow State University)研习 数学。他从1972年开始编程,1977年移民美国之后,继续从事编程工作。他参与了操作系统、编程工具、编译器与程序库的开 发,其对编程基础的研究工作得到了通用电气(GE)、纽约理工大学(Polytechnic University)、贝尔实验室(Bell Labs)、 惠普(HP)、SGI及A
8、dobe的支持。2009年Amazon旗下的搜索技术公司A开始支持这项工作。由于对C+标准模板库 的设计有贡献,1995年他获得了Dr.Dobbs Journal的杰出编程奖。 丹尼尔E.罗斯(Daniel E.Rose)是一位研究科学家,在Apple、AltaVista、Xigo、Yahoo及A从事管理工作。他广泛 地研究搜索技术,关注针对索引压缩的底层算法,以及Web搜索中的人机交互等问题。Rose曾在Apple公司带领团队为苹果电 脑创建了桌面搜索机制。他拥有圣迭戈加利福尼亚大学(University of California,San Diego)的认知科学与计算机科学博士 学位,以及
9、哈佛大学(Harvard University)的学士学位。 作者附言 如果将计算机科学与数学分离,那么这两者的发展都会有很大困难。于是,我们就试图通过一些课程,把人类文明早期就有 的数学活动与现代才有的计算机活动结合起来。本书正是基于这样一种课程而编写的。 能够与友人Dan Rose合作,我深感荣幸。他的管理工作令我们团队能够把泛型编程的原则运用到搜索引擎的设计上来,而 且他愿意把我原来那些相当分散的课程内容集结成现在这样一本连贯的书籍。Dan和我都希望读者能够喜欢我们这次合作的成 果。 A.A.S. 大家将要阅读的这本书是根据“Algorithmic Journeys”课程的笔记而撰写的,
10、该课程于2012年由Alex Stepanov在 A讲授。当Alex与我合作把课程材料改编为书籍时,我们发现:其实可以将这些材料整理得更为集中一些,使其聚焦于泛 型编程及其数学基础。这个想法促使我们对本书要讲解的话题进行了大幅度的调整,删掉了与集合论及逻辑有关的大段文字,因 为那些内容似乎和本书要讲的内容无关。同时,我们还对一些细节有所增删,以便大家能够更加连贯地阅读本书,并使那些数学 知识较缺乏的读者也能够顺畅地理解书中的内容。 Alex是数学专业出身,但我不是。因此,我很努力地试着去读懂课程里的一些材料,并根据自身体会来确定那些需要加以解 说的难点。如果你发现本书所用的一些描述方式及术语和
11、专业数学家稍有不同,或是本书在解释某个问题时多写了几个简单的步 骤,那么这应该归咎于我才对。 D.E.R. 第1章 内容提要 不懂数学,就无法了解世界。 罗吉尔培根(Roger Bacon),大著作(Opus Majus) 这是一本谈编程的书,但是它与大多数的编程书都不太一样,因为除了算法和代码之外,本书还会给出数学证明和一些讲述 从古代到20世纪各种数学发现的历史材料。 另一个更为具体的特色在于:这是一本谈论泛型编程(generic programming)的书。泛型编程是出现于20世纪80年代的 编程方法,在20世纪90年代随着C+标准模板库(Standard Template Libra
12、ry,STL)而变得流行起来。我们可以这样定义 它: 定义1.1 泛型编程是一种专注于对算法及数据结构进行设计的编程方式,它使得这些算法及数据结构能够在不损失效率的 前提下,运用到最为通用的环境中。 用过STL的读者可能在想:“不对吧?泛型编程的概念只用这么简单的一句话就能定义出来?模板和迭代器(iterator)等 特性怎么没有提到呢?”其实那些特性应该说是工具,它们使得编程语言能够支持泛型编程。程序员固然应该学会高效地使用那 些工具,然而泛型编程主要谈的是编程态度(attitude),而不是某一套工具。 笔者认为,所有的程序员都应该抱持这种编程态度,也就是说,都应该试着以这种通用的方式来编
13、写代码。如果能够写出高 品质的泛型程序,那么很容易就能使用并修改其中的各个组件。这要比那种采用硬代码来编写的程序好很多,因为后者会针对具 体的应用程序来给数据结构、算法以及接口施加一些毫无必要的限制。把程序写得通用一些可以令它变得更为简洁,也更为强 大。 1.1 编程与数学 那么,这种泛型编程的想法是从哪里来的?我们又应该怎样来学习它呢?这种想法是从数学中衍生出来的,尤其与抽象代数 (abstract algebra)这个数学分支有关。为了使大家能够理解这种编程方式,本书会对抽象代数做一些介绍,并着重讲解怎样 从抽象的运算属性来认识对象。这个话题一般是数学专业的大学生才去研究的,然而笔者认为,
14、它对于我们理解泛型编程会起到 关键的作用。 实际上,还有很多基本的编程概念也同样来自数学。对这些概念的产生及变化过程加以学习,能够促使我们更好地思考软件 的设计问题。比方说,欧几里得(Euclid)的几何原本(Elements)虽然是两千多年前写成的书,但是其中的范例仍然具 有很高的参考价值,它可以告诉我们,怎样用一些较小且较易理解的组件来构建一套复杂的系统。 尽管抽象是泛型编程的要义,但这个抽象却并不是本来就有的。我们必须从具体的事物入手,才能够获得更为抽象的认识, 要想对某个领域进行正确的抽象,就必须理解该领域的细节。 抽象代数里面的抽象很大程度上是从另外一个数学分支的具体成果中得出的,那
15、个分支比抽象代数更为古老,它叫做数论 (number theory)。为此,我们还需要介绍数论中的某些关键概念,这些概念与整数的属性有关,其中尤其值得注意的是可 除性(divisibility)。 我们在学习这些数学知识时所使用的思路可以对编程技巧起到提升作用,此外我们还会看到,对于当前某些软件来说,有一 些数学成果本身就具有极其重要的意义,这尤其体现在给网络隐私与电子商务软件提供支持的加密协议上。本书最后会举例来说 明某些数学知识在此类协议中的运用情况。 笔者会在数学和编程之间来回游走。当我们讲解某些重要的数学概念时,笔者会穿插一些对具体算法和通用编程技巧的讨 论。笔者对其中某些算法只会给出
16、简要的描述,而对另外一些算法则会在整本书里进行详细的讲解,并将其泛化。除了个别章节 只谈数学或只谈编程之外,大部分章节都会同时涉及数学和编程这两个方面。 1.2 从历史的角度来讲解 如果能把某个话题融入故事中,那么我们学起来就会更容易一些,而且也会觉得更为有趣。我们想要知道:在某个时间发生 了什么事件?都有谁与该事件相关?这些人是怎样产生某种想法的?他们是要在别人的基础之上进行研究,还是要驳斥别人的结 论?为此,本书在介绍数学概念时,还会讲一些与此有关的故事,并谈一下提出这些概念的人。笔者通常用一份简要的传记来描 述身为故事主角的数学家,这些小传不会像百科全书里面写得那样详尽,它只是想令你对这
17、位数学家的情况有所了解而已。 尽管我们会从历史的角度来谈论某些概念,但这并不是一本讲数学史的书,而且也不会按照这些概念问世的先后顺序来进行 讲解。我们可能会在空间和时间顺序上有所跳跃,因为笔者主要是想令大家了解每一个数学概念的历史背景。 1.3 阅读准备 由于书中的很多内容都和数学有关,因此你可能担心自己必须先具备丰富的数学知识,然后才能看懂这本书。其实你只要有 逻辑思考能力就行(程序员应该很擅长逻辑思考),笔者并不会要求大家具备中学代数与中学几何之外的其他数学知识。某些章 节可能会运用向量(vector)与矩阵(matrix)等线性代数(linear algebra)方面的概念,如果从前没有
18、看过这方面的资料, 那么把这些内容跳过去就可以了。若是对本书所用的记法不够熟悉,则请参考附录A。 数学中有一个很重要的部分就是对命题给出形式化证明。本书就包含了许多这样的证明过程。如果你在中学的几何课、计算 机科学专业的自动机理论(automata theory)课以及逻辑课中做过一些证明,那么应该很容易就能理解本书所给出的证明。附 录B描述了某些常用的证明技巧,并给出了范例。 笔者假设你已经是一名程序员了,而且对C、C+或Java等典型的命令式(imperative)编程语言相当熟悉。尽管书中的范 例是用C+写的,但即便你原来没有用C+写过程序,也依然应该看得懂才对。附录C解释了一些C+特有
19、的机制。虽说我们 用的是C+语言,但笔者相信,书中所讲的原则能够适用于其他各种语言。 本书所谈的很多编程话题也同时出现在Stepanov与McJones所写的编程原本(Elements of Programming)一书 中,而后者是从另外一种更加正式的角度来讲解这些话题的。想要深入研究这些话题的读者可以参考那本书,并将其与本书结合 起来阅读。在本书里,我们偶尔也会提到编程原本中的相关章节。 1.4 各章概述 在详细讲解本书内容之前,我们先来简要叙述一下各章的概况: 第2章介绍一种古老的乘法算法,以及该算法的改进方式。 第3章初步讲解数字的某些性质,并给出一种寻找素数的高效算法。 第4章介绍一
20、种寻找最大公约数(Greatest Common Divisor,GCD)的算法,后续的章节会以该算法为基础来讲述某些抽象 思维及其运用方式。 第5章关注数学结论,我们会介绍几个重要的定理,这些定理在后续的章节中发挥着重要的作用。 第6章介绍数学中的抽象代数这一领域,泛型编程的核心思想正源自该领域。 第7章运用这些数学思想对乘法算法进行泛化,使它不仅能够执行简单的算数运算,而且还可以用来解决各种实际的编程 问题。 第8章介绍一些新的抽象数学结构,并讲解怎样运用这些结构来解决一些新的问题。 第9章讲解公理系统、定理以及模型,这些都是泛型编程的基础组成部分。 第10章介绍泛型编程中的概念,并展示一
21、些看似简单的编程任务中所蕴含着的微妙问题。 第11章继续研究某些基本的编程任务,并介绍怎样运用与该问题有关的理论知识,来实现各种实用的算法。 第12章讲解硬件方面的限制是怎样促使旧算法演化出新版本的,并针对GCD来展示一些新的运用方式。 第13章把数学结论与算法成果结合起来,以便在密码学上做一次重要的运用。 第14章总结本书所提到的某些基本观念。 编程与数学是两条贯穿于全书的线索,只不过在某些章里面,其中一条线索可能要比另一条更加明显。书中的每一章都体现 了一段思路,这些思路合起来构成了全书的主旨,那就是: 要想成为优秀的程序员,就必须理解泛型编程的原则;要想理解泛型编程的原则,就必须学会抽象
22、;要想学会抽象,就必须 知道它所依据的数学基础。 以上就是笔者想要在本书中讲述的内容。 第2章 算法初谈 摩西很快就学会了算术与几何。 这些知识是他从埃及人那里学来的, 埃及人最重视的研究科目是数学。 亚历山大的斐洛(Philo of Alexandria),摩西生平(Life of Moses) 算法(algorithm)是用来完成计算任务的一系列有限步骤。由于算法与计算机编程的关系特别密切,因此很多人或许认 为,算法是一个来自计算机科学专业的概念。其实算法这个词已经有几千年历史了。数学中充满了各种各样的算法,有些算法我 们天天在用,就连小学生计算加法时所用的竖式(long addition
23、)都可以说是一种算法。 尽管算法的历史很悠久,但它并不是天生就有的,而是由人发明出来的。虽然我们并不清楚第一个发明算法的人是谁,但我 们知道,早在四千多年前埃及就已经有了某些算法。 * 古埃及文明以尼罗河为中心,尼罗河发洪水之后,土壤就变得肥沃起来,从而促进了古埃及的农业发展。可是问题在于,每 次洪水过后,用来划分财产边界的那些标志也随之消失了。于是,埃及人就用绳子丈量距离,并拟定一套流程,使自己能够根据 早前的书面记录来恢复当时的边界划分情况。有一批专职的祭司负责研究与此有关的数学技巧,这些人叫做“rope- stretcher”(拉绳者),希腊人后来把他们称为geometer,也就是“Ea
24、rth-measurer”(地形测量者)的意思。 我们很少发现与古埃及人的数学知识有关的文字记录。对于那个时期,目前只发现了两份数学文献,其中一份就是此处要提 到的莱因德数学纸草书(Rhind Mathematical Papyru),它以苏格兰收藏家莱因德得名。莱因德在埃及所买的这份纸草书是 公元前1650年左右由一位名叫阿姆士(Ahmes)的抄写员所写的。其中含有一系列算术与几何问题,而且还列有一些计算用的 表格。这份卷轴里面所写的第一个算法是一种能够迅速计算乘法的技巧,此外还有第二个算法,用来迅速地计算除法。我们首先 来讲这个快速乘法算法,在本书后面的章节中大家会发现,该算法当今依然是一
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 编程 高效 奥秘 html
链接地址:https://www.31doc.com/p-5518844.html