计算思维与离散数学之浅谈.ppt

计算思维之模式及应用 欧列川王晓峰蔡生茂 对称数问题 23232 2322322332233232 23222332232323223322232 如果200位数呢 人眼还能解决么 将眼睛观察行为转化为数学上的比较大小 考虑通过取模 整数除法得到首尾对应数 整合 设计程序 C 的做法 人类行为理解 问题求解 系统设计 数学建模算法设计编程实现 计算思维是运用计算机科学的基础概念进行人类行为理解 问题求解 系统设计以及等涵盖计算机科学之广度的一系列思维活动 2006年 美国卡内基 梅隆大学周以真教授在 CommunicationsoftheACM 定义计算思维ComputationalThinking 计算思维的普遍认可的定义 计算思维模式 何为计算思维模式 何为模式 简单地说 就是从不断重复出现的问题中发现和抽象出的解决问题的经验和规律 只要是一再重复出现的问题 就可能存在某种解决模式 2004 2005 2006 50 70 120 计算思维模式 定义的较为形象的描述 通过约简 嵌入 转化和仿真等 困难的问题得以解决的方法 递归思维 并行处理 是一种把代码译成数据又能把数据译成代码的类型检查方法采用抽象和分解来控制庞杂任务 选择合适的方式去陈述一个问题 或对问题建模使其易于处理 利用不变量简明扼要且表述性地刻画系统的行为 按照预防 保护及通过冗余 容错 纠错的方式从最坏情形恢复将处理问题的过程转化为计算的过程数学和工程思维的完美结合 仔细阅读上述定义 每组选择一条最易理解的定义进行讨论 结束后派代表 1 阐述你们的看法 举出实例 也可阐述个人的看法 seminar 五分钟讨论 计算思维的应用 数字化时代的生活 数字化时代 听了十几年 数字化 这个词 能解释一下什么意思么 数字化就是将许多复杂多变的信息转变为可以度量的数字 把它们转变为一系列二进制代码 引入计算机进行处理 这就是数字化的基本过程 运用抽象和建模的思想来进行信息处理 数字化 其实没有真正意义上的电话 电视机 通信 数字电话 Before Now 模拟信号 数字信号 信息为什么要用数字化表示 因为计算机是用二进制编码方式工作的 它无法直接理解人们日常接触到的信息 所以计算机需要采用数字化编码的形式对信息进行存储 加工 传送 我们大致可以将这些非数字化资料归纳成文本 图像 声音和视频等几类 它们要经过数字化的过程才能由计算机处理 数字信号与模拟信号相比 前者是加工信号 加工信号对于有杂波和易产生失真的外部环境和电路条件来说 具有较好的稳定性 脱离了物理环境 计算机易处理数字信号 集成数字电路 数字信号易于进行压缩 利用冗余 易于储存 表示 检索 传播 获取 数字化的优点 实现过程 拼出图像 原始图 每个人对应图上某一点 人为表示该点 图像的数字化 声卡的工作原理 为什么采用二进制 可行性 电子元件易实现可靠性 状态稳定简易性 算法简单求和法则0 0 0 0 1 1 0 1 1 1 10求积法则0 0 0 0 1 1 0 0 1 1 1逻辑性 可用进制的0 1直接代表逻辑代数中的 假 和 真 数字化时代信息得以光速传播 人与人 人与环境的交流变得更为便捷 从科学计算到信息处理 从理论计算机科学到计算机应用技术 从计算机软件到计算机硬件 从人工智能到认知系统 无不与离散数学密切相关 通过离散数学 不但可以掌握处理离散结构的描述工具和方法 而且可以提高抽象思维和严格的逻辑推理能力 为创新性研究打下基础 计算科学与离散数学 3 26 20201 58PM DiscreteMath BoLiu SCNU 19 连续VS离散 离散的印象 枯藤老树昏鸦 小桥流水人家 古道西风瘦马 夕阳西下 断肠人在天涯 天净沙 秋思 元 马致远 连续的印象 剪不断 理还乱 是离愁 恰似一江春水向东流 南唐 李煜 离散数学的内容 数理逻辑 证明 在计算科学的某些领域至关重要 构造一个证明和写一个程序的思维过程在本质上是一样的 组合分析 解决问题的一个重要方面就是计数或枚举对象 离散结构 用来表示离散对象以及它们之间关系的抽象数学结构 包括 集合 排列 关系 树 图 算法化思维 许多问题都可以通过构造一个可以被程序实现的算法来解决 它的三个步骤是 构造 选择合适的离散模型和操作步骤 验证 算法的正确性 评估 时间和空间的复杂性 应用和建模 在可以想到的任何研究领域都有离散数学的应用 计算科学 化学 植物学 动物学 语言学 地理 经济学等 构造离散模型都是极其有用的解决问题的方法 在集合论的若干悖论中 最通俗易懂的是Russell 罗素 的理发师悖论 一个乡村理发师 自夸本村无人可与相比 宣称他当然不给自己刮脸的人刮脸 但却给本村所有自己不刮脸的人刮脸 一天他发生了疑问 他是否应当给自己刮脸 K nigsberg七桥问题 Pregel河横穿K nigsberg城 河上建有七座桥 能否设计散步路线 走过所有七座桥 每座桥恰好经过一次而回到同一地点 经证明 每个点要有偶数条线 这就是概念化 模式化的解 3x 1问题 3x 1问题 对每一个正整数 如果它是奇数 则对它乘3再加1 如果它是偶数 则对它除以2 如此循环 最终都能够得到1 例 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1TomasOliveiraeSilva用了