计算思维导论

第1章引论本章要点：1.什么是计算；2.计算机科学与计算科学的区别；3.来自计算机发展史的启示；4.计算机应用；5.计算机发展趋势。

1.1 什么是计算？简单计算，如我们从幼儿就开始学习和训练的算术运算，如“3 + 2 = 5”“3 2 = 6”等，是指“数据”在“运算符”的操作下，按“规则”进行的数据变换。

我们不断学习和训练的是各种运算符的“规则”及其组合应用，目的是通过计算得到正确的结果。

广义地讲，一个函数如“”把x变成了f(x)就可认为是一次计算，在高中及大学阶段我们不断学习各种计算“规则”并应用这些规则来求解各种问题，得到正确的计算结果。

如对数与指数、微分与积分等。

“规则”可以学习与掌握，但应用“规则”进行计算则可能超出了人的计算能力，即人知道规则但却没有办法得到计算结果。

如何解决呢？一种办法是研究复杂计算的各种简化的等效计算方法(数学)使人可以计算，另一种办法是设计一些简单的规则，让机械来重复的执行完成计算，即考虑能否用机械来代替人按照“规则”自动计算。

例如：能否机械地判断方程“a1x1b1+a2x2b2+…+a n x n b n = c”是否有整数解?”，即机械地证明一个命题是否有解? 是否正确?类似的上述问题，促进了计算机科学和计算科学的诞生和发展，促进了人们思考：◆什么能够被有效地自动计算？现实世界需要计算的问题是很多的，哪些问题是可以自动计算的，哪些问题是可以在有限时间有限空间内自动计算的？这就出现了计算及计算复杂性问题。

以现实世界的各种思维模式为启发，寻找求解复杂问题的有效规则，就出现了算法及算法设计与分析问题。

例如观察人的思维模式而提出的遗传算法、观察蚂蚁行动的规律而提出的蚁群算法等。

◆如何低成本、高效地实现自动计算？如何构建一个高效的计算系统：计算机器的构建问题和软件系统的构建问题。

◆如何方便有效地利用计算系统进行计算？利用已有计算系统，面向各行各业的计算问题求解。

什么能、且如何被有效地自动计算问题就是计算学科的科学家不断在研究和解决的问题。

2 大学计算机-计算思维导论1.2 计算机科学与计算科学一般而言，“计算机科学”是研究计算机和可计算系统的理论方面的学科[1]，包括软件、硬件等计算系统的设计和建造，发现并提出新的问题求解策略、新的问题求解算法，在硬件、软件、互联网方面发现并设计使用计算机的新方式和新方法等。

简单而言，计算机科学围绕着“构造各种计算机器”和“应用各种计算机器”进行研究。

当前，计算手段已发展为与理论手段和实验手段并存的科学研究的第三种手段[2]。

理论手段是指以数学学科为代表，以推理和演绎为特征的手段，科学家通过构建分析模型和理论推导进行规律预测和发现。

实验手段是指以物理学科为代表，以实验、观察和总结为特征的手段，科学家通过直接的观察获取数据，对数据进行分析进行规律的发现。

计算手段则是以计算机学科为代表，以设计和构造为特征的手段，科学家通过建立仿真的分析模型和有效的算法，利用计算工具来进行规律预测和发现。

技术进步已经使得现实世界的各种事物都可感知可度量，进而形成数量庞大的数据或数据群，使得基于庞大数据形成仿真系统成为可能，因此依靠计算手段发现和预测规律成为不同学科的科学家进行研究的重要手段。

例如生物学家利用计算手段研究生命体的特性，化学家利用计算手段研究化学反应的机理，建筑学家利用计算手段来研究建筑结构的抗震性，经济学家社会学家利用计算手段研究社会群体网络的各种特性等。

由此计算手段与各学科结合形成了所谓的计算科学，如计算物理学、计算化学、计算生物学、计算经济学等。

著名的计算机科学家、1972年图灵奖得主Edsger Dijkstra[3]说：“我们所使用的工具影响着我们的思维方式和思维习惯，从而也将深刻地影响着我们的思维能力”。

各学科人员在利用计算手段进行创新研究的同时，也在不断地研究新型的计算手段。

这种结合不同专业的新型计算手段的研究需要专业知识与计算思维的结合，1998年John Pople便因成功地研究出量子化学综合软件包Gaussian[4]而获得诺贝尔奖，Gaussian已成为研究化学领域许多课题的重要的计算手段。

另一个典型的计算手段如求解应力或疲劳等结构力学、多物理场耦合的有限元分析手段。

以电影《阿凡达》为代表的影视创作平台也在不断利用先进的计算手段(如捕捉虚拟合成扣像手段)创造意想不到的视觉效果。

周以真(Jeannette M. Wing)教授指出计算思维(Computational Thinking)是运用计算机科学的基础概念去求解问题、设计系统和理解人类行为的一系列思维活动的统称[5]。

它是如同所有人都具备“读、写、算”能力一样，都必须具备的思维能力，计算思维建立在计算过程的能力和限制之上，由人由机器执行。

因此，理解“计算机”的思维，即理解计算系统是如何工作的? 计算系统的功能是如何越来越强大的，以及利用计算机的思维，即理解现实世界的各种事物如何利用计算系统来进行控制和处理，理解计算系统的一些核心概念，培养一些计算思维模式，对于所有学科的人员建立复合型的知识结构，进行各种新型计算手段研究以及基于新型计算手段的学科创新都有重要的意义。

技术与知识是创新的支撑，然而思维是创新的源头。

第1 章引论 3 1.3 来自计算机发展史的启示历史的回顾，不只是要记住历史事件及历史人物，而是要观察技术的发展路线，观察其带给我们的思想性的启示，这对于创新及创新性思维培养是非常有用的！1.3.1 来自计算工具发展的启示一般而言，计算与自动计算要解决以下四个问题：(1)【数据】的表示；(2)数据的【存储】及自动存储；(3) 【计算规则】的表示和(4) 【计算规则执行】及自动执行。

图1.1 计算工具的发展与演变我们首先看算盘。

算盘上的珠子可以表示和【存储】数，【计算规则】是一套口诀，按照口诀拨动珠子可以进行四则运算。

然而所有的操作都要靠人的大脑和手完成，因此算盘被认为是一种计算辅助工具，不能被归入自动计算工具范畴。

若要进行自动计算，需要由机器来自动执行规则、自动存储和获取数据。

1642年法国科学家帕斯卡(Blaise Pascal, 1623～1662)发明了著名的帕斯卡机械计算机，首次确立了计算机器的概念。

该机器用齿轮来表示与【存储】十进制各个数位上的【数字】，通过齿轮的比来解决进位问题。

低位的齿轮每转动10圈，高位上的齿轮只转动1圈。

机器可【自动执行】一些【计算规则】，“数”在计算过程中自动存储。

德国数学家莱布尼茨(Gottfried Wilhelm Leibniz, 1646～1716)随后对此进行了改进，设计了“步进轮”实现了计算规则的自动4 大学计算机-计算思维导论连续重复的执行。

帕斯卡机的意义：它告诉人们“用纯机械装置可代替人的思维和记忆”，开辟了自动计算的道路。

1822年，30岁的巴贝奇(C. Babbage)受前人杰卡德(J.Jacquard)编织机的启迪，花费10年的时间，设计并制作出了差分机。

这台差分机能够按照设计者的旨意，自动处理不同函数的计算过程。

1834年，巴贝奇设计出具有堆栈、运算器、控制器的分析机，英国著名诗人拜伦的独生女阿达.奥古斯塔(Ada Augusta)为分析机编制了人类历史上第一批程序，即一套可预先变化的有限有序的【计算规则】。

巴贝奇用了50年时间不断研究如何制造差分机，但限于当时科技发展水平，其第二个差分机和分析机均未能制造出来。

在巴贝奇去世70多年之后，Mark Ⅰ在IBM 的实验室制作成功，巴贝奇的夙愿才得以实现。

巴贝奇用一生进行科学探索和研究，这种精神永远地流传了下来。

正是由于前人对机械计算机的不断探索与研究，不断追求计算的机械化、自动化、智能化：如何能够自动存取数据？如何能够让机器识别可变化的计算规则并按照规则执行？如何能够让机器像人一样地思考？这些问题促进了机械技术和电子技术的结合，最终导致了现代计算机的出现。

现代计算机，在借鉴了前人的机械化自动化思想后，设计了能够理解和执行任意复杂程序的机器，可以进行任意形式的计算，如数学计算、逻辑推理、图形图像变换、数理统计、人工智能与问题求解等，计算机的能力在不断提高之中。

1.3.2 来自元器件发展的启示自动计算要解决数据的自动存、自动取以及随规则自动变化的问题，如何找到能够满足这种特性的元器件便成为电子时代研究者不断追求的目标。

第1 章引论 5图1.2 元器件的发展与演变1883年，爱迪生在为电灯泡寻找最佳灯丝材料的时候，发现了一个奇怪的现象：在真空电灯泡内部碳丝附近安装一截铜丝，结果在碳丝和铜板之间产生了微弱的电流。

1895年，英国的电器工程师弗莱明(J. Fleming)博士对这个“爱迪生效应”进行了深入的研究，最终发明了人类第一只电子管(真空二极管)：一种使电子单向流动的元器件。

1907年，美国人德福雷斯发明了真空三极管，他的这一发明为他赢得“无线电之父”的称号。

其实，德福雷斯所做的就是在二极管的灯丝和板极之间加了一块栅板，使电子流动可以受到控制，从而使电子管进入到普及和应用阶段。

电子管是可存储和控制二进制数的电子元器件。

在随后几十年中，人们开始用电子管制作自动计算的机器。

标志性的成果是1946年宾夕法尼亚大学的ENIAC，ENIAC[6]是世界上公认的第一台电子计算机。

ENIAC的成功奠定了“二进制”“电子技术”作为计算机核心技术的地位。

然而电子管有很多缺陷，比如体积庞大、可靠性低、功耗大等等，对于如何克服这些问题的思考促使了人们寻找性能比电子管更加优秀的替代品。

1947年，贝尔实验室的肖克莱和巴丁、布拉顿发明了点接触晶体管，两年后肖克莱进一步发明了可以批量生产的结型晶体管（1956年他们三人因为发明晶体管共同获得了诺贝尔奖），1954年德州仪器公司的迪尔发明了制造硅晶体管的方法。

1955年之后，制造晶体管的成本以每年30%的速度下降，到50年代末，这种廉价的器件已经风靡世界，以晶体管为主要器件的计算机也迈入了新的时代。

尽管晶体管代替电子管有很多优点，但还是需要使用电线将各个元件逐个连接起来，对于电路设计人员来说，能够用电线连接起来的单个电子元件的数量不能超过一定的限度。

而当时一台计算机可能就需要25000个晶体管、10万个二极管、成千上万个电阻和电容，6 大学计算机-计算思维导论其错综复杂的结构使其可靠性大为降低。

如何解决呢?1958年，费尔柴尔德半导体公司的诺伊斯和德州仪器公司的基尔比提出了集成电路的构想：在一层保护性的氧化硅薄片下面，用同一种材料（硅）制造晶体管、二极管、电阻、电容，再采用氧化硅绝缘层的平面渗透技术，以及将细小的金属线直接蚀刻在这些薄片表面上的方法把这些元件互相连接起来，这样几千个元件就可以紧密地排列在一小块薄片上。