計算機導(dǎo)論課件85

G"”m和乎叮拄企於

ifCoatpuitrScit9ct，」.u^y隊導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

0內(nèi)容提要

聲4.1概^述

任4.2計算本質(zhì)及計算學(xué)科

戌4.3計算學(xué)科各主領(lǐng)域的基本問題

聲4.4學(xué)科典型問題的認知探討

戌4.5人工智能中的若干哲學(xué)問題

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

4.1概述

科學(xué)問題的定義：

科學(xué)問題是指一定時代的科學(xué)認識主體，在已完成的

科學(xué)知識和科學(xué)實現(xiàn)的基礎(chǔ)上，提出的需要解決且有可能解

決的問題。它包含一定的求解目標和應(yīng)答域，但尚無確定的

答案。

科學(xué)問題是認識的一種形式，它既包含先前的實踐和

認知的基礎(chǔ)，又預(yù)示著進一步的實踐和認識的方向，它是

“認識以實踐為基礎(chǔ)”這一命題的具體化形式，它產(chǎn)生于人

們

的社會生產(chǎn)實踐與科學(xué)實踐過程中。從科學(xué)史來看，人類科

技進步的歷史就是一個不斷提出科學(xué)問題又不斷解決科學(xué)問

題的歷史。因此，科學(xué)問題在方法論中占有極其重要的地缶

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

能否在所從事的工作中提出（或從眾多的問題中抽?。╆P(guān)

鍵和重要的科學(xué)問題，對我們每個人來說都是一個挑戰(zhàn)。

而方法論的學(xué)習(xí)有助于我們自覺地、主動地去迎接這種挑

戰(zhàn)。

科學(xué)問題的主要特征和方法論作用

1.科學(xué)問題的主要特征

時代性：從歷史的觀來看，任何一個科學(xué)問題都具有它的

時代特征。每一個時代都有它自己的科學(xué)問題，而這些問

題的解決對科學(xué)的發(fā)展具有深遠的意義。

混沌性：科學(xué)問題顯示了人們對已有知識的不滿，并渴望

對新知識的追求，但這種追求開始的時候是模糊不清的。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

可解決性：科學(xué)問題是由于決心解決而又有可能解決才提

出的，提出科學(xué)問題后便要力圖解決它。

可變異性：相對科學(xué)問題的可解決性而言，如果一個問

題未能解決，似乎就不是科學(xué)問題，其實不然，如果他還

能引出另外具有可解決性的科學(xué)問題，則原問題仍屬于科

學(xué)問題。

可待解性：由于尚不具備解決問題的全部條件,因此許多科

學(xué)問題在當前一段時間里還很難解決或無法解決，但絕非

永遠不可解決。

2.科學(xué)問題的方法論作用

科學(xué)問題的裂變式作用

對于一門學(xué)科而言，原先科學(xué)問題的提出與解決，會

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

誘發(fā)出新的科學(xué)問題，而新的科學(xué)問題的解決又會誘發(fā)

更新的科學(xué)問題，這種父子型、子孫型科學(xué)問題的連續(xù)

出現(xiàn)和相繼解決，可以導(dǎo)致該門學(xué)科的重大理論突破。

例如對“數(shù)學(xué)基礎(chǔ)問題”的研究，導(dǎo)致了“形成系統(tǒng)相容

性

問題”的研究，最后出現(xiàn)“能行性問題”的研究，并最終

于

20世紀30年代由圖靈、哥德爾、丘奇和波斯特等人共同

奠定了計算學(xué)科的理論基礎(chǔ)，實現(xiàn)了人類對計算問題的

重大突破。

科學(xué)問題的聚變式作用

對不同科學(xué)問題的研究最終導(dǎo)致同一科學(xué)問題的發(fā)一

現(xiàn)，這種殊途同歸的結(jié)果，就是科學(xué)問題聚變式作用的

T隊導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

結(jié)果。

科學(xué)問題的激勵作用

新的重大科學(xué)問題的確定總是在以往時代科學(xué)問題結(jié)

束之際到來的，它猶如一面旗幟，象征著人類科學(xué)認識進

入到一個嶄新的階段，它召喚和激勵著人們?yōu)榻鉀Q這些富

有挑戰(zhàn)性的問題而勇往直前。

在科學(xué)哲學(xué)中，從不同角度出發(fā)，科學(xué)問題有不同的

分類方法，這里不對這些分類方法進行討論，僅對反映計

算學(xué)科本質(zhì)的根本問題、學(xué)科各領(lǐng)域的基本問題、在學(xué)科

中起重要作用的典型問題，以及人工智能中的若干哲學(xué)問

題進行分析。

BACK

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

4.2計算本質(zhì)及計算學(xué)科

計算學(xué)科根本問題的認識過程與人們對計算過程的

認識是緊密聯(lián)系在一起的，因此，要分析計算學(xué)科的根

本問題，首先要分析人們對計算本質(zhì)的認識過程。

計算本質(zhì)的認識歷史

在很早以前，人們就碰到了必須計算的問題。已經(jīng)

考證的，遠在舊石器時代，刻在骨制和石頭上的花紋就

是對某種計算的記錄。然而，在20世紀30年代以前，人

們并沒有真正認識計算的本質(zhì)。盡管如此，在人類漫長

的歲月里，人們一直沒有停止過對計算本質(zhì)的探索。很

早以前，我國的學(xué)者就認為，對于一個數(shù)學(xué)問題，只有

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

確定了其可用算盤解算它的規(guī)則時，這個問題才算可解。

這就是古代中國的“算法化”思想，它蘊含著中國古代學(xué)

箸

對計算的根本問題，即“能行性”問題的理解，這種理解

對

現(xiàn)代計算學(xué)科的研究仍具有重要的意義。中國科學(xué)院院

士吳文俊教授正是在這一基礎(chǔ)上圍繞幾何定理的機器證

明展開研究，并開拓了一個在國際上首屆國家最高科學(xué)

技術(shù)獎。

算盤作為主要的計算工具流行了相當長的一段時間，

直到中世紀，哲學(xué)家們提出了這樣一個大膽的問題:能否用

機械來實現(xiàn)人腦活動的個別功能?最初的實驗?zāi)康牟⒉皇?/p>

制造計算機,而是試圖從某個前提出發(fā)機械地得出正確的一

結(jié)論,即思維機器的制造。早在1275年西班牙神學(xué)家雷蒙

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

德?露利(RLullus)就發(fā)明了一種思維機器(“旋轉(zhuǎn)玩具”),

從而開創(chuàng)了計算機器制造的先河。

“旋轉(zhuǎn)玩具”引起了許多著名學(xué)者的研究興趣，并最

終導(dǎo)致了能進行簡單數(shù)學(xué)運算的計算機器的產(chǎn)生。1641

年，法國人帕斯卡利用齒輪技術(shù)制成了第一臺加法機；

1673年德國人萊布尼茨在帕斯卡的基礎(chǔ)上又制造了能進

行簡單加、減、乘、除的計算機器；19世紀30年代，英

國人巴貝奇設(shè)計了用于計算對數(shù)、三角函數(shù)以及其他算

術(shù)函數(shù)的“分析機”；20世紀20年代，美國人布什研制了

能解一般微分方程組的電子模擬計算機等。計算的這一

歷史包含了人們對計算過程的本質(zhì)和它的根本問題進行

的探索，同時，還為現(xiàn)代計算機的研制積累了經(jīng)驗。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

其實，對計算本質(zhì)的真正認識取決于形式化研究的

進程，而“旋轉(zhuǎn)玩具”就是一種形式化的產(chǎn)物，不僅如此,

它還標志著形式化思想革命的開始。

康托爾的集合論和羅素悖論

形式化方法和理論的研究起源于對數(shù)學(xué)的基礎(chǔ)研究。

數(shù)學(xué)的基礎(chǔ)研究是指對數(shù)學(xué)的對象、性質(zhì)及其發(fā)生、發(fā)

展的一般規(guī)律進行的科學(xué)研究。

德國數(shù)學(xué)家康托爾從1874年開始，對數(shù)學(xué)基礎(chǔ)作了

新的探討，發(fā)表了一系列集合論方面的著作，從而創(chuàng)立

了集合論。康托爾創(chuàng)立的集合論對數(shù)學(xué)概念作了重要的

擴充，對數(shù)學(xué)基礎(chǔ)的研究產(chǎn)生了重大影響，并逐步發(fā)展

成為數(shù)學(xué)的重要基礎(chǔ)。

(r\n空m不斗乎*4

JL^tpdrtmtntifCoarp^itrScittct&TerhndT以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

然而不久，數(shù)學(xué)家們卻在集合論中發(fā)現(xiàn)了邏輯矛盾，

其中最為著名的是1901年羅素在集合論概括原則的基礎(chǔ)

上發(fā)現(xiàn)的“羅素悖論”，從而導(dǎo)致了數(shù)學(xué)發(fā)展史上的第三

次

危機。

羅素悖論可以這樣形式化地定義：S={x|xs}o

為了使人們更好地理解集合論悖論，羅素將“羅素悖論”

改寫成“理發(fā)師悖論”。其大意是，一個村莊的理發(fā)師宣

布了這樣一條規(guī)定:“給且只給村里那些不自己刮胡子的人

刮胡子”?，F(xiàn)在就問:理發(fā)師給不給自己刮胡子呢?如果

理發(fā)師給自己刮胡子，他就屬于那類“自己刮胡子的人”，

按規(guī)定，該理發(fā)師不能給自己刮胡子;如果理發(fā)師不給自

己刮胡子，那么，他就屬于那類“不自己刮胡子的人”，

按

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

規(guī)定，他就應(yīng)該給自己刮胡子。由此可以推出兩個相互

矛盾的等價命題：理發(fā)師自己給自己刮胡子理發(fā)師自己

不給自己刮胡子。

圖靈對計算本質(zhì)的揭示

在歌德爾研究成果的影響下，20世紀30年代后期，圖

靈從計算一個數(shù)的一般過程入手對計算的本質(zhì)進行了研

究，從而實現(xiàn)了對計算本質(zhì)的真正認識。

根據(jù)圖靈的研究，直觀地說，所謂計算就是計算者

（人或機器）對一條兩端可無限延長的紙帶上的一串0和

1執(zhí)行指令，一步一步地改變紙帶上的0或1,經(jīng)過有限步

驟，最后得到一個滿足預(yù)先規(guī)定的符號串的變換過程。

圖靈用形式方法成功地表訴了計算這一過程的本質(zhì)。圖

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

靈的研究成果是歌德爾研究成果的進一步深化，該成果

不僅再次表明了某些數(shù)學(xué)問題是不能用任何機械過程來

解決的思想，而且還深刻地揭示了計算所具有的“能行過

程”的本質(zhì)特征。

圖靈的描述是關(guān)于數(shù)值計算的，不過，我們知道英

文字母表的字母以及漢字均可以用數(shù)來表示，因此，圖靈

機同樣可以處理非數(shù)值計算。不僅如此，更為重要的是，

由數(shù)值和非數(shù)值組成的字符串，既可以解釋成數(shù)據(jù)，又可

以解釋成程序，從而計算的每一過程都可以用字符串的形

式進行編碼，并存放在存儲器中，以后使用時譯碼，并由

處理器執(zhí)行，機器碼可以高級符號形式機械的推導(dǎo)出來。

圖靈的研究成果是：可計算性二圖靈可計算性。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

在關(guān)于可計算性問題的討論時，不可避免地要提到一個

與計算具有同等地位和意義的基本概念，那就是算法。

算法也稱為能行方法或或能行過程，是對解題（計算）過

程的精確描述，它有一組定義明確且能機械執(zhí)行的規(guī)則

（語句、指令等）組成。根據(jù)圖靈的論點，可以得到這樣

的結(jié)論，任一過程是能行的（能夠具體表現(xiàn)在一個算法

中），當且僅當它能夠被一臺圖靈機實現(xiàn)。圖靈機與當時

哥德爾、丘奇、波斯特等人提出的用于解決可計算問題的

遞歸函數(shù)、入演算和POST規(guī)范系統(tǒng)等計算模型在計算能力

上是等價的。在這一事實的基礎(chǔ)上，形成了現(xiàn)在著名的丘

奇——圖靈論題。

圖靈機等計算模型均是用來解決“能行計算”問題的,

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

理論上的能行性隱含著計算模型的正確性，而實際實現(xiàn)

中的能行性還包含時間與空間的有效性。

現(xiàn)代計算機的產(chǎn)生以及計算學(xué)科的定義

伴隨著電子學(xué)理論和技術(shù)的發(fā)展，在圖靈機這個思

想模型提出不到10年的時間里，世界上第一臺電子計算

機誕生了。

其實，圖靈機反映的是一種具有能行性的用數(shù)學(xué)方

法精確定義的計算模型，而現(xiàn)代計算機正是這種模型的

具體實現(xiàn)。正如前面提到的那樣，計算學(xué)科各分支領(lǐng)域

均可以用模型與實現(xiàn)來描述。而模型反映的是計算學(xué)科

的抽象和理論兩個過程，實現(xiàn)反映的是計算學(xué)科的設(shè)計

過程，模型與實現(xiàn)已蘊含于計算學(xué)科的抽象、理論和設(shè)

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

-計3個過程之中算學(xué)科各分支領(lǐng)域中的抽象和理論兩

個過程關(guān)心的是解決具有能行性和有效性的模型問題，設(shè)

計過程關(guān)心的是模型的具體實現(xiàn)問題，正因為如此，計算

學(xué)科中的3個形態(tài)是不可分割、密切相關(guān)的。

計算運用了科學(xué)和工程兩者的方法學(xué)，理論工作已大

大地促進了這門藝術(shù)的發(fā)展。同時，計算并沒有把新的科

學(xué)知識的發(fā)現(xiàn)與利用這些知識解決實際的問題分割開來。

理論和實踐的緊密聯(lián)系給該學(xué)科帶來了力量和生機。

正是由于計算學(xué)科理論與實踐的緊密聯(lián)系，并伴隨

著計算技術(shù)的飛速發(fā)展，計算學(xué)科現(xiàn)已成為一個極為廣的

學(xué)科。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

在進行大量分析的基礎(chǔ)上,《計算作為一門學(xué)科》報

告給計算學(xué)科作了以下定義：

計算學(xué)科是對描述和變換信息的算法過程，包括對其

理論、分析、效率、實現(xiàn)和應(yīng)用等進行的系統(tǒng)研究。它來

源于對算法理論、數(shù)理邏輯、計算模型、自動計算機器的

研究，并與存儲電子計算機的發(fā)明一起形成于20世紀40年

代初期。

計算學(xué)科包括對計算過程的分析以及計算機的設(shè)計

和使用。該學(xué)科的廣泛性在下面一段來自美國計算科學(xué)鑒

定委員會(ComputingSciencesAccreditationBoard)發(fā)布的

報告摘錄中得到強調(diào)：

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

計算學(xué)科的研究包括從算法與可計算性的研究到根

據(jù)可計算硬件和軟件的實際實現(xiàn)問題的研究。這樣，計

算學(xué)科不但包括從總體上對算法和信息處理過程進行研

究的內(nèi)容，也包括滿足給定規(guī)格要求的有效而可靠的軟

硬件設(shè)計一它包括所有科目的理論研究、實驗方法和工

程設(shè)計。

計算學(xué)科的根本問題

同樣，也是在大量分析的基礎(chǔ)上，《計算作為一門

學(xué)科》報告對學(xué)科中的根本問題作了以下概括。

計算學(xué)科的根本問題是：什么能被（有效地）自動進

fio

計算學(xué)科的根本問題討論的是“能行性”的有關(guān)內(nèi)容。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

而凡是與“能行性”有關(guān)的討論，都是處理離散對象的。

因為非離散對象，即所謂的連續(xù)對象，是很難進行能行

處理的。因此，“能行性”這個計算學(xué)科的根本問題決定

了計算機本身的結(jié)構(gòu)和它處理的對象都是離散型的，甚

至許多連續(xù)型的問題也必須在轉(zhuǎn)化為離散型問題以后才

能被計算機處理。例如，計算定積分就是把它變成離散

量，再用分段求和的方法來處理的。

正是源于計算學(xué)科的根本問題，以離散型變量為研

究對象的離散數(shù)學(xué)對計算技術(shù)的發(fā)展起著十分重要的作

用。同時，又因為計算技術(shù)的迅猛發(fā)展，使得離散數(shù)學(xué)

越來越受到重視。為此，CC2001報告特意將它從

CC1999報告的預(yù)備知識中抽取出來，列為計算學(xué)科的第

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

一個主領(lǐng)域，命名為“離散結(jié)構(gòu)”，以強調(diào)計算學(xué)科對它

的依賴性。

盡管計算學(xué)科已成為一個極為寬廣的學(xué)科，但其根

本問題仍然是：什么能被（有效地）自動進行。甚至還

可以更為直率地說，計算學(xué)科所有分支領(lǐng)域的根本任務(wù)

就是進行計算，其實質(zhì)就是字符串的變換。

在弄清計算學(xué)科的根本問題的實質(zhì)后，還可以對計

算學(xué)科根本問題作進一步的闡述：

在論述人的計算能力方面，著名的數(shù)理邏輯學(xué)家美

籍華人王浩教授認為，如果我們同意只關(guān)心作為機械過

程的計算，那么許多論述將更加清楚，并能避免像精神

GI卜計機不斗?『r技/三系

0了S(it9ct，1,.JQ計算機導(dǎo)詒

?第4章計算學(xué)科的科學(xué)問題

與人體的關(guān)系這樣的心理學(xué)和哲學(xué)的問題。因此，就機

械過程的計算而言，王浩認為：人要做機器永遠不能做

的某些計算是不容易的。

BACK

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

4.3計算學(xué)科各主領(lǐng)域的基本問題

計算學(xué)科各主領(lǐng)域的基本問題來源于各主領(lǐng)域所研

究的內(nèi)容，因此，在給出各主領(lǐng)域的基本問題前，先給

出各主領(lǐng)域所包括的主要內(nèi)容。

i.離散結(jié)構(gòu)

主要內(nèi)容：包括集合論、數(shù)理邏輯、近世代數(shù)、圖

論以及組合數(shù)學(xué)等。該領(lǐng)域與計算學(xué)科各主領(lǐng)域有著緊

密的聯(lián)系，CC2001為了強調(diào)它的重要性，特意將它列為

計算學(xué)科的第一個主領(lǐng)域。該主領(lǐng)域以抽象和理論兩個

學(xué)科形態(tài)出現(xiàn)在計算學(xué)科中，它為計算學(xué)科各分支領(lǐng)域

解決其基本問題提供了強有力的數(shù)學(xué)工具。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

2.程序設(shè)計基礎(chǔ)

⑴主要內(nèi)容：包括程序設(shè)計結(jié)構(gòu)、算法、問題求解和數(shù)據(jù)

結(jié)構(gòu)等。

⑵基本問題主要包：

①對給定的問題，如何進行有效的描述并給出算法？

②如何正確選擇數(shù)據(jù)結(jié)構(gòu)？

③如何進行設(shè)計，編碼，測試和調(diào)試程序？

3算法與復(fù)雜性

⑴主要內(nèi)容：包括算法的復(fù)雜度分析，典型的算法策略，

分布式算法，并行算法，可計算理論，P類和NP類問題,

自動機理論，密碼算法以及幾何算法等。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

⑵基本問題主要包括：

①對于給定的問題類，最好的算法是什么？要求的存儲

空間和計算時間有多少？空間和時間如何折衷？

②訪問數(shù)據(jù)的最好方法是什么？

③算法最好和最壞的情況是什么？

④算法的平均性能如何？

⑤算法的通用性如何？

4.體系結(jié)構(gòu)

⑴主要內(nèi)容：包括數(shù)字邏輯，數(shù)據(jù)的機器表示，匯編級機

器組織，存儲技術(shù)，接口和通信，多道處理和預(yù)備體系結(jié)

構(gòu)，性能優(yōu)化，網(wǎng)絡(luò)和分布式系統(tǒng)的體系結(jié)構(gòu)等。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

⑵基本問題主要包括：

①實現(xiàn)處理器、內(nèi)存和機內(nèi)通信的方法是什么？

②如何設(shè)計和控制大型計算系統(tǒng)，而且使其令人相信，

盡管存在錯誤和失敗，但它仍然是按照我們的意圖工

作的？

③哪種類型的體系結(jié)構(gòu)能夠有效的包含許多在一個計算

中能夠并行工作的處理元素？

④如何度量性能？

5.操作系統(tǒng)

⑴主要內(nèi)容：包括操作系統(tǒng)的邏輯結(jié)構(gòu)，并發(fā)處理，資

源分配與調(diào)度，存儲管理，設(shè)備管理，文件系統(tǒng)等。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

⑵基本問題主要包括：

①在計算機系統(tǒng)操作的每一個級別上，可見的對象和允

許進行的操作各是什么？

②于每一類資源，能夠?qū)ζ溥M行有效利用的最小操作集

是什么？

③如何組織接口才能使得用戶只需與抽象的資源而非硬

件的物理細節(jié)打交道？

④作業(yè)調(diào)度、內(nèi)存管理、通信、軟件資源訪問、并發(fā)任

務(wù)間的通信以及可靠性與安全性的控制策略是什么？

⑤通過少數(shù)構(gòu)造規(guī)則的重復(fù)使用進行系統(tǒng)功能擴展的原

則是什么？

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

6.網(wǎng)絡(luò)計算

⑴主要內(nèi)容：包括計算機網(wǎng)絡(luò)的體系結(jié)構(gòu)、網(wǎng)絡(luò)安全、網(wǎng)

絡(luò)管理、無線和移動計算以及多媒體數(shù)據(jù)技術(shù)等。

⑵基本問題主要包括：

①網(wǎng)絡(luò)中的數(shù)據(jù)如何進行交換？

②網(wǎng)絡(luò)協(xié)議如何驗證？

③如何保證網(wǎng)絡(luò)的安全？

④分布式計算的性能如何評價？

⑤分布式計算如何組織才能夠使通過通信網(wǎng)連接在一起的

自主計算機參加到一項計算中，而網(wǎng)絡(luò)協(xié)議、主機地址、

寬帶和資源則具有透明性？

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

7.程序設(shè)計語言

⑴主要內(nèi)容：包括程序設(shè)計模式、虛擬機、類型系統(tǒng)、

執(zhí)行控制模型、語言翻譯系統(tǒng)、程序設(shè)計語言的語義

學(xué)、基于語言的并行構(gòu)件等。

⑵基本問題主要包括：

①語言（數(shù)據(jù)類型、操作、控制結(jié)構(gòu)、引進新類型和

操作的機制）表示的虛擬機的可能組織結(jié)構(gòu)是什么？

②語言如何定義機器？機器如何定義語言？

③什么樣的表示法（語義）可以有效地用于描述計算

機應(yīng)該做什么？

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

8.人—機父互

⑴主要內(nèi)容：包括以人為中心的軟件開發(fā)和評價、圖形用

戶接口設(shè)計、多媒體系統(tǒng)的人機接口等。

⑵基本問題主要包括：

①表示物體和自動產(chǎn)生供閱覽的照片的有效方法是什么？

②接受輸入和給出輸出的有效方法是什么？

③怎樣才能減小產(chǎn)生誤解和由此產(chǎn)生的人為錯誤的風(fēng)險？

④圖表和其他工具怎樣才能通過存儲在數(shù)據(jù)集中的信息去

理解物理現(xiàn)象？

9.圖形學(xué)和可視化計算

⑴主要內(nèi)容:包括計算機圖形學(xué)、可視化、虛擬現(xiàn)實、計

算機視覺4個學(xué)科子領(lǐng)域的研究內(nèi)容。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

⑵基本問題主要內(nèi)容：

①支撐圖象產(chǎn)生以及信息瀏覽的更好模型。

②如何提取科學(xué)的（計算和醫(yī)學(xué)）和更抽象的相關(guān)數(shù)據(jù)?

③圖象形成過程的解釋和分析方法。

10.智能系統(tǒng)

⑴主要內(nèi)容：包括約束可滿足性問題、知識表示和推理、

自然語言處理、機器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)、人工智能規(guī)劃

系統(tǒng)和機器人學(xué)等。

⑵基本問題主要有：

①基本的行為模型是什么？如何建造模擬它們的機器？

②規(guī)則評估、推理、演繹和模式計算在多大程度上描

述了智能？

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

③通過這些方法模擬行為的機器的最終性能如何？

④傳感數(shù)據(jù)如何編碼才使得相似的模式有相似的代碼？

⑤電機編碼如何與傳感編碼相關(guān)聯(lián)？

⑥學(xué)習(xí)系統(tǒng)的體系結(jié)構(gòu)怎樣？

⑦這些系統(tǒng)是如何表示它們對這個世界的理解的？

1L信息管理

⑴主要內(nèi)容：包括信息模型和信息系統(tǒng)、數(shù)據(jù)庫建模、關(guān)

系數(shù)據(jù)庫、數(shù)據(jù)庫查詢語言、關(guān)系數(shù)據(jù)庫設(shè)計、事務(wù)處

理、分布式數(shù)據(jù)庫、數(shù)據(jù)挖掘、信息存儲與檢索、超文

本和超媒體、多媒體信息與多媒體系統(tǒng)、數(shù)字圖書館等。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

⑵基本問題主要包括：

①使用什么樣的建模概念來表示數(shù)據(jù)元素及其相互關(guān)系？

②怎樣把基本操作（如存儲.定位.匹配和恢復(fù)）組和成有效的

事務(wù)？

③這些事務(wù)怎樣才能與用戶有效地進行交互？

④高級查詢?nèi)绾畏g成高質(zhì)量的程序？

⑤那種機器體系結(jié)構(gòu)能夠進行有效的恢復(fù)和更新？

⑥怎樣保護數(shù)據(jù)，以避免非授權(quán)訪問、泄露和破壞？

⑦如何保護大型的數(shù)據(jù)庫，以避免由于同時更新引起的不

一致性？

⑧當數(shù)據(jù)分布在許多機器上時如何保護數(shù)據(jù)、保證性能？

⑨文本如何索引和分類才能夠進行有效的恢復(fù)？

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(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)不同的各代進行演化的？

⑤如何從可理解性和易修改性著手設(shè)計軟件？

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

13.社會和職業(yè)的問題

⑴主要內(nèi)容：包括計算的歷史、計算的社會背景、分

析方法和工具、專業(yè)和道德責(zé)任、基于計算機系統(tǒng)的

風(fēng)險與責(zé)任、知識產(chǎn)權(quán)、隱私與公民的自由、計算機

犯罪、與計算有關(guān)的經(jīng)濟問題、哲學(xué)框架等。

⑵基本問題主要包括：

①計算學(xué)科本身的文化、社會、法律和道德的問題：

②有關(guān)計算的社會影響問題，以及如何評價可能的一

些答案的問題；

③哲學(xué)問題；

④技術(shù)問題以及美學(xué)問題；

T隊導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

14.科學(xué)計算

⑴主要內(nèi)容：包括數(shù)值分析、運籌學(xué)、模擬和仿真、高

性能計算。

⑵基本問題主要包括：

①如何精確地以有限的離散過程近似表示連續(xù)和無限

的離散過程？

②如何處理這種近似產(chǎn)生的錯誤？

③給定某一類方程在某精確度水平上能以多快的速度

求解？

④如何實現(xiàn)方程的符號操作，如積分、微分以及到最

小項的歸約？

⑤如何把這些問題的答案包含到一個有效的、可靠的、

高質(zhì)量的數(shù)學(xué)軟件包中？，

BACK

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

4.4學(xué)科典型問題的認知探討

在人類社會的發(fā)展過程中，人們提出過許多具有

深遠意義的科學(xué)問題，其中也對計算學(xué)科一些分支領(lǐng)

域的形成和發(fā)展起了重要的作用。另外，在計算學(xué)科

的發(fā)展過程中，為了便于對計算學(xué)科中有關(guān)問題和概

念的本質(zhì)的理解，人們還給出了不少反映該學(xué)科某一

方面本質(zhì)特征的典型實例，這里將它們一并歸于計算

學(xué)科的典型問題。計算學(xué)科典型問題的提出及研究，

不僅有助于我們深刻地理解計算學(xué)科，而且還對該學(xué)

科的發(fā)展有著十分重要的推動作用。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

1.哥尼斯堡七橋問題

17世紀的東普魯土有一座哥尼斯堡城，城中有一座

佛夫島，普雷格爾的兩條支流環(huán)繞其旁，并將整個城市分

為北區(qū)，東區(qū)，南區(qū)和島區(qū)4個區(qū)域，全城共有7座橋?qū)?個

城區(qū)相連起來，如圖所示，人們常通過7座橋到各城區(qū)游玩,

于是產(chǎn)生了一個有趣的數(shù)學(xué)難題：尋找走遍這7座橋，目只

許走過每座橋一次，最后又回到原出發(fā)點的路徑，該問題

就是著名的“哥尼斯堡七橋問題”o

1736年，大數(shù)學(xué)家列昂納德?歐拉(L.Euler)發(fā)表了

關(guān)于“哥尼斯堡七橋問題”的論文一《與位置幾何的一個

問

題的解》，他在文中指出，從一點出發(fā)不重復(fù)的走遍七橋，

最后又回到原出發(fā)點是不可能的。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

為了解決哥尼斯堡七橋問題，歐拉用4個字母A、B、C、

D代表4個城區(qū)，并用7條線表示7座橋，如下圖所示，在圖

中只有4個點和7條線，這樣做是基于該問題本質(zhì)考慮的，

它抽象出問題最本質(zhì)的東西，忽視問題非本質(zhì)的東西，從

而將哥尼斯堡七橋問題的抽象為一個數(shù)學(xué)問題。即經(jīng)過圖

中每邊一次且僅一次的回路問題了。歐拉在論文中論證了

這樣的回路是不存在的,后來，川人望有這樣回路的圖稱

為歐拉圖。

歐拉在論文中將問題進行了一般化處理，既對給定的

任意一個河道圖與任意多座橋，判定可能不可能每座橋恰

好走過一次，并用數(shù)學(xué)方法給出了3條判定的規(guī)則：

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

⑴如果通奇數(shù)橋的地方不止兩個，滿足要求的路線是找

不到的。

⑵如果只有兩個地方通奇數(shù)座橋，可以從這兩個地方之

一出發(fā)，找到所要求的路線。

⑶如果沒有一個地方是通奇數(shù)座橋的，則無論從哪里出

發(fā)，所要求的路線都能實現(xiàn)。

歐拉的論文為圖論的形成奠定了基礎(chǔ)。今天，圖論已

廣泛地應(yīng)用于計算學(xué)科、運籌學(xué)、信息論、控制論等學(xué)之

中，并已成為我們對現(xiàn)實問題進行抽象的一個強有力的數(shù)

學(xué)工具。隨著計算科學(xué)的發(fā)展，圖論在計算學(xué)科中的作用

越來越大，同時，圖論本身也得到了充分的發(fā)展。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

在圖論中還有一個很著名的“哈密爾頓回路問題”。

該問題是愛爾蘭著名學(xué)者域舞的密木顏

(W.R.Hamilton)爵士1859年提出的一個數(shù)學(xué)問題。

其大意是：在某個圖中，能不能找到這樣的路徑，即叢

一點出發(fā)不重復(fù)地走過所有的結(jié)點，最后又回到原出發(fā)

點?！肮軤栴D回路問題”是訪問每個結(jié)點一次，而“歐

拉

回路問題”是訪問每條邊一次。對圖是否存在“歐拉回路”

前面已給出充分必要條件，而對圖是否存在“哈密爾回

路”至今仍未找到滿足該問題的充分必要條件。

療m科乎,，技w邑荽

a/CoMpA/rrScutct，’1.T隊導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

1859年哈密爾頓首先提出的一

個關(guān)于12面體的數(shù)學(xué)游戲：能否

在左圖中找到一個回路，使它含

有圖中所有結(jié)點一次且僅一次？

若把每個結(jié)點看成一座城市，連

按兩個結(jié)點的邊看成是交通線，

那么這個問題就變成能否找到一條

旅行路線，使得沿著該旅行路線

經(jīng)過每座城市恰好一次，再回到

原來的出發(fā)地呢？為此，這個問

題也被稱作周游世界問題。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

一2.梵天塔問題

相傳印度教的天神梵天在創(chuàng)造地球這一世界時，建了

一座神廟，神廟里豎有三根寶石柱子，柱子由一個銅座支

撐。梵天將64個直徑大小不一的金盤子，按照從大到小的

順序依次套放在第一根柱子上，形成一座金塔，即所謂的

梵天塔(又稱漢諾塔)o天神讓廟里的僧侶們將第一根柱子

上的64個盤子借助第二根柱子全部移到第三根柱子上，既

將整個塔遷移，同時定下3條規(guī)則：

(1)每次只能移動一個盤子；

(2)盤子只能在三根柱子上來回移動,不能放在他處；

(3)在移動過和中，三根柱子上的盤子必須始終保持大盤

在下，小盤在上。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

天神說：“當這64個盤子全部移到第三根柱子上后,世界末

日就要到了”。這就是著名的梵天塔問題。

用計算機求解一個實際問題，首先要從這個實際問題中抽

象出一個數(shù)學(xué)模型，然后設(shè)計一個解此數(shù)學(xué)模型的算法，

最后根據(jù)算法編寫程序，以過調(diào)試、編譯、連接和運行，

從而守成該問題的求解，從實際問題中抽象出一個數(shù)學(xué)模

型的實質(zhì)，其實就是要用數(shù)學(xué)的方法抽取其主要的，本質(zhì)

的內(nèi)容，最終實現(xiàn)對該問題的正確認識。

G"療m科乎,，技w邑荽

a/CoMpA/rrScutct，’1.TF算機導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

ABCABCABC

(1)(2)(3)

當11=3時漢諾塔的搬動情況

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

這樣的問題求解算法可以設(shè)計成一個遞歸結(jié)構(gòu)

的算法。

如圖所示，求解n個圓盤的漢諾塔問題的算法

為：

(1)遞歸調(diào)用nT個圓盤的漢諾塔問題算法，把

上面的nT個圓盤從A柱移到B柱

(2)把最下面的一個圓盤從A柱直接移到C柱。

(3)遞歸調(diào)用nT個圓盤的漢諾塔問題算法，把

B柱上臨時存放的nT個圓盤移到C柱。

鼠

瓦

便必

令需

書印

？露

為

&

、#

t

4

4

7

0

K時

0寸

,

/除

Z

G

?

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

梵天塔問題是一個典型的只有用遞歸方法（而不能用

其他方法）來解決的問題，遞歸是計算學(xué)科中的一個重要

概念，所謂遞歸，就是將一個較大的問題歸約為一個與

原問題相同。

根據(jù)遞歸方法，我們可發(fā)將64個盤子的梵天塔問題

轉(zhuǎn)化為求解63個盤子先移動到第二個柱子上，再將最后

一個盤子直接移動到第三個柱子上，最后又一次將63個

盤子從第二個柱子移動到第三個柱子上，這樣則可以解

決64個盤子的梵天塔問題。依此類推，63個盤子的梵天

塔求解問題可以轉(zhuǎn)化為62個盤子的梵天塔求解問題，62

個盤子的梵天塔求解問題又可以轉(zhuǎn)化為61個盤子的梵天

塔求解問題，直到1個盤子的梵天塔求解問題。再由1

機刊藝"佯在玄

JL^tpdrtwtnt豈CoarputfrS(itnet6」T隊導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

個盤子的梵天塔的求解求出2個盤子的梵天塔，直到解出

64個盤子的梵天塔問題。下面，用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-11middle,left,right)；

})

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

注：n表示n個盤子的梵天塔問題，left表示第一個柱子，

middle表示第二個柱子，right表示第三個柱子。函數(shù)

hanoi(n-l,left,rifht,middle)表示n-1階梵天塔從第一個柱子

借助第三個柱子先移到第二個柱子上，函數(shù)

move(l,left,_,right)表示將第一個柱子上最后一個盤子直接

放到第三個柱子上，函數(shù)hanoi(n-11middle,right)表示n-1個

盤子借助第一個柱子移到第三個柱子上。

在以上C語言描述的算法基礎(chǔ)上，作適當擴充就可以

形成一個完整的程序，經(jīng)過編譯和連接后，計算機就可

以執(zhí)行這個程序，并格地按照遞歸的方法將問題目求解

出來。

現(xiàn)在的問題目是當n=64時，即有64個盤子時，需要

G2"機刊藝"佯在玄

JL^tpdrtwtnt豈CoarputfrS(itnet6」TF算機導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

移動多少次盤子，要用多少時間。

按照上面的算法，n個盤子的梵天塔問題目需要移動的

盤子數(shù)是n-1個盤子的梵天塔問題目需要移動的盤子數(shù)的

2倍加1。于是h(n尸2h(n-1)+1

=2(2h(n-2)+1)+1=22h(n-2)+2+1

=23h(n-3)+2+2+l

=2%(0)+2+…+2+2+1

=2n-1+...+22+2+l=2n-l

因此，要完成梵天塔的搬遷，需要移動盤子的次數(shù)為:

2-1=18446744073709551615

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

如果每秒移動一次，一年有31536000秒，則僧侶們

一刻不停地來回搬動，也需要花費5849億年的時間。假

定計算機以每秒1000萬個盤子的速度進行搬遷，則需要

花費大約58490年的時間。

就這個例子，讀者可以了解到理論上可以計算的問

題，實際上并不一定能行，這屬于算法復(fù)雜性方面的研

究內(nèi)容。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

3.證比求易算法

I.證比求易算法

為了更好地理解計算復(fù)雜性的有關(guān)概念，我國學(xué)者洪加

威曾經(jīng)被人講了一個稱為“證比求易算法”的童話，用來

幫助

讀者理解計算復(fù)雜性的有關(guān)概念，具體內(nèi)容如下。

從前，有一個酷愛學(xué)者的年輕國王向鄰國一位聰明美

麗的公主求婚。公主出了這樣一道題：求出48770428433

377171的一個真因子。若國王能在一天之內(nèi)求出答案，公

主便接受他的求婚。國王回去后立即開始逐個數(shù)的進行計

算，他從早到晚，共算了三萬多個數(shù)，最終還是沒有結(jié)果。

國王向公主求情，公主將答案相告：223092827是它的一

個真因子。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

國王很快驗證了這個數(shù)確能除盡48770428433377171。

公主說：“我再給你一次機會，如果還求不出，將來你只

好

做我的證婚人了。”國王立即回國，并向時任宰相的大數(shù)

學(xué)

家請教，大數(shù)學(xué)家在仔細的思考后認為這個數(shù)為17位，則

最小的一為真因子不會超過9位，于是他給國王出了一個主

意：按自然數(shù)的順序給全國的老百姓每人編一個號發(fā)下去,

等公主給出數(shù)目后，立即將它們通報全國，讓每個老百姓

用自己的編號去除這個數(shù)，除盡了立即上報，賞金萬兩。

最后，國王用這個辦法求婚成功。

H.順序算法和并行算法

在“正比求易的算法”的故事中，國王最先使用■的皆

一種

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

順序算法,其復(fù)雜性表現(xiàn)在時間方面,后由宰相提出的是

一種并行算法,其復(fù)雜性表現(xiàn)在空間方面。直覺上，我們

認為順序算法解決不了的問題完全可用并行算法來解決，

甚至?xí)?，并行計算機系統(tǒng)求解問題的速度將隨著處理機

數(shù)目的不斷增加而不斷提高，從而解決難解性問題，其實

這是一種誤解。當一個問題分解到多個處理機上解決時，

由于算法中不可避免地存在必須串行執(zhí)行的操作，從而大

大限制了并行計算機的加速能力。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

4.旅行商問題與組合爆炸問題

旅行商問題(TravelingSalesmanProblem,簡稱TSP)是

威廉?哈密而頓爵士和英國數(shù)學(xué)家比威曼(T.P.Kirkman)

于19世紀初提出的一個數(shù)學(xué)問題。這是一個NP完全性問題。

其大意是：有若干個城市，任何城市之間的距離都是確定

的，現(xiàn)要求一旅行商從某城市出發(fā)，必須經(jīng)過每一個城市

且只能在每個城市逗留一次，最后回到出發(fā)城市。問如何

事先確定好一條最短的路線，使其旅行的費用最少。

人們在考慮解決這個問題時，一般首先想到的最原始

的一種方法就是：列出每一條可供選擇的路線(即對給定

的城市進行排列組合)，計算每條路線的總里程，最后從

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

一中選出一條最短的路線。假定現(xiàn)在給定的4個城市分別為

A.B.C.D各城市之間的距離為已知數(shù)（如圖1所示）。我們

可以通過一個組合的空間狀態(tài)圖來表示所有的組合（如圖2

所示）。從圖中不難看出，可供選擇的路線共有6條，從中

可以很快選出一條總距離最短的路線。由此推算我們設(shè)城

市數(shù)目為n時那么組合路徑樹則為（n-1）!。很顯然，當城市

數(shù)目不多時要找到最短距離的路線并不難，但隨著城市數(shù)

目的不斷增大，組合數(shù)目將曾指數(shù)級數(shù)規(guī)律積聚增長，一

直達到無法計算的地步，這就是所謂的“組合爆炸問題”。

假設(shè)現(xiàn)在城市的數(shù)目增為20個，組合路徑數(shù)則為（20-1）!

-1.216X10,如此龐大的數(shù)目組合，若計算機一每秒1000

萬條路線的速度計算，也需要花上386年的時間。

計算機導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

據(jù)文獻介紹，1998年，科學(xué)

家們成功地解決了美國13509個

城市之間的TSP問題，2001年又

解決了德國15112個城市之間的

TSP問題。但這一工程代價也是

巨大的，據(jù)報道，解決15112個

城市之間的TSP問題，共使用了

美國Rice大學(xué)和普林斯頓大學(xué)

之間網(wǎng)絡(luò)互連得到、有速度為

城市交通圖500MHZ的CompaqEV6Alpha

處理器組成的110臺計算機，所

有計算機花費的時間之和為22?6

年。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

TSP是最有代表性的優(yōu)化組合問題之一，它的應(yīng)用已

逐步滲透到各個技術(shù)領(lǐng)域和我們的日常生活中，至今還有

不少學(xué)者在從事這方面的研究工作，一些項目還得到美國

軍方的資助。就實際應(yīng)用而言，一個典型的例子就是物器

在電路板上鉆孔的調(diào)度問題（注^在該問題中，鉆孔的時

間是固定的，只要機器移動時間的總量上可變的），在這

里，電路上要鉆的孔相當于TSP中的“旅行費用”。在大

規(guī)

模生產(chǎn)過程尋找最短路徑能有效降低成本，這類問題的解

決還可以延伸到其他行業(yè)中去，如運輸業(yè)、后勤服務(wù)業(yè)等。

然而，由于TSP產(chǎn)生組合爆炸的問題，尋求切實可行的求

解方法就成為問題的關(guān)鍵。-------

機刊藝"佯在玄

JL^tpdrtwtnt豈CoarputfrS(itnet6」T隊導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

路徑：ABCDA

總距離：13

路徑：ABDCA

總距曷:14

路徑:ACBDA

總距離：19

路徑：ACDBA

總距曷:14

路徑：ADCBA

總距離：13

路徑：ADBCA

總距離：19

組合路徑問題

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

5、“哲學(xué)家共餐”問題

戴克斯拉針對多進程互斥地訪問有限資源的問題提出并

解決了一個被人之為“哲學(xué)家共餐”的多進程同步問題。

對哲學(xué)家共餐問題可以作這樣的描述：5個哲學(xué)家圍坐

在一張圓桌旁，每個人的前面擺有一碗面條，碗的兩旁各擺

有一只筷子（注：戴克斯拉原來提到是叉子和意大利面條，

因有人習(xí)慣用一個叉子吃面條，于是后來的研究人員又將叉

子和意大利面條改寫為中國筷子和面條）。

假設(shè)哲學(xué)家的生活除了吃飯就是思考問題（這是一種抽

象，即對該問題而言其他活動都無關(guān)緊要），而吃飯的時候

需要左手拿一只筷子，右手拿一只筷子，然后開始進餐。吃

完后又將筷子擺回原處，繼續(xù)思考問題。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

那么，一個哲學(xué)家的生活進餐可表示為：

⑴思考問題

⑵餓了停止思考，左手拿一只筷子（如果左側(cè)哲學(xué)家已

持有它，則需等待）；

⑶右手拿了一只筷子（如果左側(cè)哲學(xué)家已持有它，則需

等待）；

⑷進餐；

⑸放右手筷子；

⑹放左手筷子；

⑺重新回到思考問題狀態(tài)⑴。

現(xiàn)在的問題是：如何協(xié)調(diào)5個哲學(xué)家的生活進程，使

得每一個哲學(xué)家最終都可以進餐。

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

考慮下面的兩種情況：

⑴按哲學(xué)家的活動進程，當所有的哲學(xué)家都同時拿起左

筷子時，則所有的哲學(xué)家都將拿不到右手的筷子，并

處于等待狀態(tài)，那么哲學(xué)家都無法進餐，最終餓死。

⑵將哲學(xué)家的活動進程修改一下，變?yōu)楫斢沂值目曜幽?/p>

不到時，就放下左手的筷子，這種情況是不是就沒有

問題？不一定，因為可能在一瞬間，所有的哲學(xué)家都

同時拿起左手的筷子，則自然拿不到右手的筷子，于

是都同時放下左手的筷子，等一會，又同時拿起左手

的筷子，如此這樣永遠重復(fù)下去，則所有的哲學(xué)家一

樣都吃不到飯。

以上兩方面的問題，其實反映的是程序并發(fā)執(zhí)行時

T隊導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

選程何步的兩個問題，一個是死瑣，另一個是饑餓。

為了提高系統(tǒng)的處理能力和機器的利用率，并發(fā)程序

被廣泛的使用，因此，必須徹底解決并發(fā)程序中的死瑣和

譏餓問題。于是，人們將5個哲學(xué)家問題推廣為更一般性

的n個進程和m個共享資源的問題，并在研究過程中給出了

解決這類問題的不少方法和工具，如Petri網(wǎng)、并發(fā)程序

語言等工具。

與程序并發(fā)執(zhí)行時進程同步有關(guān)的經(jīng)典問題還有：

讀一

寫者問題(Reader-WriterProblem)、睡眠的理發(fā)師問

題(SleepingBarderProblem)等。

BACK

（r）tr療機不%丁:'z/九2a

寸Conp^ttrSattef&TerAwo.T以導(dǎo)論

?第4章計算學(xué)科的科學(xué)問題

4.5人工智能中的若干哲學(xué)問題