科學導論-分支-學科形態(tài)

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

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

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

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

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

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