第一讲-计算思维概述PPT演示课件.pptx
计算思维计算机教研室周旭Computational Thinking1 计算不再只和计算机有关，它和我们的生计算不再只和计算机有关，它和我们的生活息息相关。活息息相关。一、计算改变了什么？一、计算改变了什么？二、什么是计算？二、什么是计算？三、什么是计算思维？三、什么是计算思维？计算思维引言计算思维引言2 一、计算改变了什么一、计算改变了什么1 1计算改变了科学家的思考方式计算改变了科学家的思考方式计算生物学改变计算生物学改变着着生物学家的思考方式生物学家的思考方式数学机械化数学机械化改变着改变着数学家数学家的思考方式的思考方式计算博弈理论改变着经济学家的思考方式计算博弈理论改变着经济学家的思考方式社会计算改变社会学家的思考方式社会计算改变社会学家的思考方式3 计算生物学改变计算生物学改变着着生物学家的思考方式生物学家的思考方式最典型的案例：最典型的案例：人类的基因工程人类的基因工程-耗时耗时1010年，耗资数百亿美元。年，耗资数百亿美元。散弹枪算法提出来后，用于基因测序散弹枪算法提出来后，用于基因测序-耗时几天，耗耗时几天，耗资千把美元就能测一个基因。资千把美元就能测一个基因。（因为大量的繁杂的工作由计算机完成，大大解放了生（因为大量的繁杂的工作由计算机完成，大大解放了生物学家，从而改变着生物学家的思考方式）物学家，从而改变着生物学家的思考方式）4 数学机械化数学机械化改变着改变着数学家数学家的思考方式的思考方式数学机械化，就是刻板化和规格化。数学机械化，就是刻板化和规格化。-吴方法（吴文俊）吴方法（吴文俊）数学问题的机械化，就是要求在运算或证明过程中，每数学问题的机械化，就是要求在运算或证明过程中，每前进一步之后，都有一个确定的、必须选择的下一步，前进一步之后，都有一个确定的、必须选择的下一步，这样沿着一条有规律的、刻板的道路，一直达到结论。这样沿着一条有规律的、刻板的道路，一直达到结论。吴文俊吴文俊-中科院资深院士中科院资深院士吴先生吴先生创立了初等几立了初等几何定理何定理证明的机械化明的机械化方法，国方法，国际上称上称“吴吴方法方法”，首次，首次实现了了高效的几何定理的机高效的几何定理的机器器证明。明。5 计算博弈理论改变着经济学家计算博弈理论改变着经济学家思考方式思考方式u博弈论博弈论指的是研究人与人之间行为互动的一般理论。指的是研究人与人之间行为互动的一般理论。所谓社会，就是互动。所谓社会，就是互动。u19431943年，冯年，冯诺依曼诺依曼博弈论和经济行为博弈论和经济行为著作首次著作首次介绍了博弈论。介绍了博弈论。u博弈论：两人以上参与，双方通过不同策略相互竞博弈论：两人以上参与，双方通过不同策略相互竞争的游戏。争的游戏。u博弈：一方采用的策略会对另一方的行为产生影响。博弈：一方采用的策略会对另一方的行为产生影响。u计算思想在诺贝奖获奖理论中占到计算思想在诺贝奖获奖理论中占到70%70%以上的比例。以上的比例。6 社会计算改变社会学家社会计算改变社会学家的思考方式的思考方式根据社会科学理论，以计算技术为工具，可以：根据社会科学理论，以计算技术为工具，可以：研究人类社会的研究人类社会的组成组成、关系关系、结构结构、层次层次、行为行为、运动运动等问题；研究等问题；研究社会媒体社会媒体，促进社会人群的，促进社会人群的交流与合作交流与合作。7 一、计算改变了什么一、计算改变了什么2 2计算改变了工作方式计算改变了工作方式数字化会议数字化会议数字化医疗数字化医疗数字化教学数字化教学数字化制造数字化制造8 数字化会议数字化会议9 数字化医疗数字化医疗10 数字化教学数字化教学11 数字化制造数字化制造12 美国学者美国学者尼葛洛庞帝尼葛洛庞帝在其在其 19961996年出版的年出版的数字化生数字化生存存一书中提出的，按照一书中提出的，按照他的解释，他的解释，计算不再只与计算不再只与计算机有关，它决定我们计算机有关，它决定我们的生存。的生存。13尼葛洛尼葛洛庞帝帝（Negroponte）为美国麻美国麻省理工学院教授及媒体省理工学院教授及媒体实验室的室的创办人。人。西方媒体推崇他西方媒体推崇他为电脑和和传播科技播科技领域域最具影响力的大最具影响力的大师之一，之一，1996年年7月被月被时代代周刊列周刊列为当代最重要的未来学当代最重要的未来学家之一。家之一。计算改变了世界计算改变了世界 二、什么是计算二、什么是计算计算的定义：计算的定义：计算是指运用事先规定的规则，将一组数值变换为另一计算是指运用事先规定的规则，将一组数值变换为另一(所需所需的的)数值的过程。数值的过程。对某一类问题，如能找到一组确定的规则，当给出这类问对某一类问题，如能找到一组确定的规则，当给出这类问题中的任一具体问题后，按规则可以完全题中的任一具体问题后，按规则可以完全机械地机械地在在有限步有限步内内求出结果，则说这类问题求出结果，则说这类问题是可计算是可计算的。这种规则就是的。这种规则就是算法算法算法算法。14 猜数游戏：有自然数猜数游戏：有自然数1-10001-1000，随机选取其，随机选取其中的一个数，请大家猜数。中的一个数，请大家猜数。回答回答1010次是与否，就可以猜出该数字。次是与否，就可以猜出该数字。开始游戏15 实际问题实际问题设计算法设计算法编程实现编程实现二分查找法二分查找法16 3.3.计算思维的特征计算思维的特征计算工具与思维方式的相互影响计算工具与思维方式的相互影响家迪科斯彻：家迪科斯彻：我们使用的工具影响着我们我们使用的工具影响着我们的思维方式和思维习惯，从而也将深刻地的思维方式和思维习惯，从而也将深刻地影响着我们的思维能力影响着我们的思维能力。计算思维计算思维是是各个专业求解问题的基本途径。各个专业求解问题的基本途径。17 3.3.计算思维的特征计算思维的特征计算思维的定义计算思维的定义“计算思维计算思维”是美国卡内基梅隆大学周以真教授提出的一是美国卡内基梅隆大学周以真教授提出的一种理论。种理论。周以真认为：周以真认为：计算思维计算思维是运用计算机科学的基础概念去是运用计算机科学的基础概念去求求解问题解问题、设计系统设计系统和和理解人类行为理解人类行为，它涵盖了计算机科学，它涵盖了计算机科学的一系列思维活动的一系列思维活动。周以真（英文名JeannetteM.Wing，），美国计算机科学家。卡内基-梅隆大学教授。美国国家自然基金会计算与信息科学工程部助理部长。ACM和IEEE会士。18 问题求解中的计算思维问题求解中的计算思维系系系系统设计统设计问题问题求解求解求解求解人人人人类类行行行行为为理解理解理解理解建立建立建立建立问题问题模型模型模型模型选择选择算法算法算法算法编编程程程程实现实现19 有一座城市需要有一座城市需要铺路，不仅每栋铺路，不仅每栋房子都能沿着铺房子都能沿着铺好的道路好的道路到达到达其其他他所有的房子所有的房子，而且而且用的石砖最用的石砖最少少。设有三栋房子和设有三栋房子和三条路，哪些路三条路，哪些路是必须要铺上石是必须要铺上石砖的？砖的？铺路问题20 如果是如果是5 5栋房子？栋房子？1234521 B3C3E1D3A122问题建模问题建模图论中最小路径图论中最小路径算法算法22 警察抓小偷警察抓小偷警察局抓了警察局抓了a a，b b，c c，d d四名偷窃嫌疑犯，其四名偷窃嫌疑犯，其中只有一人是小偷，审讯记录如下：中只有一人是小偷，审讯记录如下：A A说：我不是小偷说：我不是小偷B B说：说：c c是小偷是小偷C C说：小偷肯定是说：小偷肯定是d dD D说：说：c c在冤枉人在冤枉人四个人中，四个人中，三个人说的是真话三个人说的是真话，一个人说的是假话一个人说的是假话，请问谁是小偷？请问谁是小偷？23 问题分析问题分析1依次假依次假设每个人是小每个人是小偷的情况的情况一一代入四句供一一代入四句供词2依次依次检验“四个人中三个人四个人中三个人说真真话，一个，一个人人说假假话”是否成立是否成立3如果成立，小如果成立，小偷找到找到24 数学建模数学建模将将a,b,c,d四个人四个人进行行编号号为1,2,3,4。用用变量量x存放小存放小偷的的编号。号。依次将依次将x=1,x=2,x=3,x=4代入代入问题系系统，检验“三真一假三真一假”是否成立。是否成立。25 计算计算1A说：我不是小：我不是小偷2B说：c是小是小偷3C说：小：小偷肯定是肯定是d4D说：c在冤枉人在冤枉人5三真一假三真一假1X1 1or02X=3 1or03X=4 1or04X4 1or05326 编程实现编程实现For x=1 to 4 If(x1+(x=3)+(x=4)+(x4)=3)then Print xNext x27 百元买白鸡百元买白鸡公鸡每只公鸡每只5 5元，母鸡每只元，母鸡每只3 3元，小鸡一元元，小鸡一元3 3只，只，一百元买一百只鸡，问有几种买法？一百元买一百只鸡，问有几种买法？问题分析：问题分析：X+Y+Z=100X+Y+Z=1005X+3Y+Z/3=1005X+3Y+Z/3=10028 编程编程计算思算思维能能够反映人反映人类思思维活活动，高效，高效执行。行。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 forNext for29 计算机解题方法计算机解题方法计算机解决问题步骤：计算机解决问题步骤：理解问题理解问题，寻找解决问题的条件；，寻找解决问题的条件；从问题抽象出适当的从问题抽象出适当的数学模型数学模型，然后设计解决这个数学模，然后设计解决这个数学模型的算法；型的算法；按照算法编写按照算法编写程序程序，并调试，并调试、测试测试、运行程序，得到最终运行程序，得到最终解答。解答。发现问题分析分析问题预见问题解决解决问题问题30 系统设计中的计算思维系统设计中的计算思维将系统中的变换过程映射为将系统中的变换过程映射为符号变换符号变换形式化，形式化，然后就可以用计算机进行处理。然后就可以用计算机进行处理。系系系系统设计统设计问题问题求解求解求解求解人人人人类类行行行行为为理解理解理解理解31 重要理论重要理论计算思维的本质：计算思维的本质：抽象、自动化（程序、算法）抽象、自动化（程序、算法）计算思维能力：计算思维能力：建立起利用计算机技术解决问题的思路，并理解建立起利用计算机技术解决问题的思路，并理解问题的可求解性。问题的可求解性。问题抽象、模型建立、算法设计、实现问题抽象、模型建立、算法设计、实现抽象自动化32 囚徒困境囚徒困境博弈策略建模博弈策略建模囚徒困境问题描述囚徒困境问题描述警方逮捕了警方逮捕了A A、B B两名嫌疑犯，但没有足够证据指控二人有两名嫌疑犯，但没有足够证据指控二人有罪。于是警方分开囚禁嫌疑犯，并向双方提供以下相同的罪。于是警方分开囚禁嫌疑犯，并向双方提供以下相同的选择（如表所示）：选择（如表所示）：（1 1）如果一人认罪并）如果一人认罪并检控检控对方（背叛），而对方保持沉默，对方（背叛），而对方保持沉默，则此人将获释，沉默者将判监禁则此人将获释，沉默者将判监禁1010年。年。（2 2）如果二人都保持沉默（合作），则二人同样判监）如果二人都保持沉默（合作），则二人同样判监1 1年。年。（3 3）如果二人都互相检举（背叛），则二人同样判监）如果二人都互相检举（背叛），则二人同样判监8 8年。年。策略策略A A沉默（合作）沉默（合作）A A认罪（背叛）认罪（背叛）B沉默（合作）二人同服刑1年A即时获释；B服刑10年B认罪（背叛）A服刑10年；B即时获释 A和B二人同服刑8年33 囚徒困境囚徒困境博弈策略建模博弈策略建模囚徒的策略选择囚徒的策略选择困境困境两名囚徒的选择：两名囚徒的选择：（1 1）若对方沉默，背叛会让我获释，所以我会选择背叛。）若对方沉默，背叛会让我获释，所以我会选择背叛。（2 2）若对方背叛我，我也要指控对方才能得到较低刑期，）若对方背叛我，我也要指控对方才能得到较低刑期，所以选择背叛。所以选择背叛。结结果果：两：两人人都选择背叛都选择背叛，结果二人服刑结果二人服刑8 8年。年。如果两个囚徒合作保持沉默，总体如果两个囚徒合作保持沉默，总体利益会更高。利益会更高。而两个囚徒追求个人利益，选择背而两个囚徒追求个人利益，选择背叛时，总体利益较低叛时，总体利益较低。这就是困境所在。这就是困境所在。34 囚徒困境囚徒困境博弈策略建模博弈策略建模囚徒困境的数学建模囚徒困境的数学建模（1 1）策略的符号化）策略的符号化将囚徒各种选择获得的将囚徒各种选择获得的收益收益和和支付支付转换为数值，获得表所转换为数值，获得表所示符号表。示符号表。符号分数英文中文说明T T5 5Temptation 背叛收益单独背叛成功所得R R3 3Reward合作报酬共同合作所得P P1 1Punishment 背叛惩罚共同背叛所得S S0 0Suckers受骗支付被单独背叛所获35 囚徒困境囚徒困境博弈策略建模博弈策略建模（2 2）建立收益和支付矩阵）建立收益和支付矩阵根据以下规则确定博弈双方的收益和支付根据以下规则确定博弈双方的收益和支付：一人背叛，一人合作时，一人背叛，一人合作时，背叛者得背叛者得5 5分分（背叛收益），（背叛收益），合作者得合作者得0 0分（受骗支付）；分（受骗支付）；二人都合作时，二人都合作时，双方各得双方各得3 3分分（合作报酬）；（合作报酬）；二人都背叛时，二人都背叛时，各得各得1 1分分（背叛惩罚）。（背叛惩罚）。从表可从表可见见：53105310，得出：，得出：TRPSTRPS。囚徒的收益和支付矩阵囚徒的收益和支付矩阵以符号表示的策略以符号表示的策略策略A合作A背叛策略A合作A背叛B合作A=3，B=3 A=5，B=0B合作R，RT，SB背叛A=0，B=5 A=1，B=1B背叛S，TP，P符号分数T T5 5R R3 3P P1 1S S0 036 囚徒困境囚徒困境博弈策略建模博弈策略建模（3 3）建立数学模型）建立数学模型A=RA=R，B=RB=R时，时，A=3A=3，B=3B=3；A=TA=T，B=SB=S时，时，A=5A=5，B=0B=0；A=SA=S，B=TB=T时，时，A=0A=0，B=5B=5；A=PA=P，B=PB=P时，时，A=1A=1，B=1B=1。37 囚徒困境囚徒困境博弈策略建模博弈策略建模【案例案例】生活中生活中的的“囚徒困境囚徒困境”现象现象。幼儿园小朋友互相分享玩具（幼儿园小朋友互相分享玩具（给他玩，不给他玩给他玩，不给他玩）；）；夫妻双方对家庭的态度（夫妻双方对家庭的态度（忠诚，忠诚，背叛背叛）；）；公共卫生的维持（公共卫生的维持（不扔垃圾，不扔垃圾，乱乱扔垃圾扔垃圾）；）；老板与下属的关系（老板与下属的关系（信任，不信任信任，不信任）；）；商场上的君子协定（商场上的君子协定（不违约，违约不违约，违约）；）；竞争对手竞争对手的的价格战（价格战（不降价，降价不降价，降价）；）；国家国家之之间的对抗（间的对抗（和平，战争和平，战争）等。）等。虽然括号内的前者选择是大家想要达到的目标，虽然括号内的前者选择是大家想要达到的目标，但但自私的结果自私的结果往往往往是大家是大家要要接受后者。接受后者。38 囚徒困境囚徒困境博弈策略建模博弈策略建模石头剪刀布游戏的博弈模型石头剪刀布游戏的博弈模型石头剪刀布是一种相互制约的多元博弈游戏，它是最平衡石头剪刀布是一种相互制约的多元博弈游戏，它是最平衡的游戏。的游戏。石头剪刀布不具备数学上的传递性（石头剪刀布不具备数学上的传递性（abab，bcbc时，则时，则acac）。）。石头剪刀布游戏规则绝对平衡，简单明了，没有任何规则石头剪刀布游戏规则绝对平衡，简单明了，没有任何规则漏洞。漏洞。游戏过程充满了游戏过程充满了“心理博弈心理博弈”，单次输赢取决于运气，多，单次输赢取决于运气，多次比赛的话，赢家一定是个心理博弈的高手。次比赛的话，赢家一定是个心理博弈的高手。对石头剪刀布游戏建立数学模型对石头剪刀布游戏建立数学模型。如表如表3-43-4所示。所示。博弈矩阵乙石头剪刀布甲石头01-1剪刀-101布1-1039 囚徒困境囚徒困境博弈策略建模博弈策略建模【案例案例】田忌赛马的博弈。田忌赛马的博弈。博弈矩阵齐王田忌胜者第1场上等马下等马齐王第2场中等马上等马田忌第3场下等马中等马田忌40 人类行为理解中的计算思维人类行为理解中的计算思维计算思维不仅能够反映人类思维活动，还能够通计算思维不仅能够反映人类思维活动，还能够通过计算手段来研究人类的行为。过计算手段来研究人类的行为。系系系系统设计统设计问题问题求解求解求解求解人人人人类类行行行行为为理解理解理解理解41 42 43 医学中的计算思维医学中的计算思维计算思维1）多脏器衰竭2）心血管和脑血管同时梗塞3）复杂疑难症的治疗方案的总体设计计算思维（构造思维）的培养，将有助于临床医生提出“整体构架设计解决方案”的治疗方案。44 计算思维的特性计算思维的特性1概念化，不是程序化。抽象多层次思维计算机科学不是计算机编程。像计算机科学家计算机科学不是计算机编程。像计算机科学家那样去思维意味着远远不止能为计算机编程。它要那样去思维意味着远远不止能为计算机编程。它要求能够在抽象的多个层次上思维。求能够在抽象的多个层次上思维。45 计算思维的特性计算思维的特性2基础的，不是机械的技能。现代社会每个人都必须掌握的技能基础的技能基础的技能是每一个人为了在现代社会中发挥职能所是每一个人为了在现代社会中发挥职能所必须掌握的。生搬硬套之机械的技能意味着机械的重复。必须掌握的。生搬硬套之机械的技能意味着机械的重复。46 计算思维的特性计算思维的特性3人的，不是计算机的思维。人类赋予计算机以激情创造性的使用计算机计算思维是人类求解问题的一条途径，人类聪颖且富有计算思维是人类求解问题的一条途径，人类聪颖且富有想象力，人类赋予计算机以激情。配置了计算设备，就能用想象力，人类赋予计算机以激情。配置了计算设备，就能用自己的智慧去解决那些计算时代之前不敢尝试的问题。自己的智慧去解决那些计算时代之前不敢尝试的问题。47 计算思维的特性计算思维的特性4数学和工程思维的互补与融合。计算机科学在本质上源自数学思维，构建虚拟世界的自计算机科学在本质上源自数学思维，构建虚拟世界的自由使我们能够超越物理世界去打造各种系统。由使我们能够超越物理世界去打造各种系统。48 计算思维的特性计算思维的特性5是思想，不是人造品。面向所有的人，所有地方不只是我们生产的软件、硬件等不只是我们生产的软件、硬件等人造品人造品将以物理形式将以物理形式到处呈现并时时刻刻触及我们的生活，更重要的还有将我到处呈现并时时刻刻触及我们的生活，更重要的还有将我们用以接近和求解问题、管理日常生活、与他人交流和互们用以接近和求解问题、管理日常生活、与他人交流和互动时动时计算性的思想计算性的思想；而且，面向所有的人，所有地方。；而且，面向所有的人，所有地方。49 计算思维的特性计算思维的特性6计算机科学不等同于计算机编程尽管计算思维冠以计算两个字，但尽管计算思维冠以计算两个字，但绝不是只与计算机绝不是只与计算机科学有关的思维，而是人类科学思维的一个远早于计算机科学有关的思维，而是人类科学思维的一个远早于计算机的出现的组成部分。的出现的组成部分。50 总结总结现实问题人人类思思维计算算思思维计算思算思维：运用运用计算机科学的基算机科学的基础概念概念进行行问题求解，系求解，系统设计，人，人类行行为理解等一系列的思理解等一系列的思维活活动。51 课后题课后题9 9枚铜币，其中有一枚略轻的枚铜币，其中有一枚略轻的是假币，用一台没有砝码的是假币，用一台没有砝码的天平讲假币找出来？天平讲假币找出来？52
