第一讲 计算思维概述

1、Computational Thinking,计算不再只和计算机有关，它和我们的生活息息相关。 一、计算改变了什么？ 二、什么是计算？ 三、什么是计算思维？,计算思维引言,一、计算改变了什么,计算改变了科学家的思考方式 计算生物学改变着生物学家的思考方式 数学机械化改变着数学家的思考方式 计算博弈理论改变着经济学家的思考方式 社会计算改变社会学家的思考方式,计算生物学改变着生物学家的思考方式,最典型的案例： 人类的基因工程-耗时10年，耗资数百亿美元。 散弹枪算法提出来后，用于基因测序-耗时几天，耗资千把美元就能测一个基因。 （因为大量的繁杂的工作由计算机完成，大大解放了生物学家，从而改变着生

2、物学家的思考方式）,数学机械化改变着数学家的思考方式,数学机械化，就是刻板化和规格化。-吴方法（吴文俊） 数学问题的机械化，就是要求在运算或证明过程中，每前进一步之后，都有一个确定的、必须选择的下一步，这样沿着一条有规律的、刻板的道路，一直达到结论。,吴文俊-中科院资深院士,吴先生创立了初等几何定理证明的机械化方法，国际上称“吴方法”，首次实现了高效的几何定理的机器证明。,计算博弈理论改变着经济学家思考方式,博弈论指的是研究人与人之间行为互动的一般理论。所谓社会，就是互动。 1943年，冯诺依曼博弈论和经济行为著作首次介绍了博弈论。 博弈论：两人以上参与，双方通过不同策略相互竞争的游戏。 博弈

3、：一方采用的策略会对另一方的行为产生影响。 计算思想在诺贝奖获奖理论中占到70%以上的比例。,社会计算改变社会学家的思考方式,根据社会科学理论，以计算技术为工具，可以： 研究人类社会的组成、关系、结构、层次、行为、运动等问题；研究社会媒体，促进社会人群的交流与合作。,一、计算改变了什么,计算改变了工作方式 数字化会议 数字化医疗 数字化教学 数字化制造,数字化会议,数字化医疗,数字化教学,数字化制造,美国学者尼葛洛庞帝在其 1996年出版的数字化生存一书中提出的，按照他的解释，计算不再只与计算机有关，它决定我们的生存。,13,尼葛洛庞帝 （Negroponte）为美国麻省理工学院教授及媒体实验

4、室的创办人。西方媒体推崇他为电脑和传播科技领域最具影响力的大师之一， 1996年7月被时代周刊列为当代最重要的未来学家之一。,计算改变了世界,二、什么是计算,计算的定义： 计算是指运用事先规定的规则，将一组数值变换为另一(所需的)数值的过程。 对某一类问题，如能找到一组确定的规则，当给出这类问题中的任一具体问题后，按规则可以完全机械地在有限步内求出结果，则说这类问题是可计算的。这种规则就是算法。,猜数游戏：有自然数1-1000，随机选取其中的一个数，请大家猜数。 回答10次是与否，就可以猜出该数字。,二分查找法,3.计算思维的特征,计算工具与思维方式的相互影响 家迪科斯彻：我们使用的工具影响着

5、我们的思维方式和思维习惯，从而也将深刻地影响着我们的思维能力。 计算思维是各个专业求解问题的基本途径。,3. 计算思维的特征,计算思维的定义 “计算思维”是美国卡内基梅隆大学周以真教授提出的一种理论。 周以真认为：计算思维是运用计算机科学的基础概念去求解问题、设计系统和理解人类行为，它涵盖了计算机科学的一系列思维活动。,周以真（英文名Jeannette M. Wing，），美国计算机科学家。卡内基-梅隆大学教授。美国国家自然基金会计算与信息科学工程部助理部长。ACM和IEEE会士。,问题求解中的计算思维,有一座城市需要铺路，不仅每栋房子都能沿着铺好的道路到达其他所有的房子，而且用的石砖最少。

6、设有三栋房子和三条路，哪些路是必须要铺上石砖的？,铺路问题,如果是5栋房子？,1,2,3,4,5,B,3,C,3,E,1,D,3,A,1,2,2,警察抓小偷,警察局抓了a，b，c，d四名偷窃嫌疑犯，其中只有一人是小偷，审讯记录如下： A说：我不是小偷 B说：c是小偷 C说：小偷肯定是d D说：c在冤枉人 四个人中，三个人说的是真话，一个人说的是假话，请问谁是小偷？,问题分析,数学建模,计算,编程实现,For x=1 to 4 If (x1+(x=3)+(x=4)+(x4)=3) then Print x Next x,百元买白鸡,公鸡每只5元，母鸡每只3元，小鸡一元3只，一百元买一百只鸡，问有

7、几种买法？,问题分析： X+Y+Z=100 5X+3Y+Z/3=100,编程,计算思维能够反映人类思维活动，高效执行。,For x=1 to 100 For y=1 to 100 Z=100-x-y If 5*x+3*y+z/3=100 then Print x,y,z End if Next for Next for,计算机解题方法,计算机解决问题步骤： 理解问题，寻找解决问题的条件； 从问题抽象出适当的数学模型，然后设计解决这个数学模型的算法； 按照算法编写程序，并调试、测试、运行程序，得到最终解答。,系统设计中的计算思维,将系统中的变换过程映射为符号变换形式化，然后就可以用计算机进行处理

8、。,重要理论,计算思维的本质： 抽象、自动化（程序、算法） 计算思维能力： 建立起利用计算机技术解决问题的思路，并理解问题的可求解性。 问题抽象、模型建立、算法设计、实现,囚徒困境博弈策略建模,囚徒困境问题描述 警方逮捕了A、B两名嫌疑犯，但没有足够证据指控二人有罪。于是警方分开囚禁嫌疑犯，并向双方提供以下相同的选择（如表所示）： （1）如果一人认罪并检控对方（背叛），而对方保持沉默，则此人将获释，沉默者将判监禁10年。 （2）如果二人都保持沉默（合作），则二人同样判监1年。 （3）如果二人都互相检举（背叛），则二人同样判监8年。,囚徒困境博弈策略建模,囚徒的策略选择困境 两名囚徒的选择： （

9、1）若对方沉默，背叛会让我获释，所以我会选择背叛。 （2）若对方背叛我，我也要指控对方才能得到较低刑期，所以选择背叛。 结果：两人都选择背叛，结果二人服刑8年。,如果两个囚徒合作保持沉默，总体利益会更高。 而两个囚徒追求个人利益，选择背叛时，总体利益较低。 这就是困境所在。,囚徒困境博弈策略建模,囚徒困境的数学建模 （1）策略的符号化 将囚徒各种选择获得的收益和支付转换为数值，获得表所示符号表。,囚徒困境博弈策略建模,（2）建立收益和支付矩阵 根据以下规则确定博弈双方的收益和支付： 一人背叛，一人合作时，背叛者得5分（背叛收益），合作者得0分（受骗支付）； 二人都合作时，双方各得3分（合作报酬

10、）； 二人都背叛时，各得1分（背叛惩罚）。 从表可见：5310，得出：TRPS。,囚徒困境博弈策略建模,（3）建立数学模型 A=R，B=R时，A=3，B=3； A=T，B=S时，A=5，B=0； A=S，B=T时，A=0，B=5； A=P，B=P时，A=1，B=1。,囚徒困境博弈策略建模,【案例】生活中的“囚徒困境”现象。 幼儿园小朋友互相分享玩具（给他玩，不给他玩）； 夫妻双方对家庭的态度（忠诚，背叛）； 公共卫生的维持（不扔垃圾，乱扔垃圾）； 老板与下属的关系（信任，不信任）； 商场上的君子协定（不违约，违约）； 竞争对手的价格战（不降价，降价）； 国家之间的对抗（和平，战争）等。 虽然括

11、号内的前者选择是大家想要达到的目标，但自私的结果往往是大家要接受后者。,囚徒困境博弈策略建模,石头剪刀布游戏的博弈模型 石头剪刀布是一种相互制约的多元博弈游戏，它是最平衡的游戏。 石头剪刀布不具备数学上的传递性（ab，bc时，则ac）。 石头剪刀布游戏规则绝对平衡，简单明了，没有任何规则漏洞。 游戏过程充满了“心理博弈”，单次输赢取决于运气，多次比赛的话，赢家一定是个心理博弈的高手。 对石头剪刀布游戏建立数学模型。如表3-4所示。,囚徒困境博弈策略建模,【案例】田忌赛马的博弈。,人类行为理解中的计算思维,计算思维不仅能够反映人类思维活动，还能够通过计算手段来研究人类的行为。,医学中的计算思维,

12、计算思维,1）多脏器衰竭 2）心血管和脑血管同时梗塞 3）复杂疑难症的治疗方案的总体设计,计算思维（构造思维）的培养，将有助于临床医生提出“整体构架设计解决方案”的治疗方案。,计算思维的特性,1,概念化，不是程序化。,计算机科学不是计算机编程。像计算机科学家那样去思维意味着远远不止能为计算机编程。它要求能够在抽象的多个层次上思维。,计算思维的特性,2,基础的，不是机械的技能。,基础的技能是每一个人为了在现代社会中发挥职能所必须掌握的。生搬硬套之机械的技能意味着机械的重复。,计算思维的特性,3,人的，不是计算机的思维。,计算思维是人类求解问题的一条途径，人类聪颖且富有想象力，人类赋予计算机以激情。配置了计算设备，就能用自己的智慧去解决那些计算时代之前不敢尝试的问题。,计算思维的特性,4,数学和工程思维的互补与融合。,计算机科学在本质上源自数学思维，构建虚拟世界的自由使我们能够超越物理世界去打造各种系统。,计算思维的特性,5,是思想，不是人造品。,不只是我们生产的软件、硬件等人造品将以物理形式到处呈