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

1、计算思维/“不插电”的计算机科学 CS4HS中小学师资培训项目 计算思维 1.问题的提出问题的提出 2.什么是计算思维什么是计算思维 3.3.计算思维可以做什么计算思维可以做什么 4.4.计算思维的两个计算思维的两个A A 5.5.衡量计算思维中抽象的衡量计算思维中抽象的 标准标准 6.6.计算思维的主要应用计算思维的主要应用 7.7.计算思维的影响计算思维的影响 8.8.大胆展望大胆展望 9.9.计算思维是什么，不是计算思维是什么，不是 什么什么 10.10.计算思维如何应用于我计算思维如何应用于我 国目前的教育国目前的教育 计算思维 Jeannette M. Wing (Jeannette

2、 M. Wing (周以真周以真) ) Computational Thinking (Jeannette M.Wing)曾任美国卡内基-梅隆大学 （CMU）计算机科学系主任，现任美国国家基金会 （NSF）计算机和信息科学与工程部（CISE）主任。 于1983年在美国麻省理工学院（MIT）获得计算机 科学博士学位。主要研究方向为并行分布式系统的 规范和认证以及编程语言。目前主要研究提升软件 系统安全性技术的设计和评价方法。周教授是ACM 和IEEE会士。 问题的提出 什么是计算什么是计算 数的加减乘除； 方程的求解、函数的微分积分等； 计算还包括定理的证明推导； 计算的本质是什么？计算的本质是

3、什么？ 1930年代，由于哥德尔（K.Godel，1906-1978）、丘奇 (A.Church，1903-1995)、图灵(A.M.TUI-ing，1912-1954)等数学 家的工作，人们才弄清楚什么是计算的本质，以及什么是可计算 的、什么是不可计算的等根本性问题。 计算就是依据一定的法则对有关符号串的变换过程 计算的本质就是递归计算的本质就是递归 问题的提出 计算无处不在计算无处不在计算概念的泛化计算概念的泛化 随着计算机日益广泛而深刻的运用，计算这个原本专门的数学概随着计算机日益广泛而深刻的运用，计算这个原本专门的数学概 念已经泛化到了人类的整个知识领域，并上升为一种极为普适的念已经泛

4、化到了人类的整个知识领域，并上升为一种极为普适的 科学概念和哲学概念，成为人们认识事物、研究问题的一种新视科学概念和哲学概念，成为人们认识事物、研究问题的一种新视 角、新观念和新方法。角、新观念和新方法。 计算无处不在计算无处不在计算的世界观和方法论计算的世界观和方法论 计算的观念正在渗透到宇宙学、物理学、生物学乃至社会科学等计算的观念正在渗透到宇宙学、物理学、生物学乃至社会科学等 诸多领域。诸多领域。 计算不但已经成为人们认识自然、生命、思维和社会的一种普遍计算不但已经成为人们认识自然、生命、思维和社会的一种普遍 方法，而且正在试图成为一种全新的世界观。方法，而且正在试图成为一种全新的世界观

5、。 计算哲学、计算语言学、生命计算、计算化学、计算哲学、计算语言学、生命计算、计算化学、 计算社会学、计算人类学。计算社会学、计算人类学。 问题的提出 计算无处不在计算无处不在计算新时代计算新时代 最初发明计算机的动机，在于计算机运算能力的应用，如科学、最初发明计算机的动机，在于计算机运算能力的应用，如科学、 工程等运算；工程等运算； 后来数据处理的发展也带来商业的应用；后来数据处理的发展也带来商业的应用； 近年多媒体及网络的普及，应用范围就延伸至教育、休闲以及国近年多媒体及网络的普及，应用范围就延伸至教育、休闲以及国 计民生各个方面。计民生各个方面。 问题的提出 计算方法和模型使我们敢于去处

6、理那些原本无法 由任何个人独自完成的问题求解和系统设计。 什么是计算思维 计算思维是运用计算机科学的基础概念去求解问 题、设计系统和理解人类的行为。它包括了涵盖 计算机科学之广度的一系列思维活动。 计算思维可以做什么 每个人的基本技能每个人的基本技能 计算和计算机对计算思维如同印刷出版对3R（Reading, wRiting, and aRithmetic3R） 计算机科学的成果正在成为我们解决问题的方法 问题的难易程度 寻找最优解 资源约束 环境 近似解 随机化 容错 计算思维就是通过约简、嵌入、转化和仿真等方法， 把一个看来困难的问题重新阐释成一个我们知道怎样解决 的问题。 计算思维可以做

7、什么 是一种递归思维。 是并行处理。 是代码和数据的相互转化。 是类型检查。 命名规则。 间接寻址和程序调用。 是评价方法准确性、效率、美学、简洁、优雅。 计算思维可以做什么 抽象和分解抽象和分解 描述庞杂的任务或者设计巨大复杂的系统 隐藏系统内部的实现细节 适应将来的改变（预取、缓存） 计算思维可以做什么 是按照预防、保护及通过冗余、容错、纠错的方式从最坏是按照预防、保护及通过冗余、容错、纠错的方式从最坏 情形恢复的一种思维。情形恢复的一种思维。 避免死锁 计算思维可以做什么 是是启发式推理启发式推理的方法的方法 规划 学习 调度 搜索 策略 权衡 计算思维可以做什么 举例 早晨上班前把当天

8、需要的东西放进背包-预置和缓 存 路上丢了钱包沿走过的路寻找-回推 什么时候停止租车自己买一辆-在线算法 超市付帐时应当去排哪个队-多服务器系统的性能 模型 停电时电话仍然可用-失败的无关性和设计的冗余 性 完全自动的大众图灵测试如何区分计算机和人类- 人工智能和计算代理程序 计算思维的两个A A AbstractionAbstraction（抽象）（抽象） 计算思维是抽象化的过程。（与数学类似） 计算思维同时在多个抽象层次上同时进行。 计算思维定义层次之间的关系。 AutomationAutomation（自动化）（自动化） 计算思维的思考方式是：使抽象层次及其关系机械化。机械化的 可行性是

9、由精确和严格的符号和模型所保证。 在下面是一些“机器”（人或计算机，虚拟或实际的）。 衡量计算思维中抽象的标准 有效性有效性 速度 空间 能力 正确性正确性 做正确的事 做事（停机问题） 其他其他 简单和优美 有用性 可修改性 可维护性 花费 计算思维的主要应用 关注于抽象和概念化的事物关注于抽象和概念化的事物 复杂性：可计算性问题 算法：性能、近似值、随机化、优化 数据：数据结构 抽象机器：自动机、状态机 结构设计：分解、组合、模块化、分层抽象化 语言学：句法、语义、语法 推理：正确性、逻辑、类型、证明、排错 控制：递归、循环、条件、判断、并行、分布 通讯：同步、异步、广播、p2p、客户机、

10、服务器、共享内存、消息传递 外界约束：容错、可靠性、动力 不关注于不关注于 计算机一般应用：word、excel、上网 如何编程 计算思维的影响： - -单学科中应用多种方法 生物学：生物学： 鸟枪算法 vs 基因测序 语言中的字符串 vs DNA序列 布尔网络 vs 生物网络 进程演算 vs 分子间相互作用 电路 vs 自动调节的细胞 状态图 vs 发育遗传学 计算思维的影响：机器学习 - -一种方法应用于多学科 天文学：天文学： 探索星系：机器学习 超大量多维数据分析：KD-tree 医学：医学： 药物研制 疾病诊断 疾病治疗 计算思维的影响：机器学习 - -一种方法应用于多学科 气象学：

11、气象学： 气候现象的形成研究 计算思维的影响：机器学习 - -一种方法应用于多学科 神经科学：神经科学： 运用机器学习研究语言 计算思维的影响：机器学习 - -一种方法应用于多学科 信用卡 超市 金融行业 娱乐领域 体育 计算思维的影响：机器学习 - -一种方法应用于多学科 化学：化学： 原子计算 化学反应中的算法 计算思维的影响： - -对于其他领域 数学：数学： E8的破解 18人，4年，77小时，600亿 四色定理证明 计算思维的影响： - -对于其他领域 工程学：工程学： 电气学 机械 航空 宇航 计算思维的影响： - -对于其他领域 社会：社会： 经济 法律 人文 地球学 计算思维的

12、影响： - -对于其他领域 大胆展望：计算思维不仅对于其他领域的科学家，而且对大胆展望：计算思维不仅对于其他领域的科学家，而且对 每个人都适用每个人都适用。 普适计算是昨天的梦想，今天的现实。 计算思维是今天的梦想，明天的现实。 大胆展望 概念化，不是程序化概念化，不是程序化 计算机科学不是计算机编程 追求抽象的多个层次上思维 计算思维是什么，不是什么 根本的，不是刻板的技能根本的，不是刻板的技能 根本技能意味着每个人必须掌握 刻板技能意味着机械的重复 -具有讽刺 意味的是，当计算机像人类一样思考之后，思维可就真的 变成机械的了。 计算思维是什么，不是什么 是人的，不是计算机的思维方式是人的，

13、不是计算机的思维方式 聪颖 想象力 激情 计算机只是实现人类智慧的工具 计算思维是什么，不是什么 数学和工程思维的互补与融合数学和工程思维的互补与融合 本质上源自数学思维（形式化基础） 本质上源自工程思维（面向实际） 以虚拟世界超越物理世界 计算思维是什么，不是什么 是思想，不是人造物是思想，不是人造物 非物理实体 接近和求解问题 日常生活 交流和互动 无处不在 计算思维是什么，不是什么 计算机科学计算机科学不是不是计算机编程计算机编程 智力上的挑战和引人入胜的科学问题依旧亟待理解和解决 计算机科学和其他任何科学没有冲突只有互相促进 计算思维是什么，不是什么 计算思维如何应用于我国目前的教育

14、在哪些阶段引入计算思维在哪些阶段引入计算思维 小学 初中 高中 大学 大学之后 在哪些课程中引入在哪些课程中引入 计算无所不在、像计算机科学家那样思考 计算语言学、计算生物学、计算经济学、计算天文学。 用什么样的方法引入用什么样的方法引入 不插电的计算机科学 教学与生活的关系教学与生活的关系 对教师的培养对教师的培养 参考资料 REU Sites PI Meeting,Arlington, VA,March 13, 2009, Jeannette M. Wing 不插电的计算机科学的背景 不插电的计算机科学的内容 不插电的计算机科学的内涵 实现“不插电”学习计算机科学的教学方法 二、不插电的计

15、算机科学（1 1）-内容提要 计算机无处不在，无处不用； 中小学生有必要探寻、领悟计算机的原理及其解决问题的 精妙思想； 通过游戏教学将抽象、复杂的计算机原理形象化、简单化， 使学生们了解计算机工作的基本原理； 培养学生们的“计算思维”，开发他们解决问题的方法， 自我获取知识的能力。 CS Unplugged的背景 不插电的计算机科学是一系列免费的学习活动， Unplugged通过使用卡片、串珠、蜡烛等，穿插有大量的 活动，参与一些游戏及谜题，达到学习计算机科学的目的。 这些活动向学生介绍了计算机科学中的很多概念，像二进 制数， 排序算法 以及 数据压缩等，不使用计算机，学 生可以学到计算机科

16、学中的很多思想。 不插电的计算机科学适合于各个年龄阶段的人，从孩子到 老人，从城市到乡村。在世界各地，人们使用不插电的计 算机科学已经超过15年了，无论是在教室、科学中心、家 里，甚至是在公园里，Unplungged 可以作为假日活动来 进行。 CS Unplugged的背景 为了满足人们的需要，计算机会在内部处理两类事情： 计算机会存储数据计算机会存储数据 数据是计算机工作时处理的原材料对象，计算机会将内 部数据转换为人们可以理解的信息（如：数字、词语和图 像）。 计算机通过一系列指令对数据进行处理计算机通过一系列指令对数据进行处理 通过这些指令（即算法）使得计算机能够解决许多问题 （如：排

17、序、查询、发送及传输信息）。 不插电的计算机科学的内容 二进制数和“比特” 用二进制数来存取数据 从比特到字母 从比特到图像 压缩信息 检测错误 不插电的计算机科学的内容 介绍： 保存数据是计算机首先要完成的事情 二进制是所有计算机的数据储存形式 这来源于计算机内存中晶体管的“开”“关”状态 1.二进制数和“比特” 游戏：二进制卡片游戏：二进制卡片 游戏目的游戏目的 掌握比特(bit)非0即1 ，二进制的性质以及二进制与数字之间的转 换规律。 游戏内容游戏内容 通过学生手持卡片的翻转反面和正面，代替比特的 “0”、“1” 变化；通过人数的变化，说明二进制的性质。 游戏结果游戏结果 比特是计算机

18、技术中一种常用的度量单位，非0即1 ，且容易实现； 从小比特可到大数字。 1.二进制数和“比特” 二进制数字游戏 1.二进制数和“比特” 互动： 准备卡片 你留意到卡片的规律没有? 如果向左侧继续增加一张卡片,这张卡片需要画几个点? 1.二进制数和“比特” 数字6如何表示? 1.二进制数和“比特” 数字0-9如何表示? 任何数字能用不止一种方法来表示吗? 5张卡片能表示的最大数字是多少? 能表示的最小数字是多少? 1.二进制数和“比特” 二进制01001表示多少? 这些卡片一共有多少个比特? 1.二进制数和“比特” 用任意符号代表二进制中的0和1 1.二进制数和“比特” 扩展： 进制的概念 理

19、解十进制和二进制 1.二进制数和“比特” 扩展： 生日蛋糕 Born August 2, 1971 1.二进制数和“比特” 介绍： 虽然比特很小，但计算机中的“大”数字也是由比特组成 只要是有两种状态的都可以表示比特 用手也可以表示二进制数 2.用二进制数来存取数据 游戏：二进制数的性质游戏：二进制数的性质 二进制数的相加？二进制数的相加？ 二进制数的成倍扩大？二进制数的成倍扩大？ 固定位数的二进制表示的最大数？固定位数的二进制表示的最大数？ 如何用二进制数表示一个十进制数（转换）？如何用二进制数表示一个十进制数（转换）？ 2.用二进制数来存取数据 扩展：扩展： 什么是千字节（什么是千字节（K

20、ilobyteKilobyte） 为什么为什么1 1千字节千字节=1024=1024字节字节 介绍兆字节（介绍兆字节（MegabyteMegabyte）、吉字节（）、吉字节（GigabyteGigabyte）、太字节）、太字节 （terabyteterabyte）、拍字节（）、拍字节（PetabytePetabyte） 介绍能表示两种状态的电子设备介绍能表示两种状态的电子设备 晶体管晶体管 电容器电容器 磁盘、磁带磁盘、磁带 光盘光盘 介绍介绍2424位彩色位彩色 介绍介绍10001000兆连接兆连接 介绍介绍32/6432/64位计算机位计算机 介绍介绍“128128位位SSLSSL加密加密

21、” 介绍介绍8 8进制、进制、1616进制进制 2.用二进制数来存取数据 扩展：读心术扩展：读心术 2.用二进制数来存取数据 1 2 3 4 5 6 介绍介绍 计算机中存储的任何数据（文档、电子邮件、网页、图片、音乐、计算机中存储的任何数据（文档、电子邮件、网页、图片、音乐、 视频）都是二进制视频）都是二进制 比特代表字母比特代表字母-编码和解码编码和解码 3.从比特到字母 游戏：储藏室谜题游戏：储藏室谜题 3.从比特到字母 游戏：传音游戏游戏：传音游戏 像像modemmodem一样用声音发送一样用声音发送emailemail 3.从比特到字母 介绍介绍 比特可以表示字母、图像，如：ASCII

22、码或Unicode码来存储字符； 比特表示像素存储图像。 像素（pixel） 4.从比特到图像 最简单的黑白图像中,每个像素只有两种值:黑或白,如下 面字母a的放大图。 当计算机存储这样的图片时,它只需记录图像中哪些是黑 点哪些是白点,也就是比特的组合。 4.从比特到图像 0 1 1 1 00 1 1 1 0 ？ 0 0 0 0 10 0 0 0 1 1 0 0 0 11 0 0 0 1 0 1 1 1 10 1 1 1 1 1 0 0 0 11 0 0 0 1 4.从比特到图像 游程编码(RLE)：记录每个白色或黑色连续区域的长度。 4.从比特到图像-图像压缩 1,3,1 4,1 1,4 0

23、,1,3,1 0,1,3,1 1,4 游戏：图像解码 4.从比特到图像-图像压缩 游戏：图像解码 4.从比特到图像-图像压缩 游戏：图像编码 4.从比特到图像-图像压缩 4.从比特到图像-图像压缩 4.从比特到图像-图像压缩 扩展：从比特到图像的实例-喷墨打印机 介绍介绍 压缩不但可以减小体积还可以加快运行或传输速度 游程编码可以压缩黑白图像 LZ算法 5.压缩信息 游戏：文字的压缩游戏：文字的压缩 5.压缩信息 游戏：文字的压缩游戏：文字的压缩 寻找重复的单词寻找重复的单词 计算压缩前后字符数计算压缩前后字符数 计算压缩率计算压缩率 5.压缩信息 游戏：文字的压缩游戏：文字的压缩 寻找重复的

24、单词寻找重复的单词-The, Rain, tter, pa,The Rain, -The, Rain, tter, pa,The Rain, Pitter patterPitter patter 计算压缩前后字符数计算压缩前后字符数-96/39-96/39 计算压缩率计算压缩率-41%-41% 5.压缩信息 游戏：文字的压缩游戏：文字的压缩 在实际应用中需要标记指针在实际应用中需要标记指针 5.压缩信息 Pitter patter Pitter pa(7,4) 游戏：文字的解压缩游戏：文字的解压缩 恢复一首缺词少字的诗歌恢复一首缺词少字的诗歌“Pease porridge”Pease porr

25、idge” 5.压缩信息 游戏：文字的解压缩游戏：文字的解压缩 恢复一首缺词少字的诗歌恢复一首缺词少字的诗歌“Pease porridge”Pease porridge” 5.压缩信息 扩展：自指向代码扩展：自指向代码 对于对于“Banana”Banana”该如何分解？该如何分解？ Ban(2,3)Ban(2,3) 对于对于“mississippimississippi”该如何分解？该如何分解？ miss(3,4)ppi 5.压缩信息 介绍介绍 在数据的存储、传输、处理时会产生错误在数据的存储、传输、处理时会产生错误 如何能检测甚至自动修复错误如何能检测甚至自动修复错误 奇偶校验奇偶校验 6.

26、检测错误 游戏目的游戏目的 掌握计算机中检验数据错误的奇偶校验。 游戏内容游戏内容 准备36张卡片，保证每张卡片正反两面的图案和颜色不同。学生 任意摆放其中25张卡片,你增加一行和一列。然后你背过身去，让学 生任意翻转一张卡片。 游戏结果游戏结果 您可以猜出学生翻转的是那一张卡片。使学生掌握计算机中是如 何检验数据错误的。 6.检测错误 翻卡街头魔术 6.检测错误 玩法： 让学生将卡片放在桌子上,并由他决定每张卡片放置的正 反。 接着，你可以增加几张卡片。 让学生翻转一张卡片，你总能告诉他哪一张卡片是被翻过 的。 诀窍就在你所增加的几张卡片。 6.检测错误 图中每行有多少张白色的卡片？ 左下方

27、最后两张应该是什么颜 色的卡片？ 规律在那里？ 每行每列白色卡片数量均为偶数。 6.检测错误 右图中卡片组合中，每行和每列的 白色卡片，开始均为偶数？记下现 在各行上白色卡片的总数。 哪一行白色卡片的总数不再为偶数 了呢？ 记下每列白色卡片总数。 哪一列白色卡片的总数不再为偶数 了呢？ 你能判断出是哪张卡片被翻动过? 6.检测错误 这些被放置的卡片就好比计算机中 的比特(0或1),而0和1的组合代表了 数字、字母或图像。那些新增加的 卡片我们称之为奇偶校验位。计算 机就是通过在数据中添加奇偶校验 位来保证数据不被随意修改。 利用类似奇偶校验的方法，可以保 护计算机中几乎所有的数据。 6.检测错

28、误 当发生一系列错误时，什么情况下 计算机能利用奇偶校验位来检测并 修正错误。 图中开始每行每列的白色数均为偶 数，但有两张卡片已经翻过了。 哪几行哪几列处于错误状态？ 我们能检测到错误发生了，但无法修复 它们。 6.发现更多的错误 如果计算机接收到一条信息中，提示它可能存在两个比特 的错误，那么此时计算机如何处理？ 如果同时发生两处错误，你无法确定哪个是出错的比特，你必须 让发送人重新再发送一次消息。 但有时如磁盘上的数据无法重新发送，所以纠错也是很重要的。 试着用几张卡片排列成满足奇偶检验原理的阵列（保证每 行和每列的白色卡片均为偶数）。你能在翻动两张卡片后， 保持每行和每列白色卡片总数仍

29、为偶数吗？ 不能 6.发现更多的错误 你能做到翻动3张卡片，但不被检测出来吗？ 不能 翻动4张卡片，但不被检测出来吗？ 可以，只要挑选两行和两列，翻转位于行和列交叉处的四张卡片。 6.发现更多的错误 错误数量错误数量可以检测出可以检测出可以纠错可以纠错 1YesYes 2或3YesNo 4NoNo 6.发现更多的错误 奇偶校验的特殊用法 奇偶校验阵列 RAID磁盘阵列 6.发现更多的错误 每本书在封底都有一个10位或13位的编号，称为国际标准 书号（ISBN）。 ISBN的最后一位数字称为计算机校验码。 2007年1月开始，图书统一开始使用13位的ISBN。 10位编码原理: 第一位数字乘以1

30、0,第二位数字乘以9,一直到第9位数字乘以2，将 它们相加的总和除以11，记下余数。11-余数为校验码。 校验码值为10，用X代替。 6.ISBN检测 ISBN 0-13-911991-4 (0 10) + (1 9) + (3 8) + (9 7) + (1 6)+ (1 5) + (9 4) + (9 3) + (1 2) = 172 172 11 = 15 remainder 7 11 7 = 4 6.ISBN检测 ISBN 0-14-911991-4 (0 10) + (1 9) + (4 8) + (9 7) + (1 6)+ (1 5) + (9 4) + (9 3) + (1 2) = 180 180 11 = 16 remainder 4 11 4 = 7 6.ISBN检测 如果两个数字颠倒了, 0-13-191991-4? 你能找出只改变其中一个数字,并保证最后的校验码不变 的方法吗? 不能 6.ISBN检测 13位编码