同濟大學計算機基礎(chǔ) 第1章 計算機文化與計算思維第六版

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

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

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

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

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

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

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

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

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

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

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

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

13、行為理解等涵蓋計算機科學之廣度的一系列思維活動等涵蓋計算機科學之廣度的一系列思維活動 1.3 1.3 計算思維計算思維理論思維（推理思維）理論思維（推理思維） 特征：以推理和演繹為特征特征：以推理和演繹為特征 代表學科：數(shù)學代表學科：數(shù)學 實驗思維（實證思維）實驗思維（實證思維） 特征：觀察和總結(jié)自然規(guī)律特征：觀察和總結(jié)自然規(guī)律 代表學科：物理學代表學科：物理學 計算思維（構(gòu)造思維）計算思維（構(gòu)造思維） 特征：設(shè)計和構(gòu)造特征：設(shè)計和構(gòu)造 代表學科：計算機科學代表學科：計算機科學 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研制過程就是迭代過程：研制過程就是迭代過程： 原型機原型機0 原型機原型機1 原型機原型機2 原型機原型機3示例示例2： 計算計算n的階乘的階乘f(n)=n!1.3 1.3 計算思維計算思維 遞歸遞歸 分分解解問題問題小問題小問題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īng)典數(shù)學問題世紀經(jīng)典數(shù)學問題 在哥尼斯堡的一個公園里，有七座橋?qū)⑵绽赘駹柡又袃蓚€島以及島在哥尼斯堡的一個公園里，有七座橋?qū)⑵绽赘駹柡又袃蓚€島以及島與河岸連接起來。問是否可能從這四塊陸地中任一塊出發(fā)，恰好通過每與河岸連接起來。問是否可能從這四塊陸地中任一塊出發(fā)，恰好通過每座橋一次，再回到起點？座橋一次，再回到起點？1計算思維的本質(zhì)：抽象和自動化計算思維的本質(zhì)：抽象和自動化 抽象：抽象：完全超越物理的時空觀，并完全用符號來表示完全超越物理的時空觀，并完全用

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

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

18、次加法次加法示示例例5 漢諾塔問題漢諾塔問題 大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上 從下往上按照大小順序摞著從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅片黃金圓盤。大梵天命令婆羅 門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。 并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次 只能移動一個圓盤。只能移動一個圓盤。 181.3 1.3 計算思維計算思維漢諾塔問題分析漢諾塔問題分析 假設(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，時間復雜性記作，時間復雜性記作O(2n) f(64) = 264-1=18446744073709551615 假如每秒鐘移動一次，一年假如每秒鐘移動一次，一年365天，則約需要天，則約需要584942417355年，即年，即5849億年億年 而地球的壽命才而地球的壽命才45億年。億年。 假如使用計算機進行每秒假如使用計算機進行每秒1億次的移動，也需要億次的移動，也需要5849年。年。 時間復雜性：時間復雜性：O(1) O(logn) O(n) O(nlo

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