计算机概论第一讲：什么是计算机

计算机概论

第一讲：什么是计算机

浙江理工大学计算机技术教研部

2010-9

第一讲：什么是计算机

■什么是计算

□W

■可计算的问题

口递归函数、图灵机

■元计算的物理实现

□计算机

■计算思维

■电子计算机的发展简史

什么是计算：数的集合

■运算必须在某些集合上展开

■自然数集合

N={0,1,2,3,...}

■整数集合

□1={0,±1,±2,...}

・有理数集合

□Q={b/a,be|,ae|,aWO}

■实数集合

什么是计算：基本运算

■基本运算

□:土，+,一

■四则运算

□:,一,X,4-

：1+2=3；4X5=20；九九乘法表

■逻辑运算

□与（八），或（V）,非（-）

□：1A0=0；1V0=1；T=o；o=1

什么是计算：表达式

■表达式是按照一定的123

语法给出的算式。需+41

要按运算步骤对其逐X63

次递归到基本运算来492

+9840

求解。10332

■8+63X(123+41)+8

10340

■一个表达式就清楚地

表明了求值计算的过表达式的计算过程

程。

什么是计算：复杂的计算

■如何求打？

■巴比伦算法:设定计算误差e

令：a=S/2

■先任意假定一个正令：b=(a+s/a)/2

数x0=S如果：|a-b|>e

TQXx/S.令a=b

b=(a+s/a)/2

1

Jn+1=-输出b,结束

乙

求平方根的计算过程

\/S=limx.

71—OCn

什么是计算：函数的运算

■所有的运算其实都是

描述了集合间元素的

映射关系，这种映射

关系就是函数。

■计算的过程其实就是

求解函数映射的过程。

值域

定义域

什么是计算：有限步的基本运算

■计算其实就是用已知的、具有明确结果的基本运

算去解决复杂问题的一个过程。

■计算的性质

□有穷性，仅有有限步基本运算；

□明确性，每步运算没有歧义，有确定的结果；

□有效性，可以用现实的物理手段实现；

□输入和输出：有限的输入输出。

■符合上述直观定义的计算过程就是“第考。

什么是计算：递归求解

■对复杂问题的计算求解过程其实就是一个

使用基本运算将问题逐步化简的一个过程。

■这个过程称为“递归”或“循环累积”求解。

什么是计算：计算n!

■两种不同的解决思路，已知0!=1,1!=1

n!=f(n);

1：1!=1；

2：2!=2*1!；f(n)=n*f(n-1);

3：3!=3*2!；递推

化简f(n-1)=(n-1)*f(n-2);回归

累积

---

N:n!=n*(n-1)!

简单运算的循环累积f(2)=2*f(1);

f⑴=1;

递归的过程

可计算性

■由简单运算出发可以逐步解决复杂问题；

■复杂问题可以递归为简单问题的解；

■以上两种说法是事实等价的。

■是否所有的复杂问题都是可以递归到已经

解决的基本问题上来？

■是否存在某些问题，无法采用简单运算叠

加或递归的方法加以解决？

可计算性：算法的精确定义

■要回答以上两个问题，就需要对什么是简单运算、

如何通过简单运算构造出复杂计算过程的规则加

以精确的定义。

■阿兰・图灵(AlanTuring)引入了图灵机作为算法

的精确描述，同时期的数学家阿隆佐•邱奇

CAlonzoChurch)使用“递归的数'和人-算子也对

算法进行了精确的描述。他们定义的算法被证明

是完全等价的。这就是著名的“邱奇•图灵”论题

(TheChurch-TuringThesis)

可计算性：“邱奇•图灵”论题

■该论题最基本的观点表

明，所有计算或算法都可

以由一台卤灵机来st行。

■常规的编程语言可以足够

有效的来表达任何算法。

■从有限的集合和运算出

发，计算复杂问题的极限

是什么。

■该论题无法证明，亦无法

反驳。因为它说的真的就

是计算吗？

可计算性：不可决定的问题

■希尔伯特第十问题:发明一种能够判定多项

式是否存在整数根的算法。

□YuriMatijasevic证明了这种算法不存在，

1970；

■图灵机停机问题•.发明一种能够判定图灵机

是否能够停机的算法。

不存在。意味着我们原则上不可能设计一个通

用的软件测试程序。

可计算性：可行性问题

■某些问题已经被证明至少无法用目前的计

算手段得到解决；

■某些问题理论上可解决,但是其花费的时

间又是不现实的；

■某些问题依然悬而未决;

■人的智力都可以被归结为一种计算吗?

可计算性：智能

■/夜君友的逻辑原理和

他的整个哲学可被归约

为两点：

□所有的我们的观念（概

念）都是由非常小数目

的简单观念复合而成，

它们形成了人类思维的

字每。

复杂的观念来自这些简

单的观念，通过模拟算戈特弗里德•威廉•莱布尼茨

术运算的统一的和对称GottfriedWilhelmLeibniz

的组合。1646年一1716年

元计算的物理实现

・二进制:最简单的进位计数制。

“1与0,一切数字的神奇渊源。这是造物的秘密

美妙的典范，因为，一切无非都来自上帝

莱布尼兹

■二进制数所有的运算都可最终规约为三种

布尔代数运算（与、或、非）的算法。

■可以用高低电位分别代表1和0。

元计算的物理实现：开关线路

十+

■用继电器开关电路实1,i

现逻辑运算

T-

-----------4,------

工

+c=aAb

[“与”运算

_______________________

£1

_rwv>

-

c=aVb-1।a

"或'运算c=a“非”运算

元计算的物理实现:

半导体开关电路

逻辑“与”电路

+

逻辑"或‘电路

1D

电路图逻辑符号

逻辑"非''电路

*使用逻辑电路实现加法运算

b=x八y；c=x&y

一位加法本位进位

x+y异或与Cb

Xybc

0000

0110

1010xy

1101半加器

*多位二进制加法运算

■使用一位加法器串联的方式可以很容易地

实现多位二进制加法运算。

10111001101

+10001100110

每一位的加法是两个本位+一个进位

x+y+c=(x+y)+c

M

c八)

全加器

*计算机如何记忆（存储）

■记忆可以简单表述为：外部信号是短暂

的，在其消失后，电路状态发生的改变却

是持久的。

■最基本的记忆单元：R-S触发器。

通常r,s端维持高电平，

在s置位脉冲到来时，Q

被置1,即使脉冲消失，Q

依然保持为1。

s置位复位

周以真：计算思维

ComputationalThinking

■计算思维就是把一个看来困难的问题重新阐述成

一个我们知道怎样解的问题，如通过约简、嵌入、

转化和仿真的方法。

□递归思维；

口抽象和分解；

容错和冗余；

□启发式推理。

■人的,不是计算机的思维。计算思维是人类求解

同题的一条途径，但决非试图使人类像计算机那

样地思考。

计算机体系结构

■在解决了运算和存储问题后，如何构造一

个能计算的机器？它应该具有什么结构？

■第一台计算机只存储数据，电子管制造的

运算部件按特定方式连接来表达运算步骤

（程序）。

■在处理不同计算任务时，各部件需要重新

连接。

■给你加法器和乘法器，如何计算x2+y2?

程序存储的概念

■在冯・诺依曼体系中，程序被要求在执行之前放到

计算机存储器中，还要求程序和数据采用同样的

格式——存储器只接收二进制数据

■程序必须是有限的指令数量组成的。按照一般的

理解，计算机指令是进行基本操作的机器代码

■程序的编制

□早期的计算机没有“编程(Programming)”这个概念

□编制程序是指在实际处理数据之前，确定处理这些数

据的方法和过程

程序使得计算过程完全自动化。

冯・诺依曼体系结构

■计算机有多种模型，冯・诺依曼(JohnvonNeumann)

体系结构(图1.3)——现代计算机的基础

■冯・诺依曼模型主要可归纳为以下三点

(1)计算机有五个组成部分：输入、存储、处理(运

算)、控制和输出

(2)程序和数据以二进制形式存放在计算机存储器中

(3)计算机根据程序的指令序列进行，即程序存储

(Stored-Program)的概念

计算机的五个组收§亭^

数据的存储形式

■冯・诺依曼体系并没有明确数据是怎样存储在

计算机中

■数据有多种类型，最基本的就是整数、实数

以及符号

■数据以二进制方式存储到计算机内部

■将计算机外部各种类型的数据变换为计算机

二进制模式，并且能够有效地表达这些数据

类型，就是计算机研究的重要方面——计算

机的数据组织

历史上的自动计算装置

■算盘——是最早被广泛使用的计算装置

■1642法国莱斯•帕斯卡发明的Pascaline

——人类历史上的第一台自动计算机器

■钟表齿轮计数加减，用杠杆实现进位

■程序设计语言Pascal以他的名字命名

■19世纪初英国数学家巴贝奇——计算机之父

□发明差分机

□IPOS(Input,Processing,OutputandStorage)

■穿孔卡片机和旧M公司

第一台电子计算机

■1936年英国数学家阿兰•图灵(AlanTuring)

提出计算机理论模型：只要能够被分解为

有限步骤就能够实现自动计算——图灵机

■ABC计算机(AtanasoffBerryComputer

1939年)

■ENIAC(ElectronicNumericalIntegratorsandCalculation)

计算机的里程碑意义(1946)

□世界上第一台可以真正运算、全部是电子装置

的计算机

ENIAC计算机和主要发明人J.毛赫利和艾克特v左前,

现代计算机

■计算机全名：通用数字电子计算机

■20世纪六七十年代还在使用的“模拟计算机”

也被数字计算机所取代

■今天的计算机一词也就成了数字计算机的

同义词

20世纪六七十年代还在使用的“模拟计算机”也

被数字计算机所取代

■关于计算机的“代”——并没有一致的说法

第一代计算机(1946—1959)

■电子管计算机

计算机全名为通用数字电子计算机

□体积大，故障率高

■UNIVAC的机器于1952年美国中大选预测

艾森豪威尔获胜——预测结果和实际统计

结果完全相同

■1957年旧M公司生产的第一台商用计算机

IBM701,一共生产了19台：

二进制的0和1表示数据和程序

第二代计算机(1959—1963)

■晶体管计算机

□1948年6月贝尔实验室研制成功世界上第一只晶体管

第一台晶体管的计算机是CDC制造的1604机器

□开始使用高级语言

开始通过电话线进行数据交流，虽然速度很慢，但这已

经是网络的萌芽

■并行处理被所有大型计算机和超级计算机所使用

■麻省理工学院——“多道程序”方案

第三代计算机(1663—1975年)

■集成电路(IC,IntegratedCircuits)计算机

1958年发明了集成电路

摩尔博士预言IC上能被集成的晶体管数目将会以每

18个月翻一番的速度稳定增长

——摩尔法则

旧M推出了著名的360系列计算机，不再捆绑销售

它的语言软件——开创了计算机语言市场——最终

使软件形成了一个巨大的产业

■第一颗通信卫星——卫星数据通信

图1.5著名的旧M360计算机

第四代计算机(1975年―)

■第四代计算机标志的

处理器使用的大规模

集成电路(LSIC)—

—Intel系列处理器

■1977年第一个真正意

义上的微机AppleII计算机，1977

AppleI-----有显示器、

键盘、软盘和操作系统

软件

第四代计算机(1975年-)

■1980年，旧M选择Intel8088芯片作为它的微

机的处理器--PC(PersonalComputer),

委托Microsoft设计操作系统

■旧M公司的这两个决定的巨大的影响：

□旧M公司商标的PC成为微型计算机的同义词

□Microsoft和Intel公司则在计算机软件和硬件方面成

为和旧M公司分庭抗