计算机文化与计算思维第六版.pptx

第一章计算机文化与计算思维 1 1 1引言1 2计算机的诞生和发展1 3计算思维基础 1 1引言 2 人类为什么要发明计算机 人的计算速度很低 祖冲之计算 至小数点后7位数用了15年 计算30 30的行列式需要几个人年 中国第一棵原子弹研制时 数百位科学家在大礼堂打算盘 早期的计算工具 算筹春秋战国时期世界上最早的计算工具 算盘中国唐代第一种手动式计数器沿有至今 计算尺1622年手动式 上世纪70年代被计算器取代可进行加 减 乘 除 指数 三角函数 加法器1642年机械式 只能做加法 1 1引言 3 计算器1673年德国GottfriedLeibniz 机械式可进行加 减 乘 除和开方 差分机和分析机 查尔斯 巴贝奇1812年差分机1834年分析机 分析机 体现了现代电子计算机的结构 设计思想被称为现代通用计算机的雏形 4 1 M的状态 接受状态 进位状态 初始时处于进位状态 2 从右向左扫描纸带 进位状态 读到0或空白 则改写1 进入接受状态 立即停机 读到1 则改写为0 状态保住不变 读写头左移 1 2计算机的诞生和发展 计算机的诞生图灵机 ENIAC和冯 诺依曼体系结构在理论上 工作原理 体系结构上奠定现代电子计算机的基础 图灵机 Turingmachine TM 阿兰 图灵 AlanMathisonTuring 1912 1954 解决问题 什么是计算 什么是可计算性 组成 计算X 1的图灵机M 纸带 读写头 5 1 2计算机的诞生和发展 图灵机的能力 高级程序设计语言 现代通用计算机邱奇 图灵和哥德尔断言 一切直觉上能行可计算的函数都可用图灵机计算 反之亦然邱奇 图灵论题 世界上的问题 可计算的 图灵机可计算的就是可计算的 不可计算的 图灵的贡献 图灵机模型 解决了可计算问题计算机的理论问题 图灵测试 回答了什么样的机器具有智能人工智能的理论基础 美国计算机学会ACM于1966年创立了 图灵奖 计算机科学之父 人工智能之父 ENIAC 电子数字积分计算机 1946 2 1955 10宾州大学 6 1 2计算机的诞生和发展 每秒5千次加减运算没有存储器采用十进制 第一款商用计算机 UNIVAL1947年 莫奇莱和埃克特 仅表明电子计算机时代的到来 冯 诺依曼体系结构计算机人类第二台计算机 EDVAC 离散变量自动电子计算机 1945年冯 诺依曼参与研制并且发表 关于EDVAC的报告草案 7 1 2计算机的诞生和发展 采用二进制存储程序 程序和数据一起存储在内存中五个部分 运算器 控制器 存储器 输入设备和输出设备 奠定了现代计算机体系结构和工作原理迄今为止的计算机都采用这种思想 称为冯 诺依曼计算机 计算机的分代 8 电子管 晶体管 集成电路 大规模集成电路 1 2计算机的诞生和发展 发展趋势 微型化 巨型化 网络化和智能化 未来新型计算机 9 光计算机利用光子取代电子进行数据运算 传输和存储不同波长的表示不同的数据优点 超高速缺点 体积庞大 生物计算机 分子计算机 20世纪80年代中期开始研制采用了生物芯片 量子计算机利用处于多现实态下的原子进行运算的计算机 这种多现实态是量子力学的标志 1 2计算机的诞生和发展 计算机的分类 10 按综合性能指标分类 高性能计算机 巨型机或大型机 速度最快 处理能力最强 最快 Titan每秒2亿亿次浮点运算中国 天河1A每秒4 70千万亿次浮点运算第8 工作站 介于PC与小型机之间高档微机系统高分辨率 大容量内外存 图形功能较强 微型计算机 桌面型计算机 笔记本电脑 平板电脑 移动设备 服务器 网络环境中对外提供服务的计算机系统 按用途分类 通用机 专用机 1 2计算机的诞生和发展 嵌入式计算机 数量超过PC 1 2计算机的诞生和发展 11 计算机的应用类型1 科学计算2 数据处理3 电子商务 B2B阿里巴巴 B2C京东商城 C2C淘宝网4 过程控制5 CAD CAM CIMS6 多媒体技术7 人工智能 卡斯帕罗夫对弈 深蓝 1 2计算机的诞生和发展 12 计算机文化 物质文化计算机的软 硬件设备以及使用方法 非物质文化计算机学科对自然科学和社会科学等的广泛渗透 创造和形成了新的科学思想 科学方法 科学精神 价值标准等计算机应用改变了传统社会 形成了网络社会等虚拟的社会形态产生了相应的语言 风俗 道德 法律等最重要的是计算机网络文化 13 示例1 计算f x 是 a b 上的积分数学方法牛顿 莱布尼兹 f x F x 计算思维黎曼积分 对 a b 进行n等分计算小矩形面积累加 三大科学思维 计算思维 运用计算机科学的基础概念进行问题求解 系统设计 以及人类行为理解等涵盖计算机科学之广度的一系列思维活动 1 3计算思维 理论思维 推理思维 特征 以推理和演绎为特征代表学科 数学 实验思维 实证思维 特征 观察和总结自然规律代表学科 物理学 计算思维 构造思维 特征 设计和构造代表学科 计算机科学 14 迭代法迭代过程 1 12 1 23 2 3 n n 1 n程序 s 1 for i 1 i n i s s i 经典迭代 牛顿迭代法J20研制过程就是迭代过程 原型机0原型机1原型机2原型机3 示例2 计算n的阶乘f n n 1 3计算思维 递归 分解 问题 小问题 n n 1 问题 分解 小问题 更小问题 最小问题 分解 分解 不能再分解 n n 1 n 2 1 intfac intn if n 1 return 1 elsereturn fac n 1 n voidmain inty y f 4 cout y 15 示例1 3哥尼斯堡七桥问题18世纪经典数学问题在哥尼斯堡的一个公园里 有七座桥将普雷格尔河中两个岛以及岛与河岸连接起来 问是否可能从这四块陆地中任一块出发 恰好通过每座桥一次 再回到起点 1 计算思维的本质 抽象和自动化抽象 完全超越物理的时空观 并完全用符号来表示数学抽象是一种特例 1 3计算思维 哥尼斯堡七桥问题 哥尼斯堡七桥问题的抽象 自动化 机械地一步一步自动执行 其基础和前提是抽像 16 2 计算思维的特征 是属于人的思维方式 不是计算机的思维方式递归 迭代 黎曼积分早已提出 是人类赋予计算机 可以由人执行 也可以由计算机执行 是思想 不是人造物 是概念化 不是程序化3 计算思维的基本问题 可计算性一个问题是可计算的是指可以使用计算机在有限步骤内解决邱奇 图灵论题 图灵机可以计算的就是可计算的 计算复杂性时间复杂性和空间复杂性 1 3计算思维 17 示例4矩阵相乘 Cn n An n Bn n 1 3计算思维 计算cij需要n次乘法和n 1次加法c中有n2个元素 故c需要n3次乘法和n2 n 1 次加法示例5汉诺塔问题大梵天创造世界的时候做了三根金刚石柱子 在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上 并且规定 在小圆盘上不能放大圆盘 在三根柱子之间一次只能移动一个圆盘 18 1 3计算思维 汉诺塔问题分析假设有n黄金圆盘 移动次数是f n 有f 1 1 f 2 3 f 3 7 f k 1 2 f k 1故f n 2n 1 时间复杂性记作O 2n f 64 264 1 18446744073709551615假如每秒钟移动一次 一个365天 则约需要584942417355年 即5849亿年而地球的寿命才45亿年 假使用计算机进行每秒1亿次的移动 也需要5849年 时间复杂性 O 1 O logn O n O nlogn O n2 O n3 O nk O 2n 当n值稍大时 O 2n 的问题就无法计算了 19 4 图灵测试机器能有智能吗 换一句话来 通过什么样的测试机器才能称拥有智能 1 3计算思维 无法判断对方是人还是计算机 那么就可以认为计算机具有同人相当的智力 测试场景 20 5 计算思维基本方法从方法论的角度来说 计算思维的核心是计算思维方法 1 3计算思维 约简 嵌入 转化和仿真等方法 用来把一个看来困难的问题重新阐释成一个我们知道问题怎样解决的思维方法 递归方法 并行方法 把代码译成数据又能把数据译成代码的方法 多维分析推广的类型检查方法 抽象和分解方法 用来控制庞杂的任务或进行巨大复杂系统设计 基于关注分离的方法 SoC方法 计算思维方法 来自数学和工程 来自计算机科学自身 21 1 3计算思维 选择合适