1.1 扩展知识

1.1.1 计算机界的最高奖项是什么

“图灵奖”是计算机界最负盛名的奖项，也称为计算机界的诺贝尔奖，图1.1所示为图灵奖杯。“图灵奖”由国际计算机协会（ACM）于1966年设立，又名“A.M.图灵奖（A.M.Turing Award）”，用于奖励那些对计算机事业做出杰出贡献的人们。“图灵奖”的名称取自计算机科学的先驱、英国科学家阿兰·图灵，奖项的设立目的之一就是为了纪念这位杰出的科学家。

“图灵奖”是世界计算机科学领域的最高奖项，与物理、化学、医学、经济学领域的诺贝尔奖齐名。图灵奖的大多数获奖者是计算机科学家。图灵奖对获奖者的要求极高，评奖程序也极其严格，一般每年只奖励一名计算机科学家，只有极少数年度有两名、或两名以上的在同一方向上做出杰出贡献的科学家同时获奖。

图灵奖的奖金金额不算太高，设奖初期为2万美元，1989年起增到2.5万美元，奖金通常由计算机界的一些大企业提供（通过与ACM签订协议）。目前图灵奖由英特尔公司和Google公司赞助，奖金为25万美元。2014年11月13日，虽然英特尔公司退出了赞助，Google公司反将奖金提高到1 000 000美元，和诺贝尔奖金相近。

从1966年起，到2013年的48届图灵奖评选中，共计有61名科学家获此殊荣，其中美国学者最多，此外还有英国、瑞士、荷兰、以色列等国少数学者。截至2013年，获此殊荣的华人仅有一位，他是2000年图灵奖得主姚期智。

2015年3月25日，国际计算机协会（ACM）宣布计算机数据库专家Michael Stonebraker获得2014年图灵奖。ACM在通告中称Stonebraker发明了许多几乎应用在所有现代数据库系统中的概念，并且创立多家公司，成功地商业化了他关于数据库技术的开创性工作。因为Google公司的资助，从本次颁奖起图灵奖金额变为100万美元。下面我们来了解一下计算机界的鼻祖人物图灵，以及具有代表性的图灵奖得主。

1.图灵——计算机科学之父

阿兰·麦席森·图灵（Alan Mathison Turing）生于1912年6月23日，1954年6月7日去世，英国数学家、逻辑学家，被视为计算机科学之父。

图灵很小的时候就表现出与众不同的天分，在他三四岁的时候自己学会了阅读，读的第一本书叫作《每个儿童都该知道的自然奇观》。他特别喜欢数字和智力游戏，并为之着迷。8岁时写了他的第一篇“科学”短文，题目是《说说显微镜》。16 岁时就能弄懂爱因斯坦的相对论，并且运用那深奥的理论，独立推导力学定律。

1931年，图灵考入剑桥大学国王学院。1934年他以优异成绩毕业。1935年凭借论文“论高斯误差函数”当选为国王学院院士，并于次年荣获英国著名的史密斯（Smith）数学奖。

1939年图灵被英国皇家海军招聘，并在英国军情六处监督下从事对德国机密军事密码的破译工作。图灵带领200多位密码专家，研制出效率更高、功能更强大的密码破译机，将英国战时情报中心每月破译的情报数量从39 000条提升到84 000条。这些情报发挥了重要作用。历史学家认为，图灵让“二战”的结束至少提前了两年，至少拯救了2 000万人的生命，图灵因此在1946年获得“不列颠帝国勋章”。下面列举一些图灵主要的科学功绩。

（1）图灵机

1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为《论数字计算在决断难题中的应用》（On Computable Numbers，with an Application to the Entscheidungs Problem），这是他对理论计算机的研究成果。

在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”的设想。“图灵机”与“冯·诺伊曼机”齐名，被永远载入计算机的发展史中。“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算装置，用来计算所有能想象得到的可计算函数。基本思想是用机器来模拟人们用纸笔进行数学运算的过程。

图灵机被公认为现代计算机的原型，这台机器可以读入一系列的“0”和“1”，这些数字代表了解决某一问题所需要的步骤，按这个步骤走下去，就可以解决某一特定的问题。这种观念在当时是具有革命性意义的，因为即使在20世纪50年代的时候，大部分的计算机还只能解决某一特定问题，不是通用的，而图灵机从理论上却是通用机。

“图灵机”想象使用一条无限长度的纸带子，带子上划分成许多格子。如果格里画条线，就代表“1”；空白的格子，则代表“0”。想象这个“计算机”还具有读写功能：既可以从带子上读出信息，也可以往带子上写信息。计算机仅有的运算功能是：每把纸带子向前移动一格，就把“1”变成“0”，或者把“0”变成“1”。“0”和“1”代表着在解决某个特定数学问题中的运算步骤。“图灵机”能够识别运算过程中的每一步，并且能够按部就班地执行一系列的运算，直到获得最终答案。

图灵机是一个虚拟的“计算机”，完全忽略硬件状态，考虑的焦点是逻辑结构。图灵在他那篇著名的文章里，还进一步设计出被人们称为“万能图灵机”的模型，它可以模拟其他任何一台解决某个特定数学问题的“图灵机”的工作状态。他甚至还想象在带子上存储数据和程序。“万能图灵机”实际上就是现代通用计算机的最原始的模型。

图灵是第一个提出利用某种机器实现逻辑代码的执行，以模拟人类的各种计算和逻辑思维过程的科学家。而这一点，成为了后人设计实用计算机的思路来源，成为了当今各种计算机设备的理论基石。

（2）人工智能

1950年，图灵被录用为泰丁顿（Teddington）国家物理研究所的研究人员，开始从事“自动计算机（ACE）”的逻辑设计和具体研制工作。他提出关于机器思维的问题，他的论文《计算机和智能》（Computing Machinery and Intelligence），引起了广泛的注意和深远的影响。

图灵对于人工智能的发展做出了很大的贡献，他提出的著名的图灵机模型为现代计算机的逻辑工作方式奠定了基础。1950年10月，图灵发表了另一篇名为《机器会思考吗？》（Can Machines Think？）的论文，其中提出了一种用于判定机器是否具有智能的试验方法，即图灵测试。至今，每年都有这项试验的比赛。

“图灵测试”尝试给出一个决定机器是否具有感觉的标准。“图灵测试”由计算机、被测试人和主持试验人组成。计算机和被测试人分别在两个不同的房间里。测试过程由主持人提问，由计算机和被测试人分别做出回答。观测者能通过电传打字机与机器和人联系（避免要求机器模拟人外貌和声音）。被测人在回答问题时尽可能表明他是一个“真正的”人，而计算机也将尽可能逼真的模仿人的思维方式和思维过程。如果试验主持人听取他们各自的答案后，分辨不清哪个是人回答的，哪个是机器回答的，则可以认为该计算机具有了智能。这个试验可能会得到大部分人的认可，但是却不能使所有的哲学家感到满意。

图灵测试虽然形象地描绘了计算机智能和人类智能的模拟关系，但是图灵测试还是一个片面性的试验。通过试验的机器当然可以认为具有智能，同时对于没有通过试验的机器，虽然因为它们对人类了解的不充分而不能模拟人类，但仍然可以认为具有智能。

图灵测试还有几个值得推敲的地方，比如试验主持人提出问题的标准，在试验中没有明确给出；被测人本身所具有的智力水平，图灵试验也有所疏忽；测试仅强调试验结果，而没有反映智能所具有的思维过程。所以，图灵测试还是不能完全解决机器智能的问题。

就目前来看，我们并不怀疑机器具有人类的某些智能，我们更看重的是有什么样的机器在多大地程度上能模仿人类思维，这才是人工智能研究者们努力的目标。

（3）生物数学的奠基之作

从1952年直到去世，图灵一直在生物数学方面做研究。他在1952年发表了一篇论文《形态发生的化学基础》（The Chemical Basis of Morphogenesis）。他主要的兴趣是斐波那契叶序列，即存在于植物结构的斐波那契数。他应用的反应-扩散公式，现在已经成为图案形成范畴的核心。

图灵热心于图案形成和数理生物学的研究，1952年的论文至今被视为生物数学的奠基之作。图灵后期的论文都没有发表，一直等到1992年《艾伦·图灵选集》出版，这些文章才被世人所知。图灵在数学、逻辑学、神经网络和人工智能等领域都做出了杰出的贡献。在新旧世纪交替的2000年，美国《时代》杂志评选的20世纪对人类发展最有影响的100名人物中，图灵是仅有的20位科学家、思想家”之一。在2012年，英国著名杂志《自然》称赞他是有史以来最具科学思想的人物之一。

2.莱斯利·兰波特——分布式计算理论的奠基人

2013年的图灵奖得主是微软科学家莱斯利·兰伯特（Leslie Lamport）。兰伯特1941年出生于纽约，是欧洲移民的儿子。兰伯特在读高中时就已经涉足计算机科学领域。这听起来好像没有什么了不起，但那个时间是20世纪50年代中期。当时兰伯特就读于纽约的布朗士科学高中，他和一个朋友四处“捡破烂”——通过搜寻废弃的真空管来搭建数字电路。

在麻省理工学院获学士学位以后，兰伯特到布兰代斯大学攻读数学博士，不久后放弃，到佛蒙特州一所小型文科学校——万宝路学院教授数学。之后到麻省计算机协会做兼职工作，做ILLIAC（Illinois Automatic Computer，如美国的伊利阿克ILLIAC-Ⅳ）设计，如图1.2所示。1972年获博士学位，继续研究ILLIAC。兰伯特最终得出证明，分布系统中的相对次序与观察者有关。

在随后的几十年间，他逐渐成为计算机领域名副其实的传奇人物。他在1978年发表的论文《分布式系统内的时间时钟和事件顺序》（Time，Clocks，and the Ordering of Events in a Distributed System）成为计算机科学史上被引用次数最多的文献。兰伯特为“并发系统的规范与验证”研究贡献了核心原理，他的分布式计算理论奠定了这门学科的基础。

2013年，73岁的兰伯特成为微软研究院第5位荣获图灵奖的科学家。尽管兰伯特的学术生涯充满了众多令人称道的成就，但他对自己的评价却十分谦虚。比尔·盖茨曾经这样评价兰伯特：“作为一名带头人，他界定了分布式计算的许多关键概念，并让今天执行关键任务的计算机系统成为可能。兰伯特的伟大不仅仅局限于计算机科学领域，而且还体现在努力让世界变得更加安全。”

同样地，来自微软研究院的1992年图灵奖得主巴特勒·兰普森（Butler Lampson）对他的评价也很高：“兰伯特对并发系统理论和实践在质量、范围和重要性上的贡献都是难以超越的。它们完全可以和迪克斯特拉（Dijkstra）、霍尔（Hoare）、米尔纳（Milner）和伯努利（Pnueli）等所有图灵奖得主前辈的成就相提并论，但他最大的优点是作为一名应用数学家，擅长利用数学工具来解决具有非凡现实意义的问题。”

（1）时间、时钟和相对论

兰伯特在1978年发表的论文《分布式系统内的时间、时钟和事件顺序》（Time，Clocks，and the Ordering of Events in a Distributed System）成为计算机科学史上被引用次数最多的文献。他为“并发系统的规范与验证”研究贡献了核心原理，他的分布式计算理论奠定了这门学科的基础。文章介绍了有关分布式计算、同步和异步实体之间通信的原则性思维新途径。它在当时令人耳目一新，后来成为各种并发系统行为推理的基础，是一篇开山之作。

1978年，兰伯特在Compass公司任职期间，当时他正为罗伯特·托马斯（Robert Thomas）和保罗·约翰进（Paul Johnson）共同撰写的论文《复制数据库的维护》（The Maintenance of Duplicate Databases）作序。这篇论文认为，对于两个完全相同的数据库，如果其中之一发生改变，那么对它们更新时就需要用到时间戳（Timestamp）。而在看完论文后，兰伯特发现，“它没有保留因果关系。尽管事件按照完成时间的顺序出现在系统中，但其在逻辑上并不与命令发出的顺序相一致。我意识到，如果改变时间戳的产生方法，这个问题可能很容易得到解决”。

兰伯特对问题的洞察力源自他对物理学和狭义相对论的兴趣。他意识到。确定两个事件在时间顺序上存在问题，除非两者之间有因果联系——也就是说，除非它们之间传递过信息。他由此认识到，如果这种信息的时间戮可以用来确定事件的顺序，则该系统中发生的所有事件都可以按单一顺序排列。推而广之，一个计算系统内的任何事物都可以用状态机来描述（状态机保持着特定状态，接收输入后产生一个输出，同时改变其自身的状态）。兰伯特推论，这个概念可以适用于更加复杂的系统，如银行或航空票务预订。

（2）面包店算法

兰伯特在Compass工作期间的另一个成果是在《迪克斯特拉（Dijkstra）并行编程问题新解》一文中提出的面包店算法。该算法旨在解决互斥问题：排除多个线程试图对相同存储位置写入时发生数据损坏的现象，以及在一个线程完成对特定位置写入之前另一个线程无法读取该位置的现象。其名称暗指面包店常用的排序系统：客户在进入面包店时需要选择一张有编号的票。

（3）拜占庭将军问题

离开Compass后，兰伯特加入了美国斯坦福国际研究院（SRI）。在此期间，他和同事马歇尔·皮斯（Marshall Pease）及罗伯特·肖斯塔克（Robert Shostak）合作完成了两篇旨在解决“拜占庭故障”（Byzantine failures）的论文。

当时斯坦福国际研究院有一个项目，目标是为美国航空航天局建立容错型航电计算机系统（fault-tolerant avionics computer system），这种系统要求不允许发生故障。一般说来，“普通”故障可能会导致信息丢失或过程停，但它们不会遭到损坏——即便遭到损坏，也能通过利用冗余来丢弃损坏的信息。即便过程停止，也不会给出错误答案。然而，“拜占庭故障”却可能犯错，或给出错误信息。

当时常用的技术是“三重模块冗余”（triple modular redundancy），使用3个独立的计算按照某种少数服从多数的原则“投票”，即使其中一台机器提供了错误答案，其他两台仍然会提供正确答案。但是为了证明其有效，必须拿出证据，在编写证据过程中，研究人员遇到了一个问题：“错误”计算机可能给其他两台机器分别发送不同的错误值，而后者却不知道。这就需要使用第四台计算机来应对这个故障。

兰伯特说：“如果你使用数字签名就可以用三台机器达成目的，因为如果“错误”计算机向一台计算机发送了带签名的错误值，并向另一台发送了不同的带签名错误值，后两台计算机就能够交换消息，以检查究竟发生了什么情况，因为两个不同的值都是签名发送的。”在一个朋友的启发下，兰伯特联想起拜占庭帝国军队中“司令将军和叛徒将军”的问题，于是他将这个问题及其解决方案命名为“拜占庭将军问题”。

（4）Paxos算法

兰伯特的论文《兼职议会》（The Part-Time Parliament）通过希腊神话中一个岛屿及其立法机构的类比解释了Paxos算法。为了添加一些幽默气氛，在所有的算法故事说明中，兰伯特都给人物取了希腊人的名字。论文的结论是：“可能会发生一些导致系统崩溃的事件。你可以利用系统来自我重新配置，但是如果你稍有疏忽，就可能会遇到一种情况：议会无法再通过更多的法律。在故事中恰恰发生了这种情况，而一个名叫兰普森（Lampson）的将军便接管政权，成为独裁者。”

然而，兰伯特没想到的是，这篇讨论如何构建分布式系统的论文，在相当长一段时间没有得到重视。论文的最终发表已经是10年后的事情，而且经过增补，纳入了对干预方法的思考。兰伯特后来写了一篇题为《Paxos化繁为简》（Paxos Made Simple）的文章来解释算法的简洁性——而且没有借用希腊文字游戏。随着时间的推移，人们逐渐认识到这项工作是一个真正的进步。现在，Paxos算法已经成为现代分布式系统中的一项重要技术。如果没有以Paxos及类似的技术为核心，就不可能建立一个具有顽健性的、可靠的大型分布式系统。

兰伯特作为一位拥有辉煌履历和至高荣誉的数学家，对计算机科学做出了重大贡献，他的成功充分说明思维的重要性，他同时强调“只编码不编程，相当于没有蓝图就盖房子”，从另一个角度说明计算、思维是计算机科学蓬勃发展的理论奠基石。

3.姚期智——华人的骄傲与榜样

2000年的图灵奖授予了一位美国普林斯顿大学计算机科学系教授、华裔学者姚期智，以表彰其在计算理论领域做出的卓越贡献。姚期智的英文名字是安德鲁·姚（Andrew C.Yao），祖籍湖北孝感，1946年12月24日出生于上海，幼年随父母去台湾。1967年在台湾大学毕业后去美国深造。他1972年在哈佛大学取得物理学博士学位，在做了一年博士后研究工作之后，选择到伊利诺依大学研究生院继续攻读计算机科学博士学位，并于1975年获得该学位。他曾先后在麻省理工学院、斯坦福大学、加州大学伯克利分校从事教学与研究，1986年加盟普林斯顿大学至今。姚期智的主要贡献在计算机理论方面。ACM 的授奖决定指出，姚期智对计算理论的贡献是根本性的，意义重大的，其中包括基于复杂性的伪随机数生成理论、密码学、通信复杂性等。姚期智是图灵奖近40年来首次授予一位华裔学者。

1967年，生于上海长在台湾的姚期智带着自己的行囊走进了哈佛大学，追随导师格拉肖（Sheldon Lee Glashow，1979年诺贝尔物理学奖得主），开始了自己的物理世界探索之旅，并顺利地拿到了物理学博士学位。1973年，26岁的姚期智做出了一生中的重要决定，放弃苦心钻研多年的物理学，转而投向方兴未艾的计算机技术。他曾说：“就能力和性格而言，我更适合搞计算机。物理看重直觉，你必须推想出问题的正确答案，求证也许不严格。可数学，包括计算机，最重要的是你必须用严密的数学推理来证明这个答案。我发现自己的论证能力在计算机领域更合适。”1973年，姚期智进入伊利诺伊大学攻读计算机科学，并于两年后获得博士学位。

不平凡的经历铸就了不平凡的人生，自 1975年获得美国伊利诺伊大学计算机科学博士学位后，姚期智在理论计算机领域潜心研究直至今日。多年来，姚期智以其敏锐的科学思维，在数据组织、密码学、通信复杂性乃至量子通信和计算等多个尖端科研领域，都做出了巨大而独到的贡献，曾获美国工业与应用数学学会George Polya奖，美国计算机协会算法与计算理论分会（ACM SIGACT）Donald E.Knuth奖等荣誉。国际计算机协会（ACM）在2000年授予姚期智图灵奖。姚期智是图灵奖创立以来首位获奖的亚裔学者，也是迄今为止获此殊荣的唯一华裔计算机科学家。

姚期智的人生如璀璨的明珠，闪烁着计算机科学家的高尚品格，他把缜密的计算机科学播撒到了世界各地，对计算机的发展起到了不可磨灭的作用！

人生宛如一出圆舞，总要回到情系千里的故土。出国多年，姚期智仍然心系祖国，他认为中国的图灵之路走了三分之一，“希望能为中国和同胞尽点微薄之力”。2004年，姚期智决定将 57岁以后的人生回归中国大陆，开创科学研究的新舞台。他毅然辞去了普林斯顿大学终身教职，卖掉了在美国的房子，正式加盟清华大学高等研究中心任全职教授。“我所学的东西能有机会在我出生的中国生根，有条件在该领域为中国培养出世界级的研究人员来，我觉得这是一件非常有意义的事情。”

到清华大学仅一年半，姚期智就发起了志在培养国际计算机科学领军人物的“软件科学实验班”。他最看重清华有许多很好、很有潜力的学生，“我回中国的一个目的，就是希望在短时间内，在中国，至少在我的研究领域，能够创造出一流的研究环境。”姚期智坚定地说，“我们要建立一个计算机领域的‘超级公路’，使得我们的学生从本科生开始，一直到研究生、教授，在中国工作可以比世界任何其他地方机会更好，也更感到荣耀。”

短短几年，姚期智带领他的清华团队在理论计算机科学研究方面颇有斩获。除填补了中国在《美国科学院院刊》等前沿国际刊物上发文的空白，在2006年理论计算机科学领域最顶级的学术会议FOCS上，清华大学计算机系有3篇论文入选，实现了国内学者在该会议上“零的突破”，其中一篇还获得2006年度FOCS最佳论文奖。

2007年3月29日，姚期智领导成立了清华大学理论计算机科学研究中心。他从清华开始，逐步建立中国的计算机理论科学的研究队伍，试图在国际上造成影响。姚期智饱含深情地说：“在国内，我所专长的这门学科，发展还是比较迟缓。而我们有这么多人才，能够教给他们这门学问并引导他们朝这方面走，是最快乐的事情。”

1.1.2 你了解冯·诺依曼的传奇人生吗

约翰·冯·诺依曼（John Von Neumann，1903—1957），美藉匈牙利人，20世纪最重要的数学家之一，是在现代计算机、博弈论和核武器等诸多领域内有杰出建树的最伟大的科学全才之一，被称为“计算机之父”和“博弈论之父”。

冯·诺依曼从小就显示出数学天赋，传说他3岁就能记住不少数字，6岁时能心算做8位数乘除法，8岁时学会了微积分，12岁就读懂了波莱尔的大作《函数论》。诺依曼记忆力十分惊人，读书过目成诵。上中学时，老师对他卓越的数学天赋惊叹不已，并向其父亲建议，让小诺依曼退学回家，聘请大学教授来当家庭教师。17岁时，诺依曼与老师合作发表了第一篇数学论文。

诺依曼作为全才型的天才，掌握7种语言，并在当时最新的数学分支——集合论、泛函分析等理论研究中取得突破性进展。22岁时，诺依曼获得瑞士苏黎士联邦工业大学化学工程师文凭。1926年，获布达佩斯大学数学博士学位。此后，他转向物理领域，在理论物理领域“风光无限”。风华正茂的诺依曼一下子成为科学殿堂的“文武全才”，在数学、应用数学、物理学、博弈论和数值分析等领域都有不凡的建树。

1.纯粹数学

在1930—1940年间，冯·诺依曼在纯粹数学方面取得的成就较为集中，冯·诺依曼选择了量子理论的数学基础、算子环理论、各态遍历定理3项作为他最重要数学工作。

1927年冯·诺依曼已经在量子力学领域内从事研究工作。他和希尔伯待、诺戴姆联名发表了论文《量子力学基础》。冯·诺依曼主要从事于该主题的数学形式化方面的工作。1932年，冯·诺依曼出版了他的重要著作《量子力学的数学基础》。

算子环理论研究始于1930年下半年，冯·诺依曼十分熟悉诺特和阿丁的非交换代数，很快就把它用于希尔伯特空间上有界线性算子组成的代数上去，后人把它称之为冯·诺依曼算子代数。之后的1936—1940年间，冯·诺依曼发表了6篇关于非交换算子环论文，都是20世纪分析学方面的杰作，其影响一直延伸至今。其中算子环理论的一个惊人的亮点是由冯·诺依曼命名的连续几何。普通几何学的维数为整数1、2、3等，冯·诺依曼在著作中给出，决定一个空间的维数结构实际上是它所容许的旋转群决定的，因而维数可以不再是整数，于是诞生了连续级数空间的几何学。

1932年，冯·诺依曼发表了关于遍历理论的论文，解决了遍历定理的证明，并用算子理论加以表述，它是在统计力学中遍历假设的严格处理的整个研究领域中，获得的第一项精确的数学结果。也是20世纪数学分析研究领域中取得的最有影响的成就之一，这标志着一个数学物理领域开始接近精确的现代分析的一般研究。

此外，冯·诺依曼在实变函数论、测度论、拓扑、连续群、格论等数学领域也取得不少成果，并为1900年希尔伯特提出的20世纪23个数学难题的第5个问题做出了贡献。

2.应用数学

1940年，冯·诺依曼的科学生涯转入应用数学。他开始关注当时把数学应用于物理领域的最主要工具——偏微分方程。研究同时他还不断创新，把非古典数学应用到两个新领域：对策论和电子计算机。

第二次世界大战爆发后，冯·诺依曼应召参与了许多军事科学研究计划和工程项目。1937年他关注纳维-斯克克斯方程的统计处理可能性的讨论，1949年他为海军研究部写了《湍流的最新理论》。

冯·诺依曼研究过激波问题，他在碰撞激波的相互作用方面的贡献引人注目，在这个领域中的大部分工作，直接来自国防的需要。

冯·诺依曼研究过气象学。有相当一段时间，地球大气运动的流体力学方程组所提出的极为困难的问题一直吸引着他。随着电子计算机的出现，有可能对此问题作数值研究分析。冯·诺依曼提出的第一个高度规模化的计算，处理的就是一个二维模型，它与地转近似有关。他相信人们最终能够了解、计算并实现控制、以致最终改变气候。

冯·诺依曼还曾提出用聚变引爆核燃料的建议，并支持发展氢弹。1947年军队发嘉奖令，表扬他是物理学家、工程师、武器设计师和爱国主义者。

3.博弈论

冯·诺依曼不仅曾将自己的才能用于武器研究等，而且还用于社会研究。1928年，冯·诺依曼证明了博弈论的基本原理，从而宣告了博弈论的正式诞生。由他创建的对策论，无疑是他在应用数学方面取得的最为令人羡慕的杰出成就。现如今，博弈论主要是指研究社会现象的特定数学方法。它的基本思想就是在分析多个主体之间的利害关系，给出（诸如下棋、玩扑克牌等室内游戏中）各竞赛者之间在讨价还价、交涉、结伙、利益分配等行为方式的指导建议。

博弈论也常用于经济学。1944年，冯·诺依曼和摩根斯特恩合著的《博弈论和经济行为》是经济学专业的奠基性著作之一。

4.计算机

冯·诺依曼一生最后研究的课题是电子计算机和自动化理论。1944—1945年间，冯·诺依曼研究出了现今所用的将一组数学过程转变为计算机指令语言的基本方法，当时的电子计算机（如ENIAC）缺少灵活性、普适性。冯·诺依曼设计出机器中的固定的、普适线路系统，提出“流图”、“代码”等概念，为克服以上缺点做出了重大贡献。

计算机工程的发展也应大大归功于冯·诺依曼。计算机的逻辑图式，现代计算机中存储、速度、基本指令的选取以及线路之间相互作用的设计，都深深受到冯·诺依曼思想的影响。他不仅参与ENIAC计算机的研制，而且还在普林斯顿高等研究院亲自督造了一台计算机。稍前，冯·诺依曼还和摩尔小组一起，写出了一个全新的存储程序通用电子计算机方案 EDVAC，长达 101页的报告轰动了数学界。这使得一向专搞理论研究的普林斯顿高等研究院也批准让冯·诺依曼建造计算机，其依据就是这份报告。

在冯·诺依曼生命的最后几年，他的思想仍很活跃，他综合早年对逻辑研究的成果和关于计算机的工作，把眼界扩展到一般自动机理论。他以特有的胆识进击最为复杂的问题：怎样使用不可靠元件去设计可靠的自动机，以及建造自己能再生产的自动机。开创了人工智能研究中心两大学派之一的数学学派（另一学派是心理学派），著有对人脑和计算机系统进行精确分析的著作《计算机与人脑》。

回顾冯·诺依曼辉煌的科学一生，无论在纯粹数学还是在应用数学研究方面，冯·诺依曼都显示了卓越的才能，取得了众多影响深远的重大成果。纵观其研究特点可以看出，他不断变换研究主题，常常在几种学科交叉渗透中获得成就是他的特色，其中最精髓的贡献有两点：二进制思想与程序存储思想。

鉴于冯·诺依曼在发明电子计算机中所起到关键性作用，他被西方人誉为“计算机之父”；而在经济学方面突破性的成就，又被誉为“博弈论之父”；在物理领域，他撰写的《量子力学的数学基础》已经被证明对原子物理学的发展有极其重要的价值；在化学方面，他也有相当的造诣，曾获苏黎世高等技术学院化学系大学学位，是一位当之无愧的全才。

1.1.3 为什么说世界进入了“计算”时代

对于现在的人们来说，使用计算机已是寻常之事。若问什么是计算机呢？如今解释计算机的概念就不能仅仅局限于常见的台式计算机和笔记本电脑了，从广义的形式上来说，一切包含或内置了具有计算机功能的电脑芯片的机器或设备都可以称为广义的计算机。

传统的计算机自20世纪40年代出现以来，已经发生了很大的变化，从大如楼房的“电子管计算机”，到普通个人使用的“台式计算机”；从可便于携带的“笔记本电脑”，到如今人们应用的各种电子设备，如手机、平板电脑、随身听、导航仪等，计算机的外形已经发生了巨大的变化。

不仅如此，在现如今的生活中，各种各样的服务设施如飞机、汽车、高铁等，各种行业基础设备如电子机床、医用CT等，都是具有内嵌的形式各样的广义计算机——即各种机器的“大脑”都是计算机。仔细观察可以发现，这些设施或机器的竞争点也多在其计算机控制系统，其计算机控制系统也体现了这些机器的智能化、尖端化程度。

据资料介绍，每个人每天接触或使用多达250个计算机芯片：这其中约40个芯片存在于人们的工作环境中，如所使用的台式机、笔记本电脑、打印机、扫描仪、电话系统等；约80个芯片嵌入在各种各样的家用电器中，如电视机、DVD、游戏机、自动厨房设备等；约 40个芯片存在于各种公共环境中，如ATM机、PDA、自动加油机、自动售票机等；约70个芯片存在于所使用的汽车中。

计算机不仅仅体现为上述这些硬件设备，更多地体现在软件上。人们每天在接触多达250个芯片的同时，也会接触到各种各样的计算机软件，如手机软件、生活应用软件及办公操作软件等。也就是说，形形色色的计算机，包括硬件和软件，极大地改变了人们的工作和生活环境，计算机已将人类带入了一个“计算”时代。

1.1.4 怎样理解计算的深层含义

虽然计算最初的起源是计数，随着科学应用的不断发展，如今的计算这一概念已引申到计数、运算、演算、推理、变换和操作等概念。下面就从计数、逻辑、算法这3不同的角度来理解计算所蕴含的意义。

1.计数是计算起源

计算机的起源如果从计算工具算起，至少可以追溯到人类祖先使用石头或手指计数的远古时代。古人用石头计算捕获的猎物，石头就是计算工具。美国著名科普大师艾萨克·阿西莫夫（1920—1992）曾说过，人类最早的计算工具是手指，英文Digit既表示“手指”又表示“数字”。而我国专家考证，大约在新石器时代早期，即远古传说中伏羲、黄帝之前，人们就开始用绳子打结的方法来表示数的概念，结绳就是当时的计算工具。

古人曰：“运筹帷幄中，决胜千里外”。筹策又称算筹，它是中国古代普遍采用的一种计算工具。算筹不仅可以替代手指帮助计数，而且还能做加、减、乘、除等算术运算。据古书记载，算筹一般是使用竹子、木头或兽骨制成的小棍，其长为13～14cm，直径为0.2～0.3cm，约270枚为一束，放在布袋里随身携带。人们在地面或盘子中反复摆弄这些小棍，通过移动进行计算，从而出现了“运筹”一词，运筹就是计算。古人还创造横式和纵式两种不同的摆法，两种摆法都可以用1～9来计算任意大小的自然数，与现代通用的十进制计数法完全一致。总之，算筹属于硬件，而摆法就是算筹的软件。

我国南北朝时期的杰出数学家祖冲之（429—500），他曾借助算筹这一计算工具，将圆周率π值计算到小数点后第7位，即在3.1415926至3.1415927之间，成为当时世界上最精确的π值。为了求得这个π值，需要对很多位进行包括开方在内的各种运算达到130次以上，就是今人使用纸和笔进行计算也是比较困难的。

对于圆周率π值，人们始终不满足已有的成绩。1593年，荷兰阿德里恩根据古典方法求π值，精确到小数点后第15位。1610年，德国数学家鲁道尔夫采用圆外切与内接正多边形的方法，正确地求出π值的35位有效数字。17世纪以后，由于级数理论的发展，计算 π 值的公式越来越多。到 1706年，英国数学家梅钦计算的π值突破100位小数大关。1873年英国数学家尚可斯特计算π值到小数点后707位，可惜从第528位起是错误的。到 1948年英国的弗格森和美国的伦奇共同发表的 π 值有 808位，成为人工计算圆周率的最高纪录（见图1.3）。

由于π值可以表示成一个无穷数，因此对它的计算除了掌握一定的计算方法外，主要就是进行大量的数值计算，这是对计算工具和人的耐力的一种巨大的挑战。1949年，美国马里兰州阿伯丁弹道研究实验室首次使用 ENIAC 机计算 π 值，很快就算到2037位小数，突破了千位小数。1958年超过1万位，1961年超过10万位，1973年超过100万位，1983年超过800多万位。此后，利用超级计算机计算π值，这一纪录不断被刷新。1989年5月达4.8亿位，1989年8月超过10亿位，1991年达21.6亿位，2010年达2.7万亿位。2011年10月，日本计算机奇才近藤茂利用家用计算机将圆周率计算到小数点后10万亿位，创造了吉尼斯世界纪录。

随着科技与社会的发展，越来越多的问题需要用计算来解决。计算工具的不断发展，大大提高了人类的计算能力。“数值计算方法”（又称计算方法）就是一门与计算机应用紧密结合的、实用性很强的数学课程。许多计算领域的问题，如计算力学、计算物理学、计算化学以及计算经济学等新学科都可以归结为数值计算问题。数值计算与计算机的发展相辅相成并相互促进。由于数值计算的需要，促使计算机结构及性能不断更新，而计算机的发展又推动着数值计算方法的发展。

一般来说，科学计算包括实际问题、数学模型、计算方法、程序设计和计算结果等一系列过程。科学计算的应用范围十分广泛，一些尖端的国防项目，如核武器的研制、导弹的发射等，始终都是科学计算最活跃的领域。目前，科学计算在工农业生产的各部门中也在发挥着日益重要的作用。例如，对气象资料的汇总、加工并生成天气图像，其计算量大且时限性强，要求计算机能够进行高速运算，以便对天气做出短期或中期的预报。

2.逻辑推理也能计算

逻辑（Logic）一词源于希腊词Logos，原意是指规律、理性和推理等。现代汉语中“逻辑”一词也是多义的，其主要含义是指客观事物的规律、某种理论或观点、思维规律或逻辑规则、逻辑学和逻辑知识等。因此，逻辑就是思维的规律，逻辑学就是关于思维规律的学说。有时逻辑和逻辑学这两个概念通用，逻辑的本质是寻找事物的相对关系，并用已知推断未知。

早期的逻辑学有三大流派：以亚里士多德的词项逻辑和斯多亚学派的命题逻辑为代表的古希腊逻辑，以先秦名辩学为代表的古中国逻辑，以正理论和因明学为代表的古印度逻辑。随着历史的演进，只有肇事于古希腊逻辑的西方逻辑有相对完整的历史，后来成为世界逻辑发展的主流，现代逻辑就是以古希腊逻辑为基础发展而来。

古希腊哲学家亚里士多德（公元前384—公元前322）集前人研究之大成，写成了逻辑巨著《工具论》。亚里士多德使形式逻辑从哲学、认识论中分离出来，形成了一门以推理为中心的独立科学，因此而被称为“逻辑之父”。亚里士多德认为逻辑学是一切科学的工具，他力图把思维形式和存在联系起来，按照客观实际来阐明逻辑的范畴。亚里士多德通过对各种推理模式的分析，提出了三段论，即大前提、小前提和结论3个部分。因此，人们可以把推理看成是对符号的操作，即符号演算。

逻辑是研究推理的学科，它分为辩证逻辑和形式逻辑两类。辩证逻辑是以辩证法认识论世界观为基础的逻辑学，形式逻辑是对思维的形式结构和规律进行研究的一门学科。思维的形式结构包括概念、判断和推理之间的结构与联系，概念是思维的基本单位，判断是通过概念对事物是否具有某种属性进行肯定或否定的回答，推理是由一个或几个判断推出另一个判断的思维形式。

研究推理的方法很多，利用数学方法来研究推理的规律统称为数理逻辑。我们把推理的过程理解为计算，而这种计算正是计算机能表达和适合的操作。所以，数理逻辑这门学科建立以后，发展特别迅速，除了它与数学其他分支如集合论、数论、代数、拓扑学等的发展有重大的相互影响外，它与计算机学科的相互影响也起到了很大的推动作用。

数理逻辑的主要分支包括：逻辑演算（包括命题演算和谓词演算）、模型论、证明论、递归论和公理化集合论。数理逻辑和计算机科学有许多重合之处，两者都属于模拟人类认知机理的科学。许多计算机科学的先驱者既是数学家、又是逻辑学家，如阿兰·图灵、邱奇等。

数理逻辑研究的是形式体系，作为其组成部分的命题演算与谓词演算等在计算科学中作用巨大、影响深远。我们知道，要使用计算机就首先需要编制程序，程序的本质是算法和数据结构的融合，算法的本质是逻辑与控制的结合，也就是说，在计算机内部离不开逻辑的表达与控制，计算机内部的计算很大一部分是逻辑的计算。

事实上推理与计算是相通的，数理逻辑的许多研究成果都可以用于计算科学。原则上数理逻辑已给出的思维过程可以借助计算机来实现，计算科学的深入研究又推动了数理逻辑的发展。例如，一阶逻辑中没有时间的概念，而程序的推理是涉及过程的，因此需要增加程序算子或其他包含时间概念的算子，以便适用于过程推理。数理逻辑倡导的形式化方法已经广泛渗入计算科学的各个领域中，如软件规格说明、形式语义学、程序变换、程序正确性证明、硬件综合和验证等。因此，数理逻辑与计算科学的关系非常密切，直接为计算科学的产生和发展提供了重要的思维方法和研究工具。

3.算法是计算的灵魂

算法（Algorithm）来源于9世纪波斯数学家al-Khwarizmi（花刺子密）撰写的著名的“Persian Textbook”（波斯教科书）中提出的算法这一概念。后来被赋予更一般的含义，即一组确定的、有效的、有限的解决问题的步骤，这就是算法的最初定义。1700年前后，德国科学家莱布尼茨提出了二进制算法，它为现代计算机奠定了算法基础。

算法在中国古代文献中称为“术”，最早出现在《周算经》和《九章算术》中。特别是《九章算术》，其中给出了四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数等各种算法。

现在我们理解的算法是对特定问题求解步骤的一种描述，又可细分为：数值计算算法和非数值计算算法。例如，科学计算中的求解积分、解线性方程等计算方法，称为数值计算算法；而用于管理、文字处理、图形图像处理的如排序、分类和查找等方法的描述，就称为非数值计算的算法。

算法是为解决一个特定的问题所采取的确定的有限步骤。尽管算法并不给出问题的精确解，只是说明怎样才能得到解。但是，算法是由有限个操作组成的，这些操作包括加、减、乘、除和判断等，并按顺序、分支、循环等结构组织在一起。它告诉计算机如何一步一步地进行计算，直至解决问题。对于一个给定的问题，可能有多个算法，但它们的质量可能会完全相同。衡量算法质量的主要因素是执行时间的长短和占用存储空间的多少。就目前硬件而言，尤以时间因素为贵。当然还有其他的质量因素，如收敛速度的快慢、误差积累的大小以及结果精度的高低等。

算法由一些操作和数据组成，而这些操作又是按照一定的控制结构所规定的次序执行的。因此，算法是由数据、操作和控制结构三要素组成的。

数据是指操作对象和操作结果。由于算法层出不穷，变化万千，其操作对象数据和操作结果数据名目繁多，不胜枚举。最基本的有布尔值、字符、整数和实数等；稍复杂的有向量、矩阵和记录等；更复杂的有集合、树和图，还有声音、图形和图像等。

算法中的每一步都能分解成计算机的基本操作，否则算法就是不可行的。虽然算法的操作种类很多，但最基本的有赋值运算、算术运算、逻辑运算和关系运算等；稍复杂的有算术表达式和逻辑表达式等；更复杂的有函数值计算、向量运算、矩阵运算、集合运算，以及表、栈、队列、树和图的运算等；此外，还可能是由以上列举的运算的复合和嵌套。

算法的控制结构给出了算法的框架，决定了各种操作的执行次序。任何复杂的算法都可以用顺序结构、分支结构和循环结构3种控制结构组合而成。

总之，问题的求解是计算，求解算法中的每一步骤也是计算。计算的过程是算法，算法又由计算步骤构成。计算的目的由算法实现，算法的执行由计算完成。算法是计算科学中最重要的内容，是计算的灵魂，甚至可以说：计算机科学就是算法的科学。

1.1.5 如何看待计算的复杂性

计算复杂性理论（Computational Complexity Theory）是用数学方法研究各类问题的计算复杂性的学科。它研究各种可计算问题在计算过程中资源（如时间、空间等）的耗费情况，以及在不同计算模型下，使用不同类型资源和不同数量的资源时，各类问题复杂性的本质特性和相互关系。计算复杂性理论是理论计算机科学的分支学科，它是算法分析的理论基础。

1.计算复杂性理论的发展

1964年，美国的J.Hartmanis和R.E.Stearns在普林斯顿举行的第5届开关电路理论和逻辑设计学术年会上发表了论文《递归序列的计算复杂性》（Computational Complexity of Recursive Sequences）”，文中首次使用了“计算复杂性”这一术语，由此开辟了计算科学中的新领域。为此他们获得了1993年度图灵奖。

随后在1967年，美国麻省理工学院M.Blum发表了博士论文《递归函数复杂性的机器独立理论》（A Machine Independent Theory of the Complexity of Recursive Functions），文中不但提出了计算复杂性的一些公理，而且对复杂性类的归纳也做了更高的抽象。此外，Blum还致力于将这一理论应用到对计算机系统的安全性有着重要意义的密码学中，以及软件工程中的程序正确性验证方面，并取得了令人瞩目的成就。Blum是计算复杂性理论的奠基人之一，为此他获得了1995年度图灵奖。

此后，许多研究人员对计算复杂性理论做出了不同程度的贡献。其重要的内容包括：对随机算法的去随机化的研究，对近似算法的不可近似性的研究，以及交互式证明系统理论和零知识证明等。特别是复杂性理论对近代密码学的影响非常显著，而最近复杂性理论的研究人员又进入了博弈论领域，并创立了“算法博弈论”这一分支学科。

2.算法复杂性

算法复杂性是指对算法效率的度量，它是评价算法优劣的重要依据。一个算法复杂性的高低体现在运行该算法时所需要的资源，所需资源越多，算法复杂性越高；反之，所需资源越少，则算法复杂性越低。计算机的资源，主要是指运行时间和存储空间。因而，算法复杂性有时间复杂性和空间复杂性之分。

对于任意给定的问题，设计复杂性尽可能低的算法是人们在设计算法时追求的一个重要目标。另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是选用算法时应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。

3.计算复杂性

算法复杂性是针对特定算法而言的，而计算复杂性则是针对特定问题而言的，后者反映的是问题的固有难度。计算复杂性等于最佳的算法复杂性，它在计算科学中既有理论意义，又有实用价值。

计算复杂性是指利用计算机求解问题的难易程度。度量标准包括两个方面：一是计算所需的步数或指令条数（即时间复杂度），二是计算所需的存储空间大小（即空间复杂度）。一般没有必要就一个个具体问题去研究它的计算复杂性，而应依据问题的难度去研究各种计算问题之间的联系。

一个问题的规模是指这个问题的大小。一个算法的计算复杂性直接决定了这个算法可以应用到多大规模的问题上。假设有求解同一个问题的两个算法，第一个算法的计算复杂性是 n3，第二个算法的计算复杂性是3n。用每秒百万次的计算机来计算，当n=60时，第一个算法只要用时0.2s，而第二个算法就要用时4×1028s，也就是1015年，相当于10亿台每秒百万次的计算机计算一百万年。

考察上面提到的两个算法复杂性，前者n3是一个多项式函数，后者3n是一个指数函数。当n很大时，这两个算法的效率差异是很大的。因此，一个问题如果没有多项式时间计算复杂性算法，这一问题就被称为是难解型问题。但是，要断定一个问题是否是难解型问题也是很困难的。一个问题即使长期没有找到多项式时间计算复杂性算法，也不能保证明天就一定找不到，更不能据此证明这个问题不存在多项式时间计算复杂性算法。

4.典型的复杂性计算

2000年5月，美国克雷数学研究所（Clay Mathematics Institute，CMI）的科学顾问委员会选定了7个“千禧年数学难题”，该研究所的董事会决定建立700万美元的大奖基金，每个“千禧年数学难题”的解决都可获得百万美元的奖励。这7个难题分别是：P问题对NP问题，霍奇猜想，庞加莱猜想，黎曼假设，杨-米尔斯存在性和质量缺口，纳维叶-斯托克斯方程的存在性与光滑性，贝赫和斯维讷通-戴尔猜想。其中，NP 完全性问题排在百万美元大奖的首位，足见它的显赫地位和无穷魅力。

通常将问题分为可计算和不可计算两类。计算的基本功能就是对一个问题给出“是”或“非”的判定，所以又可归结为问题的可判定和不可判定。P（Polynomial）问题指多项式时间内可以解决的问题类，它是计算复杂性理论中十分重要的问题类。现有理论认为：停机问题是不可计算或不可判定的，此类之外的问题是可计算或可判定的。

NP（Non-Polynomial）问题是不能在确定性图灵机上用多项式算法进行求解，但是可以用一种非确定性多项式算法求解的问题。许多组合、排队和路线优化问题都属于 NP 类问题，如著名的旅行商问题就是NP问题。

P=NP？问题是指P和NP的关系，到底是P=NP还是P≠NP？它是计算机科学的核心问题之一，与历史上其他难解的数学问题一样，是对人类智力的一个大挑战。尤为重要的是，在与计算有关的学术领域中，NP完全算题层出不穷，因此，P=NP？是一个对计算机和其他科学有着全面影响的问题。

如果P=NP，那么NP类算题都将能计算。学术界该做的事就是千方百计去找到各种NP算题的多项式时间算法。但是，互联网的安全问题就会成为最严重的挑战，因为破译互联网的RSA加密系统属于 NP 算题，既然它也存在多项式算法，就必须立即放弃这种加密系统，那么又该采用怎样的有效安全措施呢？

如果P≠NP，那么大量的NP类算题都将不具有确定性多项式算法。学术界就不该把精力浪费在 NP 系列的分类上，应赶紧去寻找各种 NP 算题的最优近似算法。而对于互联网和一些需要密码系统的安全问题，则可以彻底放心。

总之，计算复杂性理论是计算机理论科学和数学的一个分支，解决计算的根本问题：即是否可计算、计算复杂性的分类及这些类别联系。在计算机领域，与此相关的专业有算法分析和可计算性理论。算法分析主要考虑使用某一确定的算法来求解某个问题时所需的资源量；可计算性理论用于研究所有可能的算法来解决相同问题，尝试在受限资源条件下问题的解或不解，即讨论一般问题在何种原则上可以用何种算法解决。

1.1.6 计算是无处不在无所不能的吗

在20世纪70年代以前，计算机还仅限于专业人士使用，计算也只是计算科学家们的事情。但是今天，计算问题已经广泛渗入各个学科，从生物计算到社会计算，从绿色计算到情感计算，计算已无处不在。如果说十年前，智能终端还是一个新名词，那么今天，它已经广泛地存在于人们的工作和生活中。正如著名未来学家尼葛洛庞帝在《数字化生存》一书中所说：“计算不再只是和计算机有关，它决定着我们的生存”。

1.普适计算

在计算机发明的最初年代里，计算机是神秘的，人们研发了操作系统，利用一种全新的程序来使用计算机。到20世纪70年代末，随着微型计算机的出现，计算机出现在了人们的办公桌上，这种新潮的电器不仅能够计算，还可用于工作和娱乐，操作系统也更加简单和可用，计算机进入了桌面计算时代。

在最近的十几年中，计算技术在默默地改变着人们的生活，这种改变不是轰轰烈烈的，一切都在悄无声息的发生。传统的手工控制的设备和家用电器具有了自动控制功能，从电冰箱、洗衣机、电视机、微波炉，甚至到人们佩戴的首饰，计算似乎潜入到所有的一切中，计算进入了无形时代，人类进入了普适计算的时代。

1991年，美国施乐（Xerox）公司PARC研究中心的Mark Weiser在Scientific American上发表文章《The Computer for the 21st Century》，首次提出了普适计算（Ubiquitous Computing）的概念。1999年，IBM也提出普适计算（Pervasive Computing）的概念，即无所不在，随时随地可以进行计算的一种方式。Weiser与IBM的观点是一致的，特别强调计算资源普遍存在于环境当中，人们可以随时随地获得需要的信息和服务。

同样是在1999年，欧洲研究团体ISTAG提出了环境智能（Ambient Intelligence）的概念，与普适计算的概念类似，二者提法不同，但是含义相同，实验方向也是一致的。在美国通常称为普适计算，而欧洲的有些组织团体则称为环境智能。

今天，普适计算已经成为一个重要的研究领域，普适计算的核心思想是小型、低价、网络化的处理设备，其广泛分布在日常生活的各个场所，这些计算设备将不只依赖于命令行、图形界面进行人机交互，而更多的是依赖于“自然”的交互方式，计算设备的尺寸将缩小到毫米、甚至纳米级的级别。

普适计算概念强调和环境融为一体的计算，从而使计算机本身从人们的视线里消失。在普适计算的环境中，无线传感器网络作为普及的基础设备，将在环境设置与保护、交通传输等领域发挥作用；人体传感器网络将会大大促进健康监控以及人机交互等的发展。同时，各种新型交互技术（如触觉显示、OLED等）将使交互更容易、更方便。

普适计算的目的是建立一个充满计算和通信能力的环境，同时使这个环境与人们逐渐地融合在一起，在这个融合空间中，人们可以随时随地、透明地获得数字化服务。在普适计算环境下，整个世界是一个网络的世界，数不清的为不同目的服务的计算和通信设备都连接在这个网络中，人们能够在任何时间、任何地点、以任何方式进行信息的获取与处理。

2.网格计算

普适计算的发展，将计算置于无所不在的范围；追求高性能的计算，则将计算推向无所不能的程度。高性能计算需要实现更快的计算速度、更大负载能力和更高的可靠性。实现高性能计算的途径包括两方面，一方面是提高单一处理器的计算性能，另一方面是把这些处理器集成，由多个CPU构成一个计算机系统，这就需要研究多CPU协同分布式计算、并行计算、计算机体系结构等技术。图1.4所示为曙光CAE高性能计算平台。

网格计算（Grid Computing）就是通过利用大量异构计算机的未用资源（如CPU和磁盘存储），将其作为嵌入在分布式电信基础设施中的一个虚拟的计算机集群，为解决大规模的计算问题提供了一个模型。从本质上讲，网格计算是一种架设在互联网上的分布式计算，可以看作是由一群松散耦合的计算机组成的一个超级虚拟计算机，主要用来执行大型计算的任务。

网格是一个基础体系结构，网格是把地理位置上分散的资源集成起来的一种基础设施。通过这种基础设施，用户不需要了解基础设施上资源的具体细节就可以使用自己需要的资源。分布式资源和通信网络是网格的物理基础，网格上的资源包括计算机、集群、计算机池、仪器、设备、传感器、存储设施、数据、软件等实体。另外，这些实体工作时需要的相关软件和数据也属于网格资源。

网格作为一个集成的计算与资源环境，能够吸收各种计算资源，将它们转化成一种随处可得的、可靠的、标准的且相对经济的计算能力，其吸收的计算资源包括各种类型的计算机、网络通信能力、数据资料、仪器设备甚至有操作能力的人等各种相关资源。在科学计算领域、网格计算在分布式超级计算、高吞吐率计算、数据密集型计算等方面得到广泛的应用，这其中离不开高性能计算机这个重要资源。

发展高速度、大容量、功能强大的超级计算机，对于进行科学研究、保卫国家安全、提高经济竞争力具有非常重要的意义。诸如气象预报、航天工程、石油勘测、人类遗传基因检测、机械仿真等现代科学技术，以及开发先进的武器、军事作战的谋划和执行、图像处理及密码破译等，都离不开高性能计算机。研制超级计算机的技术水平体现了一个国家的综合国力，因此超级计算机的研制是各国在高技术领域竞争的热点。

2010年11月，超级计算机500强第一名为中国天河一号A系统，如图1.5所示。它有14 336颗Intel Xeon X5670 2.93GHz六核心处理器，2048颗我国自主研发的飞腾FT-1000八核心处理器，7168块NVIDIA Tesla M2050高性能计算卡，总计18 6368个核心，224TB内存。实测运算速度可以达到每秒2570万亿次（这意味着，它计算一天相当于一台家用计算机计算800年）。

2011年6月，超级计算机500强第一名为日本的K Computer，运行速度为每秒8.16千万亿次浮点计算（Petaflops），它由68 544个SPARC64 VIII fx处理器组成，每个处理器均内置8个内核，总内核数量为54 8352个，投资超过12.5亿美元。

3.软性计算

除了高性能的计算，计算的无所不能也体现在各行业的计算发展，如社会计算、情感计算等软科学计算。随着互联网技术的发展和应用的快速普及，计算已经不仅仅是一个技术问题，它正在全面地影响人们的思想、观念和行为，成为一种社会文化现象。随着计算机技术，特别是网络技术对社会影响的日益深入，形成了一种新型的交叉学科，即社会计算（Social Computing）。社会计算是现代计算技术与社会科学之间的交叉产物，其研究内容是面向社会活动、社会过程、社会结构、社会组织和社会功能的计算理论和方法。

社会是一个异常复杂的系统，采用简单的变量和时间参数是难以描述的。由于社会系统中的个体众多，他们之间的影响错综复杂，导致系统表现出复杂的行为，运行的结果空间庞大而难以预测。另外，许多突发事件的发生，政府和社会学家、计算机科学家都意识到，能否利用计算机强大的数据处理能力来对社会问题建模，开发新的信息系统处理方法，有效地分析海量的情报内容，使用计算机模拟手段来对社会问题进行预测和模拟，对于防范社会突发事件的发生、防范恐怖主义袭击威胁，更好的保障社会公共安全具有重要意义。

社会计算的最初研究领域是互联网，通过分析人们在网上的行为来对个人的行为建模，进行数据挖掘、知识发现等。随着普适计算的发展、传感器和可穿戴网络的逐渐普及，社会计算还从传统的Web信息计算中逐步延伸到物理世界中，通过感知物理社会中人们的移动及交互轨迹来挖掘个人、群体及社会性行为。今天，人们拥有了海量的信息，但是还缺乏海量信息处理和分析的能力，这正是社会计算发展的根本和动力所在。

情感计算是MIT媒体实验室Picard教授在1997年提出的，她指出情感计算来源于情感或能够对情感施加影响的计算。今天，情感计算（Affective Computing）已成为一个新兴研究领域。众所周知，人随时随地都会有喜怒哀乐等情感的起伏变化。那么在人与计算机交互过程中，计算机是否能够体会人的喜怒哀乐，并见机行事呢？情感计算研究就是试图创建一种能感知、识别和理解人的情感，并能针对人的情感做出智能、灵敏、友好反应的计算系统，即赋予计算机像人一样的观察、理解和生成各种情感特征的能力。

情感是一种内部的主观体验，但总是伴随着某种表情，表情包括面部表情（面部肌肉变化所组成的模式）、姿态表情（身体其他部分的表情动作）和语调表情（言语的声调、节奏和速度等方面的变化）。这3种表情也被称为体语，构成了人类的非言语交往方式。目前，情感计算研究面临的挑战很多，如情感信息的获取与建模问题，情感识别与理解问题，情感表达问题，以及自然和谐的人性化和智能化的人机交互的实现问题。

情感计算有广泛的应用前景。计算机通过对人类的情感进行获取、分类、识别和响应，进而可以帮助使用者获得高效而亲切的感觉，并有效减轻人们使用计算机的挫败感，甚至帮助人们理解自己和他人的情感世界。

1.1.7 未来世界的计算是怎样的

随着计算机网络技术的深入发展，依托于网络的各种形式的计算也得到了深入与普及的应用。科学家们给我们勾画出一个未来的远景：世界是一个计算的天地，人们的生活将从数字城市走向智慧城市，世界最终将迈向智慧地球的美好前景。

1998年1月31日，在加利福尼亚科学中心开幕典礼上，美国前副总统戈尔发表“数字地球——新世纪人类星球之认识”的演说，首次提出了数字地球（Digital Earth）的概念，指出数字地球是一种能嵌入巨量的地理信息、对地球所做的多分辨率、三维的描述方式。

戈尔描述的“数字地球”是一个关于整个地球、全方位的GIS与虚拟现实技术、网络技术相结合的产物。其核心思想是用数字化的手段来处理整个地球的自然和社会活动等诸方面的问题，最大限度地利用资源，并使人们能够通过方便的方式获得所想了解的各种地球信息，其特点是嵌入海量地理数据，实现多分辨率、三维对地球的描述，即构建一个公共的“虚拟地球”，最大限度地为人类的生存、城市的可持续发展，以及人们的日常工作、学习、生活、娱乐等提供快捷方便的服务。

很显然，“数字地球”是人类的一项浩大的工程，任何一个政府组织、企业或学术机构，都是无法独立完成的，它需要成千上万的个人、公司、研究机构和政府组织的共同努力。数字地球要解决的技术问题很多，主要涉及：计算机科学、海量数据存储、卫星遥感技术、互操作性、元数据等学科与计算。

1.数字城市

数字地球是当今世界经济和信息技术发展的客观进程，是在现代高科技条件下信息全球化、国际化的历史必然。在国际知识经济社会中，各国都将“数字地球”工程置于一个重要的战略高点。

数字城市源于数字地球的战略构想，产生于数字地球的科学背景和技术背景之下，是数字地球技术体系的集中体现，也是数字地球的重要组成部分。城市作为地球表面人口、经济、技术设施、信息最稠密的地区，数字城市理所当然成为数字地球网络系统最重要的组成部分，也是建设数字地球的关键和难点。

数字城市是充分利用遥感技术（Remote Sensing，RS）、地理信息系统（Geographical Information System，GIS）、全球定位系统（Global Position System，GPS）（简称3S技术）、计算机技术和多媒体、虚拟仿真等信息技术，对城市基础设施和与生产生活发展相关的各方面进行多主体、多层面、全方位的信息化处理和利用，是对城市的地理、资源、生态、环境、人口、经济、社会等诸方面进行数字化、网络化的管理、服务和决策功能集一体的信息系统。其核心思想是利用数字化手段，借助网络信息高速公路，最大限度地利用信息资源，整体性地解决城市所面临的经济、社会等诸多方面的问题。

数字城市是“数字地球”实施的关键节点。“数字城市”的体系结构虽然涉及多种不同的系统，但从广义上说仍属于计算机及网络所支持的系统群集。因而它具有计算机信息系统的基本特征，具有比较严密的逻辑结构。主要包含的关键技术有：宽带网络的建设、海量存储的处理、异构数据库和空间应用、数据共享与互操作技术、可视化与虚拟现实的实现等。数字城市的应用创建，又可细化分为数字社区、数字家庭、数字个人等，目前我国正在建设的数字城市就是由此演变来的。

2.智慧城市

众所周知，城市在社会国民经济的发展中赋有重要的地位，在数字化城市的进程中总是面临着环境污染、交通拥堵、能源紧缺、住房、失业、疾病等方面的问题与挑战。如何解决城市发展所带来的诸多问题，实现城市的可持续发展成为城市规划和建设的重要命题。

IBM 在 2010年正式提出了“智慧城市”的愿景。研究认为，城市由关系到其主要功能的不同类型的网络、基础设施和环境等6个核心系统组成：组织（人）、业务，政务、交通、通信、水和能源。城市是由这些相互协作、相互衔接的子系统而构成的宏观系统。智慧城市的远景是通过互联网技术，有机连接城市核心系统并作出智能化响应，从而更好地服务于人们学习、生活、工作、医疗等方面的需求，以及改善政府对交通管理、环境控制、医疗服务等城市问题的处理能力。

智慧城市是在信息技术、知识社会支撑下的、新一代创新环境下的城市形态。时下的智慧城市是指建立在物联网、云计算等信息技术上的，广泛应用社交网络、维基、Living Lab、Fab Lab等工具，营造出的一种城市发展的新形态。利用信息和通信技术，城市生活将更加智能，资源利用将更加高效。

近年来，有两种驱动力推动了城市由数字城市向智慧城市的演化，一是以物联网、云计算为代表的新一代信息技术，二是知识社会环境下开放的城市创新生态，创新成为知识社会推动城市发展的重要驱动力。智慧城市的主要特征表现为，城市具有高效而智慧的政务管理、经济管理、交通管理及生活管理等处理能力。

在数字城市和智慧城市之间，它们的差异更多是理念上的。数字城市强调的是城市的数字化，通过城市地理空间信息与城市各个方面信息的数字化将传统城市再现在一个虚拟空间中，人们可以根据需要进行浏览和查询。而智慧城市则更注重数据的挖掘和服务，强调在数据上的城市管理、服务和创新，提高城市的整体管理水平。

3.智慧地球

2008年11月，IBM总裁兼首席执行官彭明盛（Samuel J.Palmisano）首次提出了“智慧地球”这一发展概念（见图1.6）。

“智慧地球”概念直接面对于当今世界面临的重大问题，如资本与信用的危机，经济的低迷和未来的不确定性，信息爆炸而激增的风险与机会，全球化和新兴经济等等。这些问题带来的机遇和挑战，应得到全人类共同的关注与协同的解决。“智慧地球”还指出，人类出现了几乎任何东西都可以实现数字化和互连的现实，利用互联技术实现网络化的智能服务是未来社会发展的全新思路。

智慧地球的发展从根本上依赖于未来的互联网技术。欧盟科学家认为，未来的互联网将具有更多的用户、更多的内容、更复杂的结构和更多的互动参与特性。互联网将会实现用户产生内容、无处不在的访问方式以及物理世界与数字世界更好的集成。从互联网的社会网络交互性来看，提出未来互联网将是由物联网、内容与知识网、服务互联网和社会网络等构成。

所谓物联网，就是“物物相联的互联网”，是指通过射频识别（RFID）、红外感应器、全球定位系统、激光扫描器等信息传感设备，按约定的协议，把任何物品与互联网连接起来，进行信息交换和通信，以实现智能化识别、定位、跟踪、监控和管理的一种网络，是一种实现“人物互连、物物互连、人人互连”的高效能、智能化网络。内容与知识网络是由各种模型、知识和数据构成的互连网络，这些模型、数据和知识可能由用户产生，也可能由物联网产生并经智能化处理，模型、数据和知识是实现智能的重要基础；而服务互联网是指将全球各地不同提供者的服务互连起来为所有用户使用，是一种EaaS（Everything as a Server，万物皆服务）的网络，各种资源均是通过服务方式由提供者提供给用户所使用的；社会网络是指由参与互联网的用户、提供者及其相关关系等形成的网络，包括虚拟世界用户网络和现实世界用户网络以及相互之间的作用网络。

IBM提出的智慧地球思想，从一个总体产业或社会生态系统出发，针对某产业或社会领域的长远目标，调动其相关生态系统中的各个角色以创新的方法做出更大更有效的贡献，充分发挥先进信息技术的潜力，以促进整个生态系统的互动，以此推动整个产业和整个公共服务领域的变革，形成新的世界运行模型。其强调更透彻的感知（Instrumented），利用任何可以随时随地感知、测量、捕获和传递信息的设备、系统或流程；强调更全面的互连互通（Interconnected），先进的系统可按新的方式系统工作；强调更深入的智能化（Intelligence），利用先进技术获取更智能的洞察并付诸实践，进而创造新的价值。

也就是说，智慧地球在3I（Instrumented、Interconnected、Intelligence）的支持下，将以一种更智慧的方法和技术来改变政府、公司和人们交互运行的方式，提高交互的明确性、效率性、灵活性及响应速度，进而改善社会生活各方面的运行模式。智慧地球的主要含义是把新一代IT技术充分应用到各行各业之中，即把感应器嵌入和装备到电网、铁路、桥梁、隧道、公路、建筑、供水系统、大坝、油气管道等各种物体中，并且被普遍连接，形成所谓“物联网”；通过超级计算机和云计算将物联网整合起来，实现人类社会与物理系统的整合；在此基础上，人类可以以更精细和动态的方式管理生产和生活，提供更多种的服务，从而达到智慧的状态。

通过前面介绍可以看出，计算与计算机学科已经对社会和人类的思维模式产生了巨大的影响，无论哪一专业学科的研究，都应离不开计算思维的思想。了解和理解一些计算思维的思想，并能积极运用于各自学科的创新活动中，这将是未来科学研究与创新中不可或缺的一种模式。

1.1.8 计算科学与科学计算是一回事吗

一般地，从计算的视角来看，计算科学（Computational Science）是一种利用数学模型构建、定量方法分析，以及利用计算机来分析和解决科学问题的研究领域。在实际应用中，计算科学主要应用于：对各个专业学科中的问题进行数学模拟和其他形式的计算，从这个角度来说，也称其为科学计算。

1.计算科学与国家核心竞争力

西方发达国家一直将计算科学视为关系国家命脉的国家战略给予高度重视。美国通过实施1993年的高性能计算与通信（High Performance Computing & Communication，HPCC）计划、1996年的加速战略计算创新（Accelerated Strategic Computing Initiative，ASCI）计划、2002年的高产能计算系统（High Productivity Computing Systems，HPCS）计划，在许多领域内获得了一系列重大科技成就，促进了高科技与国民经济的持续发展和国防高科技武器的出现，并获得基础科学研究的强大创新能力。同时，直接推动了高效计算机快速发展，为当今高科技的世界领先地位奠定了重要基础。

2005年6月，在由美国总统信息技术咨询委员会（The President＇s Information Technology Advisory Committee，PITAC）提交的“计算科学：确保美国竞争力”（Computational Science：Ensuring America＇s Competitiveness）报告中，再次将计算科学提升到国家核心科技竞争力的高度。报告认为，21世纪科学上最重要的、经济上最有前途的前沿研究都有可能利用先进的计算技术和计算科学而得以解决。报告强调，美国目前还没有认识到计算科学在社会科学、生物医学、工程研究、国家安全以及工业改革中的中心位置，这种认识不足将危及美国的科学领先地位、经济竞争力以及国家安全。报告建议，应将计算科学长期置于国家科学与技术领城中心的领导地位。

伴随着计算机科学的飞速发展，计算科学也呈现出新的特点。从计算机的视角来看，计算科学是应用高性能计算能力预测和了解客观世界物质运动或复杂现象演化规律的科学，它包括数值模拟、工程仿真、高效计算机系统和应用软件等。目前，计算科学已经成为科学技术发展和重大工程设计中具有战略意义的研究手段，它与传统的理论研究和实验研究一起，成为促进重大科学发现和科技发展的战略支撑技术，是提高国家自主创新能力和核心竞争力的关键技术因素之一。

2.计算科学与计算学科

计算科学的发展与研究是计算学科的主要任务。一般来说，学科是指高等学校中讲授或研究知识的分科，它是高校教学和科研的细胞组织。从计算的角度来说，利用计算科学对其他学科中的问题进行计算机模拟或者其他形式的计算而形成的诸如计算物理、计算化学、计算生物等学科统称为计算学科（Computational Discipline）。

计算学科是在数学和电子科学基础上发展起来的一门新兴学科，它既是一门理论性很强的学科，又是一门实践性很强的学科。几十年来计算学科自身发展的实践表明，一方面，围绕着一些重大的背景问题，在各个分支学科和研究方向上均取得了一系列重要的理论和技术成果，推动了计算科学向深度和广度发展；另一方面，由于发展形成了一大批成熟的技术并成功地应用于各行各业，更多的人将计算科学看成是一种高新技术。

从计算机发展的角度来说，计算学科来源于对数理逻辑、计算模型、算法理论和自动计算机器的研究，形成于20世纪30年代后期。计算学科主要是对描述和变换信息的算法过程进行系统的研究，它包括算法过程的理论、分析、设计、效率分析、实现和应用等。计算学科研究的基本问题是：什么能被有效地自动进行？

1988年，美国计算机协会（ACM）和国际电气电子工程师学会计算机分会（IEEE-CS）联合完成了一份重要报告：“计算作为一门学科”。该报告把计算机科学和计算机工程统一称为计算学科，认为两者没有基础性的差别，并且第一次给出了计算学科的定义，将计算学科分为计算机科学、软件工程、计算机工程、信息技术和信息系统5个分支学科，提出了计算学科的详细内容、研究方法和一系列教学计划等，并说明了每一分支学科的重点研究方向。

3.计算机科学是计算科学的基础

计算机科学（Computer Science，CS）研究的范围很广，从计算理论、算法基础到机器人开发、计算机视觉、智能系统以及生物信息学等，其主要工作包括寻找求解问题的有效方法、构建应用计算机的新方法以及设计与实现软件。计算机科学是计算各个分支学科的基础，计算机科学专业培养的学生，更关注计算理论和算法基础，并能从事软件开发及其相关的理论研究。

ACM和IEEE-CS联合工作组在关于计算机科学的CS2008报告中，给出了计算机科学知识体的概念，为其他分支学科知识体的建立提供了范式。计算机科学知识体由3个层次组成，它们分别是知识领域（Area）、知识单元（Unit）和知识点（Topic）。计算机科学知识体共有14个知识领域，如表1.1所示。

计算机科学是研究计算机及其周围各种现象和规律的科学，分为理论计算机科学和应用计算机科学两个部分。理论计算机科学包括计算理论、信息与编码理论、算法与数据结构、程序设计语言理论、形式化方法、并行和分布式计算系统、数据库及信息检索等。应用计算机科学包括人工智能、计算机系统结构与工程、计算机图形学、计算机视觉、计算机安全和密码学、信息科学以及软件工程等。计算机科学根植于数学、电子工程和语言学，它是科学、工程和艺术的结晶。

计算机科学的研究基于图灵机和冯·诺依曼机，它们是绝大多数实际机器的计算模型。作为该计算模型的开山鼻祖，邱奇-图灵论题表明，尽管在计算的时空效率上可能有所差异，现有的各种计算系统在计算能力上是等同的。这一理论通常被认为是计算机科学的基础，可是科学家也研究其他类型的机器，如在实际层面上的并行计算机和在理论层面上概率计算机、Oracle计算机和量子计算机。从这个意义上来讲，计算机只是一种计算的工具。荷兰著名的计算机科学家埃德斯加·狄克斯特拉（E.W.Dijkstra，1930—2002）有一句名言：“我们所使用的计算工具影响着我们的思维方式和思维习惯，从而也将深刻地影响着我们的思维能力。”

计算机学科在中国的发展可以追溯到20世纪50年代创建的“计算装置与仪器”专业和“计算数学”专业，发展到20世纪70年代末期出现“计算机及应用”专业和“计算机软件”专业，直到1994年设置了“计算机科学与技术”专业。

1995年，互联网在世界范围内的蓬勃兴起使得“计算”概念发生了深刻的变化，社会对计算机人才的需求骤增，这种变化不可避免地反映到教育中。一方面，若干相关课程被引入计算机专业的教学计划中；另一方面，一些学校开设了软件工程、网络工程、信息安全、电子商务和数字媒体等新专业。同时其他相关专业也在蓬勃发展，比如与信息技术相关专业有电子信息工程、光信息科学与技术、生物信息学、通信工程、微电子学、信息与计算科学、自动化等专业，这些专业加起来，在校学生人数可达几十万之众。

计算机人才的专业基本能力包括计算思维能力、算法设计与分析能力、程序设计与实现能力、系统分析与开发应用能力。但是学科的不同形态确定了不同类型的人才所需要强调的能力是不同的。例如，研究型人才强调理论形态的内容，需要强化计算思维能力、算法设计与分析能力的培养；工程应用型人才强调设计形态的内容，要求强化程序设计与实现能力、系统分析与开发应用能力的培养。

我国高校计算机科学专业设置的一般情况是：计算机科学与技术一级学科包括计算机系统结构、计算机软件与理论、计算机应用技术3个二级学科。计算机系统结构是研究硬件与软件的功能匹配，研究计算机系统的物理和硬件结构、各组成部分的属性以及这些部分的相互联系。计算机软件与理论主要研究软件开发、维护以及使用过程中所涉及的理论、方法和技术，探讨计算机科学与技术学科发展的理论基础。计算机应用技术着重研究将计算机应用于各个领域时所涉及的原理、方法与技术。计算机科学与技术学科同其他学科之间，以及自身的3个二级学科之间将日益互相渗透、互为影响，大力发展跨学科、跨专业的研究必将促进本学科及其相关学科更大、更快的发展。

1.1.9 计算思维是科学思维吗

思维是思维主体独立信息及其意识的活动，思维最初是指人脑借助于语言对客观事物的概括和间接的反应过程。思维以感知为基础又超越感知的界限，它探索与发现事物的内部本质联系和规律性，是认识过程的高级阶段。

1.思维是一种广义的计算

思维作为一种心理现象，是认识世界的一种高级反映形式。具体地说，思维是人脑对客观事物的一种概括的、间接的反映，它反映客观事物的本质和规律。思维是在人的实践活动中，特别是在表象的基础上，借助于语言，以知识为中介来实现。思维由思维原料、思维主体和思维工具等组成。自然界提供思维的原料，人脑作为思维的主体，认识的反映形式形成了思维的工具，三者具备才有思维活动。

思维具有概括性、间接性和能动性等特征。思维是在人的感性基础上，将一类事物的共同、本质的特征和规律抽取出来，加以概括，这就是思维的概括性。感觉和知觉只能反映事物的个别属性，而思维则能反映一类事物的本质和事物之间的规律性联系。例如，通过感觉和知觉，只能感知太阳每天从东方升起，又从西方落下。通过思维，则能揭示这种现象是由于地球自转的结果。

思维的间接性是指非直接的、以其他事物做媒介来反映客观事物。思维是凭借知识和经验对客观事物进行的间接反映。例如，医生根据医学知识和临床经验，通过病史询问以及一定程度的体检和辅助检查，就能判断病人内脏器官的病变情况，并确定其病因、病情和做出治疗方案。

思维的能动性是一个重要的特征，它不仅能认识和反映客观世界，而且还能对客观世界进行改造。例如，人的肉眼看不到DNA分子，但人的思维却揭示了DNA分子的双螺旋结构，从而揭示了大自然潜藏的遗传密码。再如，人类不仅认识到物体离开地球所需的宇宙速度，还制造出了地球卫星和宇宙飞船飞向太空。

思维有多种类型，按照思维的进程方向，思维可分为横向思维、纵向思维与发散思维、收敛思维等；按照思维的抽象程度，思维可分为直观行动思维、具体形象思维和抽象逻辑思维；按照思维的形成和应用领域，思维可分为科学思维与日常思维。综观思维的种类、思维的活动特性，可以得出这样的结论：思维也是一种广义的计算。

2.科学思维的深层含义

所谓科学思维是指形成并运用于科学认识活动的、人脑借助信息符号对感性认识材料进行加工处理的方式与途径。一般来说，科学思维比日常思维更具有严谨性与科学性。

科学思维（Scientific Thinking）通常是指理性认识及其过程，即经过感性阶段获得的大量材料，通过整理和改造，形成概念、判断和推理，以便反映事物的本质和规律。科学思维是认识自然界、社会和人类意识的本质和客观规律性的思维活动，其思维内涵主要表现在：高度的客观性，围绕求得科学答案而展开的思维以及采取理论思维的形式。

科学思维是指人脑对自然界中事物的本质属性、内在规律及自然界中事物之间的联系和相互关系所做的有意思的、概况的、间接的和能动的反映，该反映以科学知识和经验为中介，体现为对多变量因果系统的消息加工过程，也就是说，科学思维是人脑对科学信息的加工活动。

现代科学思维就是指主体思维的科学化，也就是与现代科学发展相适应的最佳的思维结构，与现实系统发展相一致的合理的逻辑过程，能够迅速、准确地反映客体的优化的思维方式，这三者的有机统一，就构成现代科学思维。在科学认识活动中，现代科学思维强调必须遵守3个基本原则：在逻辑上要求严密的逻辑性，达到归纳和演绎的统一；在方法上要求辩证地分析和综合两种思维方法；在体系上实现逻辑与历史的一致，达到理论与实践的具体的历史的统一。

一般来说，科学思维立足于理性思维，运用逻辑思维方式，以系统的观点来考察研究，以创造性思维的方式实现科学研究的过程。科学思维不仅是一切科学研究和技术发展的起点，而且始终贯穿于科学研究和技术发展的全过程，是创新的灵魂。

科学思维是关于人们在科学探索活动中形成的、符合科学探索活动规律与需要的思维方法及其合理性原则的理论体系。科学思维的方式还包括归纳分类、正反比较、联想推测、由此及彼、删繁就简和启发借用等，而科学思维能力应包括审视能力、判误能力、浮想能力、综合能力和归纳能力等。

3.计算思维是科学思维

思维科学是研究思维活动规律与形式的科学。从探讨思维活动规律的角度出发，科学思维可分为发散求解思维、逻辑解析思维、哲理思辨思维、理论建构与评价思维等。

发散求解思维是指人们在科学探索中不受思维工具或思维定式的制约，从多方面自由地思考问题答案，其中包括求异思维、形象思维和直觉思维等。逻辑解析思维是指人们在科学探索中自觉运用逻辑推理工具去解析问题并由此推得问题解的思维方法，其中包括类比思维、隐喻思维、归纳思维、演绎思维和数理思维等。哲理思辨思维是指人们在科学探索中运用不同程度的思辨性哲学思维去寻求问题答案，其中包括协调思维、系统思维和辩证思维等。理论建构与评价思维是指人们在科学探索中总结解题成果进而形成和完善理论系统的思维，其中包括理论形成思维、理论检验思维和理论评价思维等。

科学思维是思维规律与思维方法的统一，从人类认识世界和改造世界的思维方式出发，科学思维又可分为理论思维、实验思维和计算思维3种。

理论思维（Theoretical Thinking）也称逻辑思维，是指通过抽象概括，建立描述事物本质的概念，应用科学的方法探寻概念之间联系的一种思维方法。它以推理和演绎为特征，以数学学科为代表。理论源于数学，理论思维支撑着所有的学科领域。正如数学一样，定义是理论思维的灵魂，定理和证明是它的精髓，公理化方法是最重要的理论思维方法。

实验思维（Experimental Thinking）也称实证思维，是通过观察和实验获取自然规律法则的一种思维方法。它以观察和归纳自然规律为特征，以物理学科为代表。实验思维的先驱是意大利科学家伽利略，他被人们誉为“近代科学之父”。与理论思维不同，实验思维往往需要借助某种特定的设备，使用它们来获取数据以便进行分析。

计算思维（Computational Thinking）也称构造思维，是指从具体的算法设计规范入手，通过算法过程的构造与实施来解决给定问题的一种思维方法，它以设计和构造为特征，以计算机学科为代表。计算思维就是思维过程或功能的计算模拟方法论，其研究的目的是提供适当的方法，使人们能借助现代和将来的计算机，逐步实现人工智能的较高目标。诸如模式识别、决赛、优化和自控等算法都属于计算思维范畴。

一般来说，理论思维对应于理论科学，实验思维对应于实验科学，而计算思维则主要体现在计算科学。计算思维作为人类科学思维的基本方式之一，应属于思维科学的一个专门领域，在现代思维方法学和应用领域中，显示出其越来越重要的地位。

1.1.10 如何培养计算思维能力

计算思维是基于广义“计算”的科学思维，计算思维能力的形成与培养一般离不开“计算”与“计算机”的理解与应用。随着信息化进程的全面推进，“计算机”正变得无处不在、无所不能。如今的计算机系统已经具有非常强大的计算能力，成为更方便的计算工具，“计算”早已超越了早期单纯的科学计算，走过了狭义的数据处理时代，发展到今天无所不在、无所不能的广义“计算”时代。

可以预见，在未来的各种社会、科研活动中，人们必须提升其基本观念和思维方式，必须在更多的时候想到并更有效地利用计算思维方法，才会发挥其更大的作用。这种使用和意识既可以是直接的，即直接使用计算思维的问题求解方法和手段；也可以是间接的，即在各种活动中自觉地采用计算思维的问题求解思想与意识。一般来说，认识与理解计算思维会从下面3个层次考虑。

1.理解计算思维的3个层面

（1）朴素的计算思维

朴素的计算思维可以说是“计算机科学之计算思维”，以面向计算机科学学科人群的研究、开发活动为主，包括了计算思维最基础和最本质的内容。

计算思维起源于计算机科学家们在研究和利用计算机进行问题求解过程中常用的思考问题的方法，在过去半个多世纪以来，从计算机和信息技术辉煌的发展过程中能够看到，涌现出了许多行之有效的分析与解决问题的典型手段与途径，这些都是计算思维的成就体现。

从最初计算机的构建开始，基于对应于高电平和低电平的0、1所构成的呈离散变化的基本状态，计算机表达和进行问题求解需找到一种特有的方式，这使得计算机科学家需要一种相应的思维方式。为了适应问题的计算机求解，需要建立一种不同的思维方式，这种不同表现为以下4个方面：

① 问题需求要用符号表示，求解过程要通过符号（及其值）的变换来实现（Symbolizing）；

② 问题的求解过程是“一步步地”（Step by Step）进行的；

③ 从简单问题求解到复杂问题求解的系统设计与实现，都需要有包括执行逻辑在内的计划和设计（Planning and Designing）；

④ 一般情况下，系统在设计阶段，就需要在设计者的头脑中先“运行”起来（Running in the Mind）。

可以看出，基本问题的计算机求解是建立在高度抽象的基础上。也就是说，数学和电子学是计算机科学非常重要的基础。构建一个恰当的物理符号系统，并对此系统实施变换是计算机科学家进行问题求解的基本手段。计算机问题求解的“可行性”限定了从问题抽象开始到设计和实现的科学实践过程；在可行步骤中，“形式化”后的符号表示及其处理过程的“机械化”和“离散特性”，又确定了计算机进行问题求解的重要特征。数学的形式化描述以及严密的表达和计算，特别是离散数学理论的应用，为计算思维的提供了重要基础和工具。

计算机科学以形式化为描述手段，以抽象思维和逻辑思维为主要思维方式；从表现形式上看，以符号为问题的表现形式，以符号变换作为问题求解途径。这些都体现了计算机“程序”的非物理特征，也揭示了计算思维的根本特征是抽象。

通过抽象可以获得问题及其求解的形式化描述，这是计算思维的基本要求。

① 抽象（Abstraction）是对事物的性质、状态及其变化过程（规律）实行符号化描述。

② 追求符号化为特征的形式化，形成对象及其变换的抽象表示，而系统状态及其有效运行，要求这种形式化具有有穷描述，并要求具有“可计算”的复杂度。

③ 作为抽象的较高境界，使用模型化方法，建立抽象水平较高的适当模型，然后依据抽象模型实现计算机表示和处理。

④ 通过抽象，实现对一类事务问题的系统描述，以保证计算对该类事务问题的有效性，即需要将思维从实例计算推进到类计算。所以，计算机科学的根本问题是什么能被有效地自动计算（Automation）。这些都基于计算机问题表示的数字化和问题求解过程的机械化。

计算机求解问题的基本形式和活动包括：算法、程序、执行、基本机器构建、系统构建、模型计算、类计算、形式化证明、处理过程中各类工具与各层系统的利用，体现为表示的形式化，执行的离散化和程序化。其基本系统涉及过程和算法的描述与实现，要求在构造性上满足有穷描述、确定性和可行性。对于复杂系统，则需要逐层虚拟得到各层（抽象）系统。

我国《高等学校计算机科学与技术专业人才专业能力构成与培养》中给出了计算思维能力的9个能力点：问题的符号表示、问题求解过程的符号表示、逻辑思维、抽象思维、形式化证明、建立模型、实现类计算、实现模型计算和利用计算机技术。其中前8个能力点都属于朴素计算思维。朴素计算思维能力是最基本的，也是培养过程中难度最大的一种计算能力。

（2）狭义的计算思维

狭义的计算思维是指“计算学科之计算思维”，以面向计算机专业人群的生产、生活等活动为主。狭义计算思维基于“计算机”以及以计算机为核心的系统的研究、设计与开发，利用活动中所需要的一种适应计算机自动计算的“思维方式”，使人机的功能在互补中得到大力提升。从这个意义上讲，与计算机相关的很多概念都可以被“计算思维”所涵盖。主要涉及的方面有：

● 最基本的问题描述方法：符号化、模型化；

● 最主要的思维方法——抽象思维、逻辑思维；

● 最基础的实现形式——程序、算法、数据结构、系统实现、操作工具；

● 最典型的问题求解过程——问题、形式化描述、计算机化；

● 最基本的问题求解方法——方法论意义上的核心概念、典型方法。

其中“最基本的问题求解方法”的意思是：按照适应计算机求解问题的基本描述和思维方式来考虑问题（构建计算系统、开发相适应的技术）的描述与求解。狭义的计算思维强调的是“如何使计算机和以计算机为核心的系统具有更强的工作能力，并开发更方便的使用技术”，即在研究、设计、开发、利用4类活动中，以研究、设计为主，开发主要指计算机专业本身所涉及的基本计算机系统、基本应用系统的开发，而利用则仅指专业活动中的利用。

狭义的计算思维除了包括朴素计算思维的内容外，还包括以下主要内容。

① 计算学科方法论意义上的核心概念：抽象层次、概念和形式模型、一致性和完备性、大问题复杂性、效率、折中与决策、绑定、演化、重用、安全性、按空间排序、按时间排序。

② 相关的典型数学方法：强调用数学语言表达事务的状态、关系和过程，经推导形成解释和判断，呈现高度抽象、高精确、具有普遍意义的基本特征。具体方法包括公理化方法、递归、归纳和迭代等构造性方法、模型化等。

③ 相关的典型系统科学方法：其核心是将对象看成一个整体，思维对应于适当抽象级别，力争系统的整体优化。一般原则是整体性、动态、最优化、模型化。具体方法包括结构化方法、OO方法、黑箱方法、功能模拟方法、信息分析方法、自底向上、自顶向下、分治法、模块化、逐步求精等。

狭义计算思维植根于计算学科相应的知识体系，以这些知识为载体，实际应用中会表现为一些更具体的方法，如约简、转化、仿真，递归、归纳、迭代，调度、并行、串行，抽象、建模、分解、归并，规划、分层、虚拟、嵌入，保护、冗余、容错、纠错、系统恢复，启发、学习、进化，可视化、示例等。

（3）广义的计算思维

随着科学学科的交叉与发展，计算机与其他学科形成的新型学科不断涌现。例如，社会计算、计算物理、计算化学、计算生物学等，“计算思维”也随之走出了计算学科。广义的计算思维是指“走出计算学科之计算思维”，是指能适应更大范围的广大人群的研究、生产与生活活动，追求在人脑和电脑的有效结合中取长补短，以获得更强大的问题求解能力。

广义的计算思维强调，能有效地利用计算技术进行问题求解，包括在科学研究与系统实现中能有效地利用计算思维的思想、方法进行问题求解。这里强调的是计算机不仅能作为工具，而且还可以有效地利用与其相适应的意识、思想、方法、技术、环境和资源等。在研究、设计、开发、利用4类活动中，以利用为主，然后依次为开发、设计、研究。特别是对不同专业的人来说，这4 类活动涉及的具体对象是不同的，它们与专业紧密相关，关键是意识、思想、方法、技术、工具、环境、资源等。

广义的计算思维包括狭义的计算思维，狭义的计算思维包括朴素的计算思维，表 1.2 所示为它们之间的包含关系。必须强调，从“朴素”到“广义”，对不同类型的人群，在原有的内容被逐渐淡化的过程中，新内容被添加进来。所以，对计算机类专业以外的人群如何进行计算思维能力的培养，是一个有待深入研究的问题。

2.培养计算思维能力

计算思维是一种思维方法，计算思维能力是指人们运用计算思维方法进行思考的能力，它们是两个不同的概念，常常被人混淆。计算思维能力是面对一个新问题，运用所有资源将其解决的能力。计算思维能力的核心是问题求解的能力，即发现问题、寻求解决问题的思路、分析比较不同的方案、验证方案并解决问题。

一般地，我们不是培养计算思维（方法），而是通过引导人们学习、掌握这种思维方法，有效地将其应用于问题的求解，以达到培养人们的计算思维能力的目的。应该认识到：计算思维能力的培养，不是一朝一夕、一年两年就可以完成的事情，它需要一个长期的过程，而且在这个过程中需要不断研究、不断实践、不断积累、不断提高。

经验告诉人们，任何能力的提升，只依靠“教”是不能实现的，“实践”是最终实现的必经之路。对于计算机专业的学生来说，依托各种专业技术课程，强调思想和方法的实践研习，是快速提高计算思维能力的最佳途径。

对于广大非专业人群（站在使用的角度，不需要考虑计算机内部结构等）来说，应该认识到：符号、程序、算法是计算机技术的基础，是理解和实现计算机问题求解的基础；而系统不同层次的抽象与虚拟，新技术的不断更新，这些属于相对层次高得能力。作为计算思维能力的培养，掌握、理解和了解一些计算学科中最基本的方法是必不可少的；全面而深入地理解与掌握更多的计算学科中的知识，一定会对你所从事的专业有更大的帮助。

当然，无论是哪一部分人，计算思维能力的培养，都需要从建立相应的意识开始。

① 建立“计算”的基本意识。要相信，计算（机）技术可以增强人们的“能力”；使用机械化的方法进行问题求解（抽象描述与思维，离散、机械可执行）有其独特的优势。

② 了解“计算”的基本功能。软件系统、硬件系统、应用系统（含嵌入式系统、网络、物联网等各类计算系统），为人们的生产、生活提供了不同的手段，要了解它们的功能性质，知道它们擅长干什么，不擅长干什么，优势是什么，劣势是什么。

③ 掌握“计算”的基本方法。在计算学科的发展中，有很多有效的问题求解方法，如递归、归纳、折中、重用、嵌入、并行、模块化、自顶向下、自底向上、逐步求精以及问题标志与处理模式等，它们不仅在计算学科中有效，而且在其他学科的问题求解中同样可以被有效地应用。

④ 会用“计算”的基本工具。使用有效的工具能够获得事半功倍的效果。计算学科中，不仅可以使用软硬件工具与系统以及各类语言（汇编、高级语言、命令），而且通过抽象表示，选用和设计有效算法及其思想，通过不同载体上程序的实现，甚至系统集成，也许可以更好地解决问题。

⑤ 具备“计算”的基本能力。结合专业，从意识、思想、方法、技术、工具、环境、资源等多渠道、多途径高效地解决问题。