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

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

2641=18,446,744,073,709,551,615如果每秒移動(dòng)一次,一年有31,536,000秒,則僧侶們一刻不停地來(lái)回搬動(dòng)也需要花費(fèi)大約5,849億年的時(shí)間.假定計(jì)算機(jī)以每秒1,000萬(wàn)個(gè)盤子的速度進(jìn)行搬遷則需要花費(fèi)大約58,490年的時(shí)間.二、學(xué)科的分類與分支學(xué)科簡(jiǎn)介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)域解決其基本問(wèn)題提供了強(qiáng)有力的數(shù)學(xué)工具

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

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

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

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

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