安徽大学《计算机基础》课件-第1章计算机与计算思维基础

1第1章

计算机与计算思维基础1.1引言1.2计算机的诞生和发展1.2.1计算机的诞生1.2.2计算机的发展1.2.3计算机的分类1.2.4计算机的应用1.3计算机的新技术1.4计算思维基础安徽大学《计算机基础》E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC244604102

1.1引言人类为什么要发明计算机？■人的计算速度很低

◆祖冲之计算π至小数点后7位数用了15年

◆

计算30×30的行列式需要几个人年

◆

中国第一棵原子弹研制时，数百位科学家在大礼堂打算盘■

早期的计算工具

◆算筹春秋战国时期 世界上最早的计算工具

◆算盘中国唐代第一种手动式计数器沿有至今

◆计算尺1622年 手动式，上世纪70年代被计算器取代

可进行加、减、乘、除、指数、三角函数

◆

加法器1642年 机械式，只能做加法

E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC244604103

◆

计算器1673年 德国GottfriedLeibniz，机械式 可进行加、减、乘、除和开方◆差分机和分析机

查尔斯.巴贝奇

1812年差分机1834年分析机

分析机：体现了现代电子计算机的结构、设计思想被称为现代通用计算机的雏形1.1引言E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC244604104（1）M的状态：接受状态、进位状态。初始时处于进位状态。（2）从右向左扫描纸带。进位状态：读到0或空白，则改写1，进入接受状态，立即停机；读到1，则改写为0，状态保住不变，读写头左移。1.计算机的诞生

图灵机、ENIAC和冯·诺依曼体系结构在理论上、工作原理、体系结构

上奠定现代电子计算机的基础

◆图灵机(Turingmachine，TM)

阿兰·图灵（AlanMathisonTuring，1912—1954）

解决问题：什么是计算？什么是可计算性？组成：计算X+1的图灵机M纸带

读写头

1.2计算机的诞生和发展E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC244604101.通用图灵机1.2计算机的诞生和发展通用图灵机图灵机M输入输出图灵机M的输出图灵机

程序通用图灵机

计算机

有时说的图灵机是指通用图灵机E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC244604106

图灵机的能力=高级程序设计语言=现代通用计算机

邱奇、图灵和哥德尔断言：一切直觉上能行可计算的函数都可用图灵机计算，反之亦然邱奇－图灵论题

世界上的问题

可计算的：图灵机可计算的就是可计算的

不可计算的

图灵的贡献

图灵机模型：解决了可计算问题

计算机的理论问题图灵测试：回答了什么样的机器具有智能人工智能的理论基础美国计算机学会ACM于1966年创立了“图灵奖”计算机科学之父人工智能之父1.2计算机的诞生和发展E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC244604107图灵测试机器能有智能吗？

换一句话来，通过什么样的测试机器才能称拥有智能？无法判断对方是人还是计算机，那么就可以认为计算机具有同人相当的智力测试场景

1.2计算机的诞生和发展E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC244604108

◆ENIAC（电子数字积分计算机）1946.2~1955.10宾州大学每秒5千次加减运算没有存储器采用十进制第一款商用计算机：UNIVAL1947年，莫奇莱和埃克特仅表明电子计算机时代的到来

1.2计算机的诞生和发展E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC244604109

◆

冯·诺依曼体系结构计算机

人类第二台计算机；EDVAC（离散变量自动电子计算机）1945年

冯·诺依曼参与研制并且发表：关于EDVAC的报告草案采用二进制存储程序：程序和数据一起存储在内存中

五个部分：运算器、控制器、存储器、输入设备和输出设备

奠定了现代计算机体系结构和工作原理迄今为止的计算机都采用这种思想，称为冯·诺依曼计算机

1.2计算机的诞生和发展E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC24460410102.计算机的分代时代年份器件运算速度软件应用一46-58电子管每秒几千次机器语言汇编语言科学计算军事领域二58-64晶体管每秒几十万次高级语言数据处理工业控制三64-70集成电路每秒几百万次操作系统文字处理图形处理四71年迄今大规模集成电路达到每秒亿亿次数据库、网络等各个领域电子管晶体管集成电路大规模集成电路1.2计算机的诞生和发展E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC2446041011

◆发展趋势：微型化、巨型化、网络化和智能化

◆未来新型计算机①光计算机

用光束代替电子进行计算和存储

具有超强的并行处理能力和超高速的运算速度②

生物计算机（分子计算机）采用由生物工程技术产生的蛋白质分子

芯片：

信息以波的形式传播

运算速度比当今最新一代计算机快10万倍，

能耗仅有十分之一

巨大的存储能力③

量子计算机

遵循量子力学规律，

进行高速数学和逻辑运算、存储及处理量子信息的物理装置

中国科学技术大学潘建伟：2017年5月，光量子计算机1.2计算机的诞生和发展E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC24460410123.计算机的分类按综合性能指标分类高性能计算机（巨型机或大型机）：速度最快、处理能力最强、最快：神威·太湖之光

每秒9.3亿亿次浮点运算2016.11 工作站：介于PC与小型机之间高档微机系统

高分辨率、大容量内外存，图形功能较强微型计算机：

桌面型计算机、笔记本电脑、平板电脑、移动设备

服务器：网络环境中对外提供服务的计算机系统按用途分类通用机专用机嵌入式计算机：数量超过PC

1.2计算机的诞生和发展E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC24460410134.计算机的应用类型

1.科学计算

2.数据处理

3.电子商务①B2B阿里巴巴 ②B2C京东商城 ③C2C淘宝网

4.过程控制

5.CAD/CAM/CIMS

6.多媒体技术

7.人工智能

机器学习、深度学习AlphaGo与李世石的人机大战1.2计算机的诞生和发展E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC24460410141.大数据

具有海量、高增长率和多样化的信息资产，

它需要全新的处理模式来增强决策力、洞察发现力和流程优化能力四个特征：◆Volume数据量巨大

单位：PB、EB、ZB◆Variety数据类型繁多

5%是结构性，95%是非结构性◆Velocity要求处理速度快，时效性高。◆Value数据价值密度相对较低

大数据思维：◆不是抽样统计

不是统计1000或10000人，而是处理全部人员信息◆允许不精确和混杂性

允许某些数据不准确，各种数据类型都有◆不是因果关系，而是相互关系

应用案例：阿里信用贷款、京东慧眼1.3计算机的新技术E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC244604102.云计算

“云”：对计算机集群的一种形象比喻，

每一群包括了几十台、甚至上百万台计算机，

通过互联网随时随地为用户提供各种资源和服务，

用户只需要一个能上网的终端设备获得资源1.3计算机的新技术用户企业过去购买计算机、存储设备搭建服务器购买发电设备建设电厂现在向云端租用服务器，申请各种资源和服务按需购买向国家电网购买电力按需购买

国家的电力系统、自来水网是一种公共设施

云也是一种公共设施。E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC2446041016三个特点：◆超大规模，弹性伸缩

“云”的规模和计算能力相当巨大

可以根据需求可以动态伸缩◆资源抽象，虚拟化

所有资源均被抽象和虚拟化了，

用户可以采用按需支付的方式购买。◆高可靠性

安全的数据存储方式，能够保证数据的可靠性，

用户无需担心软件的升级更新、病毒攻击和数据丢失云服务种类：◆IaaSInfrastructure-as-a-Service

基础架构即服务

例如：云存储、云主机、云服务器◆PaaS

Platform-as-a-Service平台即服务

云数据库、云开发平台◆SaaSSoftware-as-a-Service软件即服务如：阿里云提供的短信服务、邮件推送1.3计算机的新技术E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC244604103.物联网TheInternetofthings物物相连的互联网

通过射频识别、红外感应器、全球定位系统等各种传感设备，

按照协议，把任何物品与互联网相连接，进行信息交换和通信，

实现对物品的智能化识别、定位、跟踪、监控和管理的一种网络，

是互联网的延伸与扩展。关键技术：◆RFID技术

射频识别技术◆传感技术

各种类型的传感器◆嵌入式技术◆位置服务技术◆IPv6技术1.3计算机的新技术E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC244604104.虚拟现实VirtualRealityVR

利用计算机等设备产生一个逼真的三维视觉、触觉、嗅觉等多种感官

体验的虚拟世界，从而使处于虚拟世界中的人产生一种身临其境的感

觉。在这个虚拟世界中，人们可直接观察周围世界及物体的内在变化，

与其中的物体之间进行自然的交互，并能实时产生与真实世界相同的

感觉，使人与计算机融为一体。三个特征：◆沉浸性

用户感觉到置身于虚拟世界之中◆交互性

用户与虚拟世界交互◆想象性

虚拟的环境是人想象出来的1.3计算机的新技术E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC24460410常见设备：

输入设备

交互设备：数据手套、三维控制器、三维扫描仪

三维定位跟踪设备：电磁跟踪系统、声学跟踪系统、

光学跟踪系统、机械跟踪系统、

惯性位置跟踪系统等。

输出设备

视觉感知设备：头盔式显示器、洞穴式立体显示装置等

听觉感知设备：耳机、喇叭等

触觉反馈装置1.3计算机的新技术E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC24460410三大科学思维理论思维（推理思维）

特征：以推理和演绎为特征代表学科：数学实验思维（实证思维）特征：观察和总结自然规律代表学科：物理学计算思维（构造思维）

特征：设计和构造代表学科：计算机科学1.4计算思维基础E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC24460410示例1：计算f(x)是[a,b]上的积分数学方法：牛顿─莱布尼兹f(x)F(x)

计算思维：黎曼积分①对[a,b]进行n等分②计算小矩形面积③累加计算思维：

运用计算机科学的基础概念进行问题求解、

系统设计、以及人类行为理解等涵盖计算机

科学之广度的一系列思维活动1.4计算思维基础E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC2446041022

迭代法迭代过程：1!=12!=1!*2……n!=(n-1)!*n

程序：s=1;for(i=1;i<=n;i++)s=s*i;

经典迭代：牛顿迭代法

J20研制过程就是迭代过程：

原型机1原型机2原型机3原型机4示例2：计算n的阶乘f(n)=n!1.4计算思维基础E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC2446041023

递归

分

解问题小问题n!(n-1)!intfac(intn){if(n==1)return(1);else return(fac(n-1)*n);}

voidmain(){inty;y=f(4)cout<<y;}1.4计算思维基础E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC2446041024示例1.3哥尼斯堡七桥在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛以及岛与河岸连接起来。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？1．计算思维的本质：抽象和自动化

抽象：完全超越物理的时空观，

并完全用符号来表示数学抽象是一种特例

哥尼斯堡七桥问题的抽象

自动化：机械地一步一步自动执行，

其基础和前提是抽像

1.4计算思维基础E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC24460410案例：计算机破案

张三在家中遇害，侦查中发现A、B、C、D

四人到过现场。A说：“我没有杀人。”B说：“C是凶手。”C说：“杀人者是D”D说：“C在冤枉好人。”侦查员经过判断四人中有三人说的是真话，四人中有且只有一人是凶手，凶手到底是谁？251.4计算思维基础E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC24460410抽象用0表示不是凶手，1表示凶手,则对四人说话、侦查员判断如下表

261.4计算思维基础E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC24460410自动化采用穷举法（枚举法）

在每个人的取值范围[0，1]的所有可能中进行搜索，不能遗漏也不要重复，若表的组合条件同时满足，即为凶手。相应的伪代码为：ForA=0To1ForB=0TO1

ForC=0To1

ForD=0To1

If((A=0)+(C=1)+(D=1)+(D=0))=3And(A+B+C+D=1))

PrintA,B,C,D//输出的值是1的为凶手1.4计算思维基础E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC24460410282．计算思维的特征

◆

是属于人的思维方式，不是计算机的思维方式递归、迭代、黎曼积分早已提出，

是人类赋予计算机

◆

可以由人执行，也可以由计算机执行

◆

是思想，不是人造物

◆

是概念化，不是程序化

3．计算思维的基本问题

◆

可计算性是指可以使用计算机在有限步骤内解决

邱奇－图灵论题：图灵机可以计算的就是可计算的

◆

计算复杂性

时间复杂性和空间复杂性

1.4计算思维基础E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC24460410示例4矩阵相乘：Cn×n=An×n×Bn×n

计算cij需要n次乘法和n-1次加法

c中有n2个元素，故c需要n3次乘法和n2*(n-1)次加法示例5汉诺塔问题大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根

柱子之间一次只能移动一个圆盘。

1.4计算思维基础E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB87DC2446041030汉诺塔问题分析：假设有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计算思维基础E6636B02012BD195C019CE06C16E3054C33D0DE32711A616D0819A103DE0A8FF8F5D3603BC41BA96BB46DCF0472B73A72FC0F2BE2AA53AFE6A06217057F5472DBF2DB6715F2B3FB