PPT48344-00龚沛曾-大基第1章

1,第1章计算机与计算思维基础,1.1引言1.2计算机的诞生和发展1.2.1计算机的诞生1.2.2计算机的发展1.2.3计算机的分类1.2.4计算机的应用1.3计算机的新技术1.4计算思维基础,2,1.1引言,人类为什么要发明计算机？人的计算速度很低祖冲之计算至小数点后7位数用了15年计算3030的行列式需要几个人年中国第一棵原子弹研制时，数百位科学家在大礼堂打算盘早期的计算工具算筹春秋战国时期世界上最早的计算工具算盘中国唐代第一种手动式计数器沿有至今计算尺1622年手动式，上世纪70年代被计算器取代可进行加、减、乘、除、指数、三角函数加法器1642年机械式，只能做加法,3,计算器1673年德国GottfriedLeibniz，机械式可进行加、减、乘、除和开方差分机和分析机,查尔斯.巴贝奇1812年差分机1834年分析机,分析机：体现了现代电子计算机的结构、设计思想被称为现代通用计算机的雏形,1.1引言,4,（1）M的状态：接受状态、进位状态。初始时处于进位状态。（2）从右向左扫描纸带。进位状态：读到0或空白，则改写1，进入接受状态，立即停机；读到1，则改写为0，状态保住不变，读写头左移。,1.计算机的诞生图灵机、ENIAC和冯诺依曼体系结构在理论上、工作原理、体系结构上奠定现代电子计算机的基础图灵机(Turingmachine，TM)阿兰图灵（AlanMathisonTuring，19121954）解决问题：什么是计算？什么是可计算性？组成：计算X+1的图灵机M,纸带,读写头,1.2计算机的诞生和发展,1.通用图灵机,1.2计算机的诞生和发展,通用图灵机,图灵机M,输入,输出,图灵机M的输出,图灵机程序通用图灵机计算机有时说的图灵机是指通用图灵机,6,图灵机的能力=高级程序设计语言=现代通用计算机邱奇、图灵和哥德尔断言：一切直觉上能行可计算的函数都可用图灵机计算，反之亦然邱奇图灵论题,世界上的问题,可计算的：图灵机可计算的就是可计算的,不可计算的,图灵的贡献,图灵机模型：解决了可计算问题计算机的理论问题,图灵测试：回答了什么样的机器具有智能人工智能的理论基础,美国计算机学会ACM于1966年创立了“图灵奖”,计算机科学之父,人工智能之父,1.2计算机的诞生和发展,7,图灵测试机器能有智能吗？换一句话来，通过什么样的测试机器才能称拥有智能？,无法判断对方是人还是计算机，那么就可以认为计算机具有同人相当的智力,测试场景,1.2计算机的诞生和发展,8,ENIAC（电子数字积分计算机）1946.21955.10宾州大学,每秒5千次加减运算没有存储器采用十进制,第一款商用计算机：UNIVAL1947年，莫奇莱和埃克特,仅表明电子计算机时代的到来,1.2计算机的诞生和发展,9,冯诺依曼体系结构计算机人类第二台计算机；EDVAC（离散变量自动电子计算机）1945年冯诺依曼参与研制并且发表：关于EDVAC的报告草案,采用二进制存储程序：程序和数据一起存储在内存中五个部分：运算器、控制器、存储器、输入设备和输出设备,奠定了现代计算机体系结构和工作原理迄今为止的计算机都采用这种思想，称为冯诺依曼计算机,1.2计算机的诞生和发展,10,2.计算机的分代,电子管,晶体管,集成电路,大规模集成电路,1.2计算机的诞生和发展,11,发展趋势：微型化、巨型化、网络化和智能化未来新型计算机,光计算机用光束代替电子进行计算和存储具有超强的并行处理能力和超高速的运算速度,生物计算机（分子计算机）采用由生物工程技术产生的蛋白质分子芯片：信息以波的形式传播运算速度比当今最新一代计算机快10万倍，能耗仅有十分之一巨大的存储能力,量子计算机遵循量子力学规律，进行高速数学和逻辑运算、存储及处理量子信息的物理装置中国科学技术大学潘建伟：2017年5月，光量子计算机,1.2计算机的诞生和发展,12,3.计算机的分类,按综合性能指标分类,高性能计算机（巨型机或大型机）：速度最快、处理能力最强、最快：神威太湖之光每秒9.3亿亿次浮点运算2016.11,工作站：介于PC与小型机之间高档微机系统高分辨率、大容量内外存，图形功能较强,微型计算机：桌面型计算机、笔记本电脑、平板电脑、移动设备,服务器：网络环境中对外提供服务的计算机系统,按用途分类,通用机,专用机,嵌入式计算机：数量超过PC,1.2计算机的诞生和发展,13,4.计算机的应用类型1.科学计算2.数据处理3.电子商务B2B阿里巴巴B2C京东商城C2C淘宝网4.过程控制5.CAD/CAM/CIMS6.多媒体技术7.人工智能机器学习、深度学习,AlphaGo与李世石的人机大战,1.2计算机的诞生和发展,14,1.大数据具有海量、高增长率和多样化的信息资产，它需要全新的处理模式来增强决策力、洞察发现力和流程优化能力四个特征：Volume数据量巨大单位：PB、EB、ZBVariety数据类型繁多5%是结构性，95%是非结构性Velocity要求处理速度快，时效性高。Value数据价值密度相对较低大数据思维：不是抽样统计不是统计1000或10000人，而是处理全部人员信息允许不精确和混杂性允许某些数据不准确，各种数据类型都有不是因果关系，而是相互关系应用案例：阿里信用贷款、京东慧眼,1.3计算机的新技术,2.云计算“云”：对计算机集群的一种形象比喻，每一群包括了几十台、甚至上百万台计算机，通过互联网随时随地为用户提供各种资源和服务，用户只需要一个能上网的终端设备获得资源,1.3计算机的新技术,16,三个特点：超大规模，弹性伸缩“云”的规模和计算能力相当巨大可以根据需求可以动态伸缩资源抽象，虚拟化所有资源均被抽象和虚拟化了，用户可以采用按需支付的方式购买。高可靠性安全的数据存储方式，能够保证数据的可靠性，用户无需担心软件的升级更新、病毒攻击和数据丢失云服务种类：IaaSInfrastructure-as-a-Service基础架构即服务例如：云存储、云主机、云服务器PaaSPlatform-as-a-Service平台即服务云数据库、云开发平台SaaSSoftware-as-a-Service软件即服务如：阿里云提供的短信服务、邮件推送,1.3计算机的新技术,3.物联网TheInternetofthings物物相连的互联网通过射频识别、红外感应器、全球定位系统等各种传感设备，按照协议，把任何物品与互联网相连接，进行信息交换和通信，实现对物品的智能化识别、定位、跟踪、监控和管理的一种网络，是互联网的延伸与扩展。关键技术：RFID技术射频识别技术传感技术各种类型的传感器嵌入式技术位置服务技术IPv6技术,1.3计算机的新技术,4.虚拟现实VirtualRealityVR利用计算机等设备产生一个逼真的三维视觉、触觉、嗅觉等多种感官体验的虚拟世界，从而使处于虚拟世界中的人产生一种身临其境的感觉。在这个虚拟世界中，人们可直接观察周围世界及物体的内在变化，与其中的物体之间进行自然的交互，并能实时产生与真实世界相同的感觉，使人与计算机融为一体。三个特征：沉浸性用户感觉到置身于虚拟世界之中交互性用户与虚拟世界交互想象性虚拟的环境是人想象出来的,1.3计算机的新技术,常见设备：输入设备交互设备：数据手套、三维控制器、三维扫描仪三维定位跟踪设备：电磁跟踪系统、声学跟踪系统、光学跟踪系统、机械跟踪系统、惯性位置跟踪系统等。输出设备视觉感知设备：头盔式显示器、洞穴式立体显示装置等听觉感知设备：耳机、喇叭等触觉反馈装置,1.3计算机的新技术,三大科学思维,理论思维（推理思维）特征：以推理和演绎为特征代表学科：数学,实验思维（实证思维）特征：观察和总结自然规律代表学科：物理学,计算思维（构造思维）特征：设计和构造代表学科：计算机科学,1.4计算思维基础,示例1：计算f(x)是a,b上的积分数学方法：牛顿莱布尼兹f(x)F(x)计算思维：黎曼积分对a,b进行n等分计算小矩形面积累加,计算思维：运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动,1.4计算思维基础,22,迭代法迭代过程：1!=12!=1!*2n!=(n-1)!*n程序：s=1;for(i=1;i=n;i+)s=s*i;经典迭代：牛顿迭代法J20研制过程就是迭代过程：原型机1原型机2原型机3原型机4,示例2：计算n的阶乘f(n)=n!,递归,分解,问题,小问题,n!,(n-1)!,intfac(intn)if(n=1)return(1);elsereturn(fac(n-1)*n);,voidmain()inty;y=f(4)couty;,1.4计算思维基础,23,示例1.3哥尼斯堡七桥在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛以及岛与河岸连接起来。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？,1计算思维的本质：抽象和自动化抽象：完全超越物理的时空观，并完全用符号来表示数学抽象是一种特例,哥尼斯堡七桥问题的抽象,自动化：机械地一步一步自动执行，其基础和前提是抽像,1.4计算思维基础,案例：计算机破案张三在家中遇害，侦查中发现A、B、C、D四人到过现场。A说：“我没有杀人。”B说：“C是凶手。”C说：“杀人者是D”D说：“C在冤枉好人。”侦查员经过判断四人中有三人说的是真话，四人中有且只有一人是凶手，凶手到底是谁？,24,1.4计算思维基础,抽象,用0表示不是凶手，1表示凶手,则对四人说话、侦查员判断如下表,25,1.4计算思维基础,自动化,采用穷举法（枚举法）在每个人的取值范围0，1的所有可能中进行搜索，不能遗漏也不要重复，若表的组合条件同时满足，即为凶手。相应的伪代码为：ForA=0To1ForB=0TO1ForC=0To1ForD=0To1If(A=0)+(C=1)+(D=1)+(D=0)=3And(A+B+C+D=1)PrintA,B,C,D/输出的值是1的为凶手,1.4计算思维基础,27,2计算思维的特征是属于人的思维方式，不是计算机的思维方式递归、迭代、黎曼积分早已提出，是人类赋予计算机可以由人执行，也可以由计算机执行是思想，不是人造物是概念化，不是程序化3计算思维的基本问题可计算性是指可以使用计算机在有限步骤内解决邱奇图灵论题：图灵机可以计算的就是可计算的计算复杂性时间复杂性和空间复杂性,1.4计算思维基础,示例4矩阵相乘：Cnn=AnnBnn,计算cij需要n次乘法和n-1次加法c中有n2个元素，故c需要n3次乘法和n2*(n-1)次加法示例5汉诺塔问题大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。,1.4计算思维基础,29,汉诺塔问题分析：假设有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)假定n=64，则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)的问题就无法计算了,1.4计算思维基础,30,4图灵测试机器能有智能吗？换一句话来，通过什么样的测试机器才能称拥有智能？,无法判断对方是人还是计算机，那么就可以认为计算机具有同人相当的智力,测试场景,1.4计算思维基础,31,5计算思维基本方法计算思维的核心是计算思维方法,约简、嵌入、转化和仿真等方法，用来把一个看来困难的问题重新阐释成一个我们知道问题怎样解决的思维方法；递归方法、并行方法、把代码译成数据又能把数据译成代码的方法、多维分析推广的类型检查方法；抽象和分解方法，用来控制庞杂的任