第1章 計(jì)算機(jī)文化與計(jì)算思維

第一章計(jì)算機(jī)文化與計(jì)算思維

L1弓I吉

1.2計(jì)算機(jī)的誕生和發(fā)足

13計(jì)算思維基礎(chǔ)

1.1引言

人類為什么要發(fā)明計(jì)算機(jī)？

■人的計(jì)算速度很低

?祖沖之計(jì)算加至小數(shù)點(diǎn)后7位數(shù)用了15年

?計(jì)算30X30的行列式需要幾個(gè)人年

?中國第一棵原子彈研制時(shí)，數(shù)百位科學(xué)家在大禮堂打算盤

■早期的計(jì)算工具

?算籌春秋戰(zhàn)國時(shí)期世界上最早的計(jì)算工具

?算盤中國唐代第一種手動(dòng)式計(jì)數(shù)器沿有至今

?計(jì)算尺1622年手動(dòng)式，上世紀(jì)70年代被計(jì)算器取代

可進(jìn)行加、減、乘、除、指數(shù)、三角函數(shù)

?加法器1642年機(jī)械式，只能做加法

1.1引言

?計(jì)算器1673年德國GottfriedLeibniz,機(jī)械式

可進(jìn)行加、減、乘、除和開方

?差分機(jī)和分析機(jī)

查爾斯.巴貝奇1812年差分機(jī)1834年分析機(jī)

分析機(jī)：體現(xiàn)了現(xiàn)代電子計(jì)算機(jī)的結(jié)構(gòu)、設(shè)計(jì)思想

被稱為現(xiàn)代通用計(jì)算機(jī)的雛形

1.2計(jì)算機(jī)的誕生和發(fā)展

■計(jì)算機(jī)的誕生

圖靈機(jī)、ENIAC和馮?諾依曼體系結(jié)構(gòu)在理論上、工作原理、體系結(jié)

構(gòu)上奠定現(xiàn)代電子計(jì)算機(jī)的基礎(chǔ)

?圖靈機(jī)(Turingmachine,TM)

阿蘭?圖靈(AlanMathisonTuring,1912—1954)

解決問題；什么是計(jì)算？什么是可計(jì)算性？

組成：計(jì)算X+1的圖靈機(jī)M

L11

紙帶

讀寫頭

(1)M的狀態(tài)：接受狀態(tài)、進(jìn)位狀態(tài).初始時(shí)處于進(jìn)位狀態(tài).

(2)從右向左掃描班帶.

進(jìn)位狀態(tài)：讀到“或空白，則改寫L進(jìn)入接受狀態(tài)，立即停機(jī)；

讀到1,則改寫為o,狀態(tài)保住不變，讀寫頭左移,

1.2計(jì)算機(jī)的誕生和發(fā)展

圖靈機(jī)的能力;高級(jí)程序設(shè)計(jì)語言=現(xiàn)代通用計(jì)算機(jī)

邱奇、圖靈和哥德爾斷言，

一切直覺上能行可計(jì)算的函數(shù)都可用圖靈機(jī)計(jì)算，反之亦然

，可計(jì)算的：圖靈機(jī)可計(jì)算的就是可計(jì)算的

世界上的問題＜

、不可計(jì)算的

圖靈機(jī)模型：解決了可計(jì)算問題計(jì)歸痂亞堂十。

計(jì)算機(jī)的理論問題“昇鞏科了《乂

圖靈的貢獻(xiàn)

圖靈測(cè)試：回答了什么樣的機(jī)器具有智能

人工智能的理論基礎(chǔ)人工智能之父

美國計(jì)算機(jī)學(xué)會(huì)ACM于1966年創(chuàng)立了“圖靈獎(jiǎng)”

1.2計(jì)算機(jī)的誕生和發(fā)展

?ENIAC（電子數(shù)字積分計(jì)算機(jī)）1946.2-1955.10賓州大學(xué)

每秒5千次加減運(yùn)算

Q沒有存儲(chǔ)器

采用十進(jìn)制

第一款商用計(jì)算機(jī)：UNIVAL

1947年，莫奇萊和埃克特

僅表明電子計(jì)算機(jī)時(shí)代的到來

1.2計(jì)算機(jī)的誕生和發(fā)展

?馮?諾依曼體系結(jié)構(gòu)計(jì)算機(jī)

人類第二臺(tái)計(jì)算機(jī)；EDVAC（離散變量自動(dòng)電子計(jì)算機(jī)）1945年

馮?諾依曼參與研制并且發(fā)表：關(guān)于EDVAC的報(bào)告草案

B采用二進(jìn)制

口存儲(chǔ)程序：程序和數(shù)據(jù)一起存儲(chǔ)在內(nèi)存中

五個(gè)部分：運(yùn)算器、控制器、存儲(chǔ)器、輸入設(shè)備和輸出設(shè)備

奠定了現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)和工作原理

迄今為止的計(jì)算機(jī)都采用這種思想，稱為馮?諾依曼計(jì)算機(jī)

1.2計(jì)算機(jī)的誕生和發(fā)展

■計(jì)算機(jī)的分代

時(shí)代年份耨件運(yùn)算速度軟件應(yīng)用

機(jī)器語言科學(xué)計(jì)算

—46-58電子管每秒幾千次

匯編語言軍事領(lǐng)域

數(shù)據(jù)處理

二58-64晶體管每秒幾十萬次高級(jí)語言

工業(yè)控制

文字處理

三64-70集成電路每秒幾百萬次操作系統(tǒng)

圖形處理

四71年迄今大規(guī)模集成電路達(dá)到每秒億億次數(shù)據(jù)庫、網(wǎng)絡(luò)等各個(gè)領(lǐng)域

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

1.2計(jì)算機(jī)的誕生和發(fā)展

?發(fā)展趨勢(shì)：微型化、巨型化、網(wǎng)絡(luò)化和智能化

?未來新型計(jì)算機(jī)

①光計(jì)算機(jī)

利用光子取代電子進(jìn)行數(shù)據(jù)運(yùn)算、傳輸和存儲(chǔ)

不同波長的表示不同的數(shù)據(jù)

優(yōu)點(diǎn)：超高速

缺點(diǎn)：體積龐大

②生物計(jì)算機(jī)（分子計(jì)算機(jī)）

20世紀(jì)80年代中期開始研制

采用了生物芯片

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

利用處于多現(xiàn)實(shí)態(tài)下的原子進(jìn)行運(yùn)算的計(jì)算機(jī)，

這種多現(xiàn)實(shí)態(tài)是量子力學(xué)的標(biāo)志.

1.2計(jì)算機(jī)的誕生和發(fā)展

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

通用機(jī)

按用途分類

專用機(jī)

高性能計(jì)算機(jī)（巨型機(jī)或大型機(jī)），

速度最快、處理能力最強(qiáng)、

最快：Titan每秒2億億次浮點(diǎn)運(yùn)算

中國：天河1A每秒4.70千萬億次浮點(diǎn)運(yùn)算第8

微型計(jì)算機(jī)：

桌面型計(jì)算機(jī)、筆記本電腦、平板電腦、移動(dòng)設(shè)備

按綜合性能

工作站：介于與小型機(jī)之間高檔微機(jī)系統(tǒng)

指標(biāo)分類一PC

高分辨率、大容量內(nèi)外存，圖形功能較強(qiáng)

服務(wù)器：網(wǎng)絡(luò)環(huán)境中對(duì)外提供服務(wù)的計(jì)算機(jī)系統(tǒng)

嵌入式計(jì)算機(jī)：數(shù)量超過PC

1.2計(jì)算機(jī)的誕生和發(fā)展

■計(jì)算機(jī)的應(yīng)用類型

i.科學(xué)計(jì)算

2.數(shù)據(jù)處理

3.電子商務(wù)①B2B阿里巴巴

②B2c京東商城

③C2c淘寶網(wǎng)

4.過程控制

5.C/\I)/CAM/CIMS

6.多媒體技術(shù)

7.人工智能

卡斯帕羅夫?qū)摹吧钏{(lán)”

1.2計(jì)算機(jī)的誕生和發(fā)展

■計(jì)算機(jī)文化

?物質(zhì)文化

計(jì)算機(jī)的軟、硬件設(shè)備以及使用方法

?非物質(zhì)文化

計(jì)算機(jī)學(xué)科對(duì)臼然科學(xué)和社會(huì)科學(xué)等的廣泛滲透，

創(chuàng)造和形成了新的科學(xué)思想、科學(xué)方法、科學(xué)精神、價(jià)值標(biāo)準(zhǔn)等

計(jì)算機(jī)應(yīng)用改變r(jià)傳統(tǒng)社會(huì)，形成了網(wǎng)絡(luò)社會(huì)等虛擬的社會(huì)形態(tài)

產(chǎn)生了相應(yīng)的語言、風(fēng)俗、道德、法律等

最重要的是計(jì)算機(jī)網(wǎng)絡(luò)文化

1.3計(jì)算思維

C理論思維(推理思維)特征：以推理和演繹為特征

代表學(xué)科：數(shù)學(xué)

三大科學(xué)思維'實(shí)驗(yàn)思維(實(shí)證思維)特征：觀察和總結(jié)自然規(guī)律

代表學(xué)科：物理學(xué)

〔計(jì)算思維(構(gòu)造思維)特征：設(shè)計(jì)和構(gòu)造

代表學(xué)科：計(jì)算機(jī)科學(xué)

計(jì)算思維：運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問題求解、系統(tǒng)設(shè)計(jì)、

以及人類行為理解等涵蓋計(jì)算機(jī)科學(xué)之廣度的一系列思維活動(dòng)

示例L計(jì)算f(x)是⑶b］上的積分

數(shù)學(xué)方法牛頓-萊布尼茲：f(x)—T(x)—

計(jì)算思維黎曼積分：對(duì)進(jìn)行n等分?計(jì)算小矩形面積累加

1.3計(jì)算思維

示例2：計(jì)算n的階乘f(n)=n!

迭代法

迭代過程：1!=12!=1!*23!=2!*3……n!=(n-l)!*n

程序：

for(i=l;i<=n;i++)

s=s?i;

經(jīng)典迭代：牛頓迭代法

J20研制過程就是迭代過程：

原型機(jī)。一原型機(jī)1—原型機(jī)2

遞歸

intfac(intn)voidmaiiK)

if(n==l)inty;

return11);y=f(4)

elsecout?y;

retuni(fac(n-l)*n);}

不就再分■

1.3計(jì)算思維

i.計(jì)算思維的本質(zhì)：抽象和自動(dòng)化

抽象：完全超越物理的時(shí)空觀，并完全用符號(hào)來表示

數(shù)學(xué)抽象是一種特例

示例1.3哥尼斯堡七橋問題18世紀(jì)經(jīng)典數(shù)學(xué)問題

在用尼斯堡的一個(gè)公園里，有七座橋?qū)⑵绽赘駹柡又袃蓚€(gè)島以及島

與河岸連接起來.問是否可能從這四塊陸地中任塊出發(fā)，恰好通過每

座橋一次，再回到起點(diǎn)？

自動(dòng)化：機(jī)械地一步一步自動(dòng)執(zhí)行，其基礎(chǔ)和前提是抽像

1.3計(jì)算思維

2.計(jì)算思維的特征

?是屬于人的思維方式，不是計(jì)算機(jī)的思維方式

遞歸、迭代、黎曼積分早已提出，是人類賦予計(jì)算機(jī)

?可以由人執(zhí)行，也可以由計(jì)算機(jī)執(zhí)行

?是思想，不是人造物

?是概念化，不是程序化

3.計(jì)算思維的基本問題

?可計(jì)算性

一個(gè)問題是可計(jì)算的是指可以使用計(jì)算機(jī)在有限步驟內(nèi)解決

邱奇一圖靈論題：圖靈機(jī)可以計(jì)算的就是可計(jì)算的

?計(jì)算復(fù)雜性

時(shí)間復(fù)雜性和空間復(fù)雜性

1.3計(jì)算思維

示例4矩陣相乘：CnXn=AnXllXBnXn

產(chǎn)

計(jì)算％需要n次乘法和n?1次加法

c中有1個(gè)元素，故c需要iP次乘法和次加法

示例5漢諾塔問題

大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上

從下往上按照大小順序摞著64片黃金圓盤.大梵天命令婆羅

門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。

并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次

只能移動(dòng)一個(gè)01盤.

iAQ]

1.3計(jì)算思維

漢諾塔問題分析

假設(shè)有n黃金圓盤，移動(dòng)次數(shù)是f(n)

有f(l)=Lf(2)=3,f(3)=7.........f(k+l)=2*f(k)+l

故f(n)=2n?l,時(shí)間復(fù)雜性記作0(2-)

f(64)=2W-1=18446744073709551615

假如每秒鐘移動(dòng)一次，一個(gè)365天，則約需要584942417355年,即5849億

而地球的壽命才45億年.

假使用計(jì)算機(jī)進(jìn)行每秒1億次的移動(dòng)，也需要5849年。

時(shí)間復(fù)雜性：。⑴O(k>gn)O(n)O(nlogn)0(n2)O(n3)...0(n*0(2")

當(dāng)n值稍大時(shí)，0(2^的問題就無法計(jì)算了

1