科學(xué)導(dǎo)論-分支-學(xué)科形態(tài)

計(jì)算機(jī)學(xué)科的分支及學(xué)科形態(tài)一、學(xué)科的基本問題計(jì)算學(xué)科在各個(gè)分支學(xué)科方向的發(fā)展進(jìn)程中，不斷地出現(xiàn)了一些在表現(xiàn)形式上雖然不同，但在科學(xué)哲學(xué)的解釋下本質(zhì)上是相同或相近的問題，即學(xué)科研究與發(fā)展普遍關(guān)心的基本問題。計(jì)算學(xué)科的三個(gè)基本問題：⑴計(jì)算的平臺與環(huán)境問題⑵計(jì)算過程的能行操作與效率問題⑶計(jì)算的正確性問題學(xué)科的基本問題計(jì)算的平臺與環(huán)境問題為了實(shí)現(xiàn)自動計(jì)算—計(jì)算機(jī)的發(fā)明為了解題或證明問題本身不可解—計(jì)算模型只有構(gòu)造性計(jì)算模型才是能行的模型還必須是確定性的計(jì)算平臺的使用還必須是方便的—計(jì)算環(huán)境從某種意義上講,計(jì)算的平臺與環(huán)境問題包括計(jì)算模型計(jì)算機(jī)體系結(jié)構(gòu)操作系統(tǒng)高級程序設(shè)計(jì)軟件開發(fā)工具與開發(fā)環(huán)境學(xué)科的基本問題計(jì)算過程的能行操作與效率問題理論上的可計(jì)算,但實(shí)際上并不一定能行例:梵天塔問題相傳印度教的天神梵天在創(chuàng)造地球這一世界時(shí),建了一座神廟.神廟里豎有三根寶石柱子,柱子由一個(gè)銅座支撐.梵天將64個(gè)直徑大小不一的金盤子按照從大到小的順序依次套放在第一根柱子上,形成一座金塔.即所謂的梵天塔,又稱漢諾塔.例:梵天塔問題(續(xù))天神讓廟里的僧侶們將第一根柱子上的64個(gè)盤子,借助第二根柱子,全部移到第三根柱子上.同時(shí)定下3條規(guī)則每次只能移動一個(gè)盤子.盤子只能在三根柱子上來回移動,不能放在他處.在移動過程中,三根柱子上的盤子必須始終保持大盤在下小盤在上解決該問題的方法是遞歸解法將一個(gè)較大的問題歸約為一個(gè)或多個(gè)子問題的求解方法例:梵天塔問題(續(xù))將64個(gè)盤子的梵天塔問題轉(zhuǎn)化為求解63個(gè)盤子的梵天塔問題.如果63個(gè)盤子的梵天塔問題能夠解決,則可以先將63個(gè)盤子先移動到第二個(gè)柱子上再將最后一個(gè)盤子直接移動到第三個(gè)柱子上最后又一次將63個(gè)盤子從第二個(gè)柱子移動到第三個(gè)柱子上63個(gè)盤子的梵天塔求解問題可以轉(zhuǎn)化為62個(gè)盤子的梵天塔求解問題62個(gè)盤子的梵天塔求解問題又可以轉(zhuǎn)化為61個(gè)盤子的梵天塔求解問題…2個(gè)盤子的梵天塔求解問題又可以轉(zhuǎn)化為1個(gè)盤子的梵天塔求解問題1個(gè)盤子的梵天塔求解是直接的例:梵天塔問題(續(xù))下面用C語言對該問題的求解算法進(jìn)行描述hanoi(intn,charleft,charmiddle,charright){if(n==1)move(1,one,_,three);else{hanoi(n-1,left,right,middle);move(1,left,_,right);hanoi(n-1,middle,left,right);}}n表示n個(gè)盤子的梵天塔問題left表示第一個(gè)柱子middle表示第二個(gè)柱子right表示第三個(gè)柱子例:梵天塔問題(續(xù))問題:當(dāng)n=64時(shí),64個(gè)盤子時(shí)需要移動多少次盤子要用多少時(shí)間?設(shè)h(n)是移動n個(gè)盤子的梵天塔問題需要的移動次數(shù)n個(gè)盤子的梵天塔問題需要移動的盤子數(shù)是n-1個(gè)盤子的梵天塔問題需要移動的盤子數(shù)的2倍加1.于是

h(n)=2h(n1)+1 =2(2h(n2)+1)+1=22h(n2)+2+1 =23h(n3)+22+2+1 …… =2nh(0)+2n1+…+22+2+1 =2n1+…+22+2+1 =2n1例:梵天塔問題(續(xù))因此要完成梵天塔的搬遷需要移動盤子的次數(shù)為

2641=18,446,744,073,709,551,615如果每秒移動一次,一年有31,536,000秒,則僧侶們一刻不停地來回搬動也需要花費(fèi)大約5,849億年的時(shí)間.假定計(jì)算機(jī)以每秒1,000萬個(gè)盤子的速度進(jìn)行搬遷則需要花費(fèi)大約58,490年的時(shí)間.二、學(xué)科的分類與分支學(xué)科簡介1.離散結(jié)構(gòu)主要內(nèi)容集合論,數(shù)理邏輯,近世代數(shù),圖論以及組合數(shù)學(xué)等.該領(lǐng)域與計(jì)算學(xué)科各主領(lǐng)域有著緊密的聯(lián)系CC2001為了強(qiáng)調(diào)它的重要性,特意將它列為計(jì)算學(xué)科的第一個(gè)主領(lǐng)域.該主領(lǐng)域以抽象和理論兩個(gè)學(xué)科形態(tài)出現(xiàn)在計(jì)算學(xué)科中,它為計(jì)算學(xué)科各分支領(lǐng)域解決其基本問題提供了強(qiáng)有力的數(shù)學(xué)工具

學(xué)科的分類與分支學(xué)科簡介2.程序設(shè)計(jì)基礎(chǔ)主要內(nèi)容程序設(shè)計(jì)結(jié)構(gòu)、算法、問題求解和數(shù)據(jù)結(jié)構(gòu)等基本問題對給定的問題,如何進(jìn)行有效的描述并給出算法？如何正確選擇數(shù)據(jù)結(jié)構(gòu)？如何進(jìn)行設(shè)計(jì)編碼測試和調(diào)試程序？學(xué)科的分類與分支學(xué)科簡介3.算法與復(fù)雜性主要內(nèi)容算法的復(fù)雜度分析、典型的算法策略、分布式算法、并行算法、可計(jì)算理論、P類和NP類問題、自動機(jī)理論、密碼算法以及幾何算法等基本問題主要包括

對于給定的問題類，最好的算法是什么？要求的存儲空間和計(jì)算時(shí)間有多少？空間和時(shí)間如何折衷？訪問數(shù)據(jù)的最好方法是什么？算法最好和最壞的情況是什么？算法的平均性能如何？算法的通用性如何？學(xué)科的分類與分支學(xué)科簡介4.體系結(jié)構(gòu)主要內(nèi)容數(shù)字邏輯、數(shù)據(jù)的機(jī)器表示、匯編級機(jī)器組織、存儲技術(shù)、接口和通信、多道處理和預(yù)備體系結(jié)構(gòu)、性能優(yōu)化、網(wǎng)絡(luò)和分布式系統(tǒng)的體系結(jié)構(gòu)等。基本問題主要包括實(shí)現(xiàn)處理器內(nèi)存和機(jī)內(nèi)通信的方法是什么？如何設(shè)計(jì)和控制大型計(jì)算系統(tǒng)，而且使其令人相信，盡管存在錯(cuò)誤和失敗，但它仍然是按照我們的意圖工作的。哪種類型的體系結(jié)構(gòu)能夠有效地包含許多在一個(gè)計(jì)算中能夠并行工作的處理元素？如何度量性能？學(xué)科的分類與分支學(xué)科簡介5.操作系統(tǒng)主要內(nèi)容操作系統(tǒng)的邏輯結(jié)構(gòu)、并發(fā)處理、資源分配與調(diào)度、存儲管理、設(shè)備管理、文件系統(tǒng)等基本問題在計(jì)算機(jī)系統(tǒng)操作的每一個(gè)級別上，可見的對象和允許進(jìn)行的操作各是什么？對于每一類資源,能夠?qū)ζ溥M(jìn)行有效利用的最小操作集是什么？如何組織接口才能使得用戶只需與抽象的資源,而非硬件的物理細(xì)節(jié)打交道?作業(yè)調(diào)度,內(nèi)存管理,通信軟件,資源訪問,并發(fā)任務(wù)間的通信以及可靠性與安全的控制策略是什么?通過少數(shù)構(gòu)造規(guī)則的重復(fù)使用,進(jìn)行系統(tǒng)功能擴(kuò)展的原則是什么?學(xué)科的分類與分支學(xué)科簡介6.網(wǎng)絡(luò)計(jì)算主要內(nèi)容計(jì)算機(jī)網(wǎng)絡(luò)的體系結(jié)構(gòu),網(wǎng)絡(luò)安全,網(wǎng)絡(luò)管理,無線和移動計(jì)算,以及多媒體數(shù)據(jù)技術(shù)等基本問題網(wǎng)絡(luò)中的數(shù)據(jù)如何進(jìn)行交換?網(wǎng)絡(luò)協(xié)議如何驗(yàn)證?如何保證網(wǎng)絡(luò)的安全?分布式計(jì)算的性能如何評價(jià)?分布式計(jì)算如何組織才能夠使通過通信網(wǎng)連接在一起的自主計(jì)算機(jī)參加到一項(xiàng)計(jì)算中,而網(wǎng)絡(luò)協(xié)議,主機(jī)地址,帶寬和資源則具有透明性?學(xué)科的分類與分支學(xué)科簡介7.程序設(shè)計(jì)語言主要內(nèi)容程序設(shè)計(jì)模式,虛擬機(jī),類型系統(tǒng),執(zhí)行控制模型,語言翻譯系統(tǒng),程序設(shè)計(jì)語言的語義學(xué),基于語言的并行構(gòu)件等基本問題語言(數(shù)據(jù)類型,操作控制結(jié)構(gòu),引進(jìn)新類型和操作的機(jī)制)表示的虛擬機(jī)的可能組織結(jié)構(gòu)是什么?語言如何定義機(jī)器?如何定義語言?什么樣的表示法(語義)可以有效地用于描述計(jì)算機(jī)應(yīng)該做什么?學(xué)科的分類與分支學(xué)科簡介8.人機(jī)交互主要內(nèi)容以人為中心的軟件開發(fā)和評價(jià),圖形用戶接口設(shè)計(jì),多媒體系統(tǒng)的人機(jī)接口等基本問題表示物體和自動產(chǎn)生供閱覽的照片的有效方法是什么?接受輸入和給出輸出的有效方法是什么?怎樣才能減小產(chǎn)生誤解和由此產(chǎn)生的人為錯(cuò)誤的風(fēng)險(xiǎn)?圖表和其他工具怎樣才能通過存儲在數(shù)據(jù)集中的信息去理解物理現(xiàn)象?學(xué)科的分類與分支學(xué)科簡介9.圖形學(xué)和可視化計(jì)算主要內(nèi)容計(jì)算機(jī)圖形學(xué),可視化,虛擬現(xiàn)實(shí),計(jì)算機(jī)視覺等4個(gè)學(xué)科子領(lǐng)域的研究內(nèi)容基本問題支撐圖像產(chǎn)生以及信息瀏覽的更好模型如何提取科學(xué)的計(jì)算、醫(yī)學(xué)和更抽象的相關(guān)數(shù)據(jù)圖像形成過程的解釋和分析方法學(xué)科的分類與分支學(xué)科簡介10.智能系統(tǒng)主要內(nèi)容約束可滿足性問題,知識表示和推理,Agent,自然語言處理,機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò),人工智能規(guī)劃系統(tǒng)和機(jī)器人學(xué)等基本問題基本的行為模型是什么？如何建造模擬它們的機(jī)器？規(guī)則評估、推理、演繹和模式計(jì)算在多大程度上描述了智能？通過這些方法模擬行為的機(jī)器的最終性能如何？傳感數(shù)據(jù)如何編碼才使得相似的模式有相似的代碼。電機(jī)編碼如何與傳感編碼相關(guān)聯(lián)？學(xué)習(xí)系統(tǒng)的體系結(jié)構(gòu)怎樣？這些系統(tǒng)是如何表示它們對這個(gè)世界的理解的？學(xué)科的分類與分支學(xué)科簡介11.信息管理主要內(nèi)容信息模型與信息系統(tǒng),數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)建模,關(guān)系數(shù)據(jù)庫,數(shù)據(jù)庫查詢語言,關(guān)系數(shù)據(jù)庫設(shè)計(jì),事務(wù)處理,分布式數(shù)據(jù)庫,數(shù)據(jù)挖掘,信息存儲與檢索,超文本和超媒體,多媒體信息與多媒體系統(tǒng),數(shù)字圖書館等基本問題使用什么樣的建模概念來表示數(shù)據(jù)元素及其相互關(guān)系?怎樣把基本操作,如存儲定位,匹配和恢復(fù)組合成有效的事務(wù)?這些事務(wù)怎樣才能與用戶有效地進(jìn)行交互?高級查詢?nèi)绾畏g成高質(zhì)量的程序?哪種機(jī)器體系結(jié)構(gòu)能夠進(jìn)行有效的恢復(fù)和更新?怎樣保護(hù)數(shù)據(jù)以避免非授權(quán)訪問泄露和破壞?如何保護(hù)大型的數(shù)據(jù)庫以避免由于同時(shí)更新引起的不一致性?當(dāng)數(shù)據(jù)分布在許多機(jī)器上時(shí)，如何保護(hù)數(shù)據(jù)保證性能?文本如何索引和分類才能夠進(jìn)行有效的恢復(fù)?

學(xué)科的分類與分支學(xué)科簡介12.軟件工程主要內(nèi)容軟件過程，軟件需求與規(guī)格說明，軟件設(shè)計(jì)，軟件驗(yàn)證，軟件演化，軟件項(xiàng)目管理，軟件開發(fā)工具與環(huán)境，基于構(gòu)件的計(jì)算，形式化方法，軟件可靠性，專用系統(tǒng)開發(fā)等基本問題程序和程序設(shè)計(jì)系統(tǒng)發(fā)展背后的原理是什么?如何證明一個(gè)程序或系統(tǒng)滿足其規(guī)格說明?如何編寫不忽略重要情況且能用于安全分析的規(guī)格說明?軟件系統(tǒng)是如何歷經(jīng)不同的各代進(jìn)行演化的?如何從可理解性和易修改性著手設(shè)計(jì)軟件?學(xué)科的分類與分支學(xué)科簡介13.社會和職業(yè)的問題主要內(nèi)容計(jì)算的歷史，計(jì)算的社會背景，分析方法和工具，專業(yè)和道德責(zé)任，基于計(jì)算機(jī)系統(tǒng)的風(fēng)險(xiǎn)與責(zé)任，知識產(chǎn)權(quán)隱私與公民的自由，計(jì)算機(jī)犯罪與計(jì)算有關(guān)的經(jīng)濟(jì)問題、哲學(xué)框架等基本問題計(jì)算學(xué)科本身的文化、社會、法律和道德的問題有關(guān)計(jì)算的社會影響問題以及如何評價(jià)可能的一些答案的問題哲學(xué)問題技術(shù)問題以及美學(xué)問題學(xué)科的分類與分支學(xué)科簡介14.科學(xué)計(jì)算主要內(nèi)容數(shù)值分析,運(yùn)籌學(xué),模擬和仿真,高性能計(jì)算基本問題如何精確地以有限的離散過程近似表示連續(xù)和無限的離散過程?如何處理這種近似產(chǎn)生的錯(cuò)誤?給定某一類方程在某精確度水平上能以多快的速度求解?如何實(shí)現(xiàn)方程的符號操作如積分微分以及到最小項(xiàng)的歸約?如何把這些問題的答案包含到一個(gè)有效的、可靠的、高質(zhì)量的數(shù)學(xué)軟件包中?例:哥尼斯堡七橋問題

17世紀(jì)的東普魯士有一座哥尼斯堡(Konigsberg)城(現(xiàn)為俄國的加里寧格勒),哥尼斯堡城城中有一座奈佛夫(Kneiphof)島,普雷格爾(Pregol)河的兩條支流環(huán)繞其旁,并將整個(gè)城市分成北區(qū),東區(qū),南區(qū)和島區(qū)4個(gè)區(qū)域.全城共有7座橋?qū)?個(gè)城區(qū)相連起來.人們常通過這7座橋到各城區(qū)游玩.北區(qū)島區(qū)南區(qū)東區(qū)例:哥尼斯堡七橋問題(續(xù))問題能否從某區(qū)出發(fā),走遍這7座橋,且每座橋只走一次,最后又回到原出發(fā)點(diǎn)?許多人嘗試都未成功,也沒人能夠證明不行1736年,大數(shù)學(xué)家歐拉(L.Euler)發(fā)表了關(guān)于哥尼斯堡七橋問題的論文—《與位置幾何有關(guān)的一個(gè)問題的解》.他在文中指出:從一點(diǎn)出發(fā),不重復(fù)地走遍七橋,最后又回到原出發(fā)點(diǎn)是不可能的.歐拉開創(chuàng)了圖論例:哥尼斯堡七橋問題(續(xù))抽象從問題本質(zhì)考慮,抽象出問題最本質(zhì)的東西,忽視問題非本質(zhì)的東西,如橋的長度等.歐拉用A表示島區(qū),用B,C,D分別表示其他3個(gè)區(qū),將哥尼斯堡七橋問題轉(zhuǎn)換為從下圖A,B,C或D出發(fā),經(jīng)過每條邊一次,最后回到出發(fā)點(diǎn)例:哥尼斯堡七橋問題(續(xù))一般化一旦我們學(xué)會了一種技巧,仔細(xì)查看它是否是有啟發(fā)的,并看和它一起我們能走多遠(yuǎn)----Knuth從一個(gè)具體問題推廣到一般問題哥尼斯堡七橋問題的一般化對給定的任意一個(gè)河道圖與任意多座橋,判定可能不可能每座橋恰好走過一次回到出發(fā)點(diǎn)不回到出發(fā)點(diǎn)哥尼斯堡七橋問題的進(jìn)一步一般化圖的邊遍歷問題:從圖的任意頂點(diǎn)出發(fā),不重復(fù)地經(jīng)過圖中每一條邊(回到出發(fā)點(diǎn)/不回到出發(fā)點(diǎn))例:哥尼斯堡七橋問題(續(xù))圖的邊遍歷問題從圖的某頂點(diǎn)出發(fā),不重復(fù)地經(jīng)過圖中每一條邊,回到出發(fā)點(diǎn)當(dāng)且僅當(dāng)圖的每個(gè)頂點(diǎn)都有偶數(shù)條邊.(任意點(diǎn)為出發(fā)點(diǎn))從圖的某頂點(diǎn)出發(fā),不重復(fù)地經(jīng)過圖中每一條邊不回到出發(fā)點(diǎn)當(dāng)且僅當(dāng)圖中恰有兩個(gè)頂點(diǎn)有奇數(shù)條邊(分別為出發(fā)點(diǎn)和終點(diǎn))

三、計(jì)算機(jī)學(xué)科形態(tài)每一個(gè)學(xué)科都有其自身的知識組織結(jié)構(gòu)、學(xué)科形態(tài)、核心概念和基本工作流程方式。所謂學(xué)科形態(tài)，是指從事該領(lǐng)域工作的文化方式。對計(jì)算科學(xué)的深入研究使我們已知該學(xué)科存在三種主要的學(xué)科形態(tài)抽象理論設(shè)計(jì)學(xué)科形態(tài)第一種形態(tài):抽象科學(xué)抽象是指在思維中對同類事物去除其現(xiàn)象的次要的方面,抽取其共同的主要的方面,從而做到從個(gè)別中把握一般,從現(xiàn)象中把握本質(zhì)的認(rèn)知過程和思維方法抽象源于現(xiàn)實(shí)世界,源于經(jīng)驗(yàn),是對現(xiàn)實(shí)原形的理想化理想化后的現(xiàn)實(shí)原形與現(xiàn)實(shí)事物有了質(zhì)的區(qū)別.但它們總是現(xiàn)實(shí)事物的概念化,有現(xiàn)實(shí)背景抽象是科學(xué)認(rèn)識的基礎(chǔ)和決定性環(huán)節(jié)學(xué)科中的抽象形態(tài)包含著具體的內(nèi)容,它們是學(xué)科中所具有的科學(xué)概念,科學(xué)符號和思想模型學(xué)科形態(tài)計(jì)算學(xué)科的抽象,或稱模型化基于計(jì)算科學(xué)的實(shí)驗(yàn)科學(xué)方法,廣泛采用實(shí)驗(yàn)物理學(xué)的研究方法.按照對客觀現(xiàn)象和規(guī)律的實(shí)驗(yàn)研究過程,包含以下四個(gè)步驟：⑴確定可能世界（環(huán)境）并形成假設(shè)⑵構(gòu)造模型并做出預(yù)測；⑶設(shè)計(jì)實(shí)驗(yàn)并收集數(shù)據(jù)；⑷分析結(jié)果。這個(gè)學(xué)科形態(tài)主要出現(xiàn)在計(jì)算科學(xué)中與硬件設(shè)計(jì)和實(shí)驗(yàn)有關(guān)的研究之中。當(dāng)計(jì)算科學(xué)理論比較深奧，理解較為困難時(shí)，不少科研人員在大致了解理論、方法和技術(shù)的情況下，基于經(jīng)驗(yàn)和技能常以這種學(xué)科形態(tài)方式開展工作例:四色問題例:四色問題(續(xù))任何規(guī)范的地圖都可以至多用四種顏色著色,使得任何兩個(gè)相鄰的區(qū)域都具有不同的顏色兩個(gè)區(qū)域相鄰是指它們有一條公共邊下面兩個(gè)圖都形狀不完全相同,從著色角度是相同例:四色問題(續(xù))抽象:將地圖按如下方式轉(zhuǎn)換頂點(diǎn):地圖上每個(gè)區(qū)域邊:如果地圖上的兩個(gè)區(qū)域相鄰,則對應(yīng)的兩個(gè)頂點(diǎn)之間有一條邊前面的例子轉(zhuǎn)換成湖北省河南省河北省山東省安徽省陜西省山西省例:四色問題(續(xù))可以證明:轉(zhuǎn)換后的圖沒有交叉邊----平面圖可以證明:任何平面圖都可以至多用五種顏色著色,使得任意兩個(gè)相鄰的頂點(diǎn)都具有不同的顏色可以用如下定理歸納地證明:任何平面圖都有小于5度的頂點(diǎn)地圖的四著色問題轉(zhuǎn)換成任何平面圖都可以至多用四種顏色著色,使得任意兩個(gè)相鄰的頂點(diǎn)都具有不同的顏色轉(zhuǎn)換后的平面圖與原地圖很不相同,但是從著色角度,兩個(gè)問題是否有解是等價(jià)的抽象去除了問題的次要方面,如每個(gè)區(qū)域的形狀,大小抽象保留了問題的本質(zhì)方面----區(qū)域的相鄰性被頂點(diǎn)的相鄰性捕獲抽象得到的平面圖概念不僅可以解決地圖著色問題,而且還有其他應(yīng)用,如電路板布線問題學(xué)科形態(tài)計(jì)算學(xué)科的理論計(jì)算科學(xué)的數(shù)學(xué)基礎(chǔ)和計(jì)算科學(xué)理論,廣泛采用數(shù)學(xué)的研究方法.按統(tǒng)一的合理的理論發(fā)展過程，包含以下四個(gè)步驟：⑴對研究對象的概念抽象（定義和公理）⑵假設(shè)對象的基本性質(zhì)和對象之間可能存在的關(guān)系（定理）⑶確定這些性質(zhì)和關(guān)系是否正確（證明）⑷解釋結(jié)果（與計(jì)算機(jī)系統(tǒng)或研究對象形成對應(yīng)）這個(gè)學(xué)科形態(tài)的基本特征是其