“大學(xué)計算機基礎(chǔ)”課程 1

1、“大學(xué)計算機基礎(chǔ)” 課程考核方式按期末考試采用筆試形式，成績占該課程總評成績的60%，平時成績占40%公式計算該課程的總評成績。平時成績的組成為：考勤10%，作業(yè)10%，測驗20%(上機測驗)；若平時成績不及格，或者無故曠課超過1/3，則取消其期末考試資格，該課程成績評定為不及格。Chapter 1 IntroductionCS，ZJU9/16/2022Overview計算機是什么數(shù)據(jù)處理機模型現(xiàn)代計算機模型計算機系統(tǒng)信息系統(tǒng)因特網(wǎng)和萬維網(wǎng) 計算機文化和計算思維1.1 計算機是什么Computer從事計算工作的人Computer ScienceComputer TechnologyComput

2、er EngineeringInformation Technology，IT從技術(shù)上體積小，功能強從用途上專業(yè)到消費品計算機和計算Computer and Computation計算數(shù)學(xué)的基礎(chǔ)計算機的基礎(chǔ)期望：計算機實現(xiàn)數(shù)學(xué)意義上的“自動計算”現(xiàn)實：客觀世界的形態(tài)被“數(shù)字化”計算機素質(zhì)知道它，知道它是如何做到的計算機的定義計算機是一種現(xiàn)代化的信息處理工具，它對信息進行處理并提供結(jié)果，其結(jié)果（輸出）取決于所接收的信息（輸入）及相應(yīng)的處理算法計算機科學(xué)技術(shù)百科全書核心詞匯工具處理信息算法計算機科學(xué)與技術(shù)CS and CT計算機的設(shè)計、制造，以及運用計算機進行信息的獲取、表示、存儲、處理、控制等的

3、相關(guān)理論、原則、方法和技術(shù)CS研究現(xiàn)象和揭示其規(guī)律CT研制計算機和使用計算機進行信息處理的方法和手段1.2 數(shù)據(jù)處理機模型Data Processor Computer處理數(shù)據(jù)(Data)，得到信息(Information)Data原材料Information制成品數(shù)據(jù)處理器模型黒盒模型帶有程序功能的處理機模型黑盒模型定義了計算機的功能，給出了計算機的基本屬性，即計算機就是處理數(shù)據(jù)的機器具有程序能力的數(shù)據(jù)處理機程序（Program）簡單地被理解為按照預(yù)定的步驟進行工作程序是處理數(shù)據(jù)的算法的具體實現(xiàn)具有程序能力的處理機模型計算機的靈活性不同的數(shù)據(jù)，相同的程序，不同的結(jié)果相同的數(shù)據(jù)，不同的程序，相

4、同的結(jié)果程序原理能夠按照“程序”進行工作程序是事先編制好并存放在計算機內(nèi)部的1.3 現(xiàn)代計算機模型馮諾依曼計算機現(xiàn)代計算機模型定義了計算機的5個組成部分輸入 Input運算 Arithmetic Logic Unit存儲 Memory控制 Controller輸出 Output巴貝奇（Charles Babbage，17921871）IPOSCPU = ALU +Controller三個子系統(tǒng)CPU、Memory、I/O程序存儲原理現(xiàn)代計算機模型要求程序在執(zhí)行前存放到存儲器中還要求程序和數(shù)據(jù)采用同樣的格式程序存儲原理如何使計算機自動執(zhí)行程序程序存儲原理解決的問題程序存儲的另一個重要的理由是程序

5、的“重用”1.4 計算機系統(tǒng)計算機系統(tǒng)硬件系統(tǒng)處理器系統(tǒng)(主機)存儲器系統(tǒng)外部設(shè)備輸入設(shè)備輸出設(shè)備軟件系統(tǒng)系統(tǒng)軟件操作系統(tǒng)編程語言工具軟件應(yīng)用軟件辦公軟件其他應(yīng)用軟件硬件系統(tǒng)計算機的物理設(shè)備叫做硬件（Hardware）實現(xiàn)計算機操作過程、輸入、輸出互聯(lián)的各種電子設(shè)備術(shù)語計算機設(shè)備（Device）既可以指一個價值數(shù)億的巨型計算機系統(tǒng)，也指一個只有數(shù)十元的鼠標(biāo)器第一臺現(xiàn)代計算機1946年的ENIAC（Electronic Numerical Integrator And Computer，電子數(shù)字積分計算機）計算機歷史計算機歷史硬件史19461958 電子管19591963 晶體管19631975

6、 集成電路（IC）1975 大規(guī)模集成電路（LSIC）計算機類型按計算機的規(guī)模及銷售價進行劃分千萬USD： Supercomputer天河-1A：主機的處理器達到186368個，運算速度達到了每秒2570萬億次。數(shù)百萬USD： Mainframe Computer小型計算機PC，微型計算機嵌入式系統(tǒng)智能手機計算機軟件軟件：“看不見”的，卻是不可或缺的所有與計算機相關(guān)的文檔、程序、語言等都可以歸類為軟件軟件系統(tǒng)系統(tǒng)軟件：把服務(wù)于計算機本身應(yīng)用軟件：解決特定問題軟件的進化從專業(yè)到產(chǎn)業(yè)計算機是如何運行的通電后CPU執(zhí)行啟動程序BIOS操作系統(tǒng)調(diào)入內(nèi)存BIOS引導(dǎo)后計算機由操作系統(tǒng)管理和控制1.5 信

7、息系統(tǒng)信息系統(tǒng)有6個要素硬件軟件數(shù)據(jù)/信息人/用戶（People or User）計算機有兩類用戶，一類是以計算機為職業(yè)的另一類用戶主要就是使用計算機，大多數(shù)用戶屬于這一類。過程/處理通信1.6 因特網(wǎng)和萬維網(wǎng)Network：兩臺以上的計算機互連世界上最大的網(wǎng)：Internet目的：資源共享網(wǎng)絡(luò)的網(wǎng)絡(luò)管理上：無中心特性開放虛擬社會網(wǎng)上的各種社會形態(tài)：現(xiàn)實世界的Copy萬維網(wǎng)World Wide WebWWW簡稱為Web中文名為萬維網(wǎng)原為Internet的一種應(yīng)用（技術(shù)）Link and Webpage and Website現(xiàn)實：Internet的代名詞第一個瀏覽器軟件： Mosaic免費的瀏

8、覽器1.7計算機文化和計算思維Computer Literacy理解計算機是什么它如何被作為資源使用Computational Thinking是指運用計算機科學(xué)的基礎(chǔ)概念進行問題求解、系統(tǒng)設(shè)計以及人類行為理解等涵蓋計算機科學(xué)之廣度的一系列思維活動本質(zhì)： Abstraction、Automation狀態(tài)和過程25示例1： 計算f(x)是a, b上的積分 數(shù)學(xué)方法 牛頓萊布尼茲： f(x) F(x) 計算思維 黎曼積分：對a, b進行n等分 計算小矩形面積 累加 三大科學(xué)思維計算思維：運用計算機科學(xué)的基礎(chǔ)概念進行問題求解、系統(tǒng)設(shè)計、 以及人類行為理解等涵蓋計算機科學(xué)之廣度的一系列思維活動 1.7

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

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

11、一步一步自動執(zhí)行，其基礎(chǔ)和前提是抽像 282計算思維的特征 是屬于人的思維方式，不是計算機的思維方式 遞歸、迭代、黎曼積分早已提出，是人類賦予計算機 可以由人執(zhí)行，也可以由計算機執(zhí)行 是思想，不是人造物 是概念化，不是程序化 3計算思維的基本問題 可計算性 一個問題是可計算的是指可以使用計算機在有限步驟內(nèi)解決 邱奇圖靈論題：圖靈機可以計算的就是可計算的 計算復(fù)雜性 時間復(fù)雜性和空間復(fù)雜性 1.7計算機文化和計算思維29示例4 矩陣相乘：Cnn=AnnBnn1.7計算機文化和計算思維 計算cij需要n次乘法和n-1次加法 c中有n2個元素，故c需要n3次乘法和n2*(n-1)次加法示例5 漢諾塔

12、問題 大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上 從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅 門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。 并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次 只能移動一個圓盤。 301.7計算機文化和計算思維漢諾塔問題分析 假設(shè)有n黃金圓盤，移動次數(shù)是f(n) 有f(1)=1，f(2)=3，f(3)=7，f(k+1）=2*f(k)+1 故f(n)=2n-1，時間復(fù)雜性記作O(2n) f(64) = 264-1=18446744073709551615 假如每秒鐘移動一次，一個365天，則約需要584942417355年，即584

13、9億年 而地球的壽命才45億年。 假使用計算機進行每秒1億次的移動，也需要5849年。 時間復(fù)雜性：O(1) O(logn) O(n) O(nlogn) O(n2）O(n3) O(nk) O(2n) 當(dāng)n值稍大時，O(2n)的問題就無法計算了 314圖靈測試 機器能有智能嗎？換一句話來，通過什么樣的測試機器才能稱擁有智能？ 1.7計算機文化和計算思維無法判斷對方是人還是計算機，那么就可以認為計算機具有同人相當(dāng)?shù)闹橇?測試場景 325計算思維基本方法 從方法論的角度來說，計算思維的核心是計算思維方法 1.7計算機文化和計算思維 約簡、嵌入、轉(zhuǎn)化和仿真等方法，用來把一個看來困難的問題重新闡釋成一個我們知道問題怎樣解決的思維方法； 遞歸方法、并行方法、把代碼譯成數(shù)據(jù)又能把數(shù)據(jù)譯成代碼的方法、 多維分析推廣的類型檢查方法； 抽象和分解方法，用來控制龐雜的任務(wù)或進行巨大復(fù)雜系統(tǒng)設(shè)計； 基于關(guān)注分離的方法（SoC方法）；計算思維方法 來自數(shù)學(xué)和工程來自計算機科學(xué)自身 331.7計算機文化和計算思維 選擇合適的方式去陳述一個問題的方法、對一個問題的相關(guān)方面建模 使其易于處理的思維方法； 按照預(yù)防、保護及通過冗余、容錯、糾錯的方式，并從最壞情況進行 系統(tǒng)恢復(fù)的一種思維