计算思维与不插电的计算机.ppt

计算思维/“不插电”的计算机科学,CS4HS中小学师资培训项目,一、计算思维二、不插电的计算机科学(1),计算思维,1.问题的提出2.什么是计算思维3.计算思维可以做什么4.计算思维的两个A5.衡量计算思维中抽象的标准6.计算思维的主要应用7.计算思维的影响8.大胆展望9.计算思维是什么，不是什么10.计算思维如何应用于我国目前的教育,计算思维,JeannetteM.Wing(周以真),ComputationalThinking,(JeannetteM.Wing)曾任美国卡内基-梅隆大学（CMU）计算机科学系主任，现任美国国家基金会（NSF）计算机和信息科学与工程部（CISE）主任。于1983年在美国麻省理工学院（MIT）获得计算机科学博士学位。主要研究方向为并行分布式系统的规范和认证以及编程语言。目前主要研究提升软件系统安全性技术的设计和评价方法。周教授是ACM和IEEE会士。,问题的提出,什么是计算数的加减乘除；方程的求解、函数的微分积分等；计算还包括定理的证明推导；计算的本质是什么？1930年代，由于哥德尔（K.Godel，1906-1978）、丘奇(A.Church，1903-1995)、图灵(A.M.TUI-ing，1912-1954)等数学家的工作，人们才弄清楚什么是计算的本质，以及什么是可计算的、什么是不可计算的等根本性问题。计算就是依据一定的法则对有关符号串的变换过程计算的本质就是递归,问题的提出,计算无处不在计算概念的泛化随着计算机日益广泛而深刻的运用，计算这个原本专门的数学概念已经泛化到了人类的整个知识领域，并上升为一种极为普适的科学概念和哲学概念，成为人们认识事物、研究问题的一种新视角、新观念和新方法。计算无处不在计算的世界观和方法论计算的观念正在渗透到宇宙学、物理学、生物学乃至社会科学等诸多领域。计算不但已经成为人们认识自然、生命、思维和社会的一种普遍方法，而且正在试图成为一种全新的世界观。计算哲学、计算语言学、生命计算、计算化学、计算社会学、计算人类学。,问题的提出,计算无处不在计算新时代最初发明计算机的动机，在于计算机运算能力的应用，如科学、工程等运算；后来数据处理的发展也带来商业的应用；近年多媒体及网络的普及，应用范围就延伸至教育、休闲以及国计民生各个方面。,问题的提出,计算方法和模型使我们敢于去处理那些原本无法由任何个人独自完成的问题求解和系统设计。,什么是计算思维,计算思维是运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为。它包括了涵盖计算机科学之广度的一系列思维活动。,计算思维可以做什么,每个人的基本技能计算和计算机对计算思维如同印刷出版对3R（Reading,wRiting,andaRithmetic3R）计算机科学的成果正在成为我们解决问题的方法问题的难易程度寻找最优解资源约束环境近似解随机化容错计算思维就是通过约简、嵌入、转化和仿真等方法，把一个看来困难的问题重新阐释成一个我们知道怎样解决的问题。,计算思维可以做什么,是一种递归思维。是并行处理。是代码和数据的相互转化。是类型检查。命名规则。间接寻址和程序调用。是评价方法准确性、效率、美学、简洁、优雅。,计算思维可以做什么,抽象和分解描述庞杂的任务或者设计巨大复杂的系统隐藏系统内部的实现细节适应将来的改变（预取、缓存）,计算思维可以做什么,是按照预防、保护及通过冗余、容错、纠错的方式从最坏情形恢复的一种思维。避免死锁,计算思维可以做什么,是启发式推理的方法规划学习调度搜索策略权衡,计算思维可以做什么举例,早晨上班前把当天需要的东西放进背包-预置和缓存路上丢了钱包沿走过的路寻找-回推什么时候停止租车自己买一辆-在线算法超市付帐时应当去排哪个队-多服务器系统的性能模型停电时电话仍然可用-失败的无关性和设计的冗余性完全自动的大众图灵测试如何区分计算机和人类-人工智能和计算代理程序,计算思维的两个A,Abstraction（抽象）计算思维是抽象化的过程。（与数学类似）计算思维同时在多个抽象层次上同时进行。计算思维定义层次之间的关系。Automation（自动化）计算思维的思考方式是：使抽象层次及其关系机械化。机械化的可行性是由精确和严格的符号和模型所保证。在下面是一些“机器”（人或计算机，虚拟或实际的）。,衡量计算思维中抽象的标准,有效性速度空间能力正确性做正确的事做事（停机问题）其他简单和优美有用性可修改性可维护性花费,计算思维的主要应用,关注于抽象和概念化的事物复杂性：可计算性问题算法：性能、近似值、随机化、优化数据：数据结构抽象机器：自动机、状态机结构设计：分解、组合、模块化、分层抽象化语言学：句法、语义、语法推理：正确性、逻辑、类型、证明、排错控制：递归、循环、条件、判断、并行、分布通讯：同步、异步、广播、p2p、客户机、服务器、共享内存、消息传递外界约束：容错、可靠性、动力不关注于计算机一般应用：word、excel、上网如何编程,计算思维的影响：-单学科中应用多种方法,生物学：鸟枪算法vs基因测序语言中的字符串vsDNA序列布尔网络vs生物网络进程演算vs分子间相互作用电路vs自动调节的细胞状态图vs发育遗传学,计算思维的影响：机器学习-一种方法应用于多学科,天文学：探索星系：机器学习超大量多维数据分析：KD-tree,医学：药物研制疾病诊断疾病治疗,计算思维的影响：机器学习-一种方法应用于多学科,气象学：气候现象的形成研究,计算思维的影响：机器学习-一种方法应用于多学科,神经科学：运用机器学习研究语言,计算思维的影响：机器学习-一种方法应用于多学科,信用卡超市金融行业娱乐领域体育,计算思维的影响：机器学习-一种方法应用于多学科,化学：原子计算化学反应中的算法,计算思维的影响：-对于其他领域,数学：E8的破解18人，4年，77小时，600亿四色定理证明,计算思维的影响：-对于其他领域,工程学：电气学机械航空宇航,计算思维的影响：-对于其他领域,社会：经济法律人文地球学,计算思维的影响：-对于其他领域,大胆展望：计算思维不仅对于其他领域的科学家，而且对每个人都适用。普适计算是昨天的梦想，今天的现实。计算思维是今天的梦想，明天的现实。,大胆展望,概念化，不是程序化计算机科学不是计算机编程追求抽象的多个层次上思维,计算思维是什么，不是什么,根本的，不是刻板的技能根本技能意味着每个人必须掌握刻板技能意味着机械的重复-具有讽刺意味的是，当计算机像人类一样思考之后，思维可就真的变成机械的了。,计算思维是什么，不是什么,是人的，不是计算机的思维方式聪颖想象力激情计算机只是实现人类智慧的工具,计算思维是什么，不是什么,数学和工程思维的互补与融合本质上源自数学思维（形式化基础）本质上源自工程思维（面向实际）以虚拟世界超越物理世界,计算思维是什么，不是什么,是思想，不是人造物非物理实体接近和求解问题日常生活交流和互动无处不在,计算思维是什么，不是什么,计算机科学不是计算机编程智力上的挑战和引人入胜的科学问题依旧亟待理解和解决计算机科学和其他任何科学没有冲突只有互相促进,计算思维是什么，不是什么,计算思维如何应用于我国目前的教育,在哪些阶段引入计算思维小学初中高中大学大学之后在哪些课程中引入计算无所不在、像计算机科学家那样思考计算语言学、计算生物学、计算经济学、计算天文学。用什么样的方法引入不插电的计算机科学教学与生活的关系对教师的培养,参考资料,REUSitesPIMeeting,Arlington,VA,March13,2009,JeannetteM.Wing,不插电的计算机科学的背景不插电的计算机科学的内容不插电的计算机科学的内涵实现“不插电”学习计算机科学的教学方法,二、不插电的计算机科学（1）-内容提要,计算机无处不在，无处不用；中小学生有必要探寻、领悟计算机的原理及其解决问题的精妙思想；通过游戏教学将抽象、复杂的计算机原理形象化、简单化，使学生们了解计算机工作的基本原理；培养学生们的“计算思维”，开发他们解决问题的方法，自我获取知识的能力。,CSUnplugged的背景,不插电的计算机科学是一系列免费的学习活动，Unplugged通过使用卡片、串珠、蜡烛等，穿插有大量的活动，参与一些游戏及谜题，达到学习计算机科学的目的。这些活动向学生介绍了计算机科学中的很多概念，像二进制数，排序算法以及数据压缩等，不使用计算机，学生可以学到计算机科学中的很多思想。不插电的计算机科学适合于各个年龄阶段的人，从孩子到老人，从城市到乡村。在世界各地，人们使用不插电的计算机科学已经超过15年了，无论是在教室、科学中心、家里，甚至是在公园里，Unplungged可以作为假日活动来进行。,CSUnplugged的背景,为了满足人们的需要，计算机会在内部处理两类事情：计算机会存储数据数据是计算机工作时处理的原材料对象，计算机会将内部数据转换为人们可以理解的信息（如：数字、词语和图像）。计算机通过一系列指令对数据进行处理通过这些指令（即算法）使得计算机能够解决许多问题（如：排序、查询、发送及传输信息）。,不插电的计算机科学的内容,二进制数和“比特”用二进制数来存取数据从比特到字母从比特到图像压缩信息检测错误,不插电的计算机科学的内容,介绍：保存数据是计算机首先要完成的事情二进制是所有计算机的数据储存形式这来源于计算机内存中晶体管的“开”“关”状态,1.二进制数和“比特”,游戏：二进制卡片游戏目的掌握比特(bit)非0即1，二进制的性质以及二进制与数字之间的转换规律。游戏内容通过学生手持卡片的翻转反面和正面，代替比特的“0”、“1”变化；通过人数的变化，说明二进制的性质。游戏结果比特是计算机技术中一种常用的度量单位，非0即1，且容易实现；从小比特可到大数字。,1.二进制数和“比特”,二进制数字游戏,1.二进制数和“比特”,互动：准备卡片你留意到卡片的规律没有?如果向左侧继续增加一张卡片,这张卡片需要画几个点?,1.二进制数和“比特”,数字6如何表示?,1.二进制数和“比特”,数字0-9如何表示?任何数字能用不止一种方法来表示吗?5张卡片能表示的最大数字是多少?能表示的最小数字是多少?,1.二进制数和“比特”,二进制01001表示多少?这些卡片一共有多少个比特?,1.二进制数和“比特”,用任意符号代表二进制中的0和1,1.二进制数和“比特”,扩展：进制的概念理解十进制和二进制,1.二进制数和“比特”,扩展：生日蛋糕,BornAugust2,1971,1.二进制数和“比特”,介绍：虽然比特很小，但计算机中的“大”数字也是由比特组成只要是有两种状态的都可以表示比特用手也可以表示二进制数,2.用二进制数来存取数据,游戏：二进制数的性质二进制数的相加？二进制数的成倍扩大？固定位数的二进制表示的最大数？如何用二进制数表示一个十进制数（转换）？,2.用二进制数来存取数据,扩展：什么是千字节（Kilobyte）为什么1千字节=1024字节介绍兆字节（Megabyte）、吉字节（Gigabyte）、太字节（terabyte）、拍字节（Petabyte）介绍能表示两种状态的电子设备晶体管电容器磁盘、磁带光盘介绍24位彩色介绍1000兆连接介绍32/64位计算机介绍“128位SSL加密”介绍8进制、16进制,2.用二进制数来存取数据,扩展：读心术,2.用二进制数来存取数据,123,456,介绍计算机中存储的任何数据（文档、电子邮件、网页、图片、音乐、视频）都是二进制比特代表字母-编码和解码,3.从比特到字母,游戏：储藏室谜题,3.从比特到字母,游戏：传音游戏像modem一样用声音发送email,3.从比特到字母,介绍比特可以表示字母、图像，如：ASCII码或Unicode码来存储字符；比特表示像素存储图像。像素（pixel）,4.从比特到图像,最简单的黑白图像中,每个像素只有两种值:黑或白,如下面字母a的放大图。当计算机存储这样的图片时,它只需记录图像中哪些是黑点哪些是白点,也就是比特的组合。,4.从比特到图像,01110,？,00001,10001,01111,10001,4.从比特到图像,游程编码(RLE)：记录每个白色或黑色连续区域的长度。,4.从比特到图像-图像压缩,1,3,14,11,40,1,3,10,1,3,11,4,游戏：图像解码,4.从比特到图像-图像压缩,游戏：图像解码,4.从比特到图像-图像压缩,游戏：图像编码,4.从比特到图像-图像压缩,4.从比特到图像-图像压缩,4.从比特到图像-图像压缩,扩展：从比特到图像的实例-喷墨打印机,介绍压缩不但可以减小体积还可以加快运行或传输速度游程编码可以压缩黑白图像LZ算法,5.压缩信息,游戏：文字的压缩,5.压缩信息,游戏：文字的压缩寻找重复的单词计算压缩前后字符数计算压缩率,5.压缩信息,游戏：文字的压缩寻找重复的单词-The,Rain,tter,pa,TheRain,Pitterpatter计算压缩前后字符数-96/39计算压缩率-41%,5.压缩信息,游戏：文字的压缩在实际应用中需要标记指针,5.压缩信息,PitterpatterPitterpa(7,4),游戏：文字的解压缩恢复一首缺词少字的诗歌“Peaseporridge”,5.压缩信息,游戏：文字的解压缩恢复一首缺词少字的诗歌“Peaseporridge”,5.压缩信息,扩展：自指向代码对于“Banana”该如何分解？Ban(2,3)对于“mississippi”该如何分解？miss(3,4)ppi,5.压缩信息,介绍在数据的存储、传输、处理时会产生错误如何能检测甚至自动修复错误奇偶校验,6.检测错误,游戏目的掌握计算机中检验数据错误的奇偶校验。游戏内容准备36张卡片，保证每张卡片正反两面的图案和颜色不同。学生任意摆放其中25张卡片,你增加一行和一列。然后你背过身去，让学生任意翻转一张卡片。游戏结果您可以猜出学生翻转的是那一张卡片。使学生掌握计算机中是如何检验数据错误的。,6.检测错误,翻卡街头魔术,6.检测错误,玩法：让学生将卡片放在桌子上,并由他决定每张卡片放置的正反。接着，你可以增加几张卡片。让学生翻转一张卡片，你总能告诉他哪一张卡片是被翻过的。诀窍就在你所增加的几张卡片。,6.检测错误,图中每行有多少张白色的卡片？左下方最后两张应该是什么颜色的卡片？规律在那里？每行每列白色卡片数量均为偶数。,6.检测错误,右图中卡片组合中，每行和每列的白色卡片，开始均为偶数？记下现在各行上白色卡片的总数。哪一行白色卡片的总数不再为偶数了呢？记下每列白色卡片总数。哪一列白色卡片的总数不再为偶数了呢？你能判断出是哪张卡片被翻动过?,6.检测错误,这些被放置的卡片就好比计算机中的比特(0或1),而0和1的组合代表了数字、字母或图像。那些新增加的卡片我们称之为奇偶校验位。计算机就是通过在数据中添加奇偶校验位来保证数据不被随意修改。利用类似奇偶校验的方法，可以保护计算机中几乎所有的数据。,6.检测错误,当发生一系列错误时，什么情况下计算机能利用奇偶校验位来检测并修正错误。图中开始每行每列的白色数均为偶数，但有两张卡片已经翻过了。哪几行哪几列处于错误状态？我们能检测到错误发生了，但无法修复它们。,6.发现更多的错误,如果计算机接收到一条信息中，提示它可能存在两个比特的错误，那么此时计算机如何处理？如果同时发生两处错误，你无法确定哪个是出错的比特，你必须让发送人重新再发送一次消息。但有时如磁盘上的数据无法重新发送，所以纠错也是很重要的。试着用几张卡片排列成满足奇偶检验原理的阵列（保证每行和每列的白色卡片均为偶数）。你能在翻动两张卡片后，保持每行和每列白色卡片总数仍为偶数吗？不能,6.发现更多的错误,你能做到翻动3张卡片，但不被检测出来吗？不能翻动4张卡片，但不被检测出来吗？可以，只要挑选两行和两列，翻转位于行和列交叉处的四张卡片。,6.发现更多的错误,6.发现更多的错误,奇偶校验的特殊用法奇偶校验阵列RAID磁盘阵列,6.发现更多的错误,每本书在封底都有一个10位或13位的编号，称为国际标准书号（ISBN）。ISBN的最后一位数字称为计算机校验码。2007年1月开始，图书统一开始使用13位的ISBN。10位编码原理:第一位数字乘以10,第二位数字乘以9,一直到第9位数字乘以2，将它们相加的总和除以11，记下余数。11-余数为校验码。校验码值为10，用X代替。,6.ISBN检测,ISBN0-13-911991-4(010)+(19)+(38)+(97)+(16)+(15)+(94)+(93)+(12)=17217211=15remainder7117=4,6.ISBN检测,ISBN0-14-911991-4(010)+(19)+(48)+(97)+(16)+(15)+(94)+(93)+(12)=18018011=16remainder4114=7,6.ISBN检测,如果两个数字颠倒了,0-13-191991-4?你能找出只改变其中一个数字,并保证最后的校验码不变的方法吗?不能,6.ISBN检测,13位编码原理:第1位数字乘以1,第2位数字乘以3,第3位数字乘以1,第4位数字乘以3,以次类推，直到12位乘以3,然后将各位相加后,取总和的末位数字再减去10即可。如果结果为10取0。