计算机文化与计算思维

1、1第一章第一章 计算机文化与计算思维计算机文化与计算思维1.1 引言引言 1.2 计算机计算机的诞生和发展的诞生和发展 1.3 计算思维基础计算思维基础2 1.1 1.1 引言引言 人类为什么要发明计算机？ 人的计算速度很低 祖冲之计算祖冲之计算至小数点后至小数点后7位数用了位数用了15年年 计算计算3030的行列式需要几个人年的行列式需要几个人年 中国第一棵原子弹研制时，数百位科学家在大礼堂打算盘中国第一棵原子弹研制时，数百位科学家在大礼堂打算盘 早期的计算工具 算算 筹筹 春秋战国时期春秋战国时期世界上最早的计算工具世界上最早的计算工具 算算 盘盘 中国唐代中国唐代 第一种手动式计数器第一

2、种手动式计数器 沿有至今沿有至今 计算尺计算尺 1622年年 手动式，上世纪手动式，上世纪70年代被计算器取代年代被计算器取代可进行加、减、乘、除、指数、三角函数可进行加、减、乘、除、指数、三角函数 加法器加法器 1642年年 机械式，只能做加法机械式，只能做加法1642 Blaise Pascal1822 1822 差分机差分机1833 分析机分析机电子计算机时代电子计算机时代计算机发展史计算机发展史 人类追求的计算工具人类追求的计算工具算筹算筹中国最早的计算工具中国最早的计算工具 算筹是我国古代的计算筹是我国古代的计算工具。筹即小竹算工具。筹即小竹棍或小木棍棍或小木棍也有用骨也有用骨或金属

3、材料制成的或金属材料制成的，古人用它来进行计算，古人用它来进行计算，称为算筹。称为算筹。计算机的起源计算机的起源计算机发展史计算机发展史公元公元600年左右，我年左右，我国出现新的计算工国出现新的计算工具具算盘算盘。计算机发展史计算机发展史机械式计算机机械式计算机Blaise Pascal帕斯卡帕斯卡 计算机发展史计算机发展史1642年，年仅年，年仅19岁的法国伟大岁的法国伟大科学家科学家帕斯卡帕斯卡引用算盘的原理引用算盘的原理，发明了第一部机械式计算器，发明了第一部机械式计算器，在他的计算器中有一些互相，在他的计算器中有一些互相联锁的齿轮，一个转过十位的联锁的齿轮，一个转过十位的齿轮会使另一

4、个齿轮转过一位齿轮会使另一个齿轮转过一位，人们可以像拨电话号码盘那，人们可以像拨电话号码盘那样，把数字拨进去，计算结果样，把数字拨进去，计算结果就会出现在另一个窗口中，但就会出现在另一个窗口中，但是是只能做加减计算只能做加减计算。18121812年差分机年差分机 查尔斯查尔斯. .巴贝奇巴贝奇 1834年设计的分析机年设计的分析机 由许多轮子组成的保存数据的存储库；由许多轮子组成的保存数据的存储库；运算装置；能对操作顺序进行控制，并选运算装置；能对操作顺序进行控制，并选择所需处理的数据以及输出结果的装置。择所需处理的数据以及输出结果的装置。主要用于计算多项式，运算精度达到小数主要用于计算多项式

5、，运算精度达到小数点后点后6 6位位巴贝奇的分析机巴贝奇的分析机是历史上最早的专是历史上最早的专用计算机和通用计用计算机和通用计算机的完整构思算机的完整构思.ENIAC：长长30.4830.48米，宽米，宽1 1米，占米，占地面积地面积170170平方米，平方米，3030个操作台，个操作台，约相当于约相当于1010件普通房间的大小，件普通房间的大小，重达重达3030吨，耗电量吨，耗电量150150千瓦，造千瓦，造价价4848万美元。它使用万美元。它使用1800018000个电个电子管，子管，7000070000个电阻，个电阻，1000010000个电个电容，容，15001500个继电器，个继电

6、器，60006000多个开多个开关，每秒执行关，每秒执行50005000次加法或次加法或400400次乘法，是继电器计算机的次乘法，是继电器计算机的10001000倍、倍、手工计算的手工计算的2020万倍万倍。 计算机发展史计算机发展史 第一台电子计算机（第一台电子计算机（ENIAC）9 1.1 1.1 引言引言 计算器计算器 1673年年德国德国Gottfried Leibniz，机械式，机械式 可进行加、减、乘可进行加、减、乘、除和开方、除和开方 差分机和分析机差分机和分析机 查尔斯查尔斯. .巴贝奇巴贝奇 1812年差分机年差分机 1834年分析机年分析机 分析机：体现了现代电子计算机的

7、结构、设计思想分析机：体现了现代电子计算机的结构、设计思想 被称为现代通用计算机的雏形被称为现代通用计算机的雏形10（1）M的状态：接受状态、进位状态。初始时处于进位状态。的状态：接受状态、进位状态。初始时处于进位状态。（2）从右向左扫描纸带。）从右向左扫描纸带。 进位状态：读到进位状态：读到0或空白，则改写或空白，则改写1，进入接受状态，立即停机；，进入接受状态，立即停机； 读到读到1，则改写为，则改写为0，状态保住不变，读写头左移，状态保住不变，读写头左移。1.2 1.2 计算机的诞生和发展计算机的诞生和发展 计算机的诞生 图灵机、图灵机、ENIAC和冯和冯诺依曼体系结构在理论上、工作原理

8、、体系结诺依曼体系结构在理论上、工作原理、体系结构上奠定现代电子计算机的基础构上奠定现代电子计算机的基础 图灵机图灵机(Turing machine，TM ) 阿兰阿兰图灵（图灵（Alan Mathison Turing ，19121954） 解决问题；解决问题；什么是计算？什么是可计算性？什么是计算？什么是可计算性？ 组成：计算组成：计算X+1的图灵机的图灵机M纸带纸带 读写头读写头 111.2 1.2 计算机的诞生和发展计算机的诞生和发展 图灵机的能力图灵机的能力=高级程序设计语言高级程序设计语言=现代通用计算机现代通用计算机 邱奇、图灵和哥德尔断言：邱奇、图灵和哥德尔断言： 一切直觉上能

9、行可计算的函数都可用图灵机计算，反之亦然一切直觉上能行可计算的函数都可用图灵机计算，反之亦然邱奇邱奇图灵论题图灵论题 世界上的问题 可计算的：图灵机可计算的就是可计算的 不可计算的 图灵的贡献 图灵机模型：解决了可计算问题 计算机的理论问题图灵测试：回答了什么样的机器具有智能 人工智能的理论基础 美国计算机学会美国计算机学会ACM于于1966年创立了年创立了“图灵奖图灵奖” 计算机科学之父计算机科学之父 人工智能之父人工智能之父121.2 1.2 计算机的诞生和发展计算机的诞生和发展 ENIAC（电子数字积分计算机）（电子数字积分计算机） 1946.21955.10 宾州大学宾州大学:每秒每秒

10、5千次加减运算千次加减运算:没有存储器没有存储器:采用十进制采用十进制第一款商用计算机：第一款商用计算机：UNIVAL1947年，莫奇莱和埃克特年，莫奇莱和埃克特仅表明电子计算机时代的到来仅表明电子计算机时代的到来 131.2 1.2 计算机的诞生和发展计算机的诞生和发展 冯冯诺依曼体系结构计算机诺依曼体系结构计算机 人人类第二台计算机；类第二台计算机；EDVAC（离散变量自动电子计算机）（离散变量自动电子计算机） 1945年年 冯冯诺依曼参与研制并且发表：诺依曼参与研制并且发表：关于关于 EDVAC的报告草案的报告草案:采用二进制采用二进制 :存储程序：存储程序：程序和数据一起存储在内存中程

11、序和数据一起存储在内存中 :五个部分：五个部分：运算器、控制器、存储器、输入设备和输出设备运算器、控制器、存储器、输入设备和输出设备 奠定了现代计算机体系结构和工作原理奠定了现代计算机体系结构和工作原理迄今为止的计算机都采用这种思想，称为冯迄今为止的计算机都采用这种思想，称为冯诺依曼计算机诺依曼计算机 14 计算机的分代时代年份器件运算速度软件应用一 46-58电子管每秒几千次 机器语言汇编语言 科学计算军事领域二58-64晶体管每秒几十万次 高级语言数据处理工业控制 三64-70集成电路每秒几百万次 操作系统文字处理图形处理四71年迄今大规模集成电路达到每秒亿亿次 数据库、网络等各个领域电子

12、管电子管晶体管晶体管集成电路集成电路大规模集成电路大规模集成电路1.2 1.2 计算机的诞生和发展计算机的诞生和发展15 发展趋势：微型化、巨型化、网络化和智能化发展趋势：微型化、巨型化、网络化和智能化 未来新型计算机未来新型计算机 光计算机光计算机 利用光子取代电子进行数据运算、传输和存储利用光子取代电子进行数据运算、传输和存储 不同波长的表示不同的数据不同波长的表示不同的数据 优点：超高速优点：超高速 缺点：体积庞大缺点：体积庞大 生物计算机（分子计算机）生物计算机（分子计算机） 2 02 0 世 纪世 纪 8 08 0 年 代 中 期 开 始 研 制年 代 中 期 开 始 研 制 采用了

13、生物芯片采用了生物芯片 量子计算机量子计算机 利用处于多现实态下的原子进行运算的计算机，利用处于多现实态下的原子进行运算的计算机， 这种多现实态是量子力学的标志。这种多现实态是量子力学的标志。 1.2 1.2 计算机的诞生和发展计算机的诞生和发展16 计算机的分类 按综合性能按综合性能指标分类指标分类高性能计算机（高性能计算机（巨型机或大型机巨型机或大型机）：）： 速度最快、处理能力最强、速度最快、处理能力最强、 最快：最快：Titan 每秒每秒2亿亿次浮点运算亿亿次浮点运算 中国：天河中国：天河1A 每秒每秒4.70千万亿次浮点运算千万亿次浮点运算 第第8 工作站工作站：介于介于PCPC与小

14、型机之间高档微机系统与小型机之间高档微机系统 高分辨率、大容量内外存，图形功能较强高分辨率、大容量内外存，图形功能较强微型计算机微型计算机： 桌面型计算机、笔记本电脑、平板电脑、移动设备桌面型计算机、笔记本电脑、平板电脑、移动设备 服务器：网络环境中对外提供服务的计算机系统服务器：网络环境中对外提供服务的计算机系统按用途分类按用途分类通用机通用机专用机专用机1.2 1.2 计算机的诞生和发展计算机的诞生和发展嵌入式计算机：数量超过嵌入式计算机：数量超过PCPC 171.2 1.2 计算机的诞生和发展计算机的诞生和发展 计算机的应用类型1. 科学计算科学计算2. 数据处理数据处理3. 电子商务电

15、子商务 B2B 阿里巴巴阿里巴巴 B2C 京东商城京东商城 C2C 淘宝网淘宝网4. 过程控制过程控制5. CAD/CAM/CIMS6. 多媒体技术多媒体技术 7. .人工智能人工智能卡斯帕罗夫对弈“深蓝” 181.2 1.2 计算机的诞生和发展计算机的诞生和发展 计算机文化 物质文化物质文化 计算机的软、硬件设备以及使用方法计算机的软、硬件设备以及使用方法 非物质文化非物质文化 计算机学科对自然科学和社会科学等的广泛渗透，计算机学科对自然科学和社会科学等的广泛渗透， 创造和形成了新的科学思想、科学方法、科学精神、价值标准等创造和形成了新的科学思想、科学方法、科学精神、价值标准等 计算机应用改

16、变了传统社会，形成了网络社会等虚拟的社会形态计算机应用改变了传统社会，形成了网络社会等虚拟的社会形态 产生了相应的语言、风俗、道德、法律等产生了相应的语言、风俗、道德、法律等 最重要的是计算机网络文化最重要的是计算机网络文化 19示例示例1 1： 计算计算f(x)是是a, b上的积分上的积分 数学方法数学方法 牛顿牛顿莱布尼兹：莱布尼兹： f(x) F(x) 计算思维计算思维 黎曼积分：对黎曼积分：对a, b进行进行n等分等分 计算小矩形面积计算小矩形面积 累加累加 三大科学思维三大科学思维计算思维：计算思维：运用计算机科学的基础概念进行运用计算机科学的基础概念进行问题求解问题求解、系统设计系

17、统设计、 以及以及人类行为理解人类行为理解等涵盖计算机科学之广度的一系列思维活动等涵盖计算机科学之广度的一系列思维活动 1.3 1.3 计算思维计算思维理论思维（推理思维）理论思维（推理思维） 特征：以推理和演绎为特征特征：以推理和演绎为特征 代表学科：数学代表学科：数学 实验思维（实证思维）实验思维（实证思维） 特征：观察和总结自然规律特征：观察和总结自然规律 代表学科：物理学代表学科：物理学 计算思维（构造思维）计算思维（构造思维） 特征：设计和构造特征：设计和构造 代表学科：计算机科学代表学科：计算机科学 baxF| )(20 迭代法迭代法 迭代过程：迭代过程：1!=1 2!=1!*2

18、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 1.3 计算思维计算思维 递归递归 分分解解问题问题小问题小问题n!(n-1)!问题问题分分解解小问题小问题更小更小问题问题最小最小问题问题分分解解分分解解不能再分解不能再分解n!(n-1)!(n-2)!1! int fac(int n) if(n=1) return(1);

19、 else return(fac(n-1)*n); void main() int y; y=f(4) couty;21示例示例1.3 哥尼斯堡七桥问题哥尼斯堡七桥问题 18世纪经典数学问题世纪经典数学问题 在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛以及岛在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛以及岛与河岸连接起来。问是否可能从这四块陆地中任一块出发，恰好通过每与河岸连接起来。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？座桥一次，再回到起点？1计算思维的本质：抽象和自动化计算思维的本质：抽象和自动化 抽象：抽象：完全超越物理的时空观，并完全用符号来

20、表示完全超越物理的时空观，并完全用符号来表示 数学抽象是一种特例数学抽象是一种特例1.3 1.3 计算思维计算思维 哥尼斯堡七桥问题哥尼斯堡七桥问题 哥尼斯堡七桥问题的抽象哥尼斯堡七桥问题的抽象 自动化：自动化：机械地一步一步自动执行，其基础和前提是抽像机械地一步一步自动执行，其基础和前提是抽像 222计算思维的特征计算思维的特征 是属于人的思维方式，不是计算机的思维方式是属于人的思维方式，不是计算机的思维方式 递归、迭代、黎曼积分早已提出，是人类赋予计算机递归、迭代、黎曼积分早已提出，是人类赋予计算机 可以由人执行，也可以由计算机执行可以由人执行，也可以由计算机执行 是思想，不是人造物是思想

21、，不是人造物 是概念化，不是程序化是概念化，不是程序化 3计算思维的基本问题计算思维的基本问题 可计算性可计算性 一个问题是可计算的是指可以使用计算机在有限步骤内解决一个问题是可计算的是指可以使用计算机在有限步骤内解决 邱奇图灵论题：图灵机可以计算的就是可计算的邱奇图灵论题：图灵机可以计算的就是可计算的 计算复杂性计算复杂性 时间复杂性和空间复杂性时间复杂性和空间复杂性 1.3 1.3 计算思维计算思维23示例示例4 矩阵相乘：矩阵相乘：Cnn=AnnBnn1.3 1.3 计算思维计算思维 计算计算cij需要需要n次乘法和次乘法和n-1次加法次加法 c中有中有n2个元素，故个元素，故c需要需要

22、n3次乘法和次乘法和n2*(n-1)次加法次加法示示例例5 汉诺塔问题汉诺塔问题 大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上 从下往上按照大小顺序摞着从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗片黄金圆盘。大梵天命令婆罗 门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。 并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次 只能移动一个圆盘。只能移动一个圆盘。 241.3 1.3 计算思维计算思维汉诺塔问题分析汉诺塔

23、问题分析 假设有假设有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)的问题就无法计算了的问题就无法计算了 254图灵测试图灵测试 机器能有智能吗？换一句话来，通过什么样的测试机器才能称拥有智能？机器能有智能吗？换一句话来，通过什么样的测试机器才能称拥有智能？ 1.3 1.3 计算思维计算思维无法判断对方是人还是计算机，那么就可以认为计算机具有同人相当的智力无法判断对方是人还是计算机，那么就可以认为计算机具有同人相当的智力 测试场景测试场景 265计算思维基本方