ACM前主席系统总结了计算的7类原理（计算，通信，协作，记忆，自动化，评估和设计），并称之为“伟大的计算原理”；旨在奠定一个基础也构建起一个框架，这个基础可帮助我们认识和组织计算思维的案例，并将它们进行分类；这个框架还可以帮助我们将计算思维运用到计算机科学以外的其他大多数学科领域，让非计算机专业的学生领会计算思维的核心思想──计算原理的相互影响以及问题有效解决的思维方式。

就在70年前，除了少数专家之外，没有人听说过计算机。现在，计算机、软件和网络无处不在。在地球上的任何地方，它们都以更快的发展速度给我们的生活带来了各种各样的好处。
在这么短的几十年中，我们学会了设计和建造如此规模的系统，这真是一件令人吃惊的事。如今，通过支持大规模合作，计算技术使得知识工作能够自动化，同时也在不断扩大生产力。第二次机器革命正扑面而来1。这是如何实现的？是什么样的伟大思想使这一切成为可能？
计算机给我们带来好处的同时也带来忧虑。计算机带来的自动化是否会使很多工人失业？计算机是否会成为终极监督工具而使我们失去隐私？计算机是否会发展出超越人类的智能？计算机能做的事情会有限制吗？
我们相信，理解计算的原理和法则可以帮助人们理解计算是如何完成如此之多的工作的，并消除他们的忧虑。为此我们写了这本书，书中介绍了关于计算的一些最重要的原理，并以任何对计算有一定了解的人都能理解的方式呈现。
计算机科学（computer science）不只是设计计算设备的工程领域，它是一门关于信息处理的科学。计算受科学原理和法则支配，这些原理和法则告诉我们计算机能做什么、不能做什么。信息的法则揭示了根据物理法则无法直接得出的新的可能性和限制。专家们赋予计算机许多计算科学（computing science）告诉我们不可能拥有的能力，同时，这些专家又低估了计算机真正的能力。
计算机科学与很多其他领域相互交叉。许多科学与工程领域都有计算（computational）分支，如计算物理、计算化学、生物信息学、数字化产品设计与制造、计算社交网络、计算心脏病学等2。各层次的教育者正努力在他们拥挤的课程表中加入计算相关的课程，以保证课程体系的先进性。但仍有很多中学由于缺少计算机科学方面的教师而不能开设计算机课程。在商业领域，诸如“大数据”“云计算”“网络安全”等热门词汇也散发出共同的信号，期望“计算原理”在数据管理、分布式计算、信息保护中发挥作用。
一直以来，人们把计算看作一个按照摩尔定律高速发展的技术领域3。而我们的观点有所不同，我们相信计算更应该被描述为一个科学领域，具有跨越所有计算技术以及人工或自然的信息处理的基本原理。我们需要一种新的方法来刻画计算。就像望远镜之于天文学、显微镜之于生物学，计算机是计算的工具，而非计算的研究对象。
本书的重要原理框架（great principles framework）就是这样一种新的方法。它将计算原理分为6个类别：通信、计算、协作、记忆（存储）、评估和设计。计算原理是指用来指导或约束我们如何操纵物质和能量来进行计算的声明。计算原理可以是：（1）重现，包括描述可重复的因果关系的定律、过程及方法；（2）行为准则。局部性原理（locality principle）就是重现的一个例子：每一个计算在一定的时间间隔内，其对数据的访问都聚集在一个小的子集里。行为准则的一个例子就是网络程序员将协议软件划分为多个层次。所有这些原理的目的，都是希望通过增进理解和降低复杂性从而得到良好的设计。
每种计算技术都利用了这些类别的原理。这个框架是广泛和全面的，覆盖了计算的每个部分，包括算法、系统和设计。
从事计算工作的人员形成了许多计算领域（computing domain）——实践社区，如人工智能、网络安全、云计算、大数据、图形学以及科学计算（computational science）等。这些领域都专注于推进领域向前发展并与其他社区互动，它们既从计算原理中获益，又受其约束。没有这些计算领域的原理框架是不完整的。
由于这6个类别过于庞大，我们决定将其所覆盖的范围分成11个更容易管理的模块，就像你在目录中看到的那样。关于这一点，我们将在第1章中详细说明。
从机器到通用的数字化
计算的机器是早期计算领域的关注中心（从20世纪40年代到20世纪60年代）。计算被看作机器执行复杂演算、解方程、破译密码、分析数据及管理业务流程的行为。那时的先驱们将计算机科学定义为研究以计算机为中心的各种现象。
然而，这些年来，这一定义变得越来越没有意义。20世纪80年代的科学计算运动认为，计算是除了传统的理论和实验之外的一种新的做科学研究的方法。他们使用“计算思维”（computational thinking）这个术语作为研究和问题求解的思维训练，而不是作为建造计算机的方法。十年之后，一些领域的科学家开始发现各自领域内的自然信息处理，其中包括生物学（DNA翻译）、物理学（量子信息4）、认知科学（脑力过程）、视觉（图像识别）和经济学（信息流）。计算的重点从机器转变到信息处理，包括人工信息和自然信息。
现在，随着几乎所有事物的数字化，计算进入了人们的日常生活，包括求解问题的新方法，艺术、音乐、电影的新形式，社交网络，云计算，电子商务，以及新的学习方法等。用计算作比喻成为日常语言中的必要组成部分，比如“我的软件有反应了”或“我的大脑崩溃了需要重启”这样的表达方式。
为了应对这些变化，各大学一直都在设计新的基于原理的方法来开展关于“计算”的教学。华盛顿大学是这方面的先驱之一，它开发了关于熟练掌握信息技术的一门课程和教材，目前已经在高中和大学中广泛使用，以帮助学生学习并应用基本计算原理5。教育考试基金会（Educational Testing Foundation）与美国国家自然科学基金会（National Science Foundation）合作，开发了一门新的基于计算原理的先修课程6。现在很多人使用“计算思维”这个词，指的是在很多领域和日常生活中使用计算原理，而不仅局限于科学计算7。
随着计算领域的日趋成熟，它吸引了其他领域的众多追随者。我们知道有16本书是为感兴趣的非专业人员来解释计算的各个方面8。大部分书关注的只是单个部分的内容，如信息、编程、算法、自动化、隐私以及互联网原理等。本书则将这个领域作为一个整体来看待，给出所有各部分如何组合在一起的系统叙述。读者会发现在所有这些部分的背后是一套连贯的原理。
根据教授从其他专业转到计算机科学的研究生的经验，我们发现对于初学者来说，原理框架比技术框架更容易理解。当早期核心技术很少的时候，用技术思想的观点来描述该领域是一种好方法。1989年，美国计算机协会（Association for Computing Machinery，ACM）列出了9大核心技术。而在2005年，ACM列出了大约14种，到了2013年，则有约18种。本书的6类原理框架并不是重新定义计算的核心知识，但它确实提供了一种看待该领域并降低其表面复杂性的新方式。
起源和目标
我们经常被问及6类原理的起源。20世纪90年代，本书作者之一Peter J. Denning在乔治梅森大学（George Mason University）开始这个项目。他从众多的同事那里收集了一个可能的原理陈述的列表。他发现了7个自然的群集，并将它们称为通信、计算、记忆（存储）、协作、评估、设计和自动化9。当组织本书的时候，我们意识到自动化并不是一个操纵物质和能量的类别，而是人工智能计算领域的重点。在本书中，我们从类别集合中删除了自动化，并将其包含在计算领域中。
这6个类别并不是把计算的知识空间划分成分离的片段。它们就像六角亭的窗户，每一扇窗户都以独特的方式呈现出内部空间，但同一件事物可以从多个窗户看到。例如，互联网有时以数据通信的方式、有时以协作的方式、有时以记忆（存储）的方式被看到。
这组类别有一个类别数目可控的框架，从而满足了我们的目标。虽然计算技术的列表还将继续增长，计算领域的集合也会扩大，但是类别的数目在较长时间内应该会保持稳定。
这本书是关于计算机科学的一个整体视角，注重最深入、最广泛的原理，即“宇宙普适的”原理（cosmic principle）10。本书将计算视作一种深层次的科学领域，其原理将影响包括商业和工业在内的其他每一个领域。
这本书是为所有想利用计算科学来达到其目标的人而设计的。受过科学教育的读者可以学到从算法到系统横跨整个领域的计算原理。而计算领域内的人，例如一个想要学习并行计算的程序员，可以找到这个巨大领域内不太熟悉的部分的概述。对于大学里学习诸如“计算机科学基础”课程的学生，本书可以帮助他们理解计算技术是如何影响他们的，例如网络和互联网如何使社交网络成为可能。初出茅庐的科学家、工程师和企业家可能在本书中找到一个面向整个计算机科学的科普型方法。
致谢
Peter要感谢他在计算原理的漫长旅程中遇到的许多人，这一旅程开始于他11岁时，那时他的父亲给了他一本关于机器原理的不同寻常的书——1911年出版的《How It Works》11。1960年，他的高中数学老师和科学社团导师Ralph Money，鼓励并引导他把精力投入计算机——引领未来的机器中去。1964年，当他成为MIT Mac项目的学生时，他的导师Jack Dennis、Robert Fano、Jerry Saltzer、Fernando Corbato和Allan Scherr把他的兴趣扩展到所有计算背后的基本原理。1967年他发表的第二篇论文是关于存储管理的工作集原理，其灵感主要来自于Les Belady、Walter Kosinski、Brian Randell、Peter Neumann和Dick Karp的帮助。1969年，他带领一个工作小组设计操作系统原理的核心课程，他的队友Jack Dennis、Butler Lampson、Nico Habermann、Dick Muntz和Dennis Tsichritzis帮助确定了操作系统的原理，其中也包括Bruce Arden、Bernie Galler、Saul Rosen和Sam Conte的见解。在之后的几年里，Roger Needham和Maurice Wilkes提供了关于操作系统原理的很多新的见解。1973年，他与Ed Coffman合写了一本关于操作系统理论的书。
1975年，Jeff Buzen把他吸引到操作分析的新领域，这项研究关注计算机系统性能评估的基本原理。在那段时间里，Erol Gelenbe、Ken Sevcik、Dick Muntz、Leonard Kleinrock、Yon Bard、Martin Reiser和Mani Chandy都促进了他对计算原理的理解。
1985年，ACM教育委员会（ACM Education Board）请他领导一个项目，以确定“计算”作为一门学科应具备的核心原理，用于设计1991年ACM/IEEE的课程推荐。他非常感谢这个团队加深了他对计算原理的理解，这个团队的成员有：Douglas Comer、David Gries、Michael Mulder、Allen Tucker、Joe Turner和Paul Young。
20世纪90年代中期，他开始在一个统一的框架下收集所有的计算原理。Jim Gray嘱咐他去寻找“宇宙普适的”原理——那些有足够深度和广度的、在任何时间、在宇宙中任何部分都有效的原理。他设计了一门叫作“信息技术核心”的“旗舰”课程，并在乔治梅森大学的同事Daniel Menascé、Mark Pullen、Bob Hazen和Jim Tref il的帮助下于1998年启动了该课程。
2002年，ACM教育委员会邀请他成立一个重要原理工作组，以便就重要原理框架如何促进未来课程的设计给出建议。一个相当优秀的团队为此走到了一起，他们是：Robert Aiken、Gordon Bell、Fred Brooks、Fran Berman、Jeff Buzen、Boots Cassel、Vint Cerf、Fernando Corbato、Ed Feigenbaum、John Gorgone、Jim Gray、David Gries、David Harel、Juris Hartmanis、Lilian Israel、Anita Jones、Mitch Kapor、Alan Kay、Leonard Kleinrock、Richard LeBlanc、Peter Neumann、Paul Rosenbloom、Russ Schackelford、Mike Stonebraker、Andy Tanenbaum、Allen Tucker和Moshe Vardi。
关于计算中的科学问题，Rick Snodgrass（一个追求“Ergalics”的志同道合的人）给了我们很多睿智的建议。Vint Cerf和Rob Beverly就网络相关的章节也给出了很多有用的建议。
Peter最感谢妻子Dorothy Denning，感谢她对于清晰的逻辑流程和坚实基础的一贯坚持，感谢她始终如一地鼓励他抓紧时间写作。同时也要感谢女儿Anne Denning Schultz和Diana Denning LaVolpe对他的信任和支持。
Craig Martell之所以被吸引来合作写这本书，是因为他总是想要参数化这个世界。在这方面，计算作为一个领域呈现出特别迷人的挑战，因为它是科学、数学和工程学的融合体。他时常痴迷于这些机器居然能工作！
Craig要感谢Mitch Marcus，他们在宾夕法尼亚大学共同讲授了“信息技术及其对社会的影响”这门课程。制作这门课程教学大纲的过程开启了他对本书的贡献。他还要感谢合作者Peter Denning，是他让整个写作过程变得有趣且富有成效。最后，他要感谢Pranav Anand、Mark Gondree、Joel Young、Rob Beverly和Mathias K lsch，他们使工作毫不沉闷。
Craig对于本书的贡献离不开妻子Chaliya的耐心与全方位的支持，还有女儿Katie崇敬的笑容。有了她们，他坚信自己是这世界上最幸运的男人。

计算机科学及应用

[美] 彼得 J. 丹宁（Peter J. Denning），克雷格 H. 马特尔（Craig H. Martell） 著：
彼得 J. 丹宁（Peter J. Denning） 美国海军研究生院杰出教授，ACM前主席，著名计算机杂志《Communications of The ACM》前主编。
克雷格 H. 马特尔（Craig H. Martell） 美国海军研究生院计算机科学系副教授。

罗英伟 高良才 张伟 熊瑞勤 译：暂无简介

计算机及其相关技术正在广泛而深刻地改变着我们的生活。没有哪门科学像计算机科学这样，能够与其他科学领域产生出如此多的交叉。尤其是近年来云计算、大数据、移动应用、机器学习、人工智能等，更是引起了人们的广泛关注。计算机是如此的神奇，但是人们却很少能够真正了解计算机是如何运行并完成复杂的工作的。人们对于计算机的理解似乎总是隔着一层面纱，有时清晰，有时却又很模糊，甚至很多计算机专业人员也同样会有这种感觉。
本书并不是单纯地介绍计算机技术，而是重新审视和理解计算本质，或者说阐述“计算之道”。本书从一个不同的视角，把计算看作是一门遵从一组基本原理的科学，所有计算机相关的技术都可以从这组基本原理中找到依托。具体而言，本书提供了一种重要原理框架（great principle framework）来刻画计算科学中最具基础性的基本原理。它将计算原理分为6类：通信、计算、协作、记忆（存储）、评估和设计，而在阐述时又将其所覆盖的范围分成11个更容易管理的模块，其内容涵盖了计算的方方面面——包括计算机是如何工作的、如何选择算法、计算系统是如何组织的，以及如何进行正确而可靠的设计等。
正如作者所说，这本书是为所有想利用计算科学及相关技术来实现特定目标的人而设计的。在介绍关于计算的基本原理时，作者深思熟虑地综合描述了计算背后的基本概念，并试图以一种“任何对计算有一定了解的人都能理解”的方式呈现。因此，与其他深入剖析特定技术的书籍不同，本书努力为读者构建一个关于计算的全面视图，而更深入的知识则需要（或者值得）读者自己不断去发掘、吸收，并将它们连贯起来。
本书的作者之一Peter J. Denning教授曾是ACM的主席，是若干基本计算原理的发现者，也一直非常关注计算科学的教育，并且早在20世纪90年代就开始本书内容的研究、整理以及教育实践。本书的作者发现，随着核心技术的增加，对于初学者来说，原理框架比技术框架更容易理解。本书的原理框架并不是重新定义计算的核心知识，但它确实提供了一种看待该领域并降低其表面复杂性的新方式。从这个意义上来说，基于原理的“计算”教学，可以帮助初学者抑或专业人员更加容易地构建一个关于计算的全面视图，是一种非常值得去实践的教育理念。另一方面，本书关于基本计算原理的讨论也一定会启发更多的人对“计算之道”进行广泛而深入的思考。
本书由北京大学计算概论课程组的几位老师共同翻译，具体分工如下：前言，第8、9章及相关内容由罗英伟、张彬彬翻译，并由罗英伟负责全书翻译工作的组织和协调；序，第3、11、12章及相关内容由高良才翻译；第1、2、5、10章及相关内容由张伟翻译；第4、6、7章及相关内容由熊瑞勤翻译。译稿之中倘若有不当之处，敬请读者批评指正。

译者
2017年3月于北京大学

出版者的话
译者序
序
前言
第1章　作为科学的计算　1
计算的范型　5
计算的重要原理　9
计算在科学中的位置　12
本书的关注点　13
总结　14
致谢　14
第2章　计算领域　15
领域和基本原理　16
信息安全　19
人工智能　20
云计算　22
大数据　24
总结　26
第3章　信息　27
信息的表示　28
通信系统　30
信息的测量　34
信息的转换　38
交互系统　40
解决悖论　41
信息和发现　42
总结　43
致谢　44
第4章　机器　45
机器　46
可以计算的机器　49
程序及其表示　53
栈式计算机：计算机系统的一种简单模型　54
过程与异常　56
选择的不确定性　61
结论　64
第5章　程序设计　65
程序、程序员和程序设计语言　66
程序设计实践　68
程序中的错误　70
自动翻译　72
总结　76
第6章　计算　78
简单问题　80
实例1　简单的线性搜索　81
实例2　二分搜索　81
实例3　排序　82
实例4　矩阵乘法　84
指数级困难问题　85
实例5　所有的十位数　85
实例6　背包问题　85
实例7　参观所有城市　86
实例8　合数分解　87
计算困难但容易验证的问题　88
NP完全　89
不可计算问题　92
总结　96
第7章　存储　98
存储系统　99
存储器的基本使用模型　100
命名　101
映射　105
虚拟存储　105
共享　107
能力　108
认证　111
层级结构中的定位　112
为什么局部性是基础　116
结论　117
第8章　并行　119
并行计算的早期方向　120
并行系统的模型　123
协作的顺序进程　124
功能系统　124
事件驱动的系统　125
MapReduce系统　125
协作的顺序进程　125
功能系统　131
结论　134
第9章　排队　136
排队论遇上计算机科学　137
用模型计算和预测　139
服务器、作业、网络和规则　140
瓶颈　144
平衡方程　146
ATM　147
电话交换机　148
分时系统　149
用模型来计算　150
结论　152
第10章　设计　154
什么是设计　156
软件系统的准则　158
需求　158
正确性　159
容错性　159
时效性　160
适用性　160
设计原理、模式和示意　161
原理　161
模式　162
示意　163
软件系统的设计原理　163
层级式聚合　164
封装　165
级别　166
虚拟机　168
对象　170
客户端与服务器　171
总结　172
第11章　网络　173
弹性网络　174
数据包交换　175
互联网络协议　178
传输控制协议　179
客户端与服务器　180
域名系统　181
网络软件的组织结构　183
万维网　184
网络科学　187
致谢　188
第12章　后记　189
没有意识的机器　189
智能机器　189
架构和算法　191
经验思维　192
一个崭新的机器时代来临　192
我们的思维方式正在转变　193
设计的核心性　193
各章概要　195
注释　200
参考文献　213
索引　227