1.3 计算思维概述

1.3.1 计算思维的概念

2006年3月,时任美国卡内基-梅隆大学计算机科学系主任的周以真(Jeannette M.Wing)教授,在美国计算机权威期刊Communications of the ACM上给出了计算思维(computational thinking)的概念。周以真教授认为,计算思维是运用计算机科学的基础概念进行问题求解、系统设计,以及理解人类行为等涵盖计算机科学广度的一系列思维活动。更进一步,周以真对计算思维的概念做了如下阐释:“计算思维就是把一个看起来困难的问题重新阐述成一个人们知道怎样解决的问题,如通过约简、嵌入、转化和仿真的方法。”

国际教育技术协会(ISTE)和计算机科学教师协会(CSTA)在2011年给计算思维下了一个可操作性的定义,即计算思维是一个问题求解的过程,该过程包括以下特点:

●拟定问题,并能够利用计算机和其他工具的帮助来解决问题。

●要符合逻辑地组织和分析数据。

●通过抽象(如模型、仿真等)再现数据。

●通过算法思想(一系列有序的步骤),支持自动化的解决方案。

●分析可能的方案,找到最有效的方案,并且有效地应用这些方案和资源。

●推广该问题的求解过程,并移植到更广泛的问题中。

1.3.2 计算思维的本质

计算思维的本质是抽象(abstract)和自动化(automation)。它反映了计算的根本问题,即什么能被有效地自动执行。从操作层面上讲,计算思维就是要确定合适的抽象,并选择合适的计算方法和计算工具去解释和执行该抽象。

计算工具利用某种方法求解问题的过程是自动执行的,即计算思维的自动化特征。计算思维建立在计算工具的能力和限制之上,由人控制机器自动执行。程序自动执行的特性使原本无法由人类完成的问题求解和系统设计成为可能。

抽象的概念在计算思维中非常重要,对计算思维中的抽象有如下解释。

抽象是指对事物的性质、状态及其变化过程(规律)进行符号化描述。与数学相比,计算思维中的抽象显得更为丰富,也更为复杂。数学抽象的特点是抛开现实事物的物理、化学和生物等特性,仅保留其量的关系和空间的形式。例如,将应用题“原来有五个苹果,吃掉两个后还剩下几个?”抽象表示成“5-2”。而计算思维中的抽象却不仅仅如此。计算思维利用启发式推理来寻求解答,就是在不确定情况下的规划、学习和调度。它的计算结果可能是一系列的网页,一个赢得游戏的策略,或者一个反例。计算思维的数据类型也比较复杂,譬如,堆栈是计算机学科中常见的一种抽象数据类型,这种数据类型的基本操作是入栈、出栈等,而不是简单的加减法。算法也是一种抽象,但不能将两个算法简单地放在一起去实现并行算法。另外,数学抽象通常要解决一个具体的问题。而计算思维是通过抽象实现对一类问题的系统描述,以保证计算对该类问题的有效性,即需要将思维从实例计算推演到类的普适计算。

计算思维的抽象有不同的层次,即人们可以根据不同的抽象层次,进而有选择地忽视某些细节,控制系统的复杂性。这样,研究对象及其变换的抽象表示使问题具有可计算的复杂度。计算思维中的抽象最终要能够一步一步机械地自动执行,为了确保机械的自动化,就需要在抽象过程中进行精确和严格的符号标记和建模,同时也要求计算机系统或软件系统生产厂家能够向用户提供各种不同抽象层次之间的翻译工具。作为抽象的较高层次,可以使用模型化方法,建立抽象水平较高的模型,然后依据抽象模型实现计算机表示和处理。

下面通过三个计算思维示例了解计算思维的本质。

1.七桥问题

哥尼斯堡城地处东普鲁士,位于普雷格尔河的两岸及河中心的两个岛上,城市各部分由七座桥与两岸连接起来。多年来,当地居民总有一个愿望:从家里出去散步,能否通过每座桥恰好一次,再返回家中?但是任何人也没有找到这样一条理想的路径。

1736年,瑞士数学家欧拉(见图1-2)对此问题进行了研究,他把陆地抽象为一个点,用连接两个点的线段表示桥梁,将该问题抽象成点、线连接的数学问题(见图1-3),并给出结论:人们的愿望无法实现。同时,他发表了“一笔画定理”:一个图形要能一笔画完成必须符合两个条件,即图形是封闭连通的和图形中的奇点(与奇数条边相连的点)个数为0或2。欧拉的研究开创了数学上的新分支——拓扑学。很显然,七桥问题的解决过程体现了计算思维的抽象本质。

图1-2 莱昂哈德·欧拉(Leonhard Euler)

图1-3 七桥问题与一笔画

2.取咖啡问题

在咖啡店,物品的摆放如图1-4所示,从左至右分别是杯盖、杯子、咖啡、糖、牛奶、咖啡壶。现在,想取一杯咖啡,行动轨迹应该是:先取杯子,然后加入咖啡、糖、牛奶、水,再返回来盖上杯盖。但这条路径很低效,需要折返取杯盖。如何提高效率呢?很显然,可以将杯盖放到水壶的右侧,构成流水线。这似乎不太符合逻辑,但从工程的角度来说,将杯盖放到水壶的右侧是最高效的方法。很显然,这体现了计算思维的自动化本质。

图1-4 取咖啡问题

3.求 n 的阶乘

任何大于等于1的自然数n的阶乘表示方法可以有两种:

第一种:

第二种:

可以看出,在不同的思维下,阶乘有不同的解题(抽象)方式。不同的抽象方法和自动求解思路表明计算思维的灵活性和多样性。

1.3.3 计算思维的特征

计算思维是人类科学思维中以抽象和自动化,或者说以形式化、程序化和机械化为特征的思维形式。

1.计算思维是人的思维,而非机器的思维

计算思维是人类求解问题的一条途径,是人的思维,而非机器的思维。AlphaGo战胜了多名围棋大师,并不是机器具有思维,而是人类赋予了机器“人的思维”,从而实现了“只有想不到,没有做不到”的境界。所以,计算思维的重点是如何用计算机帮助人类解决问题,而非要像计算机那样枯燥地思考问题。

2.计算思维是能力,而非技能

计算思维是分析并解决问题的能力,而非刻板的操作技能,因此重点是培养分析问题和解决问题的能力,而不是学习某一个软件的使用。

3.计算思维是概念化的思考方式,而非程序化的

计算机科学不是计算机编程。像计算机科学家那样去思维意味着不仅要进行计算机编程,还要在抽象的多个层次上思考。所以,计算思维的重点是算法设计,即解决问题的方法和步骤,而不涉及具体的编程。

4.计算思维是一种思想,而非人造品

目前,软件、硬件等人造物以物理形式呈现在我们周围,并时时刻刻影响我们的生活。但计算思维体现的是我们用以解决问题、管理日常生活、与他人交流和互动的一种与计算有关的思想。当计算思维真正融入人类活动的整体,不再表现为一种显式哲学的时候,就成为人类一种特有的思想。

1.3.4 身边的计算思维

计算思维可以被看作一种高效解决问题的思考方式。人们在日常生活中的很多做法其实都和计算思维不谋而合,也可以说计算思维从生活中吸收了很多有用的思想和方法。下面举例介绍生活中的计算思维。

最短路径问题:如果你是邮递员,会怎样投递物品呢?通常邮递员不会盲目地挨家挨户去投递,更不会随意投递,一般会规划好自己的投递路线,按照最短路径进行优化。

分类:如果要在一堆文件中找一份重要资料,应该怎么做?一般不会随机拿一份,找不到放回,再随机拿一份找,更不会一份文件一份文件地找。通常会把文件按照内容先分类,然后再在与资料相关的文件类中找。

背包问题:用卡车运送物品到外地,能带走的物品有4种,每种物品重量不同,价值不同,由于卡车能运送的重量有限,不能把所有的物品运走,如何处理才能让卡车运走的物品价值最高?可以把所有物品的组合列出来,如果该组合卡车能装下,并且价值最高,就选择这种物品运送方案。

查找:如果要在英汉词典中查找一个英文单词,读者不会从第一页开始逐页翻看,而是会根据字典是有序排列的事实,快速地定位单词词条。

回溯:人们在路上遗失了东西之后,会沿原路边往回走边寻找。或者在一个岔路口,人们会选择沿一条路走下去,如果最后发现此路不通就会原路返回,到岔路口选择另外一条路继续寻找。

缓冲:假如将学生用的教科书视为数据,将上课视为对数据的处理,那么学生的书包就可以被视为缓冲存储。学生随身携带所有的教科书是不可能的,因此每天只能把当天要用的教科书放入书包,第二天再换入新的教科书。

并发:比如要完成三门功课的作业,在写作业的时候,可以交替完成,即写A作业,累了的时候就换B作业或C作业。从宏观上看,A、B、C作业是并发完成的,即一天“同时”完成了三门功课的作业,从微观上看,在同一时间点上,A、B、C作业又是各自独立地交替完成的。

博弈:经济学上有个“海盗分金”模型,5个海盗抢得100枚金币,他们按抽签的顺序依次提出方案,首先由1号提出分配方案,然后5人投票表决,超过半数同意方案才被通过,否则提出方案的人将被扔入大海喂鲨鱼,依此类推。在“海盗分金”模型中,“分配者”想让自己的方案获得通过的关键是事先考虑清楚“挑战者”的分配方案是什么,并用最小代价获取最大收益,拉拢“挑战者”分配方案中最不得意的人。“海盗分金”其实是一个高度简化和抽象的模型,体现了博弈的思想。

上述例子都涉及计算思维的应用。同样,在利用计算机解决问题的时候,应用计算思维的方法去设计求解,会提高问题求解的质量与效率。