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

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

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

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

Represent Text Each of the different symbols A unique bit pattern

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如何表达我们的解题过程呢？ }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;

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

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

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

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

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

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

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

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

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

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

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

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

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

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