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

1、1第一章第一章 計(jì)算機(jī)文化與計(jì)算思維計(jì)算機(jī)文化與計(jì)算思維1.1 引言引言 1.2 計(jì)算機(jī)計(jì)算機(jī)的誕生和發(fā)展的誕生和發(fā)展 1.3 計(jì)算思維基礎(chǔ)計(jì)算思維基礎(chǔ)2 1.1 1.1 引言引言 人類為什么要發(fā)明計(jì)算機(jī)？ 人的計(jì)算速度很低 祖沖之計(jì)算祖沖之計(jì)算至小數(shù)點(diǎn)后至小數(shù)點(diǎn)后7位數(shù)用了位數(shù)用了15年年 計(jì)算計(jì)算3030的行列式需要幾個人年的行列式需要幾個人年 中國第一棵原子彈研制時，數(shù)百位科學(xué)家在大禮堂打算盤中國第一棵原子彈研制時，數(shù)百位科學(xué)家在大禮堂打算盤 早期的計(jì)算工具 算算 籌籌 春秋戰(zhàn)國時期春秋戰(zhàn)國時期世界上最早的計(jì)算工具世界上最早的計(jì)算工具 算算 盤盤 中國唐代中國唐代 第一種手動式計(jì)數(shù)器第一

2、種手動式計(jì)數(shù)器 沿有至今沿有至今 計(jì)算尺計(jì)算尺 1622年年 手動式，上世紀(jì)手動式，上世紀(jì)70年代被計(jì)算器取代年代被計(jì)算器取代可進(jìn)行加、減、乘、除、指數(shù)、三角函數(shù)可進(jìn)行加、減、乘、除、指數(shù)、三角函數(shù) 加法器加法器 1642年年 機(jī)械式，只能做加法機(jī)械式，只能做加法3 1.1 1.1 引言引言 計(jì)算器計(jì)算器 1673年年德國德國Gottfried Leibniz，機(jī)械式，機(jī)械式 可進(jìn)行加、減、乘可進(jìn)行加、減、乘、除和開方、除和開方 差分機(jī)和分析機(jī)差分機(jī)和分析機(jī) 查爾斯查爾斯. .巴貝奇巴貝奇 1812年差分機(jī)年差分機(jī) 1834年分析機(jī)年分析機(jī) 分析機(jī)：體現(xiàn)了現(xiàn)代電子計(jì)算機(jī)的結(jié)構(gòu)、設(shè)計(jì)思想分析機(jī)：

3、體現(xiàn)了現(xiàn)代電子計(jì)算機(jī)的結(jié)構(gòu)、設(shè)計(jì)思想 被稱為現(xiàn)代通用計(jì)算機(jī)的雛形被稱為現(xiàn)代通用計(jì)算機(jī)的雛形4（1）M的狀態(tài)：接受狀態(tài)、進(jìn)位狀態(tài)。初始時處于進(jìn)位狀態(tài)。的狀態(tài)：接受狀態(tài)、進(jìn)位狀態(tài)。初始時處于進(jìn)位狀態(tài)。（2）從右向左掃描紙帶。）從右向左掃描紙帶。 進(jìn)位狀態(tài)：讀到進(jìn)位狀態(tài)：讀到0或空白，則改寫或空白，則改寫1，進(jìn)入接受狀態(tài)，立即停機(jī)；，進(jìn)入接受狀態(tài)，立即停機(jī)； 讀到讀到1，則改寫為，則改寫為0，狀態(tài)保住不變，讀寫頭左移，狀態(tài)保住不變，讀寫頭左移。1.2 1.2 計(jì)算機(jī)的誕生和發(fā)展計(jì)算機(jī)的誕生和發(fā)展 計(jì)算機(jī)的誕生 圖靈機(jī)、圖靈機(jī)、ENIAC和馮和馮諾依曼體系結(jié)構(gòu)在理論上、工作原理、體系結(jié)諾依曼體系結(jié)構(gòu)在

4、理論上、工作原理、體系結(jié)構(gòu)上奠定現(xiàn)代電子計(jì)算機(jī)的基礎(chǔ)構(gòu)上奠定現(xiàn)代電子計(jì)算機(jī)的基礎(chǔ) 圖靈機(jī)圖靈機(jī)(Turing machine，TM ) 阿蘭阿蘭圖靈（圖靈（Alan Mathison Turing ，19121954） 解決問題；解決問題；什么是計(jì)算？什么是可計(jì)算性？什么是計(jì)算？什么是可計(jì)算性？ 組成：計(jì)算組成：計(jì)算X+1的圖靈機(jī)的圖靈機(jī)M紙帶紙帶 讀寫頭讀寫頭 51.2 1.2 計(jì)算機(jī)的誕生和發(fā)展計(jì)算機(jī)的誕生和發(fā)展 圖靈機(jī)的能力圖靈機(jī)的能力=高級程序設(shè)計(jì)語言高級程序設(shè)計(jì)語言=現(xiàn)代通用計(jì)算機(jī)現(xiàn)代通用計(jì)算機(jī) 邱奇、圖靈和哥德爾斷言：邱奇、圖靈和哥德爾斷言： 一切直覺上能行可計(jì)算的函數(shù)都可用圖靈機(jī)

5、計(jì)算，反之亦然一切直覺上能行可計(jì)算的函數(shù)都可用圖靈機(jī)計(jì)算，反之亦然邱奇邱奇圖靈論題圖靈論題 世界上的問題 可計(jì)算的：圖靈機(jī)可計(jì)算的就是可計(jì)算的 不可計(jì)算的 圖靈的貢獻(xiàn) 圖靈機(jī)模型：解決了可計(jì)算問題 計(jì)算機(jī)的理論問題圖靈測試：回答了什么樣的機(jī)器具有智能 人工智能的理論基礎(chǔ) 美國計(jì)算機(jī)學(xué)會美國計(jì)算機(jī)學(xué)會ACM于于1966年創(chuàng)立了年創(chuàng)立了“圖靈獎圖靈獎” 計(jì)算機(jī)科學(xué)之父計(jì)算機(jī)科學(xué)之父 人工智能之父人工智能之父61.2 1.2 計(jì)算機(jī)的誕生和發(fā)展計(jì)算機(jī)的誕生和發(fā)展 ENIAC（電子數(shù)字積分計(jì)算機(jī)）（電子數(shù)字積分計(jì)算機(jī)） 1946.21955.10 賓州大學(xué)賓州大學(xué):每秒每秒5千次加減運(yùn)算千次加減運(yùn)算:

6、沒有存儲器沒有存儲器:采用十進(jìn)制采用十進(jìn)制第一款商用計(jì)算機(jī)：第一款商用計(jì)算機(jī)：UNIVAL1947年，莫奇萊和?？颂啬?，莫奇萊和?？颂貎H表明電子計(jì)算機(jī)時代的到來僅表明電子計(jì)算機(jī)時代的到來 71.2 1.2 計(jì)算機(jī)的誕生和發(fā)展計(jì)算機(jī)的誕生和發(fā)展 馮馮諾依曼體系結(jié)構(gòu)計(jì)算機(jī)諾依曼體系結(jié)構(gòu)計(jì)算機(jī) 人人類第二臺計(jì)算機(jī)；類第二臺計(jì)算機(jī)；EDVAC（離散變量自動電子計(jì)算機(jī)）（離散變量自動電子計(jì)算機(jī)） 1945年年 馮馮諾依曼參與研制并且發(fā)表：諾依曼參與研制并且發(fā)表：關(guān)于關(guān)于 EDVAC的報(bào)告草案的報(bào)告草案:采用采用二進(jìn)制二進(jìn)制 :存儲程序：存儲程序：程序和數(shù)據(jù)一起存儲在內(nèi)存中程序和數(shù)據(jù)一起存儲在內(nèi)存中 :五

7、個部分：五個部分：運(yùn)算器運(yùn)算器、控制器、控制器、存儲器存儲器、輸入設(shè)備和、輸入設(shè)備和輸出設(shè)備輸出設(shè)備 奠定了現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)和工作原理奠定了現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)和工作原理迄今為止的計(jì)算機(jī)都采用這種思想，稱為馮迄今為止的計(jì)算機(jī)都采用這種思想，稱為馮諾依曼計(jì)算機(jī)諾依曼計(jì)算機(jī) 8 計(jì)算機(jī)的分代時代年份器件運(yùn)算速度軟件應(yīng)用一 46-58電子管每秒幾千次 機(jī)器語言匯編語言 科學(xué)計(jì)算軍事領(lǐng)域二58-64晶體管每秒幾十萬次 高級語言數(shù)據(jù)處理工業(yè)控制 三64-70集成電路每秒幾百萬次 操作系統(tǒng)文字處理圖形處理四71年迄今大規(guī)模集成電路達(dá)到每秒億億次 數(shù)據(jù)庫、網(wǎng)絡(luò)等各個領(lǐng)域電子管電子管晶體管晶體管集成電路集成電

8、路大規(guī)模集成電路大規(guī)模集成電路1.2 1.2 計(jì)算機(jī)的誕生和發(fā)展計(jì)算機(jī)的誕生和發(fā)展9 發(fā)展趨勢：微型化、巨型化、網(wǎng)絡(luò)化和智能化發(fā)展趨勢：微型化、巨型化、網(wǎng)絡(luò)化和智能化 未來新型計(jì)算機(jī)未來新型計(jì)算機(jī) 光計(jì)算機(jī)光計(jì)算機(jī) 利用光子取代電子進(jìn)行數(shù)據(jù)運(yùn)算、傳輸和存儲利用光子取代電子進(jìn)行數(shù)據(jù)運(yùn)算、傳輸和存儲 不同波長的表示不同的數(shù)據(jù)不同波長的表示不同的數(shù)據(jù) 優(yōu)點(diǎn)：超高速優(yōu)點(diǎn)：超高速 缺點(diǎn)：體積龐大缺點(diǎn)：體積龐大 生物計(jì)算機(jī)（分子計(jì)算機(jī)）生物計(jì)算機(jī)（分子計(jì)算機(jī)） 2 0 2 0 世 紀(jì)世 紀(jì) 8 08 0 年 代 中 期 開 始 研 制年 代 中 期 開 始 研 制 采用了生物芯片采用了生物芯片 量子計(jì)算機(jī)

9、量子計(jì)算機(jī) 利用處于多現(xiàn)實(shí)態(tài)下的原子進(jìn)行運(yùn)算的計(jì)算機(jī)，利用處于多現(xiàn)實(shí)態(tài)下的原子進(jìn)行運(yùn)算的計(jì)算機(jī)， 這種多現(xiàn)實(shí)態(tài)是量子力學(xué)的標(biāo)志。這種多現(xiàn)實(shí)態(tài)是量子力學(xué)的標(biāo)志。 1.2 1.2 計(jì)算機(jī)的誕生和發(fā)展計(jì)算機(jī)的誕生和發(fā)展10 計(jì)算機(jī)的分類 按綜合性能按綜合性能指標(biāo)分類指標(biāo)分類高性能計(jì)算機(jī)（高性能計(jì)算機(jī)（巨型機(jī)或大型機(jī)巨型機(jī)或大型機(jī)）：）： 速度最快、處理能力最強(qiáng)、速度最快、處理能力最強(qiáng)、 最快：最快：Titan 每秒每秒2億億次浮點(diǎn)運(yùn)算億億次浮點(diǎn)運(yùn)算 中國：天河中國：天河1A 每秒每秒4.70千萬億次浮點(diǎn)運(yùn)算千萬億次浮點(diǎn)運(yùn)算 第第8 工作站工作站：介于介于PCPC與小型機(jī)之間高檔微機(jī)系統(tǒng)與小型機(jī)之間高

10、檔微機(jī)系統(tǒng) 高分辨率、大容量內(nèi)外存，圖形功能較強(qiáng)高分辨率、大容量內(nèi)外存，圖形功能較強(qiáng)微型計(jì)算機(jī)微型計(jì)算機(jī)： 桌面型計(jì)算機(jī)、筆記本電腦、平板電腦、移動設(shè)備桌面型計(jì)算機(jī)、筆記本電腦、平板電腦、移動設(shè)備 服務(wù)器：網(wǎng)絡(luò)環(huán)境中對外提供服務(wù)的計(jì)算機(jī)系統(tǒng)服務(wù)器：網(wǎng)絡(luò)環(huán)境中對外提供服務(wù)的計(jì)算機(jī)系統(tǒng)按用途分類按用途分類通用機(jī)通用機(jī)專用機(jī)專用機(jī)1.2 1.2 計(jì)算機(jī)的誕生和發(fā)展計(jì)算機(jī)的誕生和發(fā)展嵌入式計(jì)算機(jī)：數(shù)量超過嵌入式計(jì)算機(jī)：數(shù)量超過PCPC 111.2 1.2 計(jì)算機(jī)的誕生和發(fā)展計(jì)算機(jī)的誕生和發(fā)展 計(jì)算機(jī)的應(yīng)用類型1. 科學(xué)計(jì)算科學(xué)計(jì)算2. 數(shù)據(jù)處理數(shù)據(jù)處理3. 電子商務(wù)電子商務(wù) B2B 阿里巴巴阿里巴巴

11、B2C 京東商城京東商城 C2C 淘寶網(wǎng)淘寶網(wǎng)4. 過程控制過程控制5. CAD/CAM/CIMS6. 多媒體技術(shù)多媒體技術(shù) 7. .人工智能人工智能卡斯帕羅夫?qū)摹吧钏{(lán)” 121.2 1.2 計(jì)算機(jī)的誕生和發(fā)展計(jì)算機(jī)的誕生和發(fā)展 計(jì)算機(jī)文化 物質(zhì)文化物質(zhì)文化 計(jì)算機(jī)的軟、硬件設(shè)備以及使用方法計(jì)算機(jī)的軟、硬件設(shè)備以及使用方法 非物質(zhì)文化非物質(zhì)文化 計(jì)算機(jī)學(xué)科對自然科學(xué)和社會科學(xué)等的廣泛滲透，計(jì)算機(jī)學(xué)科對自然科學(xué)和社會科學(xué)等的廣泛滲透， 創(chuàng)造和形成了新的科學(xué)思想、科學(xué)方法、科學(xué)精神、價(jià)值標(biāo)準(zhǔn)等創(chuàng)造和形成了新的科學(xué)思想、科學(xué)方法、科學(xué)精神、價(jià)值標(biāo)準(zhǔn)等 計(jì)算機(jī)應(yīng)用改變了傳統(tǒng)社會，形成了網(wǎng)絡(luò)社會等虛擬

12、的社會形態(tài)計(jì)算機(jī)應(yīng)用改變了傳統(tǒng)社會，形成了網(wǎng)絡(luò)社會等虛擬的社會形態(tài) 產(chǎn)生了相應(yīng)的語言、風(fēng)俗、道德、法律等產(chǎn)生了相應(yīng)的語言、風(fēng)俗、道德、法律等 最重要的是計(jì)算機(jī)網(wǎng)絡(luò)文化最重要的是計(jì)算機(jī)網(wǎng)絡(luò)文化 13示例示例1 1： 計(jì)算計(jì)算f(x)是是a, b上的積分上的積分 數(shù)學(xué)方法數(shù)學(xué)方法 牛頓牛頓萊布尼茲：萊布尼茲： f(x) F(x) 計(jì)算思維計(jì)算思維 黎曼積分：對黎曼積分：對a, b進(jìn)行進(jìn)行n等分等分 計(jì)算小矩形面積計(jì)算小矩形面積 累加累加 三大科學(xué)思維三大科學(xué)思維計(jì)算思維：計(jì)算思維：運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問題求解問題求解、系統(tǒng)設(shè)計(jì)系統(tǒng)設(shè)計(jì)、 以及以及人類行為理解人類

13、行為理解等涵蓋計(jì)算機(jī)科學(xué)之廣度的一系列思維活動等涵蓋計(jì)算機(jī)科學(xué)之廣度的一系列思維活動 1.3 1.3 計(jì)算思維計(jì)算思維理論思維（推理思維）理論思維（推理思維） 特征：以推理和演繹為特征特征：以推理和演繹為特征 代表學(xué)科：數(shù)學(xué)代表學(xué)科：數(shù)學(xué) 實(shí)驗(yàn)思維（實(shí)證思維）實(shí)驗(yàn)思維（實(shí)證思維） 特征：觀察和總結(jié)自然規(guī)律特征：觀察和總結(jié)自然規(guī)律 代表學(xué)科：物理學(xué)代表學(xué)科：物理學(xué) 計(jì)算思維（構(gòu)造思維）計(jì)算思維（構(gòu)造思維） 特征：設(shè)計(jì)和構(gòu)造特征：設(shè)計(jì)和構(gòu)造 代表學(xué)科：計(jì)算機(jī)科學(xué)代表學(xué)科：計(jì)算機(jī)科學(xué) baxF| )(14 迭代法迭代法 迭代過程：迭代過程：1!=1 2!=1!*2 3!=2!*3 n!=(n-1)!

14、*n 程序：程序： s=1; for(i=1;i=n;i+) s=s*i; 經(jīng)典迭代：牛頓迭代法經(jīng)典迭代：牛頓迭代法 J20研制過程就是迭代過程：研制過程就是迭代過程： 原型機(jī)原型機(jī)0 原型機(jī)原型機(jī)1 原型機(jī)原型機(jī)2 原型機(jī)原型機(jī)3示例示例2： 計(jì)算計(jì)算n的階乘的階乘f(n)=n!1.3 1.3 計(jì)算思維計(jì)算思維 遞歸遞歸 分分解解問題問題小問題小問題n!(n-1)!問題問題分分解解小問題小問題更小更小問題問題最小最小問題問題分分解解分分解解不能再分解不能再分解n!(n-1)!(n-2)!1! int fac(int n) if(n=1) return(1); else return(fac(

15、n-1)*n); void main() int y; y=f(4) couty;15示例示例1.3 哥尼斯堡七橋問題哥尼斯堡七橋問題 18世紀(jì)經(jīng)典數(shù)學(xué)問題世紀(jì)經(jīng)典數(shù)學(xué)問題 在哥尼斯堡的一個公園里，有七座橋?qū)⑵绽赘駹柡又袃蓚€島以及島在哥尼斯堡的一個公園里，有七座橋?qū)⑵绽赘駹柡又袃蓚€島以及島與河岸連接起來。問是否可能從這四塊陸地中任一塊出發(fā)，恰好通過每與河岸連接起來。問是否可能從這四塊陸地中任一塊出發(fā)，恰好通過每座橋一次，再回到起點(diǎn)？座橋一次，再回到起點(diǎn)？1計(jì)算思維的本質(zhì)：抽象和自動化計(jì)算思維的本質(zhì)：抽象和自動化 抽象：抽象：完全超越物理的時空觀，并完全用符號來表示完全超越物理的時空觀，并完全用

16、符號來表示 數(shù)學(xué)抽象是一種特例數(shù)學(xué)抽象是一種特例1.3 1.3 計(jì)算思維計(jì)算思維 哥尼斯堡七橋問題哥尼斯堡七橋問題 哥尼斯堡七橋問題的抽象哥尼斯堡七橋問題的抽象 自動化：自動化：機(jī)械地一步一步自動執(zhí)行，其基礎(chǔ)和前提是抽像機(jī)械地一步一步自動執(zhí)行，其基礎(chǔ)和前提是抽像 162計(jì)算思維的特征計(jì)算思維的特征 是屬于人的思維方式，不是計(jì)算機(jī)的思維方式是屬于人的思維方式，不是計(jì)算機(jī)的思維方式 遞歸、迭代、黎曼積分早已提出，是人類賦予計(jì)算機(jī)遞歸、迭代、黎曼積分早已提出，是人類賦予計(jì)算機(jī) 可以由人執(zhí)行，也可以由計(jì)算機(jī)執(zhí)行可以由人執(zhí)行，也可以由計(jì)算機(jī)執(zhí)行 是思想，不是人造物是思想，不是人造物 是概念化，不是程序化

17、是概念化，不是程序化 3計(jì)算思維的基本問題計(jì)算思維的基本問題 可計(jì)算性可計(jì)算性 一個問題是可計(jì)算的是指可以使用計(jì)算機(jī)在有限步驟內(nèi)解決一個問題是可計(jì)算的是指可以使用計(jì)算機(jī)在有限步驟內(nèi)解決 邱奇圖靈論題：圖靈機(jī)可以計(jì)算的就是可計(jì)算的邱奇圖靈論題：圖靈機(jī)可以計(jì)算的就是可計(jì)算的 計(jì)算復(fù)雜性計(jì)算復(fù)雜性 時間復(fù)雜性和空間復(fù)雜性時間復(fù)雜性和空間復(fù)雜性 1.3 1.3 計(jì)算思維計(jì)算思維17示例示例4 矩陣相乘：矩陣相乘：Cnn=AnnBnn1.3 1.3 計(jì)算思維計(jì)算思維 計(jì)算計(jì)算cij需要需要n次乘法和次乘法和n-1次加法次加法 c中有中有n2個元素，故個元素，故c需要需要n3次乘法和次乘法和n2*(n-1

18、)次加法次加法示例示例5 漢諾塔問題漢諾塔問題 大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上 從下往上按照大小順序摞著從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅片黃金圓盤。大梵天命令婆羅 門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。 并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次 只能移動一個圓盤。只能移動一個圓盤。 181.3 1.3 計(jì)算思維計(jì)算思維漢諾塔問題分析漢諾塔問題分析 假設(shè)有假設(shè)有n黃金圓盤，

19、移動次數(shù)是黃金圓盤，移動次數(shù)是f(n) 有有f(1)=1，f(2)=3，f(3)=7，f(k+1）=2*f(k)+1 故故f(n)=2n-1，時間復(fù)雜性記作，時間復(fù)雜性記作O(2n) f(64) = 264-1=18446744073709551615 假如每秒鐘移動一次，一個假如每秒鐘移動一次，一個365天，則約需要天，則約需要584942417355年，即年，即5849億億年年 而地球的壽命才而地球的壽命才45億年。億年。 假使用計(jì)算機(jī)進(jìn)行每秒假使用計(jì)算機(jī)進(jìn)行每秒1億次的移動，也需要億次的移動，也需要5849年。年。 時間復(fù)雜性：時間復(fù)雜性：O(1) O(logn) O(n) O(nlog

20、n) O(n2）O(n3) O(nk) O(2n) 當(dāng)當(dāng)n值稍大時，值稍大時，O(2n)的問題就無法計(jì)算了的問題就無法計(jì)算了 194圖靈測試圖靈測試 機(jī)器能有智能嗎？換一句話來，通過什么樣的測試機(jī)器才能稱擁有智能？機(jī)器能有智能嗎？換一句話來，通過什么樣的測試機(jī)器才能稱擁有智能？ 1.3 1.3 計(jì)算思維計(jì)算思維無法判斷對方是人還是計(jì)算機(jī)，那么就可以認(rèn)為計(jì)算機(jī)具有同人相當(dāng)?shù)闹橇o法判斷對方是人還是計(jì)算機(jī)，那么就可以認(rèn)為計(jì)算機(jī)具有同人相當(dāng)?shù)闹橇?測試場景測試場景 205計(jì)算思維基本方法計(jì)算思維基本方法 從方法論的角度來說，計(jì)算思維的核心是計(jì)算思維方法從方法論的角度來說，計(jì)算思維的核心是計(jì)算思維方法 1.3 1.3 計(jì)算思維計(jì)算思維 約簡、嵌入、轉(zhuǎn)化和仿真等方法，用來把一個看來困難的問題重新闡約簡、嵌入、轉(zhuǎn)化和仿真等方法，用