計(jì)算機(jī)概論

第一講：什么是計(jì)算機(jī)

浙江理工大學(xué)計(jì)算機(jī)技術(shù)教研部

2010-9

第一講：什么是計(jì)算機(jī)

■什么是計(jì)算

□W

■可計(jì)算的問題

口遞歸函數(shù)、圖靈機(jī)

■元計(jì)算的物理實(shí)現(xiàn)

□計(jì)算機(jī)

■計(jì)算思維

■電子計(jì)算機(jī)的發(fā)展簡(jiǎn)史

什么是計(jì)算：數(shù)的集合

■運(yùn)算必須在某些集合上展開

■自然數(shù)集合

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

■整數(shù)集合

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

?有理數(shù)集合

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

■實(shí)數(shù)集合

什么是計(jì)算：基本運(yùn)算

■基本運(yùn)算

□:土，+,一

■四則運(yùn)算

□:,一,X,4-

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

■邏輯運(yùn)算

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

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

什么是計(jì)算：表達(dá)式

■表達(dá)式是按照一定的123

語(yǔ)法給出的算式。需+41

要按運(yùn)算步驟對(duì)其逐X63

次遞歸到基本運(yùn)算來(lái)492

+9840

求解。10332

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

10340

■一個(gè)表達(dá)式就清楚地

表明了求值計(jì)算的過(guò)表達(dá)式的計(jì)算過(guò)程

程。

什么是計(jì)算：復(fù)雜的計(jì)算

■如何求打？

■巴比倫算法:設(shè)定計(jì)算誤差e

令：a=S/2

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

數(shù)x0=S如果：|a-b|>e

TQXx/S.令a=b

b=(a+s/a)/2

1

Jn+1=-輸出b,結(jié)束

乙

求平方根的計(jì)算過(guò)程

\/S=limx.

71—OCn

什么是計(jì)算：函數(shù)的運(yùn)算

■所有的運(yùn)算其實(shí)都是

描述了集合間元素的

映射關(guān)系，這種映射

關(guān)系就是函數(shù)。

■計(jì)算的過(guò)程其實(shí)就是

求解函數(shù)映射的過(guò)程。

值域

定義域

什么是計(jì)算：有限步的基本運(yùn)算

■計(jì)算其實(shí)就是用已知的、具有明確結(jié)果的基本運(yùn)

算去解決復(fù)雜問題的一個(gè)過(guò)程。

■計(jì)算的性質(zhì)

□有窮性，僅有有限步基本運(yùn)算；

□明確性，每步運(yùn)算沒有歧義，有確定的結(jié)果；

□有效性，可以用現(xiàn)實(shí)的物理手段實(shí)現(xiàn)；

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

■符合上述直觀定義的計(jì)算過(guò)程就是“第考。

什么是計(jì)算：遞歸求解

■對(duì)復(fù)雜問題的計(jì)算求解過(guò)程其實(shí)就是一個(gè)

使用基本運(yùn)算將問題逐步化簡(jiǎn)的一個(gè)過(guò)程。

■這個(gè)過(guò)程稱為“遞歸”或“循環(huán)累積”求解。

什么是計(jì)算：計(jì)算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!；遞推

化簡(jiǎn)f(n-1)=(n-1)*f(n-2);回歸

累積

---

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

簡(jiǎn)單運(yùn)算的循環(huán)累積f(2)=2*f(1);

f⑴=1;

遞歸的過(guò)程

可計(jì)算性

■由簡(jiǎn)單運(yùn)算出發(fā)可以逐步解決復(fù)雜問題；

■復(fù)雜問題可以遞歸為簡(jiǎn)單問題的解；

■以上兩種說(shuō)法是事實(shí)等價(jià)的。

■是否所有的復(fù)雜問題都是可以遞歸到已經(jīng)

解決的基本問題上來(lái)？

■是否存在某些問題，無(wú)法采用簡(jiǎn)單運(yùn)算疊

加或遞歸的方法加以解決？

可計(jì)算性：算法的精確定義

■要回答以上兩個(gè)問題，就需要對(duì)什么是簡(jiǎn)單運(yùn)算、

如何通過(guò)簡(jiǎn)單運(yùn)算構(gòu)造出復(fù)雜計(jì)算過(guò)程的規(guī)則加

以精確的定義。

■阿蘭?圖靈(AlanTuring)引入了圖靈機(jī)作為算法

的精確描述，同時(shí)期的數(shù)學(xué)家阿隆佐?邱奇

CAlonzoChurch)使用“遞歸的數(shù)'和人-算子也對(duì)

算法進(jìn)行了精確的描述。他們定義的算法被證明

是完全等價(jià)的。這就是著名的“邱奇?圖靈”論題

(TheChurch-TuringThesis)

可計(jì)算性：“邱奇?圖靈”論題

■該論題最基本的觀點(diǎn)表

明，所有計(jì)算或算法都可

以由一臺(tái)鹵靈機(jī)來(lái)st行。

■常規(guī)的編程語(yǔ)言可以足夠

有效的來(lái)表達(dá)任何算法。

■從有限的集合和運(yùn)算出

發(fā)，計(jì)算復(fù)雜問題的極限

是什么。

■該論題無(wú)法證明，亦無(wú)法

反駁。因?yàn)樗f(shuō)的真的就

是計(jì)算嗎？

可計(jì)算性：不可決定的問題

■希爾伯特第十問題:發(fā)明一種能夠判定多項(xiàng)

式是否存在整數(shù)根的算法。

□YuriMatijasevic證明了這種算法不存在，

1970；

■圖靈機(jī)停機(jī)問題?.發(fā)明一種能夠判定圖靈機(jī)

是否能夠停機(jī)的算法。

不存在。意味著我們?cè)瓌t上不可能設(shè)計(jì)一個(gè)通

用的軟件測(cè)試程序。

可計(jì)算性：可行性問題

■某些問題已經(jīng)被證明至少無(wú)法用目前的計(jì)

算手段得到解決；

■某些問題理論上可解決,但是其花費(fèi)的時(shí)

間又是不現(xiàn)實(shí)的；

■某些問題依然懸而未決;

■人的智力都可以被歸結(jié)為一種計(jì)算嗎?

可計(jì)算性：智能

■/夜君友的邏輯原理和

他的整個(gè)哲學(xué)可被歸約

為兩點(diǎn)：

□所有的我們的觀念（概

念）都是由非常小數(shù)目

的簡(jiǎn)單觀念復(fù)合而成，

它們形成了人類思維的

字每。

復(fù)雜的觀念來(lái)自這些簡(jiǎn)

單的觀念，通過(guò)模擬算戈特弗里德?威廉?萊布尼茨

術(shù)運(yùn)算的統(tǒng)一的和對(duì)稱GottfriedWilhelmLeibniz

的組合。1646年一1716年

元計(jì)算的物理實(shí)現(xiàn)

?二進(jìn)制:最簡(jiǎn)單的進(jìn)位計(jì)數(shù)制。

“1與0,一切數(shù)字的神奇淵源。這是造物的秘密

美妙的典范，因?yàn)?，一切無(wú)非都來(lái)自上帝

萊布尼茲

■二進(jìn)制數(shù)所有的運(yùn)算都可最終規(guī)約為三種

布爾代數(shù)運(yùn)算（與、或、非）的算法。

■可以用高低電位分別代表1和0。

元計(jì)算的物理實(shí)現(xiàn)：開關(guān)線路

十+

■用繼電器開關(guān)電路實(shí)1,i

現(xiàn)邏輯運(yùn)算

T-

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

工

+c=aAb

[“與”運(yùn)算

_______________________

￡1

_rwv>

-

c=aVb-1?a

"或'運(yùn)算c=a“非”運(yùn)算

元計(jì)算的物理實(shí)現(xiàn):

半導(dǎo)體開關(guān)電路

邏輯“與”電路

+

邏輯"或‘電路

1D

電路圖邏輯符號(hào)

邏輯"非''電路

*使用邏輯電路實(shí)現(xiàn)加法運(yùn)算

b=x八y；c=x&y

一位加法本位進(jìn)位

x+y異或與Cb

Xybc

0000

0110

1010xy

1101半加器

*多位二進(jìn)制加法運(yùn)算

■使用一位加法器串聯(lián)的方式可以很容易地

實(shí)現(xiàn)多位二進(jìn)制加法運(yùn)算。

10111001101

+10001100110

每一位的加法是兩個(gè)本位+一個(gè)進(jìn)位

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

M

c八)

全加器

*計(jì)算機(jī)如何記憶（存儲(chǔ)）

■記憶可以簡(jiǎn)單表述為：外部信號(hào)是短暫

的，在其消失后，電路狀態(tài)發(fā)生的改變卻

是持久的。

■最基本的記憶單元：R-S觸發(fā)器。

通常r,s端維持高電平，

在s置位脈沖到來(lái)時(shí)，Q

被置1,即使脈沖消失，Q

依然保持為1。

s置位復(fù)位

周以真：計(jì)算思維

ComputationalThinking

■計(jì)算思維就是把一個(gè)看來(lái)困難的問題重新闡述成

一個(gè)我們知道怎樣解的問題，如通過(guò)約簡(jiǎn)、嵌入、

轉(zhuǎn)化和仿真的方法。

□遞歸思維；

口抽象和分解；

容錯(cuò)和冗余；

□啟發(fā)式推理。

■人的,不是計(jì)算機(jī)的思維。計(jì)算思維是人類求解

同題的一條途徑，但決非試圖使人類像計(jì)算機(jī)那

樣地思考。

計(jì)算機(jī)體系結(jié)構(gòu)

■在解決了運(yùn)算和存儲(chǔ)問題后，如何構(gòu)造一

個(gè)能計(jì)算的機(jī)器？它應(yīng)該具有什么結(jié)構(gòu)？

■第一臺(tái)計(jì)算機(jī)只存儲(chǔ)數(shù)據(jù)，電子管制造的

運(yùn)算部件按特定方式連接來(lái)表達(dá)運(yùn)算步驟

（程序）。

■在處理不同計(jì)算任務(wù)時(shí)，各部件需要重新

連接。

■給你加法器和乘法器，如何計(jì)算x2+y2?

程序存儲(chǔ)的概念

■在馮?諾依曼體系中，程序被要求在執(zhí)行之前放到

計(jì)算機(jī)存儲(chǔ)器中，還要求程序和數(shù)據(jù)采用同樣的

格式——存儲(chǔ)器只接收二進(jìn)制數(shù)據(jù)

■程序必須是有限的指令數(shù)量組成的。按照一般的

理解，計(jì)算機(jī)指令是進(jìn)行基本操作的機(jī)器代碼

■程序的編制

□早期的計(jì)算機(jī)沒有“編程(Programming)”這個(gè)概念

□編制程序是指在實(shí)際處理數(shù)據(jù)之前，確定處理這些數(shù)

據(jù)的方法和過(guò)程

程序使得計(jì)算過(guò)程完全自動(dòng)化。

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

■計(jì)算機(jī)有多種模型，馮?諾依曼(JohnvonNeumann)

體系結(jié)構(gòu)(圖1.3)——現(xiàn)代計(jì)算機(jī)的基礎(chǔ)

■馮?諾依曼模型主要可歸納為以下三點(diǎn)

(1)計(jì)算機(jī)有五個(gè)組成部分：輸入、存儲(chǔ)、處理(運(yùn)

算)、控制和輸出

(2)程序和數(shù)據(jù)以二進(jìn)制形式存放在計(jì)算機(jī)存儲(chǔ)器中

(3)計(jì)算機(jī)根據(jù)程序的指令序列進(jìn)行，即程序存儲(chǔ)

(Stored-Program)的概念

計(jì)算機(jī)的五個(gè)組收§亭^

數(shù)據(jù)的存儲(chǔ)形式

■馮?諾依曼體系并沒有明確數(shù)據(jù)是怎樣存儲(chǔ)在

計(jì)算機(jī)中

■數(shù)據(jù)有多種類型，最基本的就是整數(shù)、實(shí)數(shù)

以及符號(hào)

■數(shù)據(jù)以二進(jìn)制方式存儲(chǔ)到計(jì)算機(jī)內(nèi)部

■將計(jì)算機(jī)外部各種類型的數(shù)據(jù)變換為計(jì)算機(jī)

二進(jìn)制模式，并且能夠有效地表達(dá)這些數(shù)據(jù)

類型，就是計(jì)算機(jī)研究的重要方面——計(jì)算

機(jī)的數(shù)據(jù)組織

歷史上的自動(dòng)計(jì)算裝置

■算盤——是最早被廣泛使用的計(jì)算裝置

■1642法國(guó)萊斯?帕斯卡發(fā)明的Pascaline

——人類歷史上的第一臺(tái)自動(dòng)計(jì)算機(jī)器

■鐘表齒輪計(jì)數(shù)加減，用杠桿實(shí)現(xiàn)進(jìn)位

■程序設(shè)計(jì)語(yǔ)言Pascal以他的名字命名

■19世紀(jì)初英國(guó)數(shù)學(xué)家巴貝奇——計(jì)算機(jī)之父

□發(fā)明差分機(jī)

□IPOS(Input,Processing,OutputandStorage)

■穿孔卡片機(jī)和舊M公司

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

■1936年英國(guó)數(shù)學(xué)家阿蘭?圖靈(AlanTuring)

提出計(jì)算機(jī)理論模型：只要能夠被分解為

有限步驟就能夠?qū)崿F(xiàn)自動(dòng)計(jì)算——圖靈機(jī)

■ABC計(jì)算機(jī)(AtanasoffBerryComputer

1939年)

■ENIAC(ElectronicNumericalIntegratorsandCalculation)

計(jì)算機(jī)的里程碑意義(1946)

□世界上第一臺(tái)可以真正運(yùn)算、全部是電子裝置

的計(jì)算機(jī)

ENIAC計(jì)算機(jī)和主要發(fā)明人J.毛赫利和艾克特v左前,

現(xiàn)代計(jì)算機(jī)

■計(jì)算機(jī)全名：通用數(shù)字電子計(jì)算機(jī)

■20世紀(jì)六七十年代還在使用的“模擬計(jì)算機(jī)”

也被數(shù)字計(jì)算機(jī)所取代

■今天的計(jì)算機(jī)一詞也就成了數(shù)字計(jì)算機(jī)的

同義詞

20世紀(jì)六七十年代還在使用的“模擬計(jì)算機(jī)”也

被數(shù)字計(jì)算機(jī)所取代

■關(guān)于計(jì)算機(jī)的“代”——并沒有一致的說(shuō)法

第一代計(jì)算機(jī)(1946—1959)

■電子管計(jì)算機(jī)

計(jì)算機(jī)全名為通用數(shù)字電子計(jì)算機(jī)

□體積大，故障率高

■UNIVAC的機(jī)器于1952年美國(guó)中大選預(yù)測(cè)

艾森豪威爾獲勝——預(yù)測(cè)結(jié)果和實(shí)際統(tǒng)計(jì)

結(jié)果完全相同

■1957年舊M公司生產(chǎn)的第一臺(tái)商用計(jì)算機(jī)

IBM701,一共生產(chǎn)了19臺(tái)：

二進(jìn)制的0和1表示數(shù)據(jù)和程序

第二代計(jì)算機(jī)(1959—1963)

■晶體管計(jì)算機(jī)

□1948年6月貝爾實(shí)驗(yàn)室研制成功世界上第一只晶體管

第一臺(tái)晶體管的計(jì)算機(jī)是CDC制造的1604機(jī)器

□開始使用高級(jí)語(yǔ)言

開始通過(guò)電話線進(jìn)行數(shù)據(jù)交流，雖然速度很慢，但這已

經(jīng)是網(wǎng)絡(luò)的萌芽

■并行處理被所有大型計(jì)算機(jī)和超級(jí)計(jì)算機(jī)所使用

■麻省理工學(xué)院——“多道程序”方案

第三代計(jì)算機(jī)(1663—1975年)

■集成電路(IC,IntegratedCircuits)計(jì)算機(jī)

1958年發(fā)明了集成電路

摩爾博士預(yù)言IC上能被集成的晶體管數(shù)目將會(huì)以每

18個(gè)月翻一番的速度穩(wěn)定增長(zhǎng)

——摩爾法則

舊M推出了著名的360系列計(jì)算機(jī)，不再捆綁銷售

它的語(yǔ)言軟件——開創(chuàng)了計(jì)算機(jī)語(yǔ)言市場(chǎng)——最終

使軟件形成了一個(gè)巨大的產(chǎn)業(yè)

■第一顆通信衛(wèi)星——衛(wèi)星數(shù)據(jù)通信

圖1.5著名的舊M360計(jì)算機(jī)

第四代計(jì)算機(jī)(1975年―)

■第四代計(jì)算機(jī)標(biāo)志的

處理器使用的大規(guī)模

集成電路(LSIC)—

—Intel系列處理器

■1977年第一個(gè)真正意

義上的微機(jī)AppleII計(jì)算機(jī)，1977

AppleI-----有顯示器、

鍵盤、軟盤和操作系統(tǒng)

軟件

第四代計(jì)算機(jī)(1975年-)

■1980年，舊M選擇Intel8088芯片作為它的微

機(jī)的處理器--PC(PersonalComputer),

委托Microsoft設(shè)計(jì)操作系統(tǒng)

■舊M公司的這兩個(gè)決定的巨大的影響：

□舊M公司商標(biāo)的PC成為微型計(jì)算機(jī)的同義詞

□Microsoft和Intel公司則在計(jì)算機(jī)軟件和硬件方面成

為和舊M公司分庭抗