1、1,第一章 計算機文化與計算思維,1.1 引言 1.2 計算機的誕生和發(fā)展 1.3 計算思維基礎,2,1.1 引言,人類為什么要發(fā)明計算機？ 人的計算速度很低 祖沖之計算至小數(shù)點后7位數(shù)用了15年 計算3030的行列式需要幾個人年 中國第一棵原子彈研制時，數(shù)百位科學家在大禮堂打算盤 早期的計算工具 算 籌 春秋戰(zhàn)國時期世界上最早的計算工具 算 盤 中國唐代 第一種手動式計數(shù)器 沿有至今 計算尺 1622年 手動式，上世紀70年代被計算器取代 可進行加、減、乘、除、指數(shù)、三角函數(shù) 加法器 1642年 機械式，只能做加法,3,1.1 引言, 計算器 1673年德國Gottfried Leibniz

2、，機械式 可進行加、減、乘、除和開方 差分機和分析機,查爾斯.巴貝奇 1812年差分機 1834年分析機,分析機：體現(xiàn)了現(xiàn)代電子計算機的結構、設計思想 被稱為現(xiàn)代通用計算機的雛形,4,（1）M的狀態(tài)：接受狀態(tài)、進位狀態(tài)。初始時處于進位狀態(tài)。 （2）從右向左掃描紙帶。 進位狀態(tài)：讀到0或空白，則改寫1，進入接受狀態(tài)，立即停機； 讀到1，則改寫為0，狀態(tài)保住不變，讀寫頭左移。,1.2 計算機的誕生和發(fā)展, 計算機的誕生 圖靈機、ENIAC和馮諾依曼體系結構在理論上、工作原理、體系結構上奠定現(xiàn)代電子計算機的基礎 圖靈機(Turing machine，TM ) 阿蘭圖靈（Alan Mathison T

3、uring ，19121954） 解決問題；什么是計算？什么是可計算性？ 組成：計算X+1的圖靈機M,紙帶,讀寫頭,5,1.2 計算機的誕生和發(fā)展,圖靈機的能力=高級程序設計語言=現(xiàn)代通用計算機 邱奇、圖靈和哥德爾斷言： 一切直覺上能行可計算的函數(shù)都可用圖靈機計算，反之亦然邱奇圖靈論題,世界上的問題,可計算的：圖靈機可計算的就是可計算的,不可計算的,圖靈的貢獻,圖靈機模型：解決了可計算問題 計算機的理論問題,圖靈測試：回答了什么樣的機器具有智能 人工智能的理論基礎,美國計算機學會ACM于1966年創(chuàng)立了“圖靈獎”,計算機科學之父,人工智能之父,6,1.2 計算機的誕生和發(fā)展, ENIAC（電子

4、數(shù)字積分計算機） 1946.21955.10 賓州大學,每秒5千次加減運算 沒有存儲器 采用十進制,第一款商用計算機：UNIVAL 1947年，莫奇萊和?？颂?僅表明電子計算機時代的到來,7,1.2 計算機的誕生和發(fā)展, 馮諾依曼體系結構計算機 人類第二臺計算機；EDVAC（離散變量自動電子計算機） 1945年 馮諾依曼參與研制并且發(fā)表：關于 EDVAC的報告草案,采用二進制 存儲程序：程序和數(shù)據(jù)一起存儲在內存中 五個部分：運算器、控制器、存儲器、輸入設備和輸出設備,奠定了現(xiàn)代計算機體系結構和工作原理 迄今為止的計算機都采用這種思想，稱為馮諾依曼計算機,8, 計算機的分代,電子管,晶體管,集成

5、電路,大規(guī)模集成電路,1.2 計算機的誕生和發(fā)展,9, 發(fā)展趨勢：微型化、巨型化、網絡化和智能化 未來新型計算機, 光計算機 利用光子取代電子進行數(shù)據(jù)運算、傳輸和存儲 不同波長的表示不同的數(shù)據(jù) 優(yōu)點：超高速 缺點：體積龐大, 生物計算機（分子計算機） 20世紀80年代中期開始研制 采用了生物芯片, 量子計算機 利用處于多現(xiàn)實態(tài)下的原子進行運算的計算機， 這種多現(xiàn)實態(tài)是量子力學的標志。,1.2 計算機的誕生和發(fā)展,10, 計算機的分類,按綜合性能指標分類,高性能計算機（巨型機或大型機）： 速度最快、處理能力最強、 最快：Titan 每秒2億億次浮點運算 中國：天河1A 每秒4.70千萬億次浮點運

6、算 第8,工作站：介于PC與小型機之間高檔微機系統(tǒng) 高分辨率、大容量內外存，圖形功能較強,微型計算機： 桌面型計算機、筆記本電腦、平板電腦、移動設備,服務器：網絡環(huán)境中對外提供服務的計算機系統(tǒng),按用途分類,通用機,專用機,1.2 計算機的誕生和發(fā)展,嵌入式計算機：數(shù)量超過PC,11,1.2 計算機的誕生和發(fā)展, 計算機的應用類型1. 科學計算2. 數(shù)據(jù)處理3. 電子商務 B2B 阿里巴巴 B2C 京東商城 C2C 淘寶網 4. 過程控制5. CAD/CAM/CIMS6. 多媒體技術 7.人工智能,卡斯帕羅夫對弈“深藍”,12,1.2 計算機的誕生和發(fā)展, 計算機文化 物質文化 計算機的軟、硬件

7、設備以及使用方法 非物質文化 計算機學科對自然科學和社會科學等的廣泛滲透， 創(chuàng)造和形成了新的科學思想、科學方法、科學精神、價值標準等 計算機應用改變了傳統(tǒng)社會，形成了網絡社會等虛擬的社會形態(tài) 產生了相應的語言、風俗、道德、法律等 最重要的是計算機網絡文化,13,示例1： 計算f(x)在a, b上的積分 數(shù)學方法 牛頓萊布尼茲： f(x) F(x) 計算思維 黎曼積分：對a, b進行n等分 計算小矩形面積 累加,三大科學思維,計算思維：運用計算機科學的基礎概念進行問題求解、系統(tǒng)設計、 以及人類行為理解等涵蓋計算機科學之廣度的一系列思維活動,1.3 計算思維,理論思維（推理思維） 特征：以推理和演

8、繹為特征 代表學科：數(shù)學,實驗思維（實證思維） 特征：觀察和總結自然規(guī)律 代表學科：物理學,計算思維（構造思維） 特征：設計和構造 代表學科：計算機科學,14,迭代法 迭代過程：1!=1 2!=1!*2 3!=2!*3 n!=(n-1)!*n 程序： s=1; for(i=1;i=n;i+) s=s*i; 經典迭代：牛頓迭代法 J20研制過程就是迭代過程： 原型機0 原型機1 原型機2 原型機3,示例2： 計算n的階乘f(n)=n!,1.3 計算思維,遞歸,分解,問題,小問題,n!,(n-1)!,問題,分解,小問題,更小問題,最小問題,分解,分解,不能再分解,n!,(n-1)!,(n-2)!,

9、1!,int fac(int n) if(n=1) return(1); else return(fac(n-1)*n); ,void main() int y; y=f(4) couty; ,15,示例1.3 哥尼斯堡七橋問題 18世紀經典數(shù)學問題 在哥尼斯堡的一個公園里，有七座橋將普雷格爾河中兩個島以及島與河岸連接起來。問是否可能從這四塊陸地中任一塊出發(fā)，恰好通過每座橋一次，再回到起點？,1計算思維的本質：抽象和自動化 抽象：完全超越物理的時空觀，并完全用符號來表示 數(shù)學抽象是一種特例,1.3 計算思維,哥尼斯堡七橋問題,哥尼斯堡七橋問題的抽象,自動化：機械地一步一步自動執(zhí)行，其基礎和前提

10、是抽象,16,2計算思維的特征 是屬于人的思維方式，不是計算機的思維方式 遞歸、迭代、黎曼積分早已提出，是人類賦予計算機 可以由人執(zhí)行，也可以由計算機執(zhí)行 是思想，不是人造物 是概念化，不是程序化 3計算思維的基本問題 可計算性 一個問題是可計算的是指可以使用計算機在有限步驟內解決 邱奇圖靈論題：圖靈機可以計算的就是可計算的 計算復雜性 時間復雜性和空間復雜性,1.3 計算思維,17,示例4 矩陣相乘：Cnn=AnnBnn,1.3 計算思維,計算cij需要n次乘法和n-1次加法 c中有n2個元素，故c需要n3次乘法和n2*(n-1)次加法 示例5 漢諾塔問題 大梵天創(chuàng)造世界的時候做了三根金剛石

11、柱子，在一根柱子上 從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅 門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。 并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次 只能移動一個圓盤。,18,1.3 計算思維,漢諾塔問題分析 假設有n黃金圓盤，移動次數(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億年。 假如使用計算

12、機進行每秒1億次的移動，也需要5849年。 時間復雜性：O(1) O(logn) O(n) O(nlogn) O(n2）O(n3) O(nk) O(2n) 當n值稍大時，O(2n)的問題就無法計算了,19,4圖靈測試 機器能有智能嗎？換一句話來，通過什么樣的測試機器才能稱擁有智能？,1.3 計算思維,無法判斷對方是人還是計算機，那么就可以認為計算機具有同人相當?shù)闹橇?測試場景,20,5計算思維基本方法 從方法論的角度來說，計算思維的核心是計算思維方法,1.3 計算思維, 約簡、嵌入、轉化和仿真等方法，用來把一個看來困難的問題重新闡釋成一個我們知道問題怎樣解決的思維方法； 遞歸方法、并行方法、把代碼譯成數(shù)據(jù)又能把數(shù)據(jù)譯成代碼的方法、 多維分析推廣的類型檢查方法； 抽象和分解方法，用來控制龐雜的任務或進行巨大復雜系統(tǒng)設計； 基于關注分離的方法（SoC方法）；,計算思維方法,來自數(shù)學和工程,來自計算機科學自身,21,1.3 計算思維,