大學(xué)計(jì)算機(jī)基礎(chǔ)

—教學(xué)課件二

教師姓名：李瑩

E-Mail:liying@

北京航空航天大學(xué)

容提要

一層次二層次

第1章計(jì)算機(jī)基礎(chǔ)知識(shí)子課程1:數(shù)據(jù)庫技術(shù)基礎(chǔ)

第2章計(jì)算機(jī)系統(tǒng)

子課程2：網(wǎng)頁設(shè)計(jì)與制作

子課程3：數(shù)學(xué)建模與MATLAB

子課程4：多媒體動(dòng)畫設(shè)計(jì)

第6章程序設(shè)計(jì)基礎(chǔ)子課程5：軟件工程基礎(chǔ)

2

第1章計(jì)算機(jī)基礎(chǔ)知識(shí)

1.1概述

1.2計(jì)算機(jī)科學(xué)研究與應(yīng)用

1.3未來計(jì)算機(jī)的發(fā)展趨勢(shì)

1.4信息的表示與存儲(chǔ)

1.5信息技術(shù)

2學(xué)時(shí)

本章重點(diǎn)

■計(jì)算機(jī)的發(fā)展史、特點(diǎn)及應(yīng)用

■進(jìn)位計(jì)數(shù)制及其轉(zhuǎn)換

■原碼、反碼、補(bǔ)碼的概念

■字符和漢字編碼

為什么使用計(jì)算機(jī)?

■原始目的：科學(xué)計(jì)算

■計(jì)算機(jī)可以做任何計(jì)算嗎？

>P問題一Polynomial:計(jì)算機(jī)可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算出準(zhǔn)確

結(jié)果。

>NP問題一Non-DeterministicPolynomial:計(jì)算機(jī)不可能在多

項(xiàng)式時(shí)間內(nèi)計(jì)算出準(zhǔn)確結(jié)果，但是可以驗(yàn)證結(jié)果是否正確。

■如何區(qū)分P和NP?

>根據(jù)時(shí)間復(fù)雜度判定

?在n個(gè)數(shù)中找到最大值O(n);將n個(gè)數(shù)從小到大排序O(n2)

?TSP問題O(nn)(枚舉)

為什么使用計(jì)算機(jī)?

■結(jié)論：如果算法的時(shí)間復(fù)雜度是好，那么計(jì)算機(jī)不能計(jì)算準(zhǔn)

確結(jié)果，只能通過枚舉法驗(yàn)證結(jié)果是否正確。

6

1.1概述

?1.1.1電子計(jì)算機(jī)的產(chǎn)生

?1.1.2計(jì)算機(jī)發(fā)展的幾個(gè)階段

?1.1.3計(jì)算機(jī)的特點(diǎn)和應(yīng)用

?1.1.4計(jì)算機(jī)的分類

7

電子計(jì)算機(jī)的產(chǎn)生

嬲牌曲航湖端算力=電子講算信久:制

算盤加法器

PascalCharlesBabbage

BlaiseHaSCal1822差分機(jī)

ENIACMARKI1833分析機(jī)8

第一臺(tái)電子計(jì)算機(jī)

ENIAC

＞5000次加法/秒

＞體重30噸

＞占地170M2

＞18800只電子管

＞1500個(gè)繼電器

＞耗電150KW

＞耗資40萬美元

9

著名人物

CharlesBabbageAllanTuringVonNeumann

10

馮?諾依曼機(jī)VS圖靈機(jī)

■馮?諾依曼機(jī)

(1)特點(diǎn)：

＞程序和數(shù)據(jù)用二進(jìn)制表示;

＞程序存儲(chǔ)的概念;

＞計(jì)算機(jī)由五個(gè)基本部分組成：輸入、存儲(chǔ)、運(yùn)算、控制、

輸出

11

馮諾依曼機(jī)VS圖靈機(jī)

(2)體系結(jié)構(gòu)思想

＞采用存儲(chǔ)程序方式；

?存儲(chǔ)器是以地址訪問的線性編址的一維結(jié)構(gòu)，每個(gè)單元

位數(shù)固定；

＞指令由操作碼和地址組成；

＞通過執(zhí)行指令直接發(fā)出控制信號(hào)控制計(jì)算機(jī)的操作；

＞以運(yùn)算器為中心；

＞數(shù)據(jù)以二進(jìn)制表示；

12

馮?諾依曼思想

■馮?諾依曼體系結(jié)構(gòu)

＞控制流

》數(shù)據(jù)流

13

圖靈機(jī)

■圖靈機(jī)

(1)基本思想：用機(jī)器模擬人的計(jì)算過程：1)在紙上寫上或擦

除某個(gè)符號(hào)；2)把注意力從紙的一個(gè)位置移動(dòng)到另一個(gè)位置。

每一階段，人要決定下一步的動(dòng)作，依賴于1)人當(dāng)前所關(guān)注的

紙上某個(gè)位置的符號(hào)；2)人當(dāng)前思維的狀態(tài)。

12*3+7-6=?

(2)基本組成：三個(gè)部件：一條無限紙帶、一個(gè)讀寫頭、一個(gè)

狀態(tài)寄存器；一套規(guī)則；三個(gè)動(dòng)作：改寫當(dāng)前格、左移一格、

右移一格。

14

圖靈機(jī)

有限自動(dòng)機(jī)

讀/寫頭

紙帶上的符號(hào)

紙帶

TuringMachine

圖靈機(jī)

⑶本質(zhì)：圖靈機(jī)是一個(gè)五元組(K,6,s,H),

>K是有窮個(gè)狀態(tài)的集合；

A2是字母表，即符號(hào)的集合；

>SWK是初始狀態(tài)；

AHWK是停機(jī)狀態(tài)的集合，當(dāng)控制器內(nèi)部狀態(tài)為停機(jī)狀態(tài)

時(shí)圖靈機(jī)結(jié)束計(jì)算；

>6是轉(zhuǎn)移函數(shù)，即控制器的規(guī)則集合。

16

圖靈機(jī)

例子：力表示空格，外表示機(jī)器的初始狀態(tài)，力表示機(jī)器的

結(jié)束狀態(tài)，設(shè)帶子上的輸入信息是10100010,讀入頭位對(duì)準(zhǔn)

最右邊第一個(gè)為0的方格，狀態(tài)為初始狀態(tài)分。規(guī)則如下:

>q101Lq2q110Lq3q^bbN

>qQQLq11L

2292^2q?bbN

>q3QILq210Lq3bbNq4

bb10100010bbb

/~\讀一寫頭

狀態(tài)

q,控制器

17

圖靈機(jī)

■計(jì)算結(jié)果是10100011,即對(duì)給定的數(shù)加1。

■以上命令計(jì)算的是這樣一個(gè)函數(shù)：S(x)=x+lo當(dāng)沒有輸入

時(shí)，即初始狀態(tài)所指的方格為空格時(shí)，不改變空格符

,讀寫頭不動(dòng)并停機(jī)。

18

圖靈機(jī)

(4)意義：

＞明確什么是可計(jì)算的——有輸入、有輸出、有變換

＞奠定人工智能基礎(chǔ)——機(jī)器代替人工作

＞不是具體機(jī)器，而是思想模型

19

馮諾依曼機(jī)vs圖靈機(jī)

■圖靈機(jī)圖靈機(jī)

＞將計(jì)算機(jī)械化

A只要符合圖靈機(jī)的就是可計(jì)算的

■馮諾依曼機(jī)曼機(jī)

＞程序控制

＞有限時(shí)間解決有限問題

■注意：可計(jì)算和可以在有限時(shí)間內(nèi)精確計(jì)算不同。

＞圖靈機(jī)說明算法能否被機(jī)械計(jì)算

＞馮諾依曼機(jī)說明算法能否在有限時(shí)間被準(zhǔn)確計(jì)算

＞無程序純硬件實(shí)現(xiàn)的算法屬于圖靈機(jī)但不屬于馮諾依曼機(jī)

20

摩爾定律

transistor

集成電路中晶體管的數(shù)量大約每18個(gè)月翻一倍。

21

1.1.2計(jì)算機(jī)發(fā)展的幾個(gè)階段

電子管一晶體管一集成電路一大規(guī)模集成電路

第一代第一代

（1946-1958）（1958~1964）

電子管晶體管

5千~幾萬（次/秒）幾萬~幾十萬

（次/秒）

第三代第四代

（1964~1970）（1971~至今）

中、小集成電路大規(guī)模集成電路

幾十萬~幾百萬上千萬~萬億

（次/秒）（次/秒）

22

津__

一定，?摩爾定律

計(jì)多

刖第

單

位

eois

,7519>85199019

晶19

時(shí)

10M

體500

(tranmsl

toes)

2000師6)間

管百

,v

1M

m25

Pencil

___執(zhí)萬

ssor

數(shù)“Prooe

，一ao4

B6行每

10OK

1.0

aoaae秒

^--§0286的

p_______

1OK

0.1指

Eioao令

0.01

L4004數(shù)

計(jì)算機(jī)的CPU性能

每18個(gè)月，集成度將翻一番，速度

將提高一倍，而其價(jià)格將降低一半。

電子計(jì)算機(jī)的發(fā)展

集成電路

廠也于元件

隹成電路指包含精細(xì)電路的硅晶片，

采用中、小呆有時(shí)小于平方厘米，集成電路

1~~一.一廠--=>?

口向3團(tuán)尸O國像的?0。

規(guī)模集成電應(yīng)用廣泛，從簡單的記憶電路到包含8?冊(cè)盟礙理滁

數(shù)百萬電子元件的中央處理器（CPU）■克。地回同回回黜

路代替了獨(dú)都是集成電路家族中的一員。

集成電路

立元件晶體；子當(dāng)回回衿］4@向》回回￥回

管。連接線

塑料底座

24

將電腦濃縮在一顆芯片上

晶75000,000

體

管

數(shù)

0.18微米芯片

目

1。微米芯片4004奔騰4

25

1J.3計(jì)算機(jī)的特點(diǎn)和應(yīng)用

■計(jì)算機(jī)的特點(diǎn)

＞高速、精確的運(yùn)算能力

＞準(zhǔn)確的邏輯判斷能力

＞強(qiáng)大的存儲(chǔ)能力

＞自動(dòng)功能

＞網(wǎng)絡(luò)與通信功能

計(jì)算機(jī)在信息社會(huì)中的應(yīng)用

計(jì)算機(jī)的應(yīng)用十分廣泛工商：電子商務(wù)、AD/CAM

教育：多媒體教育、遠(yuǎn)程教育!

（彩醫(yī)藥：CAT、MRI、遠(yuǎn)程醫(yī)療

1力、

弋』）:娛樂：虛擬現(xiàn)實(shí)、影視特技

政府：電子政府IW、二c，J

J，J

能科研：數(shù)據(jù)采集、計(jì)算分析家庭：家庭信息化庭4

27

計(jì)算機(jī)的主要應(yīng)用領(lǐng)域

07丘科學(xué)計(jì)算其它領(lǐng)域一

1電子商務(wù)

^^12.數(shù)據(jù)處理網(wǎng)絡(luò)與通信

人工智能

多媒體技術(shù)

CAD/CAM/C1MS

I3.實(shí)時(shí)控制

28

LL4計(jì)算機(jī)的分類

按速度等指標(biāo)分類

r專用計(jì)算機(jī)

按用途及使用范圍分類Y

I通用計(jì)算機(jī)

<=>

29

<A

1.2計(jì)算機(jī)科學(xué)研究與應(yīng)用

「.人工智能像?

4.云計(jì)算

12.網(wǎng)格計(jì)算

13.中間件技術(shù)三

30

L3未來計(jì)算機(jī)的發(fā)展趨勢(shì)

■未來新的一代

■發(fā)展趨勢(shì)

＞模糊計(jì)算機(jī)

＞巨型化

＞生物計(jì)算機(jī)

A微型化

＞光子計(jì)算機(jī)

＞網(wǎng)絡(luò)化

＞超導(dǎo)計(jì)算機(jī)

A智能化

＞量子計(jì)算機(jī)

31

1.4信息的表示與存儲(chǔ)

?1.4.1數(shù)據(jù)與信息

?122計(jì)算機(jī)中的數(shù)據(jù)

?1.2.3計(jì)算機(jī)中數(shù)據(jù)的單位

?1.2.4進(jìn)位計(jì)數(shù)制及其轉(zhuǎn)換

?125數(shù)值的編碼

?1.2.6字符的編碼

32

1.4.1數(shù)據(jù)與信息

數(shù)據(jù)：是信息的載體

信息：數(shù)值、文字、語音、圖形和圖像。

信息必須數(shù)字化編碼，才能傳送、存儲(chǔ)和處理。

輸入設(shè)備輸出設(shè)備

數(shù)值十/二進(jìn)制轉(zhuǎn)換內(nèi)存二/十進(jìn)制轉(zhuǎn)換數(shù)值

------------------------------------------------------A-------------------->

西文Ascn碼西文字形碼西文

---------------------------->

漢字輸入碼/機(jī)內(nèi)碼轉(zhuǎn)換.漢字字形碼漢字

聲音、圖像模/數(shù)轉(zhuǎn)換、數(shù)/模轉(zhuǎn)換聲音、圖像

---------------->

33

1.4.2計(jì)算機(jī)中的數(shù)據(jù)

IIENIAC采用十進(jìn)制

________________________

馮?諾依曼研制IAS時(shí)，提

|出了二進(jìn)制的表示方法

、進(jìn)制的優(yōu)點(diǎn);至

所有元器件只需具有兩個(gè)不同的穩(wěn)定狀態(tài)

運(yùn)算規(guī)則簡單

計(jì)算機(jī)的理論基礎(chǔ)是邏輯

34

L4.3計(jì)算機(jī)中數(shù)據(jù)的單位

位度量數(shù)據(jù)的最小單位

字節(jié)存儲(chǔ)容量的基本單位

字長計(jì)算機(jī)一次能夠并行處理的二進(jìn)制數(shù)

35

數(shù)據(jù)的單位

字節(jié)1Byte=8bit

千字節(jié)1KB=1024B

兆字節(jié)1MB=1024KB

吉字節(jié)1GB=1024MB

太字節(jié)1TB=1024GB

拍字節(jié)1PB=1024TB

艾字節(jié)1EB=1024PB

36

1A4進(jìn)位計(jì)數(shù)制及其轉(zhuǎn)換

■進(jìn)位計(jì)數(shù)制

■進(jìn)位制中的三個(gè)要素：

＞數(shù)碼：數(shù)制中固定的基本符號(hào)

＞基數(shù)：某種進(jìn)位制所包含的的數(shù)字符號(hào)（或

數(shù)碼）的個(gè)數(shù)。N進(jìn)制的基數(shù)是N。

＞位權(quán)：在某種進(jìn)位制中，各數(shù)碼的位權(quán)是以

該進(jìn)位制的基數(shù)為底的幕次方。

例：十進(jìn)制數(shù)9788的基數(shù)、各數(shù)碼的位權(quán)分別是多少?

37

常用的進(jìn)位制類型

數(shù)制類型基數(shù)數(shù)碼權(quán)形式表示

二進(jìn)制20,121B

八進(jìn)制80,1,2,3,4,5,6,7810

十進(jìn)制100,1,2,3,4,5,6,7,8,9101D

0,1,2,3,4,5,6,7,8,9,

十六進(jìn)制16161H

A,B,C,D,E,F

一不同進(jìn)制數(shù)的表示方法

在該數(shù)的后面加上字母B（二進(jìn)制）、0（八進(jìn)制）、

D（十進(jìn)制）、H（十六進(jìn)制）來表示。

例：（10100101）B表示二進(jìn)制數(shù)。

38

幾種不同的進(jìn)制數(shù)的基本符號(hào)

-H吐制（D）3制（D）八進(jìn)制（O）十六進(jìn)制（H）

0000

1111

21022

31133

410044

510155

611066

711177

81000108

91001119

10101012A

11101113B

12110014C

13110115D

14111016E

15111117F

39

不同進(jìn)制間的轉(zhuǎn)換

R進(jìn)制＞■*〈十進(jìn)制

R進(jìn)制）一■〈十進(jìn)制

八進(jìn)制）—，＜］十六進(jìn)制

■轉(zhuǎn)換基本原則：

對(duì)整數(shù)部分和小數(shù)部分分別進(jìn)行轉(zhuǎn)換

40

R進(jìn)制轉(zhuǎn)換為十進(jìn)制

十進(jìn)制

把各個(gè)R進(jìn)制數(shù)按權(quán)展開求和

弄清進(jìn)位制中三要素:

數(shù)碼、基數(shù)、位權(quán)

41

二進(jìn)制表示形式

任意一個(gè)二進(jìn)制數(shù)B,可表示成如下形式：

=n_1n-2

(B)2Bn_1x2+Bn_2x2+…+B]X2i+B0x2°

2m+1m

+B_]X2T+B_2X2_+???+B_m+1x2~+B_mx2"

式中4是數(shù)碼，其取值范圍為0?1；i為數(shù)碼的編號(hào)(整

數(shù)位取n-1?0,小數(shù)位取-1?-m)；2為基數(shù)。

21

例：(110.01)B=1X2+1X2+0X2°

+0X2-1+1X2-2=(6.25)D

42

八進(jìn)制表示形式

任意一個(gè)八進(jìn)制數(shù)Q,可表示成如下形式：

n_1n-2

(Q)8=Qn-ix8+Qn_2x8+…+Qp8i+Q0x8°+Q.p8T

2m+1m

+Q_2X8-+…+Q_m+1x8-+Q_mx8-

式中Q是數(shù)碼，其取值范圍為0?7；i為數(shù)碼的編號(hào)(整

數(shù)位取nT?0,小數(shù)位取-1?-m)；8為基數(shù)。

例：八進(jìn)制(123.45)o=l*82+2X81+3X8°

+4X8T+5X8—2

=(83.578125)D

43

十六進(jìn)制表示形式

任意一個(gè)十六進(jìn)制數(shù)H,可表示成如下形式：

n2

(H)16=Hn-iX16nT+Hn_2xl6-+…+H0xl60

2m+1ffl

+H_ixl6T+H_2X16-+??,+H_m+1xl6-+H_mxl6-

式中均是數(shù)碼，其取值范圍為0?F；i為數(shù)碼的編號(hào)(整數(shù)

位取nT?0,小數(shù)位取T?-m)；16為基數(shù)。

例：十六進(jìn)制(123.45)/1義162+2X161+3X16。

+4X16T+5X16-2

二(291.26953125)D

44

十進(jìn)制表示形式

任意一個(gè)十進(jìn)制數(shù)D,可表示成如下形式：

(D)=Dn_ixion_1+D_xlOn-2+???+DiXlO1+DxlO°

10J.V11X11Cni21.Vo

-1-2m+1-m

+D-iXlO+D_2X10+■--+D_m+1xlO~+D_mxlO

式中以是數(shù)碼，其取值范圍為0?9；i為數(shù)碼的編號(hào)(整數(shù)

位取nT?0,小數(shù)位取-1~-111)；10為基數(shù)。

21

例：(123.45)D=1X10+2X10+3X10°

2

+4X10T+5X10-=(123.45)D

45

練習(xí)

例把下面的二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)

(1101.101)B

=lx23+lx22+0x21+1x20+1X2-1+0x2-2+lx2-3

=8+4+0+l+0.5+0+0.125

二(13.625)D

46

練習(xí)

例把下面的八進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)。

2-123

(456.124)0=4x8+5x81+6x8°+lxS+2x8-+4x8-

=256+40+6+0,125+0.03125+0.0078125

二(302.1640625)D

例把下面的十六進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)。

3212

(32CF.48)H=3xl6+2xl6+CxlG+Fxl60+4*16一】+8xl6-

=12288+512+192+15+0.25+0.03125