計算機科學(xué)導(dǎo)論之二課件

1、第二講計算機科學(xué)的內(nèi)容計算學(xué)科的根本問題三個學(xué)科形態(tài)主要領(lǐng)域基本問題典型問題示例第1頁，共27頁。計算機科學(xué)的根本問題 計算機科學(xué)與計算科學(xué) 定義：計算學(xué)科是對描述和變換信息的算 法過程，包括對其理論分析、設(shè)計、 效率實現(xiàn)和應(yīng)用等進(jìn)行的系統(tǒng)研究。計算學(xué)科的根本問題 計算學(xué)科的根本問題是什么能被有 效地自動進(jìn)行。 第2頁，共27頁。計算學(xué)科中的3個學(xué)科形態(tài) 抽象形態(tài) 學(xué)科中的抽象形態(tài)包含著學(xué)科中所具有的科學(xué)概念、科學(xué)符號和思想模型。按客觀現(xiàn)象的研究過程，抽象形態(tài)包括以下4個步驟的內(nèi)容： 1）形成假設(shè) 2）建造模型并作出預(yù)測 3）設(shè)計實驗并收集數(shù)據(jù) 4）對結(jié)果進(jìn)行分析 第3頁，共27頁。計算學(xué)科中

2、的3個學(xué)科形態(tài) 理論形態(tài) 理論是經(jīng)過實踐檢驗的系統(tǒng)化了的科學(xué)知識體系，由科學(xué)概念、科學(xué)原理以及對這些概念原理的理論論證所組成的體系。在計算學(xué)科中，理論形態(tài)包括以下4個步驟的內(nèi)容： 1）表述研究對象的特征定義和公理 2）假設(shè)對象之間的基本性質(zhì)和對象之間可能存在 的關(guān)系定理 3）確定這些關(guān)系是否為真證明 4）結(jié)論 第4頁，共27頁。計算學(xué)科中的3個學(xué)科形態(tài) 設(shè)計形態(tài) 設(shè)計形態(tài)具有較強的實踐性，社會性和綜合性。在計算學(xué)科中，從為解決某個問題而實現(xiàn)系統(tǒng)或裝置的過程來看，設(shè)計形態(tài)包括以下4個步驟的內(nèi)容： 1）需求分析 2）建立規(guī)格說明 3）設(shè)計并實現(xiàn)該系統(tǒng) 4）對系統(tǒng)進(jìn)行測試與分析 第5頁，共27頁。計

3、算學(xué)科中的3個學(xué)科形態(tài) 三種形態(tài)關(guān)系 設(shè)計、抽象和理論3個形態(tài)針對具體的研究領(lǐng)域均起作用，在具體研究中，就是要在其理論的指導(dǎo)下，運用其抽象工具進(jìn)行各種設(shè)計工作，最終的成果將是計算機的軟硬件系統(tǒng)及其相關(guān)資料。 抽象源于現(xiàn)實世界 理論源于數(shù)學(xué) 設(shè)計源于工程 第6頁，共27頁。計算機學(xué)科各主領(lǐng)域的基本問題 離散結(jié)構(gòu) 主要內(nèi)容：包括集合論、數(shù)理邏輯、近世代數(shù)、圖論、以及組合數(shù)學(xué)等。 第7頁，共27頁。計算機學(xué)科各主領(lǐng)域的基本問題 程序設(shè)計基礎(chǔ) 1）主要內(nèi)容：包括程序設(shè)計結(jié)構(gòu)、算法、問 題求解和數(shù)據(jù)結(jié)構(gòu)等 2）基本問題主要包括： 對給定的問題，如何進(jìn)行有效的描述并給 出算法？ 如何正確選擇數(shù)據(jù)結(jié)構(gòu)？ 如

4、何進(jìn)行設(shè)計、編碼、測試和調(diào)試程序？ 第8頁，共27頁。計算機學(xué)科各主領(lǐng)域的基本問題 算法與復(fù)雜性 1) 主要內(nèi)容：包括算法的復(fù)雜度分析、典型的算法策略、分布式算法、并行算法、可計算理論、自動機理論、密碼算法等 2）基本問題主要包括 對于給定的問題類，最好的算法是什么？要求的存儲空間和計算時間有多少？空間和時間如何折衷？算法最好和最壞的情況是什么？ 算法的通用性如何？ 第9頁，共27頁。計算機學(xué)科各主領(lǐng)域的基本問題 體系結(jié)構(gòu) 1) 主要內(nèi)容：包括數(shù)字邏輯數(shù)據(jù)的機器表示、匯編級機器組織、存儲技術(shù)、接口和通信、性能優(yōu)化網(wǎng)絡(luò)和分布式系統(tǒng)的體系結(jié)構(gòu)等 2）基本問題主要包括: 實現(xiàn)處理器內(nèi)存和機內(nèi)通信的方

5、法是什么？ 如何設(shè)計和控制大型計算系統(tǒng)？ 哪種類型的體系結(jié)構(gòu)能夠有效地包含許多在一個計算中能夠并行工作的處理元素？第10頁，共27頁。計算機學(xué)科各主領(lǐng)域的基本問題 操作系統(tǒng) 1）主要內(nèi)容：包括操作系統(tǒng)的邏輯結(jié)構(gòu)、并發(fā)處 理資源分配與調(diào)度、存儲管理、設(shè)備管理等 2）基本問題主要包括： 在計算機系統(tǒng)操作的每一個級別上，可見的對象和 允許進(jìn)行的操作各是什么？ 對于每一類資源能夠?qū)ζ溥M(jìn)行有效利用的最小操作 集是什么？ 如何組織接口才能使得用戶只需與抽象的資源而非 硬件的物理細(xì)節(jié)打交道？ 作業(yè)調(diào)度、內(nèi)存管理、并發(fā)任務(wù)間的通信等。第11頁，共27頁。計算機學(xué)科各主領(lǐng)域的基本問題 網(wǎng)絡(luò)計算 1）主要內(nèi)容：包

6、括計算機網(wǎng)絡(luò)的體系結(jié)構(gòu)、網(wǎng)絡(luò)安 全、網(wǎng)絡(luò)管理、無線和移動計算，以及多媒體數(shù) 據(jù)技術(shù)等 2）基本問題主要包括 網(wǎng)絡(luò)中的數(shù)據(jù)如何進(jìn)行交換？網(wǎng)絡(luò)協(xié)議如何驗證？ 如何保證網(wǎng)絡(luò)的安全？ 分布式計算的性能如何 評價？ 分布式計算如何組織才能夠使通過通信 網(wǎng)連接在一起的自主計算機參加到一項計算中？第12頁，共27頁。計算機學(xué)科各主領(lǐng)域的基本問題 程序設(shè)計語言 1）主要內(nèi)容：包括程序設(shè)計模式、類型系統(tǒng)、執(zhí)行控制模型、語言翻譯系統(tǒng)、程序設(shè)計語言的語義學(xué)等 2）基本問題主要包括 語言（數(shù)據(jù)類型、操作、控制結(jié)構(gòu)、引進(jìn)新類型和操作的機制）表示的虛擬機的可能組織結(jié)構(gòu)是什么？ 語言如何定義機器？機器如何定義語言？ 什么樣

7、的表示法語義可以有效地用于描述計算機應(yīng)該做什么？ 第13頁，共27頁。計算機學(xué)科各主領(lǐng)域的基本問題 人機交互 1）主要內(nèi)容：包括以人為中心的軟件開發(fā)和評價，圖形用戶接口設(shè)計，多媒體系統(tǒng)的人機接口等 2）基本問題主要包括 表示物體和自動產(chǎn)生供閱覽的照片的有效方法是什么？ 接受輸入和給出輸出的有效方法是什么？ 怎樣才能減小產(chǎn)生誤解和由此產(chǎn)生的人為錯誤的風(fēng)險？ 圖表和其他工具怎樣才能通過存儲在數(shù)據(jù)集中的信息去理解物理現(xiàn)象？ 第14頁，共27頁。計算機學(xué)科各主領(lǐng)域的基本問題 圖形學(xué)和可視化計算 1）主要內(nèi)容：包括計算機圖形學(xué)、可視化、虛擬現(xiàn)實、計算機視覺等4個學(xué)科子領(lǐng)域的研究內(nèi)容 2）基本問題主要包括

8、 支撐圖像產(chǎn)生以及信息瀏覽的更好模型？ 如何提取科學(xué)的計算和醫(yī)學(xué)和更抽象的相關(guān)數(shù)據(jù)？ 圖像形成過程的解釋和分析方法 ？ 第15頁，共27頁。計算機學(xué)科各主領(lǐng)域的基本問題 智能系統(tǒng) 1）主要內(nèi)容：知識表示和推理、Agent、自然語言處理、機器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)、人工智能和機器人學(xué)等 2基本問題主要有 基本的行為模型是什么？如何建造模擬它們的機器？ 規(guī)則評估、推理、演繹在多大程度上描述了智能？ 通過這些方法模擬行為的機器的最終性能如何？ 傳感數(shù)據(jù)如何編碼才使得相似的模式有相似的代碼 ？學(xué)習(xí)系統(tǒng)的體系結(jié)構(gòu)怎樣 ？ 第16頁，共27頁。計算機學(xué)科各主領(lǐng)域的基本問題 信息管理 1）主要內(nèi)容：包括信息模型與信

9、息系統(tǒng)、數(shù)據(jù)庫系統(tǒng)、數(shù)據(jù)建模、數(shù)據(jù)庫查詢語言、關(guān)系數(shù)據(jù)庫設(shè)計、事務(wù)處理、分布式數(shù)據(jù)庫、數(shù)據(jù)挖掘、信息存儲與檢索、超文本和超媒體、多媒體信息與多媒體系統(tǒng)、數(shù)字圖書館等 2）基本問題主要包括 高級查詢?nèi)绾畏g成高質(zhì)量的程序 ？怎樣保護(hù)數(shù)據(jù)以避免非授權(quán)訪問泄露和破壞 ？如何保護(hù)大型的數(shù)據(jù)庫以避免同時更新引起的不一致性 ？當(dāng)數(shù)據(jù)分布在許多機器上時如何保護(hù)數(shù)據(jù)保證性能 ？文本如何索引和分類才能夠進(jìn)行有效的恢復(fù) ？ 第17頁，共27頁。計算機學(xué)科各主領(lǐng)域的基本問題 軟件工程 1）主要內(nèi)容：包括軟件過程、軟件需求與規(guī)格說明、軟件設(shè)計、軟件驗證、軟件演化、軟件項目管理、軟件開發(fā)工具與環(huán)境、形式化方法、軟件可靠

10、性等 2）基本問題主要包括 如何證明一個程序或系統(tǒng)滿足其規(guī)格說明 ？如何編寫不忽略重要情況且能用于安全分析的規(guī)格說明？ 軟件系統(tǒng)是如何歷經(jīng)不同的各代進(jìn)行演化的 ？如何從可理解性和易修改性著手設(shè)計軟件 ？ 第18頁，共27頁。計算機學(xué)科各主領(lǐng)域的基本問題 社會和職業(yè)的問題 1）主要內(nèi)容：包括計算的歷史、計算的社會背景、分析方法和工具、專業(yè)和道德責(zé)任、基于計算機系統(tǒng)的風(fēng)險與責(zé)任、知識產(chǎn)權(quán)、隱私與公民的自由、計算機犯罪與計算有關(guān)的經(jīng)濟問題等 2）基本問題主要包括 計算機學(xué)科本身的文化社會法律和道德的問題 ？有關(guān)計算的社會影響問題以及如何評價可能的一些答案的問題 ？哲學(xué)問題 ？技術(shù)問題以及美學(xué)問題 ？

11、 第19頁，共27頁。計算機學(xué)科各主領(lǐng)域的基本問題 科學(xué)計算 1）主要內(nèi)容：包括數(shù)值分析、運籌學(xué)、模擬和仿真、高性能計算 2）基本問題主要包括 如何精確地以有限的離散過程近似表示連續(xù)和無限的離散過程？ 如何處理這種近似產(chǎn)生的錯誤 ？給定某一類方程在某精確度水平上能以多快的速度求解 ？如何實現(xiàn)方程的符號操作如積分微分以及到最小項的歸約 ？第20頁，共27頁。計算機科學(xué)典型問題示例 哥尼斯堡七橋問題 尋找走遍這7座橋且只許走過每座橋一次，最后又回到原出發(fā)點的路徑 第21頁，共27頁。計算機科學(xué)典型問題示例 梵天塔問題 1）每次只能移動一個盤子；2）盤子只能在三根柱子上來回移動不能放在他處 ；3）在

12、移動過程中三根柱子上的盤子必須始終保持大盤在下小盤在上 天神說，當(dāng)這64個盤子全部移到第三根柱子上后，世界末日就要到了。 第22頁，共27頁。計算機科學(xué)典型問題示例 證比求易算法 一個酷愛數(shù)學(xué)的年輕國王向鄰國一位聰明美麗的公主求婚，公主出了這樣一道題：求出48 770 428 433 377 171的一個真因子。若國王能在一天之內(nèi)求出答案，公主便接受他的求婚。國王回去后從早到晚共算了三萬多個數(shù)最終還是沒有結(jié)果，國王向公主求情，公主將答案相告223 092 827是它的一個真因子。公主說我再給你一次機會，如果還求不出將來你只好做我的證婚人了。國王立即回國并向時任宰相的大數(shù)學(xué)家求教，大數(shù)學(xué)家在仔細(xì)

13、地思考后認(rèn)為這個數(shù)為17位，則最小的一個真因子不會超過9位。于是他給國王出了一個主意，按自然數(shù)的順序給全國的老百姓每人編一個號發(fā)下去，等公主給出數(shù)目后立即將它們通報全國，讓每個老百姓用自己的編號去除這個數(shù)，除盡了立即上報，賞金萬兩。最后國王用這個辦法求婚成功。第23頁，共27頁。計算機科學(xué)典型問題示例 旅行商問題與組合爆炸問題 威廉哈密爾頓爵士和英國數(shù)學(xué)家克克曼T.P.Kirkman于19世紀(jì)初提出的一個數(shù)學(xué)問題。大意是有若干個城市，任何兩個城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)，必須經(jīng)過每一個城市且只能在每個城市逗留一次，最后回到原出發(fā)城市。問如何事先確定好一條最短的路線使其旅行的費用最少。 。 第24頁，共27頁。計算機科學(xué)典型問題示例 旅行商問題與組合爆炸問題第25頁，共27頁。計算機科學(xué)典型問題示例 旅行商問題與組合爆炸問題據(jù)文獻(xiàn)介紹，1998年科學(xué)家們成功地解決了美國13509個城市之間的TSP問題，2001年又解決了德國15112個城市之間的TSP問題，但這一工程代價也是巨大的。據(jù)報道解決15112個城市之間的TSP問題，共使用了美國Rice大學(xué)和普林斯頓大學(xué)之間網(wǎng)絡(luò)互連的由速度為500MHz 的Compaq EV6 Alpha 處理器組成的110臺計算機，所有計算機花費的時間之和為2