計算機概論第一講：什么是計算機

計算機概論

第一講：什么是計算機

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

2010-9

第一講：什么是計算機

■什么是計算

□W

■可計算的問題

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

■元計算的物理實現(xiàn)

□計算機

■計算思維

■電子計算機的發(fā)展簡史

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

■運算必須在某些集合上展開

■自然數(shù)集合

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

■整數(shù)集合

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

?有理數(shù)集合

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

■實數(shù)集合

什么是計算：基本運算

■基本運算

□:土，+,一

■四則運算

□:,一,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

■一個表達式就清楚地

表明了求值計算的過表達式的計算過程

程。

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

■如何求打？

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

令：a=S/2

■先任意假定一個正令：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é)束

乙

求平方根的計算過程

\/S=limx.

71—OCn

什么是計算：函數(shù)的運算

■所有的運算其實都是

描述了集合間元素的

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

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

■計算的過程其實就是

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

值域

定義域

什么是計算：有限步的基本運算

■計算其實就是用已知的、具有明確結(jié)果的基本運

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

■計算的性質(zhì)

□有窮性，僅有有限步基本運算；

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

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

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

■符合上述直觀定義的計算過程就是“第考。

什么是計算：遞歸求解

■對復(fù)雜問題的計算求解過程其實就是一個

使用基本運算將問題逐步化簡的一個過程。

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

什么是計算：計算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)!

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

f⑴=1;

遞歸的過程

可計算性

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

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

■以上兩種說法是事實等價的。

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

解決的基本問題上來？

■是否存在某些問題，無法采用簡單運算疊

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

可計算性：算法的精確定義

■要回答以上兩個問題，就需要對什么是簡單運算、

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

以精確的定義。

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

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

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

算法進行了精確的描述。他們定義的算法被證明

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

(TheChurch-TuringThesis)

可計算性：“邱奇?圖靈”論題

■該論題最基本的觀點表

明，所有計算或算法都可

以由一臺鹵靈機來st行。

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

有效的來表達任何算法。

■從有限的集合和運算出

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

是什么。

■該論題無法證明，亦無法

反駁。因為它說的真的就

是計算嗎？

可計算性：不可決定的問題

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

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

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

1970；

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

是否能夠停機的算法。

不存在。意味著我們原則上不可能設(shè)計一個通

用的軟件測試程序。

可計算性：可行性問題

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

算手段得到解決；

■某些問題理論上可解決,但是其花費的時

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

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

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

可計算性：智能

■/夜君友的邏輯原理和

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

為兩點：

□所有的我們的觀念（概

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

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

它們形成了人類思維的

字每。

復(fù)雜的觀念來自這些簡

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

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

的組合。1646年一1716年

元計算的物理實現(xiàn)

?二進制:最簡單的進位計數(shù)制。

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

美妙的典范，因為，一切無非都來自上帝

萊布尼茲

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

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

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

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

十+

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

現(xiàn)邏輯運算

T-

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

工

+c=aAb

[“與”運算

_______________________

￡1

_rwv>

-

c=aVb-1?a

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

元計算的物理實現(xiàn):

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

邏輯“與”電路

+

邏輯"或‘電路

1D

電路圖邏輯符號

邏輯"非''電路

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

b=x八y；c=x&y

一位加法本位進位

x+y異或與Cb

Xybc

0000

0110

1010xy

1101半加器

*多位二進制加法運算

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

實現(xiàn)多位二進制加法運算。

10111001101

+10001100110

每一位的加法是兩個本位+一個進位

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

M

c八)

全加器

*計算機如何記憶（存儲）

■記憶可以簡單表述為：外部信號是短暫

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

是持久的。

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

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

在s置位脈沖到來時，Q

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

依然保持為1。

s置位復(fù)位

周以真：計算思維

ComputationalThinking

■計算思維就是把一個看來困難的問題重新闡述成

一個我們知道怎樣解的問題，如通過約簡、嵌入、

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

□遞歸思維；

口抽象和分解；

容錯和冗余；

□啟發(fā)式推理。

■人的,不是計算機的思維。計算思維是人類求解

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

樣地思考。

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

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

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

■第一臺計算機只存儲數(shù)據(jù)，電子管制造的

運算部件按特定方式連接來表達運算步驟

（程序）。

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

連接。

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

程序存儲的概念

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

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

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

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

理解，計算機指令是進行基本操作的機器代碼

■程序的編制

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

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

據(jù)的方法和過程

程序使得計算過程完全自動化。

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

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

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

■馮?諾依曼模型主要可歸納為以下三點

(1)計算機有五個組成部分：輸入、存儲、處理(運

算)、控制和輸出

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

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

(Stored-Program)的概念

計算機的五個組收§亭^

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

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

計算機中

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

以及符號

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

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

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

類型，就是計算機研究的重要方面——計算

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

歷史上的自動計算裝置

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

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

——人類歷史上的第一臺自動計算機器

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

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

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

□發(fā)明差分機

□IPOS(Input,Processing,OutputandStorage)

■穿孔卡片機和舊M公司

第一臺電子計算機

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

提出計算機理論模型：只要能夠被分解為

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

■ABC計算機(AtanasoffBerryComputer

1939年)

■ENIAC(ElectronicNumericalIntegratorsandCalculation)

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

□世界上第一臺可以真正運算、全部是電子裝置

的計算機

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

現(xiàn)代計算機

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

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

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

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

同義詞

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

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

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

第一代計算機(1946—1959)

■電子管計算機

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

□體積大，故障率高

■UNIVAC的機器于1952年美國中大選預(yù)測

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

結(jié)果完全相同

■1957年舊M公司生產(chǎn)的第一臺商用計算機

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

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

第二代計算機(1959—1963)

■晶體管計算機

□1948年6月貝爾實驗室研制成功世界上第一只晶體管

第一臺晶體管的計算機是CDC制造的1604機器

□開始使用高級語言

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

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

■并行處理被所有大型計算機和超級計算機所使用

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

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

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

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

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

18個月翻一番的速度穩(wěn)定增長

——摩爾法則

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

它的語言軟件——開創(chuàng)了計算機語言市場——最終

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

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

圖1.5著名的舊M360計算機

第四代計算機(1975年―)

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

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

集成電路(LSIC)—

—Intel系列處理器

■1977年第一個真正意

義上的微機AppleII計算機，1977

AppleI-----有顯示器、

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

軟件

第四代計算機(1975年-)

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

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

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

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

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

□Microsoft和Intel公司則在計算機軟件和硬件方面成

為和舊M公司分庭抗