第一讲-计算思维概述PPT演示课件.pptx

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