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

計算機(jī)學(xué)科的分支及學(xué)科形態(tài)一、學(xué)科的基本問題計算學(xué)科在各個分支學(xué)科方向的發(fā)展進(jìn)程中，不斷地出現(xiàn)了一些在表現(xiàn)形式上雖然不同，但在科學(xué)哲學(xué)的解釋下本質(zhì)上是相同或相近的問題，即學(xué)科研究與發(fā)展普遍關(guān)心的基本問題。計算學(xué)科的三個基本問題：⑴計算的平臺與環(huán)境問題⑵計算過程的能行操作與效率問題⑶計算的正確性問題學(xué)科的基本問題計算的平臺與環(huán)境問題為了實現(xiàn)自動計算—計算機(jī)的發(fā)明為了解題或證明問題本身不可解—計算模型只有構(gòu)造性計算模型才是能行的模型還必須是確定性的計算平臺的使用還必須是方便的—計算環(huán)境從某種意義上講,計算的平臺與環(huán)境問題包括計算模型計算機(jī)體系結(jié)構(gòu)操作系統(tǒng)高級程序設(shè)計軟件開發(fā)工具與開發(fā)環(huán)境學(xué)科的基本問題計算過程的能行操作與效率問題理論上的可計算,但實際上并不一定能行例:梵天塔問題相傳印度教的天神梵天在創(chuàng)造地球這一世界時,建了一座神廟.神廟里豎有三根寶石柱子,柱子由一個銅座支撐.梵天將64個直徑大小不一的金盤子按照從大到小的順序依次套放在第一根柱子上,形成一座金塔.即所謂的梵天塔,又稱漢諾塔.例:梵天塔問題(續(xù))天神讓廟里的僧侶們將第一根柱子上的64個盤子,借助第二根柱子,全部移到第三根柱子上.同時定下3條規(guī)則每次只能移動一個盤子.盤子只能在三根柱子上來回移動,不能放在他處.在移動過程中,三根柱子上的盤子必須始終保持大盤在下小盤在上解決該問題的方法是遞歸解法將一個較大的問題歸約為一個或多個子問題的求解方法例:梵天塔問題(續(xù))將64個盤子的梵天塔問題轉(zhuǎn)化為求解63個盤子的梵天塔問題.如果63個盤子的梵天塔問題能夠解決,則可以先將63個盤子先移動到第二個柱子上再將最后一個盤子直接移動到第三個柱子上最后又一次將63個盤子從第二個柱子移動到第三個柱子上63個盤子的梵天塔求解問題可以轉(zhuǎn)化為62個盤子的梵天塔求解問題62個盤子的梵天塔求解問題又可以轉(zhuǎn)化為61個盤子的梵天塔求解問題…2個盤子的梵天塔求解問題又可以轉(zhuǎn)化為1個盤子的梵天塔求解問題1個盤子的梵天塔求解是直接的例:梵天塔問題(續(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個盤子的梵天塔問題left表示第一個柱子middle表示第二個柱子right表示第三個柱子例:梵天塔問題(續(xù))問題:當(dāng)n=64時,64個盤子時需要移動多少次盤子要用多少時間?設(shè)h(n)是移動n個盤子的梵天塔問題需要的移動次數(shù)n個盤子的梵天塔問題需要移動的盤子數(shù)是n-1個盤子的梵天塔問題需要移動的盤子數(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秒,則僧侶們一刻不停地來回搬動也需要花費大約5,849億年的時間.假定計算機(jī)以每秒1,000萬個盤子的速度進(jìn)行搬遷則需要花費大約58,490年的時間.二、學(xué)科的分類與分支學(xué)科簡介1.離散結(jié)構(gòu)主要內(nèi)容集合論,數(shù)理邏輯,近世代數(shù),圖論以及組合數(shù)學(xué)等.該領(lǐng)域與計算學(xué)科各主領(lǐng)域有著緊密的聯(lián)系CC2001為了強(qiáng)調(diào)它的重要性,特意將它列為計算學(xué)科的第一個主領(lǐng)域.該主領(lǐng)域以抽象和理論兩個學(xué)科形態(tài)出現(xiàn)在計算學(xué)科中,它為計算學(xué)科各分支領(lǐng)域解決其基本問題提供了強(qiáng)有力的數(shù)學(xué)工具

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

對于給定的問題類，最好的算法是什么？要求的存儲空間和計算時間有多少？空間和時間如何折衷？訪問數(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)等?；締栴}主要包括實現(xiàn)處理器內(nèi)存和機(jī)內(nèi)通信的方法是什么？如何設(shè)計和控制大型計算系統(tǒng)，而且使其令人相信，盡管存在錯誤和失敗，但它仍然是按照我們的意圖工作的。哪種類型的體系結(jié)構(gòu)能夠有效地包含許多在一個計算中能夠并行工作的處理元素？如何度量性能？學(xué)科的分類與分支學(xué)科簡介5.操作系統(tǒng)主要內(nèi)容操作系統(tǒng)的邏輯結(jié)構(gòu)、并發(fā)處理、資源分配與調(diào)度、存儲管理、設(shè)備管理、文件系統(tǒng)等基本問題在計算機(jī)系統(tǒng)操作的每一個級別上，可見的對象和允許進(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ò)計算主要內(nèi)容計算機(jī)網(wǎng)絡(luò)的體系結(jié)構(gòu),網(wǎng)絡(luò)安全,網(wǎng)絡(luò)管理,無線和移動計算,以及多媒體數(shù)據(jù)技術(shù)等基本問題網(wǎng)絡(luò)中的數(shù)據(jù)如何進(jìn)行交換?網(wǎng)絡(luò)協(xié)議如何驗證?如何保證網(wǎng)絡(luò)的安全?分布式計算的性能如何評價?分布式計算如何組織才能夠使通過通信網(wǎng)連接在一起的自主計算機(jī)參加到一項計算中,而網(wǎng)絡(luò)協(xié)議,主機(jī)地址,帶寬和資源則具有透明性?學(xué)科的分類與分支學(xué)科簡介7.程序設(shè)計語言主要內(nèi)容程序設(shè)計模式,虛擬機(jī),類型系統(tǒng),執(zhí)行控制模型,語言翻譯系統(tǒng),程序設(shè)計語言的語義學(xué),基于語言的并行構(gòu)件等基本問題語言(數(shù)據(jù)類型,操作控制結(jié)構(gòu),引進(jìn)新類型和操作的機(jī)制)表示的虛擬機(jī)的可能組織結(jié)構(gòu)是什么?語言如何定義機(jī)器?如何定義語言?什么樣的表示法(語義)可以有效地用于描述計算機(jī)應(yīng)該做什么?學(xué)科的分類與分支學(xué)科簡介8.人機(jī)交互主要內(nèi)容以人為中心的軟件開發(fā)和評價,圖形用戶接口設(shè)計,多媒體系統(tǒng)的人機(jī)接口等基本問題表示物體和自動產(chǎn)生供閱覽的照片的有效方法是什么?接受輸入和給出輸出的有效方法是什么?怎樣才能減小產(chǎn)生誤解和由此產(chǎn)生的人為錯誤的風(fēng)險?圖表和其他工具怎樣才能通過存儲在數(shù)據(jù)集中的信息去理解物理現(xiàn)象?學(xué)科的分類與分支學(xué)科簡介9.圖形學(xué)和可視化計算主要內(nèi)容計算機(jī)圖形學(xué),可視化,虛擬現(xiàn)實,計算機(jī)視覺等4個學(xué)科子領(lǐng)域的研究內(nèi)容基本問題支撐圖像產(chǎn)生以及信息瀏覽的更好模型如何提取科學(xué)的計算、醫(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ī)器的最終性能如何？傳感數(shù)據(jù)如何編碼才使得相似的模式有相似的代碼。電機(jī)編碼如何與傳感編碼相關(guān)聯(lián)？學(xué)習(xí)系統(tǒng)的體系結(jié)構(gòu)怎樣？這些系統(tǒng)是如何表示它們對這個世界的理解的？學(xué)科的分類與分支學(xué)科簡介11.信息管理主要內(nèi)容信息模型與信息系統(tǒng),數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)建模,關(guān)系數(shù)據(jù)庫,數(shù)據(jù)庫查詢語言,關(guān)系數(shù)據(jù)庫設(shè)計,事務(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ù)庫以避免由于同時更新引起的不一致性?當(dāng)數(shù)據(jù)分布在許多機(jī)器上時，如何保護(hù)數(shù)據(jù)保證性能?文本如何索引和分類才能夠進(jìn)行有效的恢復(fù)?

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

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

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