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

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

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

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

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

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

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

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

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

9、計(jì)算機(jī)文化和計(jì)算思維理論思維（推理思維） 特征：以推理和演繹為特征 代表學(xué)科：數(shù)學(xué) 實(shí)驗(yàn)思維（實(shí)證思維） 特征：觀察和總結(jié)自然規(guī)律 代表學(xué)科：物理學(xué) 計(jì)算思維（構(gòu)造思維） 特征：設(shè)計(jì)和構(gòu)造 代表學(xué)科：計(jì)算機(jī)科學(xué) 26 迭代法 迭代過(guò)程：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研制過(guò)程就是迭代過(guò)程： 原型機(jī)0 原型機(jī)1 原型機(jī)2 原型機(jī)3示例2： 計(jì)算n的階乘f(n)=n!1.7計(jì)算機(jī)文化和計(jì)算思維 遞歸 分解問(wèn)題小問(wèn)題n!(n-1)!問(wèn)題分解小問(wèn)題更小問(wèn)題最小問(wèn)題分解分解不能再

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 哥尼斯堡七橋問(wèn)題 18世紀(jì)經(jīng)典數(shù)學(xué)問(wèn)題 在哥尼斯堡的一個(gè)公園里，有七座橋?qū)⑵绽赘駹柡又袃蓚€(gè)島以及島與河岸連接起來(lái)。問(wèn)是否可能從這四塊陸地中任一塊出發(fā)，恰好通過(guò)每座橋一次，再回到起點(diǎn)？1計(jì)算思維的本質(zhì)：抽象和自動(dòng)化 抽象：完全超越物理的時(shí)空觀，并完全用符號(hào)來(lái)表示 數(shù)學(xué)抽象是一種特例1.7計(jì)算機(jī)文化和計(jì)算思維 哥尼斯堡七橋問(wèn)題 哥尼斯堡七橋問(wèn)題的抽象 自動(dòng)化：機(jī)械地

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

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

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