第一章計算機文化與計算思維

L1弓I吉

1.2計算機的誕生和發足

13計算思維基礎

1.1引言

人類為什么要發明計算機？

■人的計算速度很低

?祖沖之計算加至小數點后7位數用了15年

?計算30X30的行列式需要幾個人年

?中國第一棵原子彈研制時，數百位科學家在大禮堂打算盤

■早期的計算工具

?算籌春秋戰國時期世界上最早的計算工具

?算盤中國唐代第一種手動式計數器沿有至今

?計算尺1622年手動式，上世紀70年代被計算器取代

可進行加、減、乘、除、指數、三角函數

?加法器1642年機械式，只能做加法

1.1引言

?計算器1673年德國GottfriedLeibniz,機械式

可進行加、減、乘、除和開方

?差分機和分析機

查爾斯.巴貝奇1812年差分機1834年分析機

分析機：體現了現代電子計算機的結構、設計思想

被稱為現代通用計算機的雛形

1.2計算機的誕生和發展

■計算機的誕生

圖靈機、ENIAC和馮?諾依曼體系結構在理論上、工作原理、體系結

構上奠定現代電子計算機的基礎

?圖靈機(Turingmachine,TM)

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

解決問題；什么是計算？什么是可計算性？

組成：計算X+1的圖靈機M

L11

紙帶

讀寫頭

(1)M的狀態：接受狀態、進位狀態.初始時處于進位狀態.

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

進位狀態：讀到“或空白，則改寫L進入接受狀態，立即停機；

讀到1,則改寫為o,狀態保住不變，讀寫頭左移,

1.2計算機的誕生和發展

圖靈機的能力;高級程序設計語言=現代通用計算機

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

一切直覺上能行可計算的函數都可用圖靈機計算，反之亦然

，可計算的：圖靈機可計算的就是可計算的

世界上的問題＜

、不可計算的

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

計算機的理論問題“昇鞏科了《乂

圖靈的貢獻

圖靈測試：回答了什么樣的機器具有智能

人工智能的理論基礎人工智能之父

美國計算機學會ACM于1966年創立了“圖靈獎”

1.2計算機的誕生和發展

?ENIAC（電子數字積分計算機）1946.2-1955.10賓州大學

每秒5千次加減運算

Q沒有存儲器

采用十進制

第一款商用計算機：UNIVAL

1947年，莫奇萊和埃克特

僅表明電子計算機時代的到來

1.2計算機的誕生和發展

?馮?諾依曼體系結構計算機

人類第二臺計算機；EDVAC（離散變量自動電子計算機）1945年

馮?諾依曼參與研制并且發表：關于EDVAC的報告草案

B采用二進制

口存儲程序：程序和數據一起存儲在內存中

五個部分：運算器、控制器、存儲器、輸入設備和輸出設備

奠定了現代計算機體系結構和工作原理

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

1.2計算機的誕生和發展

■計算機的分代

時代年份耨件運算速度軟件應用

機器語言科學計算

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

匯編語言軍事領域

數據處理

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

工業控制

文字處理

三64-70集成電路每秒幾百萬次操作系統

圖形處理

四71年迄今大規模集成電路達到每秒億億次數據庫、網絡等各個領域

電子管晶體管集成電路大規模集成電路

1.2計算機的誕生和發展

?發展趨勢：微型化、巨型化、網絡化和智能化

?未來新型計算機

①光計算機

利用光子取代電子進行數據運算、傳輸和存儲

不同波長的表示不同的數據

優點：超高速

缺點：體積龐大

②生物計算機（分子計算機）

20世紀80年代中期開始研制

采用了生物芯片

③量子計算機

利用處于多現實態下的原子進行運算的計算機，

這種多現實態是量子力學的標志.

1.2計算機的誕生和發展

■計算機的分類

通用機

按用途分類

專用機

高性能計算機（巨型機或大型機），

速度最快、處理能力最強、

最快：Titan每秒2億億次浮點運算

中國：天河1A每秒4.70千萬億次浮點運算第8

微型計算機：

桌面型計算機、筆記本電腦、平板電腦、移動設備

按綜合性能

工作站：介于與小型機之間高檔微機系統

指標分類一PC

高分辨率、大容量內外存，圖形功能較強

服務器：網絡環境中對外提供服務的計算機系統

嵌入式計算機：數量超過PC

1.2計算機的誕生和發展

■計算機的應用類型

i.科學計算

2.數據處理

3.電子商務①B2B阿里巴巴

②B2c京東商城

③C2c淘寶網

4.過程控制

5.C/\I)/CAM/CIMS

6.多媒體技術

7.人工智能

卡斯帕羅夫對弈“深藍”

1.2計算機的誕生和發展

■計算機文化

?物質文化

計算機的軟、硬件設備以及使用方法

?非物質文化

計算機學科對臼然科學和社會科學等的廣泛滲透，

創造和形成了新的科學思想、科學方法、科學精神、價值標準等

計算機應用改變r傳統社會，形成了網絡社會等虛擬的社會形態

產生了相應的語言、風俗、道德、法律等

最重要的是計算機網絡文化

1.3計算思維

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

代表學科：數學

三大科學思維'實驗思維(實證思維)特征：觀察和總結自然規律

代表學科：物理學

〔計算思維(構造思維)特征：設計和構造

代表學科：計算機科學

計算思維：運用計算機科學的基礎概念進行問題求解、系統設計、

以及人類行為理解等涵蓋計算機科學之廣度的一系列思維活動

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

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

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

1.3計算思維

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

迭代法

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

程序：

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

s=s?i;

經典迭代：牛頓迭代法

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

原型機。一原型機1—原型機2

遞歸

intfac(intn)voidmaiiK)

if(n==l)inty;

return11);y=f(4)

elsecout?y;

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

不就再分■

1.3計算思維

i.計算思維的本質：抽象和自動化

抽象：完全超越物理的時空觀，并完全用符號來表示

數學抽象是一種特例

示例1.3哥尼斯堡七橋問題18世紀經典數學問題

在用尼斯堡的一個公園里，有七座橋將普雷格爾河中兩個島以及島

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

座橋一次，再回到起點？

自動化：機械地一步一步自動執行，其基礎和前提是抽像

1.3計算思維

2.計算思維的特征

?是屬于人的思維方式，不是計算機的思維方式

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

?可以由人執行，也可以由計算機執行

?是思想，不是人造物

?是概念化，不是程序化

3.計算思維的基本問題

?可計算性

一個問題是可計算的是指可以使用計算機在有限步驟內解決

邱奇一圖靈論題：圖靈機可以計算的就是可計算的

?計算復雜性

時間復雜性和空間復雜性

1.3計算思維

示例4矩陣相乘：CnXn=AnXllXBnXn

產

計算％需要n次乘法和n?1次加法

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

示例5漢諾塔問題

大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上

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

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

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

只能移動一個01盤.

iAQ]

1.3計算思維

漢諾塔問題分析

假設有n黃金圓盤，移動次數是f(n)

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

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

f(64)=2W-1=18446744073709551615

假如每秒鐘移動一次，一個365天，則約需要584942417355年,即5849億

而地球的壽命才45億年.

假使用計算機進行每秒1億次的移動，也需要5849年。

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

當n值稍大時，0(2^的問題就無法計算了

1