算机文化与计算思维.ppt

1,第一章 计算机文化与计算思维,1.1 引言 1.2 计算机的诞生和发展 1.3 计算思维基础,2,1.1 引言,人类为什么要发明计算机？人的计算速度很低 祖冲之计算至小数点后7位数用了15年 计算3030的行列式需要几个人年 中国第一棵原子弹研制时，数百位科学家在大礼堂打算盘 早期的计算工具 算 筹 春秋战国时期世界上最早的计算工具 算 盘 中国唐代 第一种手动式计数器 沿有至今 计算尺 1622年 手动式，上世纪70年代被计算器取代可进行加、减、乘、除、指数、三角函数 加法器 1642年 机械式，只能做加法,1822 差分机,1833 分析机,计算机发展史,人类追求的计算工具,算筹中国最早的计算工具,算筹是我国古代的计算工具。筹即小竹棍或小木棍也有用骨或金属材料制成的，古人用它来进行计算，称为算筹。,计算机的起源,计算机发展史,公元600年左右，我国出现新的计算工具算盘。,计算机发展史,Blaise Pascal帕斯卡,计算机发展史,1642年，年仅19岁的法国伟大科学家帕斯卡引用算盘的原理，发明了第一部机械式计算器，在他的计算器中有一些互相联锁的齿轮，一个转过十位的齿轮会使另一个齿轮转过一位，人们可以像拨电话号码盘那样，把数字拨进去，计算结果就会出现在另一个窗口中，但是只能做加减计算。,1812年差分机,查尔斯.巴贝奇 1834年设计的分析机,由许多轮子组成的保存数据的存储库；运算装置；能对操作顺序进行控制，并选择所需处理的数据以及输出结果的装置。主要用于计算多项式，运算精度达到小数点后6位,是历史上最早的专用计算机和通用计算机的完整构思.,计算机发展史,9,1.1 引言,计算器 1673年德国Gottfried Leibniz，机械式 可进行加、减、乘、除和开方 差分机和分析机,查尔斯.巴贝奇 1812年差分机 1834年分析机,分析机：体现了现代电子计算机的结构、设计思想 被称为现代通用计算机的雏形,10,（1）M的状态：接受状态、进位状态。初始时处于进位状态。（2）从右向左扫描纸带。进位状态：读到0或空白，则改写1，进入接受状态，立即停机；读到1，则改写为0，状态保住不变，读写头左移。,1.2 计算机的诞生和发展,计算机的诞生 图灵机、ENIAC和冯诺依曼体系结构在理论上、工作原理、体系结构上奠定现代电子计算机的基础 图灵机(Turing machine，TM)阿兰图灵（Alan Mathison Turing，19121954）解决问题；什么是计算？什么是可计算性？组成：计算X+1的图灵机M,纸带,读写头,11,1.2 计算机的诞生和发展,图灵机的能力=高级程序设计语言=现代通用计算机 邱奇、图灵和哥德尔断言：一切直觉上能行可计算的函数都可用图灵机计算，反之亦然邱奇图灵论题,世界上的问题,可计算的：图灵机可计算的就是可计算的,不可计算的,图灵的贡献,图灵机模型：解决了可计算问题 计算机的理论问题,图灵测试：回答了什么样的机器具有智能 人工智能的理论基础,美国计算机学会ACM于1966年创立了“图灵奖”,计算机科学之父,人工智能之父,12,1.2 计算机的诞生和发展,ENIAC（电子数字积分计算机）1946.21955.10 宾州大学,每秒5千次加减运算没有存储器采用十进制,第一款商用计算机：UNIVAL1947年，莫奇莱和埃克特,仅表明电子计算机时代的到来,13,1.2 计算机的诞生和发展,冯诺依曼体系结构计算机 人类第二台计算机；EDVAC（离散变量自动电子计算机）1945年 冯诺依曼参与研制并且发表：关于 EDVAC的报告草案,采用二进制 存储程序：程序和数据一起存储在内存中 五个部分：运算器、控制器、存储器、输入设备和输出设备,奠定了现代计算机体系结构和工作原理迄今为止的计算机都采用这种思想，称为冯诺依曼计算机,14,计算机的分代,电子管,晶体管,集成电路,大规模集成电路,1.2 计算机的诞生和发展,15,发展趋势：微型化、巨型化、网络化和智能化 未来新型计算机,光计算机 利用光子取代电子进行数据运算、传输和存储 不同波长的表示不同的数据 优点：超高速 缺点：体积庞大,生物计算机（分子计算机）20世纪80年代中期开始研制 采用了生物芯片,量子计算机 利用处于多现实态下的原子进行运算的计算机，这种多现实态是量子力学的标志。,1.2 计算机的诞生和发展,16,计算机的分类,按综合性能指标分类,高性能计算机（巨型机或大型机）：速度最快、处理能力最强、最快：Titan 每秒2亿亿次浮点运算 中国：天河1A 每秒4.70千万亿次浮点运算 第8,工作站：介于PC与小型机之间高档微机系统 高分辨率、大容量内外存，图形功能较强,微型计算机：桌面型计算机、笔记本电脑、平板电脑、移动设备,服务器：网络环境中对外提供服务的计算机系统,按用途分类,通用机,专用机,1.2 计算机的诞生和发展,嵌入式计算机：数量超过PC,17,1.2 计算机的诞生和发展,计算机的应用类型1.科学计算2.数据处理3.电子商务 B2B 阿里巴巴 B2C 京东商城 C2C 淘宝网4.过程控制5.CAD/CAM/CIMS6.多媒体技术 7.人工智能,卡斯帕罗夫对弈“深蓝”,18,1.2 计算机的诞生和发展,计算机文化 物质文化 计算机的软、硬件设备以及使用方法 非物质文化 计算机学科对自然科学和社会科学等的广泛渗透，创造和形成了新的科学思想、科学方法、科学精神、价值标准等 计算机应用改变了传统社会，形成了网络社会等虚拟的社会形态 产生了相应的语言、风俗、道德、法律等 最重要的是计算机网络文化,19,示例1：计算f(x)是a,b上的积分 数学方法 牛顿莱布尼兹：f(x)F(x)计算思维 黎曼积分：对a,b进行n等分 计算小矩形面积 累加,三大科学思维,计算思维：运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动,1.3 计算思维,理论思维（推理思维）特征：以推理和演绎为特征 代表学科：数学,实验思维（实证思维）特征：观察和总结自然规律 代表学科：物理学,计算思维（构造思维）特征：设计和构造 代表学科：计算机科学,20,迭代法 迭代过程：1!=1 2!=1!*2 3!=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!,int fac(int n)if(n=1)return(1);else return(fac(n-1)*n);,void main()int y;y=f(4)couty;,21,示例1.3 哥尼斯堡七桥问题 18世纪经典数学问题 在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛以及岛与河岸连接起来。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？,1计算思维的本质：抽象和自动化 抽象：完全超越物理的时空观，并完全用符号来表示 数学抽象是一种特例,1.3 计算思维,哥尼斯堡七桥问题,哥尼斯堡七桥问题的抽象,自动化：机械地一步一步自动执行，其基础和前提是抽像,22,2计算思维的特征 是属于人的思维方式，不是计算机的思维方式 递归、迭代、黎曼积分早已提出，是人类赋予计算机 可以由人执行，也可以由计算机执行 是思想，不是人造物 是概念化，不是程序化 3计算思维的基本问题 可计算性 一个问题是可计算的是指可以使用计算机在有限步骤内解决 邱奇图灵论题：图灵机可以计算的就是可计算的 计算复杂性 时间复杂性和空间复杂性,1.3 计算思维,23,示例4 矩阵相乘：Cnn=AnnBnn,1.3 计算思维,计算cij需要n次乘法和n-1次加法 c中有n2个元素，故c需要n3次乘法和n2*(n-1)次加法示例5 汉诺塔问题 大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上 从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗 门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次 只能移动一个圆盘。,24,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 假如每秒钟移动一次，一个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)的问题就无法计算了,25,4图灵测试 机器能有智能吗？换一句话来，通过什么样的测试机器才能称拥有智能？,1.3 计算思维,无法判断对方是人还是计算机，那么就可以认为计算机具有同人相当的智力,测试场景,26,5计算思维基本方法 从方法论的角度来说，计算思维的核心是计算思维方法,1.3 计算思维,约简、嵌入、转化和仿真等方法，用来把一个看来困难的问题重新阐释 成一个我们知道问题怎样解决的思维方法；递归方法、并行方法、把代码译成数据又能把数据译成代码的方法、多维分析推广的类型检查方法；抽象和分解方法，用来控制庞杂的任务或进行巨大复杂系统设计；基于关注分离的方法（SoC方法）；,计算思维方法,来自数学和工程,来自计算机科学自身,27,1.3 计算思维,选择合适的方式去陈述一个问题的方法、对一个问题的相关方面建模 使其易于处理的思维方法；按照预防、保护及通过冗余、容错、纠错的方式，并从最坏情况进行 系统恢复的一种思维方法；启发式推理，用于在不确定情况下的规划、学习和调度的思维方法；利用海量数据来加快计算,在时间和空间之间，在处理能力和存储容量 之间进行折衷的思维方法。,6计算思维应用 计算物理 计算化学 计算生物学 计算经济学,