1、1.1 引言 1 人類為什么要發明計算機？ 人的計算速度很低 祖沖之計算至小數點后7位數用了15年 計算3030的行列式需要幾個人年 中國第一棵原子彈研制時，數百位科學家在大禮堂打算盤 早期的計算工具 算 籌 春秋戰國時期世界上最早的計算工具 算 盤 中國唐代 第一種手動式計數器 沿有至今 計算尺 1622年 手動式，上世紀70年代被計算器取代可進行加、減、乘、除、指數、三角函數 加法器 1642年 機械式，只能做加法第1頁/共20頁第1頁，共20頁。1.1 引言 2 計算器 1673年德國Gottfried Leibniz，機械式 可進行加、減、乘、除和開方 差分機和分析機 查爾斯.巴貝奇

2、1812年差分機 1834年分析機 分析機：體現了現代電子計算機的結構、設計思想 被稱為現代通用計算機的雛形第2頁/共20頁第2頁，共20頁。3（1）M的狀態：接受狀態、進位狀態。初始時處于進位狀態。（2）從右向左掃描紙帶。 進位狀態：讀到0或空白，則改寫1，進入接受狀態，立即停機； 讀到1，則改寫為0，狀態保住不變，讀寫頭左移。1.2 計算機的誕生和發展 計算機的誕生 圖靈機、ENIAC和馮諾依曼體系結構在理論上、工作原理、體系結構上奠定現代電子計算機的基礎 圖靈機(Turing machine，TM ) 阿蘭圖靈（Alan Mathison Turing ，19121954） 解決問題；什

3、么是計算？什么是可計算性？ 組成：計算X+1的圖靈機M紙帶 讀寫頭 第3頁/共20頁第3頁，共20頁。41.2 計算機的誕生和發展 圖靈機的能力=高級程序設計語言=現代通用計算機 邱奇、圖靈和哥德爾斷言： 一切直覺上能行可計算的函數都可用圖靈機計算，反之亦然邱奇圖靈論題 世界上的問題 可計算的：圖靈機可計算的就是可計算的 不可計算的 圖靈的貢獻 圖靈機模型：解決了可計算問題 計算機的理論問題圖靈測試：回答了什么樣的機器具有智能 人工智能的理論基礎 美國計算機學會ACM于1966年創立了“圖靈獎” 計算機科學之父 人工智能之父第4頁/共20頁第4頁，共20頁。 ENIAC（電子數字積分計算機）

4、1946.21955.10 賓州大學51.2 計算機的誕生和發展每秒5千次加減運算沒有存儲器采用十進制第一款商用計算機：UNIVAL1947年，莫奇萊和埃克特僅表明電子計算機時代的到來 第5頁/共20頁第5頁，共20頁。 馮諾依曼體系結構計算機 人類第二臺計算機；EDVAC（離散變量自動電子計算機） 1945年 馮諾依曼參與研制并且發表：關于 EDVAC的報告草案61.2 計算機的誕生和發展采用二進制 存儲程序：程序和數據一起存儲在內存中 五個部分：運算器、控制器、存儲器、輸入設備和輸出設備 奠定了現代計算機體系結構和工作原理迄今為止的計算機都采用這種思想，稱為馮諾依曼計算機 第6頁/共20頁

5、第6頁，共20頁。 計算機的分代7時代年份器件運算速度軟件應用一 46-58電子管每秒幾千次 機器語言匯編語言 科學計算軍事領域二58-64晶體管每秒幾十萬次 高級語言數據處理工業控制 三64-70集成電路每秒幾百萬次 操作系統文字處理圖形處理四71年迄今大規模集成電路達到每秒億億次 數據庫、網絡等各個領域電子管晶體管集成電路大規模集成電路1.2 計算機的誕生和發展第7頁/共20頁第7頁，共20頁。 發展趨勢：微型化、巨型化、網絡化和智能化 未來新型計算機8 光計算機 利用光子取代電子進行數據運算、傳輸和存儲 不同波長的表示不同的數據 優點：超高速 缺點：體積龐大 生物計算機（分子計算機） 2

6、0世紀80年代中期開始研制 采用了生物芯片 量子計算機 利用處于多現實態下的原子進行運算的計算機， 這種多現實態是量子力學的標志。 1.2 計算機的誕生和發展第8頁/共20頁第8頁，共20頁。 計算機的分類 9按綜合性能指標分類高性能計算機（巨型機或大型機）： 速度最快、處理能力最強、 最快：Titan 每秒2億億次浮點運算 中國：天河1A 每秒4.70千萬億次浮點運算 第8 工作站：介于PC與小型機之間高檔微機系統 高分辨率、大容量內外存，圖形功能較強微型計算機： 桌面型計算機、筆記本電腦、平板電腦、移動設備 服務器：網絡環境中對外提供服務的計算機系統按用途分類通用機專用機1.2 計算機的誕

7、生和發展嵌入式計算機：數量超過PC 第9頁/共20頁第9頁，共20頁。1.2 計算機的誕生和發展10 計算機的應用類型1. 科學計算2. 數據處理3. 電子商務 B2B 阿里巴巴 B2C 京東商城 C2C 淘寶網4. 過程控制5. CAD/CAM/CIMS6. 多媒體技術 7.人工智能卡斯帕羅夫對弈“深藍” 第10頁/共20頁第10頁，共20頁。1.2 計算機的誕生和發展11 計算機文化 物質文化 計算機的軟、硬件設備以及使用方法 非物質文化 計算機學科對自然科學和社會科學等的廣泛滲透， 創造和形成了新的科學思想、科學方法、科學精神、價值標準等 計算機應用改變了傳統社會，形成了網絡社會等虛擬的

8、社會形態 產生了相應的語言、風俗、道德、法律等 最重要的是計算機網絡文化 第11頁/共20頁第11頁，共20頁。12示例1： 計算f(x)是a, b上的積分 數學方法 牛頓萊布尼茲： f(x) F(x) 計算思維 黎曼積分：對a, b進行n等分 計算小矩形面積 累加 三大科學思維計算思維：運用計算機科學的基礎概念進行問題求解、系統設計、 以及人類行為理解等涵蓋計算機科學之廣度的一系列思維活動 1.3 計算思維理論思維（推理思維） 特征：以推理和演繹為特征 代表學科：數學 實驗思維（實證思維） 特征：觀察和總結自然規律 代表學科：物理學 計算思維（構造思維） 特征：設計和構造 代表學科：計算機科

9、學 第12頁/共20頁第12頁，共20頁。13 迭代法 迭代過程：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)!1! int fac(int n) if(n=1) return(1); else return(fac(n-1)*n); void main()

10、int y; y=f(4) couty;第13頁/共20頁第13頁，共20頁。14示例1.3 哥尼斯堡七橋問題 18世紀經典數學問題 在哥尼斯堡的一個公園里，有七座橋將普雷格爾河中兩個島以及島與河岸連接起來。問是否可能從這四塊陸地中任一塊出發，恰好通過每座橋一次，再回到起點？1計算思維的本質：抽象和自動化 抽象：完全超越物理的時空觀，并完全用符號來表示 數學抽象是一種特例1.3 計算思維 哥尼斯堡七橋問題 哥尼斯堡七橋問題的抽象 自動化：機械地一步一步自動執行，其基礎和前提是抽像 第14頁/共20頁第14頁，共20頁。152計算思維的特征 是屬于人的思維方式，不是計算機的思維方式 遞歸、迭代、

11、黎曼積分早已提出，是人類賦予計算機 可以由人執行，也可以由計算機執行 是思想，不是人造物 是概念化，不是程序化 3計算思維的基本問題 可計算性 一個問題是可計算的是指可以使用計算機在有限步驟內解決 邱奇圖靈論題：圖靈機可以計算的就是可計算的 計算復雜性 時間復雜性和空間復雜性 1.3 計算思維第15頁/共20頁第15頁，共20頁。16示例4 矩陣相乘：Cnn=AnnBnn1.3 計算思維 計算cij需要n次乘法和n-1次加法 c中有n2個元素，故c需要n3次乘法和n2*(n-1)次加法示例5 漢諾塔問題 大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上 從下往上按照大小順序摞著64片黃金圓

12、盤。大梵天命令婆羅 門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。 并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次 只能移動一個圓盤。 第16頁/共20頁第16頁，共20頁。171.3 計算思維漢諾塔問題分析 假設有n黃金圓盤，移動次數是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億次的移動，

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