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

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

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

4、析、典型的算法策略、分布式算法、并行算法、可計(jì)算理論、自動(dòng)機(jī)理論、密碼算法等 2）基本問題主要包括 對(duì)于給定的問題類，最好的算法是什么？要求的存儲(chǔ)空間和計(jì)算時(shí)間有多少？空間和時(shí)間如何折衷？算法最好和最壞的情況是什么？ 算法的通用性如何？,計(jì)算機(jī)學(xué)科各主領(lǐng)域的基本問題,體系結(jié)構(gòu) 1) 主要內(nèi)容：包括數(shù)字邏輯數(shù)據(jù)的機(jī)器表示、匯編級(jí)機(jī)器組織、存儲(chǔ)技術(shù)、接口和通信、性能優(yōu)化網(wǎng)絡(luò)和分布式系統(tǒng)的體系結(jié)構(gòu)等 2）基本問題主要包括: 實(shí)現(xiàn)處理器內(nèi)存和機(jī)內(nèi)通信的方法是什么？ 如何設(shè)計(jì)和控制大型計(jì)算系統(tǒng)？ 哪種類型的體系結(jié)構(gòu)能夠有效地包含許多在一個(gè)計(jì)算中能夠并行工作的處理元素？,計(jì)算機(jī)學(xué)科各主領(lǐng)域的基本問題,操作

5、系統(tǒng) 1）主要內(nèi)容：包括操作系統(tǒng)的邏輯結(jié)構(gòu)、并發(fā)處 理資源分配與調(diào)度、存儲(chǔ)管理、設(shè)備管理等 2）基本問題主要包括： 在計(jì)算機(jī)系統(tǒng)操作的每一個(gè)級(jí)別上，可見的對(duì)象和 允許進(jìn)行的操作各是什么？ 對(duì)于每一類資源能夠?qū)ζ溥M(jìn)行有效利用的最小操作 集是什么？ 如何組織接口才能使得用戶只需與抽象的資源而非 硬件的物理細(xì)節(jié)打交道？ 作業(yè)調(diào)度、內(nèi)存管理、并發(fā)任務(wù)間的通信等。,計(jì)算機(jī)學(xué)科各主領(lǐng)域的基本問題,網(wǎng)絡(luò)計(jì)算 1）主要內(nèi)容：包括計(jì)算機(jī)網(wǎng)絡(luò)的體系結(jié)構(gòu)、網(wǎng)絡(luò)安 全、網(wǎng)絡(luò)管理、無線和移動(dòng)計(jì)算，以及多媒體數(shù) 據(jù)技術(shù)等 2）基本問題主要包括 網(wǎng)絡(luò)中的數(shù)據(jù)如何進(jìn)行交換？網(wǎng)絡(luò)協(xié)議如何驗(yàn)證？ 如何保證網(wǎng)絡(luò)的安全？ 分布式計(jì)算

6、的性能如何 評(píng)價(jià)？ 分布式計(jì)算如何組織才能夠使通過通信 網(wǎng)連接在一起的自主計(jì)算機(jī)參加到一項(xiàng)計(jì)算中？,計(jì)算機(jī)學(xué)科各主領(lǐng)域的基本問題,程序設(shè)計(jì)語(yǔ)言 1）主要內(nèi)容：包括程序設(shè)計(jì)模式、類型系統(tǒng)、執(zhí)行控制模型、語(yǔ)言翻譯系統(tǒng)、程序設(shè)計(jì)語(yǔ)言的語(yǔ)義學(xué)等 2）基本問題主要包括 語(yǔ)言（數(shù)據(jù)類型、操作、控制結(jié)構(gòu)、引進(jìn)新類型和操作的機(jī)制）表示的虛擬機(jī)的可能組織結(jié)構(gòu)是什么？ 語(yǔ)言如何定義機(jī)器？機(jī)器如何定義語(yǔ)言？ 什么樣的表示法語(yǔ)義可以有效地用于描述計(jì)算機(jī)應(yīng)該做什么？,計(jì)算機(jī)學(xué)科各主領(lǐng)域的基本問題,人機(jī)交互 1）主要內(nèi)容：包括以人為中心的軟件開發(fā)和評(píng)價(jià)，圖形用戶接口設(shè)計(jì)，多媒體系統(tǒng)的人機(jī)接口等 2）基本問題主要包括 表示

7、物體和自動(dòng)產(chǎn)生供閱覽的照片的有效方法是什么？ 接受輸入和給出輸出的有效方法是什么？ 怎樣才能減小產(chǎn)生誤解和由此產(chǎn)生的人為錯(cuò)誤的風(fēng)險(xiǎn)？ 圖表和其他工具怎樣才能通過存儲(chǔ)在數(shù)據(jù)集中的信息去理解物理現(xiàn)象？,計(jì)算機(jī)學(xué)科各主領(lǐng)域的基本問題,圖形學(xué)和可視化計(jì)算 1）主要內(nèi)容：包括計(jì)算機(jī)圖形學(xué)、可視化、虛擬現(xiàn)實(shí)、計(jì)算機(jī)視覺等4個(gè)學(xué)科子領(lǐng)域的研究?jī)?nèi)容 2）基本問題主要包括 支撐圖像產(chǎn)生以及信息瀏覽的更好模型？ 如何提取科學(xué)的計(jì)算和醫(yī)學(xué)和更抽象的相關(guān)數(shù)據(jù)？ 圖像形成過程的解釋和分析方法 ？,計(jì)算機(jī)學(xué)科各主領(lǐng)域的基本問題,智能系統(tǒng) 1）主要內(nèi)容：知識(shí)表示和推理、Agent、自然語(yǔ)言處理、機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)、人工智能

8、和機(jī)器人學(xué)等 2基本問題主要有 基本的行為模型是什么？如何建造模擬它們的機(jī)器？ 規(guī)則評(píng)估、推理、演繹在多大程度上描述了智能？ 通過這些方法模擬行為的機(jī)器的最終性能如何？ 傳感數(shù)據(jù)如何編碼才使得相似的模式有相似的代碼 ？ 學(xué)習(xí)系統(tǒng)的體系結(jié)構(gòu)怎樣 ？,計(jì)算機(jī)學(xué)科各主領(lǐng)域的基本問題,信息管理 1）主要內(nèi)容：包括信息模型與信息系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)、數(shù)據(jù)建模、數(shù)據(jù)庫(kù)查詢語(yǔ)言、關(guān)系數(shù)據(jù)庫(kù)設(shè)計(jì)、事務(wù)處理、分布式數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘、信息存儲(chǔ)與檢索、超文本和超媒體、多媒體信息與多媒體系統(tǒng)、數(shù)字圖書館等 2）基本問題主要包括 高級(jí)查詢?nèi)绾畏g成高質(zhì)量的程序 ？ 怎樣保護(hù)數(shù)據(jù)以避免非授權(quán)訪問泄露和破壞 ？ 如何保護(hù)大型的

9、數(shù)據(jù)庫(kù)以避免同時(shí)更新引起的不一致性 ？ 當(dāng)數(shù)據(jù)分布在許多機(jī)器上時(shí)如何保護(hù)數(shù)據(jù)保證性能 ？ 文本如何索引和分類才能夠進(jìn)行有效的恢復(fù) ？,計(jì)算機(jī)學(xué)科各主領(lǐng)域的基本問題,軟件工程 1）主要內(nèi)容：包括軟件過程、軟件需求與規(guī)格說明、軟件設(shè)計(jì)、軟件驗(yàn)證、軟件演化、軟件項(xiàng)目管理、軟件開發(fā)工具與環(huán)境、形式化方法、軟件可靠性等 2）基本問題主要包括 如何證明一個(gè)程序或系統(tǒng)滿足其規(guī)格說明 ？ 如何編寫不忽略重要情況且能用于安全分析的規(guī)格說明？ 軟件系統(tǒng)是如何歷經(jīng)不同的各代進(jìn)行演化的 ？ 如何從可理解性和易修改性著手設(shè)計(jì)軟件 ？,計(jì)算機(jī)學(xué)科各主領(lǐng)域的基本問題,社會(huì)和職業(yè)的問題 1）主要內(nèi)容：包括計(jì)算的歷史、計(jì)算的社

10、會(huì)背景、分析方法和工具、專業(yè)和道德責(zé)任、基于計(jì)算機(jī)系統(tǒng)的風(fēng)險(xiǎn)與責(zé)任、知識(shí)產(chǎn)權(quán)、隱私與公民的自由、計(jì)算機(jī)犯罪與計(jì)算有關(guān)的經(jīng)濟(jì)問題等 2）基本問題主要包括 計(jì)算機(jī)學(xué)科本身的文化社會(huì)法律和道德的問題 ？ 有關(guān)計(jì)算的社會(huì)影響問題以及如何評(píng)價(jià)可能的一些答案的問題 ？ 哲學(xué)問題 ？ 技術(shù)問題以及美學(xué)問題 ？,計(jì)算機(jī)學(xué)科各主領(lǐng)域的基本問題,科學(xué)計(jì)算 1）主要內(nèi)容：包括數(shù)值分析、運(yùn)籌學(xué)、模擬和仿真、高性能計(jì)算 2）基本問題主要包括 如何精確地以有限的離散過程近似表示連續(xù)和無限的離散過程？ 如何處理這種近似產(chǎn)生的錯(cuò)誤 ？ 給定某一類方程在某精確度水平上能以多快的速度求解 ？ 如何實(shí)現(xiàn)方程的符號(hào)操作如積分微分以及

11、到最小項(xiàng)的歸約 ？,計(jì)算機(jī)科學(xué)典型問題示例,哥尼斯堡七橋問題,尋找走遍這7座橋且只許走過每座橋一次，最后又回到原出發(fā)點(diǎn)的路徑,計(jì)算機(jī)科學(xué)典型問題示例,梵天塔問題,1）每次只能移動(dòng)一個(gè)盤子；2）盤子只能在三根柱子上來回移動(dòng)不能放在他處 ；3）在移動(dòng)過程中三根柱子上的盤子必須始終保持大盤在下小盤在上 天神說，當(dāng)這64個(gè)盤子全部移到第三根柱子上后，世界末日就要到了。,計(jì)算機(jī)科學(xué)典型問題示例,證比求易算法,一個(gè)酷愛數(shù)學(xué)的年輕國(guó)王向鄰國(guó)一位聰明美麗的公主求婚，公主出了這樣一道題：求出48 770 428 433 377 171的一個(gè)真因子。若國(guó)王能在一天之內(nèi)求出答案，公主便接受他的求婚。國(guó)王回去后從早到

12、晚共算了三萬多個(gè)數(shù)最終還是沒有結(jié)果，國(guó)王向公主求情，公主將答案相告223 092 827是它的一個(gè)真因子。公主說我再給你一次機(jī)會(huì)，如果還求不出將來你只好做我的證婚人了。國(guó)王立即回國(guó)并向時(shí)任宰相的大數(shù)學(xué)家求教，大數(shù)學(xué)家在仔細(xì)地思考后認(rèn)為這個(gè)數(shù)為17位，則最小的一個(gè)真因子不會(huì)超過9位。于是他給國(guó)王出了一個(gè)主意，按自然數(shù)的順序給全國(guó)的老百姓每人編一個(gè)號(hào)發(fā)下去，等公主給出數(shù)目后立即將它們通報(bào)全國(guó)，讓每個(gè)老百姓用自己的編號(hào)去除這個(gè)數(shù)，除盡了立即上報(bào)，賞金萬兩。最后國(guó)王用這個(gè)辦法求婚成功。,計(jì)算機(jī)科學(xué)典型問題示例,旅行商問題與組合爆炸問題,威廉哈密爾頓爵士和英國(guó)數(shù)學(xué)家克克曼T.P.Kirkman于19世紀(jì)

13、初提出的一個(gè)數(shù)學(xué)問題。大意是有若干個(gè)城市，任何兩個(gè)城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)，必須經(jīng)過每一個(gè)城市且只能在每個(gè)城市逗留一次，最后回到原出發(fā)城市。問如何事先確定好一條最短的路線使其旅行的費(fèi)用最少。 。,計(jì)算機(jī)科學(xué)典型問題示例,旅行商問題與組合爆炸問題,計(jì)算機(jī)科學(xué)典型問題示例,旅行商問題與組合爆炸問題,據(jù)文獻(xiàn)介紹，1998年科學(xué)家們成功地解決了美國(guó)13509個(gè)城市之間的TSP問題，2001年又解決了德國(guó)15112個(gè)城市之間的TSP問題，但這一工程代價(jià)也是巨大的。據(jù)報(bào)道解決15112個(gè)城市之間的TSP問題，共使用了美國(guó)Rice大學(xué)和普林斯頓大學(xué)之間網(wǎng)絡(luò)互連的由速度為500MHz 的Compaq EV6 Alpha 處理器組成的110臺(tái)計(jì)算機(jī)，所有計(jì)算機(jī)花費(fèi)