同济大学计算机基础第1章计算机文化与计算思维第六版.

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