第3章  计算思维及其作用体现
　　【问题描述】?自计算机诞生以来，还没有哪一项技术像计算机技术如此迅猛地发展，以致改变着人们的工作方式和思维方式，这种思维方式就是计算思维。计算思维本质与计算学科形态虽然呈现的形式不同，但其目标是一致的，其宗旨是寻找通用的方法，处理类似的问题。
　　【知识重点】?主要介绍计算思维的4种表现形式：逻辑思维、算法思维、网络思维、系统思维，它们是计算思维在计算机学科领域中的应用和研究内容，为深入学习和研究提供思路。
　　【教学要求】?通过关联知识，了解计算思维在计算机学科研究中的研究内容；通过习题解析，加深理解计算思维的基本概念；通过知识背景，了解计算思维倡导者和相关科学家的生平事迹。
3.1  关 联 知 识
　　今天，计算机科学不仅为信息产业提供了完整的知识体系和科学工具，而且还提供了一种从信息变换角度有效地定义问题、分析问题和解决问题的思维方式，这就是作为计算机科学主线的计算思维。本节介绍计算思维的4种表现形式：逻辑思维、算法思维、网络思维、系统      思维。
3.1.1  逻辑思维
　　逻辑是研究人类思维规律和思维形式结构的一门学科，因而通常被称作为逻辑学（logic），它是用符号化、公理化、形式化的方法来研究思维规律的科学。逻辑学最初是由古希腊著名的哲学家、科学家和教育家亚里士多德提出来的。
　　逻辑思维（logical thinking）又称为抽象思维（abstract thinking），是人类运用概念、判断、推理等思维方式反映事物本质与规律的认识过程，也是一种普遍的能力和思维方式。
　　1．逻辑思维的基本理论
　　在当代计算机科学中，逻辑思维或计算逻辑思维是指以布尔逻辑和图灵机为基础，精准地对解决问题的计算过程建模，定义并验证求解方法的正确性。逻辑思维的理论基础是数理逻辑、逻辑代数、逻辑电路、逻辑程序设计等。
　　（1）数理逻辑（mathmedical logic）。17世纪中叶德国哲学家、数学家莱布尼茨（Leibniz）给逻辑学引进了一套符号体系，被称为数理逻辑，也称为符号逻辑（symbolic logic）或理论逻辑（theory logic）。数理逻辑是用数学方法建立一套符号体系的方法来研究推理的形式结构和规律的一门学科，包括逻辑演算、集合论、证明论、模型论、递归论等内容。数理逻辑既是逻辑学的一个分支，也是现代数学的一个分支。数理逻辑的特点是语言叙述简单明了、通俗流畅、逻辑性强，从而能对人的思维进行运算和推理。莱布尼茨对逻辑学的贡献是巨大的，被认为是数理逻辑的奠基人。数理逻辑主要包含命题逻辑和谓词逻辑，这两种逻辑构成了数理逻辑的理论基础。
　　（2）逻辑代数（logic algebra）。1847年，英国数学家乔治·布尔（George Boole）建立了称为“代数逻辑”（algebraic logic）的运算法则，即利用“与”（and）、“或”（or）、“非”（not）法则来研究逻辑代数问题，从而初步奠定了逻辑代数的基础。人们为了纪念布尔的突出贡献，故将其称为“布尔逻辑”（Boole logic）。布尔逻辑用3个逻辑变量“与”“或”“非”表示逻辑关系，用两个逻辑值1和0表示逻辑结果的“真”与“假”。
　　（3）逻辑电路（logic circuit）。20世纪30年代，美国学者克劳德·香农将布尔代数引入计算科学领域，并首次提出了可以用电子线路来实现布尔代数表达式。由于布尔代数只有1和0两个值，与电路分析中的“开”和“关”现象完全一致，都只有两种不同的状态，所以可以按布尔代数逻辑变量的“真”或“假”对应开关的闭合或断开。
　　（4）逻辑程序设计（logic programming）。应用计算机求解实际问题时，人们必须用计算机能理解的形式语言告诉它“做什么”或者是“怎么做”，而计算机理解这些语言的过程，正是按照人们赋予它的形式化规程（编译过的程序），将它们规约为自己的基本操作。在进行程序设计时，一个问题的逻辑表达式几乎就是某个程序设计语言（如逻辑程序设计语言Prolog）的一个子程序，而用某个语言编写的程序（如数据库查询语言SQL程序）就是逻辑表达式。这类语言的功能特点是只要告诉它做什么，而不需要告诉它怎么做。
　　【实例3-1】 设计一个判断某一年是否为闰年的程序。
　　【解析】 判断某一年是否为闰年的准则是符合下面两个条件之一：
　　① 年号能被4整除，但不能被100整除，则为闰年。
　　② 年号能被4整除，又能被400整除，则为闰年。
　　整合条件①和条件②，其逻辑表达式为

（年号整除4 and（not（年号整除100）））or（年号整除400）

若逻辑值为真，则为闰年。否则，不是闰年。
　　设年份为year，如果用C语言来表示，判断是否为闰年的逻辑表达式为

（year%400＝＝0）||（（ year%4＝＝0）&&（year%100!＝0））

　　输入year，根据上述逻辑表达式的值，即可得到是否为闰年的结论。
　　随着逻辑代数研究和应用的深入，促进了数理逻辑的发展，符号系统不断完善，逐步奠定了现代数理逻辑的理论基础，使之成为一门独立的学科。同时，也成为人工智能的奠基石。逻辑研究能够提高一个人的理解、分析、评价和构造论证的能力。
　　2．逻辑思维的基本方法
　　“逻辑”通常指人们思考问题，从某些已知条件出发推出合理结论的规律。例如，某人的逻辑性强，就是说他善于推理，能够得出正确的结论。例如评价某人说话“前言不搭后语”，就是说话缺乏逻辑性或逻辑思维能力。那么，如何提高逻辑思维能力呢？实例3-1是利用数学方法实现逻辑问题求解，而现实世界中的许多问题是无法用数学公式来描述和解决的，只能用逻辑思维的思想方法来解决现实世界中的实际问题。逻辑思维的方法很多，熟悉和运用下列方法，对提高我们的逻辑思维能力和逻辑推理能力会有很大的促进作用。
　　（1）归纳与演绎（induction and deduction）是人类认识和辨别事物时非常重要的两种技能。其中，归纳是指从多个个别的事物中获得普遍的规律，例如黑猫、白猫、花猫，可以归纳为“猫”；而演绎则与归纳相反，它是指从普遍性规律推导出个别性规则，例如“猫”可以演绎为黑猫、白猫、花猫等。由此可见，归纳就是从个别到一般，演绎是一般到个别，它反映了人们认识世界事物的一般规律，是科学研究中广泛应用的逻辑思维方法。马克思主义认识论认为，一切科学研究都必须运用到归纳与演绎的逻辑思维方法，例如达尔文通过大量观察、研究一切实验材料，然后进行归纳，得出“生物进化论”。
　　演绎推理的主要形式有“推理三段论”和“结论三段论”。
　　① 推理三段论就是以逻辑推理形式描述推理过程，例如逻辑学中著名的“苏格拉底三段论”。
　　P：所有的人都是要死的；
　　Q；苏格拉底是人；
　　R：苏格拉底是要死的。
　　又例如在人工智能程序中的“三段论”有：
　　◆ 所有A是B，所有B是C，则所有A是C。
　　◆ 所有A是B，所有B不是C，则所有A不是C。
　　◆ 有些A是B，所有B是C，则有些A是C。
　　◆ 有些A是B，所有B不是C，则有些A不是C。
　　② 结论三段论是指在解题过程中，如果具有前提，需要得出结论，则可运用文氏图法来解题。文氏图（Venn diagram）也称为韦恩图（Wayne figure），它是将逻辑关系可视化的图示方法。
　　【实例3-2】 例如计算机专业一班喜欢篮球的有18个学生，喜欢足球的有16个学生，既喜欢篮球又喜欢足球的有4个学生，问该班总共有多少学生。通过文氏图可以很快得到答案，如图3-1所示。
　　【解析】 通过文氏图计算方法，可以得出计算机专业一班为
18－4＋16＝30人
　　（2）分析法（analysis method）是逻辑思维的基本方法，通过把事物进行分解，对事物的各个属性加以研究，是认识事物整体，掌握事物本质和规律的必要阶段。
　　逻辑的研究对象是思维和推理，在逻辑思维中“概念思维”是一切推理的基础，概念是反映对象特有属性或本质属性的思维形式。属性可分为本质属性和非本质属性，是事物所具有的各种性质。事物的本质属性是指对该事物具有决定意义的特有属性，而非本质属性是指对该事物不具有决定意义的其他属性。例如，对于“人”这个概念来说，能思维并能创造和使用工具是其基本属性，是“人”区别于动物的根据所在，至于有脚、能走、有生命等，则属于非本质属性。
　　“概念思维”及其“属性”是逻辑思维分析法中的重要概念。分析法解题的关键是“将条件用尽”，即对问题所给的条件逐个列出，并且分析其中的隐含条件。运用分析法，可以使看上去很复杂的问题变得很简单，它对提高人们缜密的推理有很大的帮助。
　　【实例3-3】 我国古代数学家张丘建在《算经》一书中提出了：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？
　　【解析】 若公鸡每只3元，母鸡每只5元，小鸡每三只1元，求100元买100只鸡有多少种方案，它是穷举算法的典型实例。设公鸡为x，母鸡为y，小鸡为z，可列出其联立方程如下：
　　　x＋y＋z＝100
　　　3x＋5y＋z/3＝100
　　两个方程中有3个变量，因而是不定式求解。虽然两个方程式不可能解出3个确定的未知数，但只要对上述有限集合中1≤x＜33，1≤y＜20，3≤z＜100，z mod 3＝0的x，y，z的各种组合值进行试算，只要结果符合两个表达式的值都为100，就记录有一种方案。
　　对于这类不确定性问题的求解，若利用穷举算法，则可以得出多个答案。这就是“将条件用尽”的含义所在。
　　（3）排除法（exclusive method）是指排除掉不可能的，剩下的总会有正确的。福尔摩斯说过：“当排除了所有其他可能性，还剩一个时，不管有多么地不可能，那都是真相。”所以在面对多项选择时，排除法是快速判断的有效方法。正确运用排除法，往往能收到事半功倍的效果。
　　【实例3-4】 一位幼儿园的老师带着7位小朋友做一个有趣的智力游戏，她让6位小朋友围坐成一圈，让另一位小朋友坐在中央，并拿出7顶帽子，其中4顶白色的，3顶黑色的。老师用眼罩蒙住7位小朋友的眼睛，并将7顶帽子分别戴在7位小朋友的头上，然后揭开围坐在圈上的6名小朋友的眼罩。这时，老师说：现在你们7人猜一猜自己头上戴的帽子的颜色。由于坐在中央的小朋友的遮挡，每个小朋友只能看到5个人的帽子。静思了好一会儿之后，坐在中央的、仍然被蒙住眼睛的小朋友举手说“我猜到了”。那么，这位小朋友是怎样猜到自己头上帽子的颜色的呢？
　　【解析】 对于周围6个小朋友，如果这6人中有人能看到4顶白帽子，那么就能肯定自己戴的是黑帽子；如果能看到3顶黑帽子，便能判断出自己戴的是白帽子。既然这6个人都无法确定出自己所戴的帽子的颜色，那么就可以推测出每一个人和对面的人（被遮住看不到的那个人）帽子颜色不同，所以一圈6人必然是三白三黑，于是位于中央的这位小朋友自己戴的帽子无疑是白色。
　　（4）假设法（hypothesis?method）是作为判断事物真假的一个重要思维方法，具有极其广泛的应用价值。在现实世界中，会常常遇到一些难以决策或难以确定的问题。在此情况下，不妨给出一个假设，然后由该假设列出可能会出现的结果。如果该结果不是我们想要的或所希望的，也就在无形中排除掉了某些可能性。当然，这种假设必须是逻辑性的、合理的。如果假设与真实问题南辕北辙，那么，假设就变得毫无意义了。
　　【实例3-5】 有一对孪生兄弟，他们两人能听懂别人的话但却说不出话来，所以在他们回答别人的问题时，只能用点头或摇头来表示。其中，兄（甲）惯说假话，不说真话；弟（乙）却惯说真话，不说假话。有一天，兄弟两人在一个交叉路口处玩耍，此交叉路口一条通往县城（A），一条通往乡镇（B）。此时对面走来一个外地人，向这兄弟俩询问去县城走哪一条路，这兄弟俩有摇头的，也有点头的，因此使这个问路人不知所云，无所适从。面对这种情况，该如何是好呢？
　　【解析】 面对这种情况，这个问路人只好问其中一个人，看另一个人的反应。问路人只要站在A、B任一条路上，对着兄弟俩其中一个人问：我去县城走哪条路，看另一个人怎么回答。对此，我们会得到如表3-1所示答案。
表3-1  问题答案
被询问者
X
Y
被询问者
X
Y
X为甲（路对）
摇头
点头
X为乙（路对）
摇头
摇头
X为甲（路错）
点头
摇头
X为乙（路错）
点头
点头

　　由表3-1可知，如果两个人答案不一样，说明被问的这个人是甲，那根据另一个的反应去选择就可以了；如果两个人答案一样，则说明被问的人是乙，两个人都摇头，这条路就选对了；如果两个人都点头，这条路就选错了。
　　逻辑思维能力是指遵循逻辑规则进行思考的能力，一个人逻辑思维能力并不是与生俱来的，它需要有一个长期的训练过程，在长期的训练中不断提高。例如，从事数学工作或计算机编程工作的人，其逻辑思维能力通常比从事其他工作的人逻辑思维能力要强。
3.1.2  算法思维
　　假设已经知道一个问题是可计算的，但可能存在许多计算过程去解决该问题，那么如何确定（选择）计算过程呢？算法思维的目的就是找出求解该问题的巧妙计算过程，使得计算时间短、使用的计算资源少，而巧妙的计算过程所体现的方法称为算法，这种求解问题的思维方式称为算法思维（algorithm thinking）。
　　1．算法思维的基本概念
　　算法（algorithm）是指对解题方案准确而完整的描述，是对问题求解的方法步骤的详细陈述。算法代表着用系统的方法描述解决问题的策略机制，人类求解问题的这个策略机制就是算法思维。在当代，人们是借助计算机来求解实际问题的，并且在解决问题过程中至少包含两个步骤：一是发现潜在的算法；二是以程序的方法表示并实现算法。
　　（1）发现算法是指寻找一个快速有效的计算方法，使问题得到圆满解决。事实上，发现问题往往比分析和解决问题更难。算法的发现是一门富有挑战性的艺术，大致可分为如下4个阶段。
　　第一阶段：分析、理解、抽象和归纳问题。
　　第二阶段：寻找一个可能解决问题的算法过程的思路。
　　第三阶段：用数学符号语言对算法步骤加以详细描述。
　　第四阶段：从准确度出发，对算法的复杂度（时间复杂度和空间复杂度）进行评估。
　　（2）算法实现是指将经过分析、抽象、归纳所形成的问题求解算法，用一种类似于计算机指令的形式加以准确描述，然后通过计算机运行，求得问题求解结果。常用的算法描述方法有自然语言、流程图、伪代码、计算机语言等。
　　2. 算法思维的基本策略
　　算法策略（algorithm policy）是指在问题空间中搜索所有可能的解决问题的方法，直至选择一种有效的方法解决问题。其中，算法是面向实现的；策略是面向问题的；问题空间（problem space）是问题解决者对一个问题所达到的全部认识状态，并且一个问题解决者对问题的解决过程就是穿越其问题空间搜索一条通往问题目标状态的路径。
　　用计算机计算或处理的问题可分为数值数据计算、非数值数据处理、数据元素排序等，并且许多问题可以通过多条路径来达到问题求解的目的。在问题解决过程中，算法思维所强调的是解决问题的有效性，并以“构造性”和“自动化”来体现。
　　（1）构造性不仅证明问题“解”的存在（对应数学中的存在性证明），而且要构造出适用于该问题的算法，从而构造出问题的解（对应数学中的构造性证明）。
　　（2）自动化就是计算过程自动化，即算法能够在图灵机或其他计算机上一步接一步地自动执行，直到计算过程完成并给出问题的解，整个过程不需要人工干涉。
3.1.3  网络思维
　　在解决实际问题时，很多计算过程需要将多个部件连接成一个计算系统，如果把这些部件看作一个节点（node），那么一个计算系统就是由多个节点连接而成的网络（network）。如果网络的整体价值大于其节点价值之和，则称为网络效应（network effect）。
　　1．网络思维的核心概念
　　通常把一个网络看作一个硬件系统、软件系统、数据系统、应用服务系统、社会网络系统等。把强调计算过程中的连通性（connectivity）与消息传递（message passing）特征的思维方式称为网络思维（network thinking），并且用名字空间（name space）和网络拓扑（network topology）概念来体现连通性，用协议栈（protocol stack）技术实现消息传递。网络协议、名字空间和拓扑结构是网络思维的3个核心概念。
　　（1）网络协议（network protocol）是确定节点集合以及多个节点之间连接与通信的规则（约定）。作为计算思维的网络体现，协议的一个基本要求是无歧义地、足够精确地描述网络连接与通信的操作系列，并且有助于解决资源冲突、异常处理、故障容错等问题。
　　（2）名字空间（name space）是用于规定网络节点的名字及其合法使用规则，也可包括命名其他客体（如消息、操作等）的规则。
　　（3）拓扑结构（topological structure）是网络中各个站点相互连接的形式，例如局域网中文件服务器、工作站和电缆等的连接形式。拓扑结构分为总线型、星状、环状、树状、混合型等。
　　由此可见，网络思维是名字空间、拓扑结构和协议栈组成的整体思维。在一个实际的网络系统中，一个协议往往不能包含所有规则，而需要几个协议相互配合一起工作，从而构成了协议栈。
　　2．网络思维研究的内容
　　计算机网络是计算机与通信技术的结合体，因而网络思维研究涉及以下4方面的内容。
　　（1）网络路径与联通问题。路径是研究网络图按一定顺序穿越一系列节点的轨迹，若一个图中任意两点间有连通路径，则称此图为连通图。网络的目的就是使信息在不同的节点间      传输。
　　（2）网络流量问题。流量是指单位时间内流经某一路径的流动实体的量，网络流量体现的是网络被频繁使用的程度，是网络研究的重要内容。如果流量问题解决不好，会使网络效率      降低。
　　（3）网络群体行为问题。该问题形如交通高峰期在一个高速公路网络上选择行车路线，因此，所研究的问题形如车辆延迟取决于交通拥塞的情况，它与本车司机和其他司机选择的路线有关。
　　（4）网络的分布与并发问题。这是指在某一时刻在不同的网络节点上有多个用户进行同一业务操作，例如订票操作。其研究的内容是管理系统必须具有允许多个用户同时操作的管理      机制。
3.1.4  系统思维
　　系统思维（system thinking）是指按照系统科学方法论来思考问题，是用系统的观点来认识和处理问题的各种方法的总称。系统思维为现代科学技术的研究带来了革命性的变化，并在社会、经济和科学技术等各个方面得到了广泛应用。例如，当论及计算机时，便自然想到计算机硬件系统和计算机软件系统。当论及数据库时，便自然想到数据库应用系统。由此可见，系统思维已经成为人们良好思维习惯的一部分，并且自然而然地按照系统思维方法分析和解决问题。
　　1．系统思维的基本概念
　　人们在解决大型、复杂的计算、控制、管理等问题时，需要有具体的系统，如仿真系统、导弹系统、信息系统等，而这些系统的核心是计算系统。如何使计算系统高效、可靠地工作，需要从“系统科学”的观点出发,以计算思维分析系统的结构组成，寻找提高系统性能的思想     策略。
　　系统一词来源于英文system的音译，并可分为自然系统与人为系统两大类。自然系统遵循自然的法则，如大气系统、生态系统等；而人为系统则相对较复杂，如卫星系统、社会系统等。
　　迄今为止，虽然没有给出“系统”的确切定义，但从实际系统结构的逻辑思维和抽象角度讲，系统是由若干相互联系、相互作用的要素组成的、具有特定功能的有机整体。这一定义包含了系统的功能、过程、状态、结构、演化、层次等特性。
　　（1）功能特性是指系统所表现出来的，具有并能够提供的特性、功效、作用、能力等。
　　（2）过程特性是指各项功能在系统运行过程中的次序和约束关系，用于反映和处理系统的状态及状态的改变。
　　（3）状态特性是指系统的那些可以观察和识别的形态特征。一般而言，状态表达的是系统的形态特性，功能表达的是系统的静态特性，过程表达的是系统的动态特性。
　　（4）结构特性是指系统内各构件（元素和子系统）之间的相互联系和相互作用的拓扑关系。
　　（5）演化特性是指系统的结构、状态、特征、行为、功能等随时间的推移所发生的变化。
　　（6）层次特性是指系统的功能、过程、构件和结构均可在不同层次上描述和刻画。一般来说，按照层次结构，可把一个系统描述为组件∈模块∈单元∈子系统∈系统。
　　2．系统思维的基本方法
　　系统思维的主要方法有层次思维和模型思维，例如，计算机系统和网络系统，可抽象成3个层次：第一层为用户层；第二层为应用层；第三层为系统层，并且各层中可包含硬件和软件模块。
　　系统科学研究主要采用符号模型而非实物模型，符号模型包括概念模型（concept model）、逻辑模型（logic model）、数学模型（mathematical model）和计算模型（computational model）。
　　3．系统思维的三个利器
　　计算机科学经过多年的发展，在系统特性的基础上，形成并产生了一套完整的系统思维方法。系统思维的基本思想是将现实世界抽象成具有层次结构的系统，再将该系统分解成模块结构，然后组合成为系统，并且无缝执行计算过程。抽象化、模块化、无缝连接这3个过程，被认为是系统思维的三个利器。
　　（1）抽象化（abstraction）是指从多个层次（多个角度或视野）理解一个系统，并且每个层次仅仅考虑有限的、该层次特有的问题，并且用一套精确规定的抽象概念和方法，统一处理该层次所有的计算过程，解决该层的特有问题。抽象化的产物称为抽象，抽象化与抽象都是同一英语单词abstraction，抽象化或抽象具备以下3个性质。
◆	有限性（finiteness）。从多个层次理解一个计算系统，每个抽象仅仅考虑一个层次中有限的特有问题，忽略同一层次中其他问题的细节，其他层次的问题留在其他层次中解决。
◆	精确性（precision）。抽象化的产物是一个计算抽象，是语义精确、格式规范的计算      概念。
◆	通用性（generality）。计算抽象强调用一个抽象代表多个具体需求，即用一套统一的方法处理该层次所有的计算过程，解决该层次的特有问题。这种统一的方法不是只对特定问题有效，而是可以触类旁通，用于其他实例，这种通用性也被称为抽象的泛化（generalization）。
　　抽象化是所有科学技术共有的方法，在计算机学科领域的抽象化主要体现在以下3方面。
　　① 数据抽象（data abstraction）。数据抽象是指将某一类数据及其操作（存储操作、运算操作、通信操作）的抽象。通常针对这些数据抽象的多个操作步骤组合起来才能解决一个问题，例如数据类型（data type）和数据结构（data structure）就是数据抽象的典型实例。
　　② 控制抽象（control abstraction）。控制抽象是指控制多个步骤如何组合起来实现计算过程的操作抽象，它一方面确定某个步骤何时激活，另一方面确定计算过程的实施策略（通过逻辑判断，实行顺序执行、条件跳转、函数调用）。
　　③ 硬件抽象（hardware abstraction）。硬件抽象是指对输入设备、存储设备、输出设备、运算控制设备、存储设备、总线与接口等的抽象。
　　（2）模块化（modularity）是计算机学科中一个极为重要的概念，并且有着极为重要的作       用。它是一种将复杂系统分解为更便于分析、设计、管理的模块化方式，是一种分而治之的思想策略，也是分析和解决复杂问题而采取的一种有效手段。模块化可以理解为一个系统是由多个模块按照一定的规则连接组合而成的，也可以反过来理解为如何将一个系统分解成多个模块的组合。如何将一个大型、复杂系统分解为便于分析、设计、计算的模块（子系统），然后如何将多个模块组合还原成一个完整的系统，是实现模块化所要研究的问题。模块化的目的是便于对复杂系统进行各个击破，以实现整个系统的最优化设计。模块化程序设计、分治算法、有限元方法等，都是源于模块化方法。
　　（3）无缝连接（seamlessness）也称为无缝级联，是指由多个子系统组成的系统中，让计算过程在全系统中流畅地运行，而不出现缝隙和瓶颈。因此在设计一个系统时，应该考虑系统需要什么样的抽象，如何划分子系统和如何组合而成，如何实现无缝连接，这些是实现自动化的基础。
　　可以把在程序执行过程中的就绪状态、执行状态和等待状态看作无缝连接的实例。进程已获得所需资源并被调入内存在等待运行时为就绪状态；进程占有CPU且正在执行的状态为执行状态；由于资源不足或等待某事件为等待状态。三个状态是一个连续转换过程，没有缝隙和瓶颈。
3.2  习 题 解 析
　　本章习题主要考查学生对计算思维相关概念理解和掌握的程度。通过习题解析，进一步加深对计算思维概念的理解，了解计算思维在计算机学科中的作用体现。
3.2.1  选择题
　　1．按照人类思维的基本类型划分，可以分为感性思维、理性思维、抽象思维和（    ）等。
A．形象思维     	B．逻辑思维       	C．科学思维       	D．计算思维
　　【解析】 按照人类思维的基本类型划分，可分为感性思维、理性思维、抽象思维和形象思维等。[参考答案] A
　　2．如果从科学思维的具体手段和求解功能划分，可以分为发散求解、哲理思辨、理论构建和（    ）。
A．科学计算     	B．逻辑解析    	C．问题收敛     	D．创造性思维
　　【解析】 从科学思维的具体手段和求解功能划分，可分为发散求解、哲理思辨、理论构建和逻辑解析。[参考答案] B
　　3．数学建模的基本步骤（过程）主要包括模型描述、模型构想、模型建立和（    ）。
A. 模型抽象   	B. 模型设计      	C. 模型测试      	D. 模型验证
　　【解析】 数学建模的基本步骤（过程）主要包括模型描述、模型构想、模型建立和模型验证?4?个步骤。[参考答案] D
　　4．（    ）不属于人类思维特征。
A. 概括性特征  	B. 间接性特征     	C. 可靠性特征   	D. 能动性特征
　　【解析】 人类思维具有概括性特征、间接性特征和能动性特征。[参考答案] C
　　5．（    ）不属于人类科学思维。
A. 理论思维    	B. 实证思维      	C. 计算思维   	D. 形象思维
　　【解析】 科学思维又可分为理论思维、实证思维和计算思维。[参考答案] D
　　6．（    ）不对应理论思维、实证思维和计算思维。
A. 理论科学   	B. 实验科学      	C. 计算科学     	D. 行为科学
　　【解析】 逻辑思维、实证思维和计算思维分别对应于理论科学、实验科学和计算科学。
[参考答案] D
　　7．利用计算机求解一个问题时，通常是按照（    ）、算法设计、编写程序、程序编译、运行调试等步骤进行的。
A. 提出问题    	B. 分析问题     	C. 解决问题     	D. 总结问题
　　【解析】 利用计算机求解一个问题时，通常是按照分析问题、算法设计、编写程序、程序编译、运行调试等步骤进行的。[参考答案] B
　　8．问题抽象过程通常分为3个层次，不包括（    ）。
A. 计算理论     	B. 信息处理     	C. 硬件系统     	D. 软件系统
　　【解析】 问题抽象过程通常分为计算理论、信息处理和硬件系统3个层次。[参考答案] D
　　9．求解一个具体问题时，算法处理主要涉及3个过程，不包括（    ）。
A. 选择算法    	B. 分析算法      	C. 描述算法      	D. 验证算法
　　【解析】 求解一个具体问题时，算法处理主要涉及选择算法、分析算法和描述算法。[参考答案] D
　　10．人类对自然的认识和理解经历了3个阶段，不包括（    ）。
??A. 经验的       	B. 理论的        	C. 计算的       	D. 学习的
　　【解析】 人类对自然的认识和理解经历了经验的、理论的和计算的3个阶段。[参考答案] D
3.2.2  问答题
　　1. 什么是科学思维？
　　【解析】 科学思维是关于人们在科学探索活动中形成的、符合科学探索活动规律与需要的思维方法及其合理性原则的理论体系。
　　2. 什么是逻辑思维？
　　【解析】 逻辑思维是利用逻辑工具对思维内容进行抽象的思维活动，逻辑思维过程得以形式化、规则化和通用化就是要求创造出与科学相适应的科学逻辑，如形式逻辑、数理逻辑和辩证逻辑等。
　　3. 什么是系统思维？
　　【解析】 系统思维是指考虑到客体联系的普遍性和整体性，认识主体在认识客体的过程中，将客体视为一个相互联系的系统，以系统的观点来考察研究客体，并主要从系统的各个要素之间的联系、系统与环境的相互作用中，综合地考察客体的认识心理过程。
　　4. 什么是创造性思维？
　　【解析】 创造性思维是指在科学研究过程中形成一种不受或较少受传统思维和范式的束缚，超越常规思维、构筑新意、独树一帜、捕捉灵感或相信直觉，以实现科学研究突破的一种思维方式。
　　5. 什么是计算思维？
　　【解析】 计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。
　　6．计算思维的本质是什么？
　　【解析】 计算思维的本质是抽象（abstraction）和自动化（automation），可将其概括为        “两A”。
　　7．按照人类求解问题的过程抽象，通常分为哪几个阶段？ 
　　【解析】 问题求解是一个非常复杂的思维活动过程，就个体对某事物的思维过程而言，可以将其概括为4个阶段：发现问题、明确问题、提出假设、验证假设、问题实施。
　　8. 按照计算机求解问题的过程抽象，通常分为哪几个阶段？
　　【解析】 用计算机实现问题求解的过程是以计算机为工具、利用计算思维解决问题的实践活动，通常可分为问题分析、算法设计、程序编码、程序编译、运行调试等阶段。
　　9. 在计算机科学中，抽象的含义和基本方法是什么？
　　【解析】 抽象是指从具体事物中发现其本质特征和方法的过程。在计算机科学中，抽象的基本方法是发现→提取→命名→表达。
　　10. 计算思维能力的基本含义是什么？计算思维能力培养的核心是什么？
　　【解析】 计算思维能力是指具有按照计算机求解问题的基本方式去考虑问题的求解过程，提出问题的解决方法，构建出相应的算法和程序的能力。计算思维能力培养的核心是“问题求解”能力的培养。
3.3  知 识 背 景
　　计算思维涵盖了计算科学、自动控制、人工智能等领域的一系列思维活动。本节介绍在这些研究领域作出了突出贡献的4位华人（裔）科学家：周以真、钱学森、姚期智、傅京孙。
3.3.1  计算机科学家——周以真
　　周以真（Jeannette M. Wing，1956—，见图3-2），美国计算机科学家，现任哥伦比亚大学数据科学研究院主任及计算机科学教授。
　　周以真1956年12月4日出生，1979年6月在麻省理工学院获得学士和硕士学位，其导师中有图灵奖得主罗纳德·李维斯特（Ronald  Rivest）。1983年，她获麻省理工学院博士学位；1983—1985年，在南加州大学任助理教授；1985年起，任教于卡内基-梅隆大学；2004—2007年，曾担任该校计算机系主任。2006年3月，周以真教授在美国卡内      基-梅隆大学（Carnegie Mellon University，CMU）给出了计算思维的定义：计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等涵盖计算机科学之广度的一系列思维活动。这一定义，揭示了计算思维概念的核心，指出了计算思维的思想观点和方法，从而引发了全世界计算机学界的高度关注和重        视。周以真教授的主要研究领域是形式方法、可信计算、分布式系统、编程语言等。1993年，她与图灵奖得主芭芭拉·利斯科夫合作，提出了著名的Liskov代换原则，是面向对象基本原则之一。
3.3.2  中国导弹之父——钱学森
　　钱学森（Tsien Hsue-shen，1911—2009，见图3-3），世界著名科学家，空气动力学家，中国载人航天奠基人，被誉为“中国航天之父”“中国科学院资深院士”和“中国工程院资深院士”。
　　钱学森在20世纪80年代提出：人机结合能产生“精神生产力”，并指出计算机所能处理的实质上是人脑逻辑思维当中的知性思维。所谓“知性思维”，即为一种能运用普通形式逻辑的思维规则所进行的思维，一种能用确定的、可行的方式描述出来的思维。虽然在20世纪80年代初并没有提出计算思维这个概念，但这个“知性思维”与“计算思维”的概念是不谋而合的。
　　钱学森1911年12月11日出生于上海，祖籍浙江省杭州市临安。他1935年9月进入美国麻省理工学院航空系学习，1936年9月获麻省理工学院航空工程硕士学位，后转入加州理工学院航空系学习，成为世界著名的大科学家冯·卡门（Theodore von  kármán）最受重视的学生。
　　1939年，钱学森获美国加州理工学院航空、数学博士学位。从此，钱学森在美国从事空气动力学、固体力学和火箭、导弹等领域研究，并与导师共同完成高速空气动力学问题研究课题和建立“卡门-钱学森”公式，在28岁时就成为世界知名的空气动力学家，并创立了工程控制论。
　　钱学森1943年任加州理工学院助理教授，1945年任加州理工学院副教授，1947年任麻省理工学院教授，1949年任加州理工学院喷气推进中心主任、教授。
　　1949年，当中华人民共和国宣告诞生的消息传到美国后，钱学森和夫人期盼着能早日回国，为自己的国家效力。此时的美国已掀起麦卡锡主义的反共热潮。钱学森因被怀疑为共产党人和拒绝揭发朋友，突然被美国军事部门吊销了参加机密研究的证书。
　　1950年，钱学森准备回国时，被美国官员拦住，并将其关进监狱，而当时美国海军次长丹尼·金布尔（Dan A. Kimball）声称：钱学森无论走到哪里，都抵得上5 个师的兵力。从此，钱学森受到了美国政府迫害，同时也失去了宝贵的自由。移民局抄了他的家，在特米那岛上将他拘留14天，直到收到加州理工学院送去的1.5万美元巨额保释金后才释放了他。
　　在中国政府的强烈要求下，1955年8月4日，钱学森被允许离开美国，10月8日抵达广州。回国前，钱学森向曾经的老师冯·卡门告别时送给他《工程控制论》，冯·卡门激动地说：“你现在在学术上已超过了我。”回国后，他长期担任火箭、导弹和卫星研制的技术领导职务。1956年初，钱学森向中共中央、国务院提出《建立我国国防航空工业的意见书》。同时，钱学森组建了中国第一个火箭、导弹研究所——国防部第五研究院并担任首任院长。他主持完成了“喷气和火箭技术的建立”规划，参与了近程导弹、中近程导弹和中国第一颗人造地球卫星的研制，直接领导了用中近程导弹运载原子弹“两弹结合”试验，参与制定了中国第一个星际航空的发展规划，发展建立了工程控制论和系统学等。
　　在钱学森的带领下，1964年10月16日中国第一颗原子弹爆炸成功，1967年6月17日中国第一颗氢弹空爆试验成功，1970年4月24日中国第一颗人造卫星发射成功。1985年，钱学森获国家科技进步奖特等奖，1991年被国务院、中央军委授予“国家杰出贡献科学家”荣誉称号和一级英模奖章。1998年，他被聘为解放军总装备部科学技术委员会高级顾问。在中国科学院第九次院士大会和中国工程院第四次院士大会上，他被授予“中国科学院资深院士”和“中国工程院资深院士”称号。1999年，他获中共中央、国务院、中央军委颁发“两弹一星功勋       奖章”。
　　钱学森的著作颇丰，1954年《工程控制论》英文版出版，该书的俄文版、德文版、中文版分别于1956年、1957年、1958年出版。此外，他还编写了《物理力学讲义》《星际航行概论》《论系统工程》等著作。
　　2009年10月31日上午8时6分，中国航天之父——钱学森，在北京逝世，享年98岁。
3.3.3  计算机科学家——姚期智
　　姚期智（Andrew Chi-Chih Yao，1946—，见图3-4），世界著名物理学家，计算机图灵奖获得者。姚期智1946年12月24日出生于中国上海，祖籍湖北省孝感市孝昌县。1967年，他获得台湾大学物理学士学位，之后赴美留学，1972年获得美国哈佛大学物理博士学位，师从格拉肖（Sheldon Lee Glashow，1979年诺贝尔物理学奖得主）。1973年，26岁的姚期智放弃物理学，转而投向计算机科学技术。1975年，他获得美国伊利诺伊大学计算机科学博士学位；同年9月，进入美国麻省理工学院数学系，担任助理教授；1976年9月，进入斯坦福大学计算机系，担任助理教授；1981年8月，进入加州大学伯克利分校计算机系，担任教授；1982年10月，担任斯坦福大学计算机系教授。1986年7月，他在普林斯顿大学计算机科学系担任Wiliam and Edna Macaleer工程与应用科学教授。
　　1993年，姚期智最先提出量子通信复杂性，基本上完成了量子计算机的理论基础。1995年，他提出分布式量子计算模式，后来成为分布式量子算法和量子通信协议安全性的基础，对计算理论包括伪随机数生成、密码学与通信复杂度作出了突出贡献。
　　姚期智在计算机科学领域的研究方向包括计算理论及其在密码学和量子计算中的应用，并且在3个方面具有突出贡献。
　　（1）创建了理论计算机科学的重要次领域：通信复杂性和伪随机数生成计算理论；
　　（2）奠定现代密码学基础，在基于复杂性的密码学和安全形式化方法方面有根本性贡献；
　　（3）解决线路复杂性、计算几何、数据结构及量子计算等领域的开放性问题并建立全新    典范。
　　姚期智1998年被选为美国国家科学院院士，2000年被选为美国科学与艺术学院院士。美国计算机协会（ACM）也把2000年度的图灵奖授予他。
　　2003年10月，姚期智正式加盟清华大学高等研究中心，受聘为清华大学计算机系首席教授；2004年当选为中国科学院外籍院士；2007年3月29日，领导成立清华大学理论计算机科学研究中心。
　　2010年6月，清华大学-麻省理工学院-香港中文大学理论计算机科学研究中心正式成立，姚期智担任主任。2011年1月，他开始担任清华大学交叉信息研究院院长。2017年2月，他放弃外国国籍成为中国公民，正式转为中国科学院院士，加入中国科学院信息技术科学部；11月，加盟中国人工智能企业旷视科技Face++，出任旷视学术委员会首席顾问，推动产学研的本质创新；12月，任清华大学金融科技研究院管委会主任。
3.3.4  模式识别之父——傅京孙
　　傅京孙（King-sun Fu，1930—1985，见图3-5），美籍华裔模式识别与机器智能专家，美国国家工程院院士，台湾“中央研究院”院士。傅京孙为国际知名学者，图形识别科学创始人。与香农、布鲁克斯等人为人工智能领域行为主义学派的代表人物。
　　傅京孙1930年10月2日出生于浙江丽水，1949年去台湾，台湾大学电机系毕业，获加拿大多伦多大学科学硕士、美国伊利诺伊大学博士学位，主修电机及计算机软件专业，后为美国波音公司研究工      程师。
　　傅京孙1961年始任教于普渡大学电机工程系，达23年，历任助教、副教授、教授，1971年被选为美国电机及电子工程学会（IEEE）荣誉会员，1975年任普渡大学高斯工程讲座教授，其间数度赴IBM公司、加州大学伯克利分校IBM华生研究中心、麻省理工学院、斯坦福大学从事研究和教学，结合数学、工程学和计算机知识，创立了“图形识别”学科，以此作为资讯分析与传输的基础依据。
　　傅京孙1976年当选为美国国家工程院院士；同年，获麦考艾科学贡献奖；1977年其图形识别、影像处理及在遥测、医学等方面的应用的论文获美国计算机学会杰出论文奖；1978年被选为台湾“中央研究院”院士。他执教23年间培养了博士生80多人。他多次返台讲学交流，推动资讯科学研究及其应用，曾担任第一届国际图形识别大会总主席，1985年初担任普渡大学（计算机）研究中心主任，1985年4月29日病逝于美国。
　　傅京孙的主要贡献是在模式识别方面，被称为模式识别之父。他是国际模式识别学会（International Society for Pattern Recognition，IAPR）第一任主席，IEEE-CS机器智能与模式识别委员会的第一任主席，《模式分析与机器智能》学报的主编，组织和主持了多次国际学术会      议，曾担任第一届国际图形识别大会总主席。他出版了5本专著和18本编著作品，发表过约400篇论文，是国际智能控制学科（International Intelligent Control Discipline，IICD）的奠基人。在每届国际模式识别大会上，都会颁发一项以中国人命名的奖项——King Sun Fu Prize（傅京孙奖），用于鼓励获奖者在模式识别领域的杰出技术成就。可以说，这一项颁给研究人员的终身成就奖，是模式识别领域的最高荣誉。

　　
- 36 -
计算机科学与计算思维导论学习辅导

- 35 -
第3章?计算思维及其作用体现