計(jì)算概論與程序設(shè)計(jì)基礎(chǔ)-計(jì)算機(jī)的基本原理-

計(jì)算概論

第一講

計(jì)算機(jī)的基本原理

計(jì)算機(jī)的理論模型——圖靈機(jī)從數(shù)學(xué)危機(jī)到圖靈機(jī)圖靈機(jī)的基本構(gòu)成圖靈機(jī)的運(yùn)行機(jī)理

計(jì)算機(jī)為什么能計(jì)算？

數(shù)的二進(jìn)制表示

二進(jìn)制數(shù)的布爾運(yùn)算已解問題：數(shù)的表示

二進(jìn)制.待解問題：如何進(jìn)行計(jì)算？計(jì)算機(jī)中數(shù)的邏輯運(yùn)算方法

布爾代數(shù)

1854年：布爾發(fā)表《思

維規(guī)律的研究——邏輯

與概率的數(shù)學(xué)理論基

礎(chǔ)》，并綜合其另一篇

文章《邏輯的數(shù)學(xué)分

析》，創(chuàng)立了一門全新

的學(xué)科－布爾代數(shù)；為計(jì)算機(jī)的開關(guān)電路設(shè)

計(jì)提供了重要的數(shù)學(xué)方

法和理論基礎(chǔ)。英國數(shù)學(xué)家布爾（G.Boole）計(jì)算機(jī)中數(shù)的邏輯運(yùn)算方法

基本邏輯運(yùn)算

與

或

非

復(fù)合邏輯運(yùn)算

同或

異或

與非

或非

與或非英國數(shù)學(xué)家布爾（G.Boole）計(jì)算機(jī)中數(shù)的邏輯運(yùn)算方法FRE

AB邏輯函數(shù)表達(dá)式：F=

AB

真值表A

B

F

0

0

0

0

1

0

1

0

0

1

1

1B計(jì)算機(jī)中數(shù)的邏輯運(yùn)算方法FARE

邏輯函數(shù)表達(dá)式：F=

A+BF0111A

0

0

1

1

B0101真值表計(jì)算機(jī)中數(shù)的邏輯運(yùn)算方法邏輯函數(shù)表達(dá)式：F=

A+BEARF1001FA真值表ABF1F20001011010101101計(jì)算機(jī)中數(shù)的邏輯運(yùn)算方法真值表

異或兩數(shù)相同為“0”兩數(shù)相異為“1”同或

兩數(shù)相同為“1”

兩數(shù)相異為“0”F

=

A

BF

=

A

B加法的計(jì)算舉例：A=1101,

B=1001,

求

A+B

1

1

0

1+

1

0

0

11

0

0

11

0

1

1

0加法的計(jì)算舉例：A=1101,

B=1001,

求

A+B異或

與AB本位

進(jìn)位

1+

1

1+

0

1

0

1

1+1

00

1

1

+

00

11854年的布爾代數(shù)半加器半加器或an

bncn

-1sn

cnScn-1an---加數(shù)；bn---被加數(shù)；cn-1---低位的進(jìn)位sn---本位和；cn---進(jìn)位

1

1

0

1+

1

0

0

1

1

0

0

11

0

1

1

0已解問題：數(shù)的表示

——

二進(jìn)制.已解問題：計(jì)算方法

——

布爾代數(shù)待解問題：布爾運(yùn)算如何實(shí)現(xiàn)？1854年的布爾代數(shù)與門或門異或門小結(jié)電路為什么能計(jì)算？數(shù)字運(yùn)算

可以轉(zhuǎn)換

二進(jìn)制數(shù)的運(yùn)算；二進(jìn)制運(yùn)算

可以轉(zhuǎn)換為

基本的“布爾運(yùn)算”

；基本的“布爾運(yùn)算”

都可以

由電路完成；所以電路能“算數(shù)”！CPU計(jì)算機(jī)的過去、現(xiàn)在

和

未來下集預(yù)告Thanks.計(jì)算概論

第一講

計(jì)算機(jī)的基本原理

計(jì)算機(jī)的理論模型——圖靈機(jī)從數(shù)學(xué)危機(jī)到圖靈機(jī)圖靈機(jī)的基本構(gòu)成圖靈機(jī)的運(yùn)行機(jī)理

計(jì)算機(jī)為什么能計(jì)算？

數(shù)的二進(jìn)制表示

二進(jìn)制數(shù)的布爾運(yùn)算計(jì)算機(jī)的理論模型——圖靈機(jī)

本節(jié)內(nèi)容

圖靈機(jī)的構(gòu)成

運(yùn)作機(jī)理

示例

圖靈機(jī)的意義

前節(jié)回顧

三次數(shù)學(xué)危機(jī)

圖靈的貢獻(xiàn)

提到了“圖靈機(jī)”圖靈機(jī)的構(gòu)成

圖靈機(jī)的組成一條存儲(chǔ)帶

雙向無限延長

上有一個(gè)個(gè)小方格

每個(gè)小方格可存儲(chǔ)一個(gè)數(shù)字/字母一個(gè)控制器

可以存儲(chǔ)當(dāng)前自身的狀態(tài)；

包含一個(gè)讀寫頭，可以讀、寫、更改存儲(chǔ)帶上每一格的數(shù)字/字母

可以根據(jù)讀到的字母/數(shù)字變換自身的狀態(tài)

可以沿著存儲(chǔ)帶一格一格地左移/右移圖靈機(jī)如何工作

圖靈機(jī)的工作步驟：1.準(zhǔn)備：（1）存儲(chǔ)帶上符號(hào)初始化；（2）控制器設(shè)置好自身當(dāng)前狀態(tài)；（3）讀寫頭置于起始位置；（4）準(zhǔn)備好工作程序；2.反復(fù)執(zhí)行以下工作直到停機(jī)：（1）讀寫頭讀出存儲(chǔ)帶上當(dāng)前方格中的字母/數(shù)字；（2）根據(jù)

自身當(dāng)前狀態(tài)

和

所讀到的字符，找到相應(yīng)的程序語句；（3）根據(jù)

相應(yīng)程序語句，做三個(gè)動(dòng)作：

①

在當(dāng)前存儲(chǔ)帶方格上寫入一個(gè)相

應(yīng)的字母/數(shù)字；

②

變更自身狀態(tài)至新狀態(tài)；

③

讀寫頭向左或向右移一步；1111111q1q1q2q2q3q31b1b1b111bbbRRRLHHq1q2q2q3q3q3當(dāng)前狀態(tài)：q1q1

1

1

R

q1當(dāng)前機(jī)器狀態(tài)當(dāng)前讀入的符合當(dāng)前應(yīng)寫入的符號(hào)讀寫頭的動(dòng)作機(jī)器應(yīng)轉(zhuǎn)入的狀態(tài)圖靈機(jī)運(yùn)行前的準(zhǔn)備工作：

（1）存儲(chǔ)帶上符號(hào)初始化；

當(dāng)前字母表：{

1，b

}（2）設(shè)置好控制器當(dāng)前狀態(tài)；

控制器狀態(tài)集合：

{

q1,

q2,

q3

}

控制器當(dāng)前狀態(tài)：q1（3）讀寫頭置于起始位置；（4）準(zhǔn)備好工作程序；圖靈機(jī)程序五元組:<q,

b,

a,

m,

q’>1111111q1q1q2q2q3q31b1b1b111bbbRRRLHHq1q2q2q3q3q3當(dāng)前狀態(tài)：q1與當(dāng)前狀況匹配

的程序語句圖靈機(jī)開始工作：（1）讀寫頭讀出存儲(chǔ)帶上當(dāng)前方格中的字母/數(shù)字；（2）根據(jù)

自身當(dāng)前狀態(tài)

和

所讀到的字符，找到相應(yīng)的程序語句；（3）根據(jù)

相應(yīng)程序語句，做三個(gè)動(dòng)作：

①

在當(dāng)前存儲(chǔ)帶方格上寫入

數(shù)字“1”；

①

變更自身狀態(tài)至新狀態(tài)

“q1”；

②

讀寫頭向”右”移一步；1111111q1q1q2q2q3q31b1b1b111bbbRRRLHHq1q2q2q3q3q3當(dāng)前狀態(tài)：q1與當(dāng)前狀況匹配

的程序語句1111111q1q1q2q2q3q31b1b1b111bbbRRRLHHq1q2q2q3q3q3當(dāng)前狀態(tài)：q1與當(dāng)前狀況匹配

的程序語句1111111q1q1q2q2q3q31b1b1b111bbbRRRLHHq1q2q2q3q3q3當(dāng)前狀態(tài)：q1與當(dāng)前狀況匹配

的程序語句1111111q1q1q2q2q3q31b1b1b111bbbRRRLHHq1q2q2q3q3q3當(dāng)前狀態(tài)：q1與當(dāng)前狀況匹配

的程序語句11111111q1q1q2q2q3q31b1b1b111bbbRRRLHHq1q2q2q3q3q3當(dāng)前狀態(tài)：q2與當(dāng)前狀況匹配

的程序語句11111111q1q1q2q2q3q31b1b1b111bbbRRRLHHq1q2q2q3q3q3當(dāng)前狀態(tài)：q2與當(dāng)前狀況匹配

的程序語句11111111q1q1q2q2q3q31b1b1b111bbbRRRLHHq1q2q2q3q3q3當(dāng)前狀態(tài)：q2與當(dāng)前狀況匹配

的程序語句11111111q1q1q2q2q3q31b1b1b111bbbRRRLHHq1q2q2q3q3q3當(dāng)前狀態(tài)：q2與當(dāng)前狀況匹配

的程序語句11111111q1q1q2q2q3q31b1b1b111bbbRRRLHHq1q2q2q3q3q3當(dāng)前狀態(tài)：q2與當(dāng)前狀況匹配

的程序語句1111111q1q1q2q2q3q31b1b1b111bbbRRRLHHq1q2q2q3q3q3當(dāng)前狀態(tài)：q2與當(dāng)前狀況匹配

的程序語句

給定符號(hào)序列

A，如果能找到一

個(gè)圖靈機(jī)，得出對(duì)應(yīng)的符號(hào)序列

B，那么從

A

到

B

就是可計(jì)算的。

也就是說：

對(duì)于一個(gè)問題的輸入A，問:

A能否推證出B?

如果能找到一個(gè)圖靈機(jī)，得出對(duì)應(yīng)的

符號(hào)序列

B，那么從

A

到

B

就是可

計(jì)算的。

否則，該問題不可計(jì)算。

成功

停機(jī)圖靈機(jī)停機(jī)意味著什么？圖靈機(jī)如何工作圖靈機(jī)為什么受到重視？簡單！強(qiáng)大！可實(shí)現(xiàn)！圖靈機(jī)的理論意義

可計(jì)算性的判定；

意義：

給出了一個(gè)可實(shí)現(xiàn)的通

用計(jì)算模型；

引入了通過“讀寫符號(hào)”

和“狀態(tài)改變”進(jìn)行運(yùn)

算的思想；

證實(shí)了基于簡單字母表

完成復(fù)雜運(yùn)算的能力；

引入了存儲(chǔ)區(qū)、程序、

控制器等概念的原型；計(jì)算機(jī)為什么能夠進(jìn)行計(jì)算？下節(jié)預(yù)告計(jì)算概論

第一講

計(jì)算機(jī)的基本原理

計(jì)算機(jī)的理論模型——圖靈機(jī)從數(shù)學(xué)危機(jī)到圖靈機(jī)圖靈機(jī)的基本構(gòu)成圖靈機(jī)的運(yùn)行機(jī)理

計(jì)算機(jī)為什么能計(jì)算？

數(shù)的二進(jìn)制表示

二進(jìn)制數(shù)的布爾運(yùn)算計(jì)算機(jī)為什么能進(jìn)行計(jì)算？

“數(shù)”在計(jì)算機(jī)中如何表示？

計(jì)算機(jī)中“數(shù)”的邏輯運(yùn)算方式？

邏輯運(yùn)算方式的物理實(shí)現(xiàn)？關(guān)于計(jì)算機(jī)中數(shù)的表示

若采用字母表

{

1,

b

}

符號(hào)

“b”

表示計(jì)算對(duì)象和計(jì)算結(jié)果的邊界

符號(hào)“

1”

表示計(jì)算對(duì)象和計(jì)算結(jié)果的數(shù)值

遇到的問題：

使用符號(hào)

“1”表示數(shù)字

1

數(shù)值

1,000,000

應(yīng)由一百萬個(gè)

1來表示

讀入這一個(gè)數(shù)，讀寫頭就要移動(dòng)一百萬次

顯然不合理、不實(shí)際關(guān)于計(jì)算機(jī)中數(shù)的表示

如果使用“十進(jìn)制”

字母表中包含11個(gè)符號(hào)：

{

0,

1,

…,

9,

b

}用于圖靈機(jī)控制的程序

要大量增加確定當(dāng)前指令也需要更

多的時(shí)間q1q1q2q2q3q31b1b1b111bbbRRRLHHq1q2q2q3q3q3q1

0

0

Rq1

1

1

R

……q1

9

9

R

……q3

b

b

Hq1q1q1

q3關(guān)于計(jì)算機(jī)中數(shù)的表示

由此可知：字母表中的符號(hào)越多，讀入移動(dòng)次數(shù)減少，但程序數(shù)量就越多字母表中的符號(hào)越少，程序量會(huì)減少，但讀入移動(dòng)次數(shù)就越多

字母表與狀態(tài)：字母表中符號(hào)的最優(yōu)數(shù)量，可能是歐拉常數(shù)

e（2.7182818284590...），取整后為

3。與具有兩個(gè)狀態(tài)的電子元件相比，具有三個(gè)狀態(tài)的電子元件在制造上更困難，可靠性更低。

十進(jìn)制、二進(jìn)制、十六進(jìn)制

十進(jìn)制：

計(jì)數(shù)符號(hào)：0、1、2、3、4、5、6、7、8、9

基數(shù)：10

二進(jìn)制：計(jì)數(shù)符號(hào)：0、1基數(shù)：2

十六進(jìn)制：

計(jì)數(shù)符號(hào)：0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F256

=

2×102

+

5×101