第0章 计算思维概论.ppt

课程计划计算思维 第0章课程计划与计算思维 2 课程内容考核方式教学平台 教育在线计算思维简介课程论文 课程计划 3 课程内容 计算机应用能力基础11月中下旬参加全校上机统考 自学 教学部提供练习环境 自己课下练习 简单介绍课程的学习目标 培养计算思维能力计算基础及c 高级程序设计语言 4 考核方式 1 计算机应用能力基础 机考 20分2 平时成绩 30分上机测试和作业 15分平时出勤 15分3 期末考试 机考 50分 5 如何使用教育在线 使用 教育在线 进行学习交流活动 下面我们来演示 下的教育在线http 222 30 60 9 eol homepage common opencourse 6 计算思维简介 请同学们思考的问题 1 进入大学后 如何学习 学习什么 2 对于大学计算机课程 学习什么 希望下面的内容对你有所帮助 7 计算思维简介 一个古老而又年轻的概念 计算思维 正在科技界和教育界萌发 激荡和蔓延 所到之处 彻底更新和改变了现在被广泛认同的一些理论和认识 一种新的关于计算和计算机科学的观点正在以雷霆万钧之势荡涤着旧有的传统 焕发出面向新时代和新技术的崭新面貌 从事计算机科学 思维科学 教育科学 社会科学 人文科学等各方面的专家 围绕着不同的要求和目的被吸引到这一领域里来 这种共同的兴趣将酝酿着新的重大的理论革命和技术飞跃 一种全新的对于计算机科学的理解和应用的时代已经展现在我们的面前 8 计算思维简介 思维通过表达形成一个体系 形成科学 思维的过程也是科学研究的对象 科学本身是思维的形态 在科学思维的谱系中 真正具备了系统和完善的表达体系的思维模式只有三个 分别是实证思维 逻辑思维和计算思维 三大科学思维构成了科技创新的三大支拄 作为三大科学思维支柱之一 并具有鲜明时代特征的计算思维 尤其应当引起我们国家的高度重视 9 计算思维简介 逻辑思维 对于自然现象 人工现象 的数学抽象是将问题逻辑化 成为一个推理系统 数学从基本的假设出发 通过建立运动方程求解 通过逻辑的方法计算运动的规律 逻辑思维要通过数学这个体系表达 定义是理论思维的灵魂 定理和证明则是它的精髓 公理化方法是最重要的思维方法 科学界一般认为 公理化方法是世界科学技术革命推动的源头 以理论为基础的学科主要是指数学 数学是所有学科的基础 10 计算思维简介 实证思维 对于自然现象 人工现象 的物理抽象是将问题单纯化 成为一个验证体系 实证思维要通过物理这个形态体系表达 实证思维的先驱应当首推意大利著名的物理学家 天文学家和数学家伽利略 他开创了以实验为基础具有严密逻辑理论体系的近代科学 被人们誉为 近代科学之父 爱因斯坦为之评论说 伽利略的发现 以及他所用的科学推理方法 是人类思想史上最伟大的成就之一 而且标志着物理学的真正开端 以实验为基础的学科有物理 化学 地学 天文学 生物学 医学 农业科学 冶金 机械 以及由此派生的众多学科 11 计算思维简介 东西方思维的差异 西方是实证主义学派 东方是经验主义学派 中医自成体系 广义的说也是一门科学 但是中医理论的基本出发点 阴阳学说 天人合一假设 不具备证伪性 所以在西方的哲学观念下不认为是科学体系 12 计算思维简介 计算思维 对于自然现象 人工现象 的计算抽象是将问题符号化 成为一个计算系统 计算科学将运动抽象成为符号系统和变换的演化 13 计算思维简介 与实证思维和逻辑思维不同 计算思维关注的是人类思维中有关可行性 可构造性和可评价性的部分 当一个原始人面对一块石头准备加工工具时 他脑子里的思维既不是对于石头本身属性的物理认识 也不是对于这件工具用途的逻辑推理 他所想到的是实实在在的加工这件工具的操作细节 是如何一步一步完成从石头到工具的过程 这些步骤之间的顺序 每一个步骤完成的标准 以及某一步骤失败后的替代措施 就是现代意义上的可操作性和可验证性 原始人把这些思维逐步地映射到具体的加工工程 一定是先有工程的思维 后有工程的实践 14 计算思维简介 这样的思维就包含了计算思维所有核心的内容 尽管从程度上来说 原始人类的思维还是低浅的和简单的 但是计算思维确实存在于人类的自然思维之中 是人类思维活动中固有的和先天的成分 没有计算机之前 就有了计算思维的萌芽和表现 只是在有了计算机之后 计算思维的问题才被真正关注 得到突飞猛进的发展 成为现代人类必须掌握的基本思维能力 15 计算思维简介 美国华裔女科学家 现任美国国家科学基金计算机与信息科学与工程学部负责人 美国国家科学院计算机科学与通讯部门主席 周以真 jeannettem wing 教授首先提出并定义了 计算思维 computationalthinking ct 计算思维是运用计算机科学的基础概念进行问题求解 系统设计 以及人类行为理解等涵盖计算机科学之广度的一系列思维活动 2011年 图灵奖获得者richardm karp提出了 计算透镜 computationallens 理念 其核心是将计算作为一种通用的思维方式 通过这种广义的计算 涉及信息 执行算法 关注复杂度 来描述各类自然过程和社会过程 从而解决各个学科的问题 16 计算思维简介 在美国 计算思维 的提出得到了美国教育界和科学界的广泛支持 在美国科学基金会启动的 大学计算教育振兴的途径 中投入巨资进行美国计算教育的改革并对 计算思维 所发挥的作用取得了共识 美国科学基金会还启动了以计算思维为核心的重大基础研究 进一步将计算思维的培育扩展到美国的各个研究领域 17 计算思维简介 在我国 计算思维的重要性也已引起了科学家和教育界的高度重视 教育部高等学校计算机基础课程教学指导委员会主任委员陈国良院士等积极地倡导把培养学生的 计算思维 能力作为计算机基础教学的核心任务 并由此建设更加完备的计算机基础课程体系和教学内容 陈国良等认为大学第一门计算机基础课程是计算思维培养的一个关键 初步构建了以计算思维为核心的 计算思维导论 课程 并给出了该课程任务 基本要求 教学内容和教学方法 18 计算思维简介 大学计算机课程就是进行计算思维教育 计算思维教育的目的是培养一种思维习惯 一种像计算机科学家思考问题那样的习惯 19 计算思维简介 如1998年图灵奖获得者 计算机科学家詹姆士 格雷 jamesgray 的思维习惯是这样的 1 首先对问题进行非常简单的陈述 也即要说明解决一个什么样的问题 他认为 一个能够清楚表述的问题 能够得到周围人的支持 虽然不清楚具体该怎么做 但对问题解决之后能够带来的益处非常清楚 2 其次 解决问题的方案和所取得的进步要有可测试性 3 最后一点 是整个研究和解决问题的过程能够被划分为一些小的步骤 这样就可以看到中间每一个取得进步的过程 20 计算思维简介 在技术层面 美国国家研究立法委员会计算机文化协会主席史耐德 snyderlawrence 教授在其撰写的 新编信息技术导论 技能 概念和能力 一书中指出 人们可以从抽象的角度来思考信息技术 他写道 当你成为数字文人之后 你可以从抽象的角度来思考技术 而且更喜欢 习惯 提以下问题 1 对于这个软件 我必须学会用哪些功能 才能帮助我完成任务 2 该软件的设计者希望我知道些什么 3 该软件的设计者希望我做些什么 4 该软件向我展示了哪些隐喻 5 为完成指定的任务 该软件还需要其他哪些信息 6 我是否在其他软件中见到过这个软件中的操作 21 计算思维简介 在专业层面 对于一个专业的计算问题 计算机科学家 中国科学院院士陈国良教授常说 一种习惯 从计算的手段来看 我们应当使计算机械化 如算盘 手摇计算机 模拟计算机 电子数字计算机 从计算的过程来看 我们应当使计算形式化 如图灵机 计算理论 从计算的执行来看 我们应当使计算自动化 如冯 诺依曼机 在计算思维的研究中 教育部大学计算机课程教学指导委员会主任委员李廉教授认为 在传统的教学中 计算思维是隐藏在能力培养内容中的 要靠学生 悟 出来 现在要把这些明白的讲出来 让学生自觉地去学习 提高培养质量 缩短培养的时间 22 计算思维简介 美国计算机科学技术教师协会则认为 计算思维的教育应存在于每一所学校的每一堂课程的教学中 是否采用了计算思维 该协会认为 对于一个要解决的问题 教师是否能有意识 习惯 的提出以下问题 1 人与计算机的计算能力有多大 各自的局限性是什么 2 研究的问题复杂性有多大 3 问题解决的判定条件是什么 4 什么样的技术可以应用于当前的问题讨论中 5 什么样的计算策略更能有效地解决当前的问题 计算思维表述体系框架 12个核心概念 cc1991 绑定 大问题的复杂性 概念模型和形式模型 一致性和完备性 效率 演化 抽象层次 按空间排序 按时间排序 重用 安全性 折中和结论 计算思维简介 计算思维简介 计算思维的作用 人类基因组计划 物种起源 1859第1版 1872第6版 计算折纸 通过构建算法来回答折纸中遇到的问题 亚马逊网上购物推荐系统 音乐合成软件cooledit 作曲软件平台nyquist 计算思维简介 计算思维简介 例如 2013年4月发布了中国首个3d全景网络地质博物馆 浙江东方地质博物馆 该博物馆以 天 地 人 和 的大地质概念为主题 通过3d科技展示 大宇宙 大地球 大人类 大地质 大历史 将实体博物馆无法演示的历史 地质知识 用时空交融的方式予以展现 不仅全景展示矿物岩石的构造及成因 地质演变的进程 自然环境的变迁 以及古生物的演化过程 还将馆藏宝物在网上以3d形式更立体 更形象的方式与观众见面 同时配以相应的地质知识介绍 真实再现了馆藏实物珍品所蕴藏的历史故事 为观众勾勒出了一幅恢弘 壮观的地球演变和人类文明的历史画卷 激发人们节约能源 爱护地球的热情和行动力 27 计算思维简介 问题1 最小生成树关注焦点难题解决 优化 规划摘要我们的社会是由许多网络连接起来的 电话网 公用设施的供应网络 计算机网络和道路网络 对某一特定的网络通常有些关于选择该在哪安置这些路 电缆或无线电连接设备等 以下活动探索一种方式来优化在一个网络中对各联系对象间的选择 专有名词最小生成树 贪婪算法 图形算法 28 计算思维简介 原始问题 泥泞城市铺路从前 有一个没有路的城市 在暴风雨之后走过这个城市附近是特别困难的 因为地面非常的泥泞 汽车陷入了泥水中并且把人的靴子都弄脏了 这个城市的市长决定对某些街道进行铺路 但又不想花太多的钱因为这个城市还需要建一个游泳池 因此这个市长指定了两种情况 1 应该让足够的街道被铺好使得让每个人都可以从他们的房子只经过铺好的路走到别人家的房子 中间可以经过别人家的房子 2 铺路的总费用应该最小 29 计算思维简介 下图显示这个城市的布局 在每个房子之间铺路石的数量代表铺那条路线的费用 接下来的问题是计算允许人民从任意一间房子到达任意另外一间 同时所需铺路石的最少数目 30 计算思维简介 31 计算思维简介 策略1 从空白图开始的策略 如果有必要就渐渐地增加砖块直到所有的房子都连接起来 这是一个好的策略 事实上 你能保证找到一种优化解决方案 如果你增加路径的时候按顺序的增加路径长度 但一旦所有的房子都连接起来之后就不再添加任何路径 不同的解决方法是通过改变添加相同长度路径的顺序而已 策略2 将所有的路径都铺好 然后再把冗余的路径除掉 这将产生一个优化解决方法 但需要相当大的工作 32 计算思维简介 解法1 33 计算思维简介 解法2 34 计算思维简介 问题的抽象表示 问题的一种解法 35 计算思维简介 相关知识假设你是设计一项公共设施如电力 煤气或水等应该如何传输到一个新的社区 一个网络的点线或管道是必要连接到所有的家庭以及公共设施公司 每个家庭必须连接到网络上的一个点 但其他线路从公共设施到房子间的线路通常不是很重要的 只要线路存在就行 这个任务设计的一个使总路径最短的网络称作最小生成树 36 计算思维简介 相关知识最小生成树不仅在天然气和电力网络中很有用 他们帮助我们在不同应用如计算机网络 电话网 石油管道和飞机航线中解决问题 然而 正如上面所说的 你必须在考虑线路的代价的同时也考虑到线路的方便与否 这对在图表中解决其他问题诸如 旅行商问题 如何寻找在网络中访问所有的节点最短的路径第一步是很有用的 37 计算思维简介 相关知识最小生成树问题存在高效的算法 方法 一个简单的最佳解决方法就是从没有任何连接开始 然后不断添加连接和增加规模 只把网络中先前没有连接的部分连接起来 这种方法之前已经提到过 但是学生们必须自己发现这种算法 这种算法在j b kruskal于1956年发表之后叫做kruskal算法 38 计算思维简介 问题2 网络中的路由和死锁关注焦点解决问题的协作能力 逻辑推理的合理性 计划编制摘要人们在争夺稀缺资源时 筹划周密是必要的 当对资源的需求有依赖关系时 如 汽车使用公路 通过网络获取信息 有可能出现 死锁 的情况 在任何人继续下去之前 死锁都一直存在 因此 有些人总是必须返回的 协作程序要求每人在出现 死锁 之前完成预想的结果 专有名词路由 死锁 信息传输 39 计算思维简介 原始问题 橙子游戏6个小孩玩11个橙子的游戏 其中d小孩有一只手是空的 将孩子用字母做了标签 橙子也同样做了标签 一个字母对应两个橙子 孩子们穿同样标记的衣服以展现他们的字母 这些橙子被混合在一起 使字母跟对应的小孩暂时不能在一起 孩子们一手举着一个橙子 40 计算思维简介 游戏的目标是让孩子们通过橙子 使每个孩子最终持有他们相应的橙子 如 a小孩必须持有包含a标签的橙子等等 这里有两条必须遵循的规则 a 小孩一只手只能举一个橙子 b 橙子只能通过空手 然后立即传给圆中的邻居 上图的游戏规则是 只允许c或e的小孩传橙子给d小孩 d小孩可以从c或e小孩传得橙子 41 计算思维简介 游戏过程中 小孩们很快就会发现 如果他们 贪婪 一旦得到自己的橙子就不放手 那么该组可能永远无法实现其目标 强调个人不 赢 的游戏是必要的 但在该游戏中 只有当每个人都有自己的橙子 这个问题才被真正解决 42 计算思维简介 变换与拓展该游戏有很多可能的变化 例如 1 尝试在更大或者更小的圆圈中玩这种游戏 2 有其它小孩进来的变异规则 3 在小孩间不交谈的情况下进行游戏 4 尝试用一种不同的配置传递消息 如 所有小孩坐在一条直线上 或者对某些小孩有两个甚至更多的邻居 如右图 5 这个问题可以模拟出由一个人来操纵令牌 自动协作 但策略仍可加以探讨 43 计算思维简介 相关知识如道路系统和交通拥堵 电话和电脑系统中 路由和死锁在许多不同类型的网络是个重要的问题 工程师们花了很多时间来弄清楚如何解决这些问题 以及如何设计网络 其中的问题是容易解决的 在许多不同类型的网络里 路由 拥塞和死锁 可成为当前令人沮丧的问题 试想一下 你最喜欢的时间 却是交通最拥挤的时间段被耗掉 在纽约市的交通街上 堵塞的情况已经出现好几次了 它变得如此的拥挤 以致出现死锁的情况 没有