计算思维引导 陶先平 南京大学计算机软件研究所.

Presentation on theme: "计算思维引导 陶先平 南京大学计算机软件研究所."— Presentation transcript:

1 计算思维引导 陶先平 南京大学计算机软件研究所

2 我们用计算机干什么？ 抽 象 物理世界 虚拟世界 走向物理世界与虚拟世界的无缝连接

3 数据抽象 解释 数据抽象 核心概念： 信息形态、信息组织、 存储、检索与利用

4 Represent information as bit patterns
怎么把一段文字“放到”计算机里？ 用数字（二进制）代码来代替文字段落：每个文字对应一个唯一的、可区别的代码字。文章由文字组成，每个文字对应替换为相应的代码字得到的就是文章代码。文章代码就是二进制位串。 相应的逆过程就是解码。 你怎么知道计算机里一段二进制串表达的就是王国维的“三境界”？

5 Represent Text Each of the different symbols A unique bit pattern

6 每个人的电脑里都有不少.txt文件。什么文件是.txt文件？
ASCII码 每个人的电脑里都有不少.txt文件。什么文件是.txt文件？

7 Represent integers 0000和1000无法区分；
加法计算不便，而加法是计算机中计算的最根本操作：2+（-2）不能直接得到0000；符号位无法直接参与运算； 补码101101是十进制的多少？

8 Represent Images 如果你用放大镜去看这个画的真迹，你必定会看到画布上密布着有色调、灰度的“点”。正是这样的宏观上连续的点，构成了我们的“画”或者叫图像 那我们该如何将这幅画“存”到计算机中？

9 Pixel and bitmap 532*528*24/8/1024=822

10 Represent Sound 按照我们处理图像数字化的方法，你会如何思考这个问题？ 声音的物理特征(振幅)的数字化

11 一个例子 – “渡河问题” 问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、“羊菜”不能在无人在场时共处，当然只有人能驾船。 图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理的渡河“操作”能够实现该状态的转变。 起始状态是“人狼羊菜”，结束状态是“空”。“允许状态”只有10个。 问题的解：找到一条从起始状态到结束状态的尽可能短的通路。 空 ( 成功 ) 人羊狼菜 人狼菜 人羊狼 人羊菜 狼菜 狼 菜 人羊 羊

12 问题编码 上述关系可以用一个布尔矩阵表示： 在编码世界中，一切皆有可能！ So, we just need to……
狼菜 空 上述关系可以用一个布尔矩阵表示： 人羊狼菜 人狼菜 人羊狼 人羊 在编码世界中，一切皆有可能！ So, we just need to…… 空 它也可以表示成一个“数”： …… 或者，也可以表示成符号串：16#28#2#6#3#768#384#320#112#32

13 问题抽象 问题抽象 算法是计算思维的核心概念: 方法层: 算法 表示层: 编程 实现层: 机器 这差不多也就是计算机科学的主要内容了 算法
从此页到12页，是从问题、平台和解释三个层面，分别说明这三个层面中的抽象化和自动化。 因为报告时间问题，建议最多挑一个去讲，其它的跳过。

14 找假币---何谓“计算思维”？ 给你70个外观完全一样的金币,但是你知道 其中有一个是假币,其重量比真币轻。给你 一架没有砝码的天平，你可以在天平两边 摆任意多个金币，比较他们的轻重。 请设计一种方法，通过若干次称量，确定 哪一个是假币。

15 √ 我们为什么会这样思考来找到最快的方法？ 解空间： 所有可能的假币位置构成的集合 第一种方案: 第二种方案: 几乎每次压缩空间到一半
算法运行后，所有可能的解构成的集合 √ 几乎每次压缩空间到一半 几乎每次压缩空间到三分之一

16 如何表达我们的这个思想？写个程序！ Procedure FindIt(n) { //从n个硬币中找出一个较轻的假币
if n=1 {假币；程序结束；} if n=2 { //只有两个硬币 称量中天平上翘起的是假币；程序结束； } //有多于两个硬币 将硬币分为几乎数量相同的三堆n1,n2,n3； //其中必定有两堆数量相同 称量其中数量相同的两堆； //不妨假设n1=n2 if 两堆不同重 { //不妨假设n1堆轻 FindIt(n1); } else FindIt(n3);

17 No！ 到此为止，这个问题我们解决了吗？ 我们还应该至少回答这些问题： 你能证明你的解法是正确的吗？ 你能证明你的解法是最优的吗？
你能证明你的程序没有错误吗？ 7/6/2019

18 再一个互动游戏： 统计到场人数： 0，所有人都站起来，每个人都握有一个 数字：1
1，每两个人组成一组，将手中数字相加， 并记住。其中一人坐下； 2，重复第一步，直到教室中只有一人； 3，最后一人，大声报出数字；

19 这个游戏，给了我们什么启发？

20 空间压缩 1，依然是压缩”问题”空间： N压缩到n-1 ==》n压缩到n/2 三人或者四人或者……都是一种可能的选择，只要一次统计能够被“简单”完成 2，如果每次分组（两人组）后，组内的统计、累计都可以在组内完成， 那么：我就只需要完成分组、同步和最后数据的收集工作 每个小组，可以并行完成组内工作 每个小组都是一个小型计算机系统 N个人，如果小组规模是m，那么我只需要进行约logmn次的分组、同步工作 我是一个管理了多个可并行运行的计算机系统的“并行计算机系统” 多核系统是一个典型案例 分治法+并行处理：极大提高了问题求解的效率

21 如何表达我们的解题过程呢？ }else{ //slaves 接收master给予的数据； for (i=1 to n/p step 1){
假设我们有p+1个处理器(0,…,p),其中第 0号是master，其它是slave Parallel Procedure count(n) { if (I’m the master){ 将n个数据分为p份：n1,n2,…,np for (i=1 to p step 1){ count(ni); } receive value from pi; sum = sum+value； }else{ }else{ //slaves 接收master给予的数据； for (i=1 to n/p step 1){ value= GetValue(i); sum = sum+value； } send sum to master;

22 系统抽象 平台 核心概念： 系统模型、功能逻辑、 接口、实现 系统抽象

23 系统抽象层 应用（问题） 计算机程序运行支撑 软件(算法) 算法 编程语言 操作系统/虚拟机 指令集体系结构ISA 微体系结构 硬件
功能部件 电路 微电子

24 是什么导致了我们的独特视角？

25 关于计算思维的一些理解 计算思维是我们认知计算的过程中积累形成的思 考“模式”
计算思维教/学需要传递计算给我们带来的可能 性以及实现这些可能的基本方法 算法是解读计算思维的最佳载体 这一页是第一段的Index

26 计算思维是我们认知计算过程中积累的思考“模式”
思维是一种认知过程 计算思维是我们认知计算过程中若干层 面的抽象及其实现中“沉淀”下来的一 些…… 从这一页到13页，想从认知计算的角度，解读为什么：计算思维以抽象化和自动化思维为两大根本要素

27 计算思维：抽象化+自动化： 三个层面的抽象过程及相应的自动化过程
计算思维：抽象化+自动化： 三个层面的抽象过程及相应的自动化过程 如何去“传递”抽象化+自动化？ 这一段的总结，引出下段：我们不能机械的传递这两个词，而是要通过一些具体的内容，让学生感悟到这两个词

28 计算思维教/学需要传递/感悟计算给我们带来 的可能性以及实现这些可能的基本方法
想以前想不到之事 做以前做不到之事 做以前做不好之事 红色的三个“事”就是“可能性”的三种

29 想以前想不到之事 全球脉动(Global Pulse)计划： 联合国已经推出的新项目，希望利用“大数据”来促进全球经 济发展
进行所谓的“情绪分析”，使用软件来对社交网站和文本消息 中的信息作出分析 帮助预测某个给定地区的失业率、支出削减或是疾病爆发等现 象 目标在于利用数字化的早期预警信号来提前指导援助项目，以 阻止某个地区重新陷入贫困等困境 模拟社会现象

30 做以前做不到之事 HGP计划 人类基因组计划 计算机科学家 遗传学家 生物化学家 生理学家 细胞生物学家 结构生物学家 临床和病理学家

31 做以前做不好之事 ERP系统 针对物资资源管理（物流）、人力资源管理（人流）、 财务资源管理（财流）、信息资源管理（信息流）而 开展的集成一体化的企业管理 信息技术带给了我们庞大的处理能力： 复杂业务模型、复杂管理要求、 复杂合作关系、复杂时空数据类型……

32 人有多大胆 地有多大产 计算给这个世界带来的不是这个和那个技术，也 不是这个或者那个炫目应用
计算带给我们的是无限的想象空间和强有力的实 现手段 人有多大胆 地有多大产

33 试图给出计算思维的定义 美国卡内基-梅隆大学教授Jeannette M. Wing(周以真)领导世界上最早的”计算思维研究中心”, 并大力推动这一概念。 ------Computational Thinking: What and Why? Link Magazine, 2010

34 结束语 计算思维看不见，摸不着，但影响着你的决策！
计算思维：当你面临一个要解决的问题时，如果你的第一感觉是去寻找一个数学模型对问题和解进行建模，去尝试着通过算法来寻找解，并尝试着思考如何用一个辅助工具开展计算时，计算思维已经在影响你了！ 有很多的计算过程中沉淀下来的模式，被封装为计算思维，可以被我们直接使用

35 作业 1，请你设计一个递归程序：程序输入为n个硬币，第m个为假币.程序输出寻找假币的过程和称量次数。
2，请你为某个型号的电子词典，设计一个查找单词的递归算法(伪代码) 提示：1，电子词典已经按照词典序排好了序,，词典中共有n个单词； 2，你可以直接使用compare(x,y)函数来判断单词x和y是否相同；compare函数在单词x排在y之前时，得到值-1，相同时得到值0，之后时得到值1； 3，请自行查阅“折半查找法”，并从中获得帮助； 4，查找的结果是：“没有发现”或者“发现”