第1章 计算机文化与计算思维

第一章计算机文化与计算思维

L1弓I吉

1.2计算机的诞生和发足

13计算思维基础

1.1引言

人类为什么要发明计算机？

■人的计算速度很低

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

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

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

■早期的计算工具

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

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

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

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

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

1.1引言

♦计算器1673年德国GottfriedLeibniz,机械式

可进行加、减、乘、除和开方

♦差分机和分析机

查尔斯.巴贝奇1812年差分机1834年分析机

分析机：体现了现代电子计算机的结构、设计思想

被称为现代通用计算机的雏形

1.2计算机的诞生和发展

■计算机的诞生

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

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

♦图灵机(Turingmachine,TM)

阿兰•图灵(AlanMathisonTuring,1912—1954)

解决问题；什么是计算？什么是可计算性？

组成：计算X+1的图灵机M

L11

纸带

读写头

(1)M的状态：接受状态、进位状态.初始时处于进位状态.

(2)从右向左扫描班带.

进位状态：读到“或空白，则改写L进入接受状态，立即停机；

读到1,则改写为o,状态保住不变，读写头左移,

1.2计算机的诞生和发展

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

邱奇、图灵和哥德尔断言，

一切直觉上能行可计算的函数都可用图灵机计算，反之亦然

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

世界上的问题＜

、不可计算的

图灵机模型：解决了可计算问题计归痂亚堂十。

计算机的理论问题“昇巩科了《乂

图灵的贡献

图灵测试：回答了什么样的机器具有智能

人工智能的理论基础人工智能之父

美国计算机学会ACM于1966年创立了“图灵奖”

1.2计算机的诞生和发展

♦ENIAC（电子数字积分计算机）1946.2-1955.10宾州大学

每秒5千次加减运算

Q没有存储器

采用十进制

第一款商用计算机：UNIVAL

1947年，莫奇莱和埃克特

仅表明电子计算机时代的到来

1.2计算机的诞生和发展

♦冯•诺依曼体系结构计算机

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

冯•诺依曼参与研制并且发表：关于EDVAC的报告草案

B采用二进制

口存储程序：程序和数据一起存储在内存中

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

奠定了现代计算机体系结构和工作原理

迄今为止的计算机都采用这种思想，称为冯•诺依曼计算机

1.2计算机的诞生和发展

■计算机的分代

时代年份耨件运算速度软件应用

机器语言科学计算

—46-58电子管每秒几千次

汇编语言军事领域

数据处理

二58-64晶体管每秒几十万次高级语言

工业控制

文字处理

三64-70集成电路每秒几百万次操作系统

图形处理

四71年迄今大规模集成电路达到每秒亿亿次数据库、网络等各个领域

电子管晶体管集成电路大规模集成电路

1.2计算机的诞生和发展

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

♦未来新型计算机

①光计算机

利用光子取代电子进行数据运算、传输和存储

不同波长的表示不同的数据

优点：超高速

缺点：体积庞大

②生物计算机（分子计算机）

20世纪80年代中期开始研制

采用了生物芯片

③量子计算机

利用处于多现实态下的原子进行运算的计算机，

这种多现实态是量子力学的标志.

1.2计算机的诞生和发展

■计算机的分类

通用机

按用途分类

专用机

高性能计算机（巨型机或大型机），

速度最快、处理能力最强、

最快：Titan每秒2亿亿次浮点运算

中国：天河1A每秒4.70千万亿次浮点运算第8

微型计算机：

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

按综合性能

工作站：介于与小型机之间高档微机系统

指标分类一PC

高分辨率、大容量内外存，图形功能较强

服务器：网络环境中对外提供服务的计算机系统

嵌入式计算机：数量超过PC

1.2计算机的诞生和发展

■计算机的应用类型

i.科学计算

2.数据处理

3.电子商务①B2B阿里巴巴

②B2c京东商城

③C2c淘宝网

4.过程控制

5.C/\I)/CAM/CIMS

6.多媒体技术

7.人工智能

卡斯帕罗夫对弈“深蓝”

1.2计算机的诞生和发展

■计算机文化

♦物质文化

计算机的软、硬件设备以及使用方法

♦非物质文化

计算机学科对臼然科学和社会科学等的广泛渗透，

创造和形成了新的科学思想、科学方法、科学精神、价值标准等

计算机应用改变r传统社会，形成了网络社会等虚拟的社会形态

产生了相应的语言、风俗、道德、法律等

最重要的是计算机网络文化

1.3计算思维

C理论思维(推理思维)特征：以推理和演绎为特征

代表学科：数学

三大科学思维'实验思维(实证思维)特征：观察和总结自然规律

代表学科：物理学

〔计算思维(构造思维)特征：设计和构造

代表学科：计算机科学

计算思维：运用计算机科学的基础概念进行问题求解、系统设计、

以及人类行为理解等涵盖计算机科学之广度的一系列思维活动

示例L计算f(x)是⑶b］上的积分

数学方法牛顿-莱布尼兹：f(x)—T(x)—

计算思维黎曼积分：对进行n等分♦计算小矩形面积累加

1.3计算思维

示例2：计算n的阶乘f(n)=n!

迭代法

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

程序：

for(i=l;i<=n;i++)

s=s♦i;

经典迭代：牛顿迭代法

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

原型机。一原型机1—原型机2

递归

intfac(intn)voidmaiiK)

if(n==l)inty;

return11);y=f(4)

elsecout«y;

retuni(fac(n-l)*n);}

不就再分■

1.3计算思维

i.计算思维的本质：抽象和自动化

抽象：完全超越物理的时空观，并完全用符号来表示

数学抽象是一种特例

示例1.3哥尼斯堡七桥问题18世纪经典数学问题

在用尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛以及岛

与河岸连接起来.问是否可能从这四块陆地中任块出发，恰好通过每

座桥一次，再回到起点？

自动化：机械地一步一步自动执行，其基础和前提是抽像

1.3计算思维

2.计算思维的特征

♦是属于人的思维方式，不是计算机的思维方式

递归、迭代、黎曼积分早已提出，是人类赋予计算机

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

♦是思想，不是人造物

♦是概念化，不是程序化

3.计算思维的基本问题

♦可计算性

一个问题是可计算的是指可以使用计算机在有限步骤内解决

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

♦计算复杂性

时间复杂性和空间复杂性

1.3计算思维

示例4矩阵相乘：CnXn=AnXllXBnXn

产

计算％需要n次乘法和n・1次加法

c中有1个元素，故c需要iP次乘法和次加法

示例5汉诺塔问题

大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上

从下往上按照大小顺序摞着64片黄金圆盘.大梵天命令婆罗

门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。

并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次

只能移动一个01盘.

iAQ]

1.3计算思维

汉诺塔问题分析

假设有n黄金圆盘，移动次数是f(n)

有f(l)=Lf(2)=3,f(3)=7.........f(k+l)=2*f(k)+l

故f(n)=2n・l,时间复杂性记作0(2-)

f(64)=2W-1=18446744073709551615

假如每秒钟移动一次，一个365天，则约需要584942417355年,即5849亿

而地球的寿命才45亿年.

假使用计算机进行每秒1亿次的移动，也需要5849年。

时间复杂性：。⑴O(k>gn)O(n)O(nlogn)0(n2)O(n3)...0(n*0(2")

当n值稍大时，0(2^的问题就无法计算了

1