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

G"”m和乎叮拄企於

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

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

0內(nèi)容提要

聲4.1概^述

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

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

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

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

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

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

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

4.1概述

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

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

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

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

答案。

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

認(rèn)知的基礎(chǔ)，又預(yù)示著進(jìn)一步的實(shí)踐和認(rèn)識(shí)的方向，它是

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

們

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

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

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

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

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

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

能否在所從事的工作中提出（或從眾多的問題中抽取）關(guān)

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

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

戰(zhàn)。

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

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

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

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

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

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

對(duì)新知識(shí)的追求，但這種追求開始的時(shí)候是模糊不清的。

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

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

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

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

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

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

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

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

學(xué)問題。

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

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

永遠(yuǎn)不可解決。

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

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

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

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

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

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

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

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

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

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

性

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

于

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

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

重大突破。

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

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

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

T隊(duì)導(dǎo)論

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

結(jié)果。

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

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

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

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

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

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

分類方法，這里不對(duì)這些分類方法進(jìn)行討論，僅對(duì)反映計(jì)

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

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

題進(jìn)行分析。

BACK

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

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

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

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

計(jì)算學(xué)科根本問題的認(rèn)識(shí)過程與人們對(duì)計(jì)算過程的

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

本問題，首先要分析人們對(duì)計(jì)算本質(zhì)的認(rèn)識(shí)過程。

計(jì)算本質(zhì)的認(rèn)識(shí)歷史

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

考證的，遠(yuǎn)在舊石器時(shí)代，刻在骨制和石頭上的花紋就

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

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

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

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

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

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

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

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

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

箸

對(duì)計(jì)算的根本問題，即“能行性”問題的理解，這種理解

對(duì)

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

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

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

技術(shù)獎(jiǎng)。

算盤作為主要的計(jì)算工具流行了相當(dāng)長的一段時(shí)間，

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

機(jī)械來實(shí)現(xiàn)人腦活動(dòng)的個(gè)別功能?最初的實(shí)驗(yàn)?zāi)康牟⒉皇?/p>

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

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

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

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

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

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

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

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

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

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

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

行簡(jiǎn)單加、減、乘、除的計(jì)算機(jī)器；19世紀(jì)30年代，英

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

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

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

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

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

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

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

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

其實(shí)，對(duì)計(jì)算本質(zhì)的真正認(rèn)識(shí)取決于形式化研究的

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

它還標(biāo)志著形式化思想革命的開始。

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

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

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

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

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

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

了集合論?？低袪杽?chuàng)立的集合論對(duì)數(shù)學(xué)概念作了重要的

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

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

(r\n空m不斗乎*4

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

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

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

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

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

次

危機(jī)。

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

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

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

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

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

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

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

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

按

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

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

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

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

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

不給自己刮胡子。

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

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

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

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

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

（人或機(jī)器）對(duì)一條兩端可無限延長的紙帶上的一串0和

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

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

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

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

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

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

靈的研究成果是歌德爾研究成果的進(jìn)一步深化，該成果

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

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

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

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

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

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

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

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

式進(jìn)行編碼，并存放在存儲(chǔ)器中，以后使用時(shí)譯碼，并由

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

圖靈的研究成果是：可計(jì)算性二圖靈可計(jì)算性。

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

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

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

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

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

算法也稱為能行方法或或能行過程，是對(duì)解題（計(jì)算）過

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

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

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

中），當(dāng)且僅當(dāng)它能夠被一臺(tái)圖靈機(jī)實(shí)現(xiàn)。圖靈機(jī)與當(dāng)時(shí)

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

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

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

奇——圖靈論題。

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

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

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

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

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

中的能行性還包含時(shí)間與空間的有效性。

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

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

想模型提出不到10年的時(shí)間里，世界上第一臺(tái)電子計(jì)算

機(jī)誕生了。

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

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

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

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

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

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

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

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

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

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

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

計(jì)過程關(guān)心的是模型的具體實(shí)現(xiàn)問題，正因?yàn)槿绱耍?jì)算

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

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

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

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

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

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

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

學(xué)科。

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

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

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

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

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

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

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

源于對(duì)算法理論、數(shù)理邏輯、計(jì)算模型、自動(dòng)計(jì)算機(jī)器的

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

代初期。

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

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

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

報(bào)告摘錄中得到強(qiáng)調(diào)：

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

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

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

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

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

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

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

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

程設(shè)計(jì)。

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

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

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

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

fio

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

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

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

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

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

因?yàn)榉请x散對(duì)象，即所謂的連續(xù)對(duì)象，是很難進(jìn)行能行

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

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

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

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

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

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

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

用。同時(shí)，又因?yàn)橛?jì)算技術(shù)的迅猛發(fā)展，使得離散數(shù)學(xué)

越來越受到重視。為此，CC2001報(bào)告特意將它從

CC1999報(bào)告的預(yù)備知識(shí)中抽取出來，列為計(jì)算學(xué)科的第

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

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

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

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

的依賴性。

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

本問題仍然是：什么能被（有效地）自動(dòng)進(jìn)行。甚至還

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

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

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

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

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

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

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

GI卜計(jì)機(jī)不斗?『r技/三系

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

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

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

械過程的計(jì)算而言，王浩認(rèn)為：人要做機(jī)器永遠(yuǎn)不能做

的某些計(jì)算是不容易的。

BACK

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

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

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

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

計(jì)算學(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)域與計(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é)工具。

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

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

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

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

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

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

⑵基本問題主要包：

①對(duì)給定的問題，如何進(jìn)行有效的描述并給出算法？

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

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

3算法與復(fù)雜性

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

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

自動(dòng)機(jī)理論，密碼算法以及幾何算法等。

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

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

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

⑵基本問題主要包括：

①對(duì)于給定的問題類，最好的算法是什么？要求的存儲(chǔ)

空間和計(jì)算時(shí)間有多少？空間和時(shí)間如何折衷？

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

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

④算法的平均性能如何？

⑤算法的通用性如何？

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)等。

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

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

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

⑵基本問題主要包括：

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

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

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

作的？

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

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

④如何度量性能？

5.操作系統(tǒng)

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

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

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

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

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

⑵基本問題主要包括：

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

許進(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ò)展的原

則是什么？

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

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

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

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

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

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

⑵基本問題主要包括：

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

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

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

④分布式計(jì)算的性能如何評(píng)價(jià)？

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

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

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

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

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

?第4章計(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ì)算

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

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

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

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

8.人—機(jī)父互

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

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

⑵基本問題主要包括：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10.智能系統(tǒng)

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

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

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

⑵基本問題主要有：

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

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

述了智能？

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

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

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

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

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

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

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

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

1L信息管理

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

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

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

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

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

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

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

⑵基本問題主要包括：

①使用什么樣的建模概念來表示數(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)訪問、泄露和破壞？

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

一致性？

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

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

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

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

?第4章計(jì)算學(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ì)軟件？

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

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

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

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

⑴主要內(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ì)問題、哲學(xué)框架等。

⑵基本問題主要包括：

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

②有關(guān)計(jì)算的社會(huì)影響問題，以及如何評(píng)價(jià)可能的一

些答案的問題；

③哲學(xué)問題；

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

T隊(duì)導(dǎo)論

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

14.科學(xué)計(jì)算

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

性能計(jì)算。

⑵基本問題主要包括：

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

的離散過程？

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

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

求解？

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

小項(xiàng)的歸約？

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

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

BACK

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.哥尼斯堡七橋問題

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

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

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

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

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

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

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

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

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

問

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

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

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

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

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

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

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

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

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

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

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

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

為歐拉圖。

歐拉在論文中將問題進(jìn)行了一般化處理，既對(duì)給定的

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

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

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

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

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

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

不到的。

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

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

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

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

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

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

中，并已成為我們對(duì)現(xiàn)實(shí)問題進(jìn)行抽象的一個(gè)強(qiáng)有力的數(shù)

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

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

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

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

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

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

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

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

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

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

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

拉

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

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

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

療m科乎,，技w邑荽

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

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

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

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

在左圖中找到一個(gè)回路，使它含

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

若把每個(gè)結(jié)點(diǎn)看成一座城市，連

按兩個(gè)結(jié)點(diǎn)的邊看成是交通線，

那么這個(gè)問題就變成能否找到一條

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

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

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

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

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

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

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

一2.梵天塔問題

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

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

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

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

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

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

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

(1)每次只能移動(dòng)一個(gè)盤子；

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

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

在下，小盤在上。

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

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

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

天神說：“當(dāng)這64個(gè)盤子全部移到第三根柱子上后,世界末

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

用計(jì)算機(jī)求解一個(gè)實(shí)際問題，首先要從這個(gè)實(shí)際問題中抽

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

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

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

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

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

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

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

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

ABCABCABC

(1)(2)(3)

當(dāng)11=3時(shí)漢諾塔的搬動(dòng)情況

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

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

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

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

的算法。

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

為：

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

上面的nT個(gè)圓盤從A柱移到B柱

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

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

B柱上臨時(shí)存放的nT個(gè)圓盤移到C柱。

鼠

瓦

便必

令需

書印

？露

為

&

、#

t

4

4

7

0

K時(shí)

0寸

,

/除

Z

G

?

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

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

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

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

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

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

原問題相同。

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

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

一個(gè)盤子直接移動(dòng)到第三個(gè)柱子上，最后又一次將63個(gè)

盤子從第二個(gè)柱子移動(dòng)到第三個(gè)柱子上，這樣則可以解

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

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

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

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

機(jī)刊藝"佯在玄

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

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

個(gè)盤子的梵天塔的求解求出2個(gè)盤子的梵天塔，直到解出

64個(gè)盤子的梵天塔問題。下面，用C語言對(duì)該問題的求

解算法進(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-11middle,left,right)；

})

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

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

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

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

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

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

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

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

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

盤子借助第一個(gè)柱子移到第三個(gè)柱子上。

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

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

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

出來。

現(xiàn)在的問題目是當(dāng)n=64時(shí)，即有64個(gè)盤子時(shí)，需要

G2"機(jī)刊藝"佯在玄

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

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

移動(dòng)多少次盤子，要用多少時(shí)間。

按照上面的算法，n個(gè)盤子的梵天塔問題目需要移動(dòng)的

盤子數(shù)是n-1個(gè)盤子的梵天塔問題目需要移動(dòng)的盤子數(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

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

2-1=18446744073709551615

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

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

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

如果每秒移動(dòng)一次，一年有31536000秒，則僧侶們

一刻不停地來回搬動(dòng)，也需要花費(fèi)5849億年的時(shí)間。假

定計(jì)算機(jī)以每秒1000萬個(gè)盤子的速度進(jìn)行搬遷，則需要

花費(fèi)大約58490年的時(shí)間。

就這個(gè)例子，讀者可以了解到理論上可以計(jì)算的問

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

究內(nèi)容。

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

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

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

3.證比求易算法

I.證比求易算法

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

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

幫助

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

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

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

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

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

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

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

個(gè)真因子。

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

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

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

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

公主說：“我再給你一次機(jī)會(huì)，如果還求不出，將來你只

好

做我的證婚人了?！眹趿⒓椿貒?，并向時(shí)任宰相的大數(shù)

學(xué)

家請(qǐng)教，大數(shù)學(xué)家在仔細(xì)的思考后認(rèn)為這個(gè)數(shù)為17位，則

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

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

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

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

最后，國王用這個(gè)辦法求婚成功。

H.順序算法和并行算法

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

一種

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

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

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

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

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

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

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

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

這是一種誤解。當(dāng)一個(gè)問題分解到多個(gè)處理機(jī)上解決時(shí)，

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

大限制了并行計(jì)算機(jī)的加速能力。

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

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

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

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

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

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

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

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

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

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

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

人們?cè)诳紤]解決這個(gè)問題時(shí)，一般首先想到的最原始

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

萬條路線的速度計(jì)算，也需要花上386年的時(shí)間。

計(jì)算機(jī)導(dǎo)論

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

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

家們成功地解決了美國13509個(gè)

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

解決了德國15112個(gè)城市之間的

TSP問題。但這一工程代價(jià)也是

巨大的，據(jù)報(bào)道，解決15112個(gè)

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

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

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

城市交通圖500MHZ的CompaqEV6Alpha

處理器組成的110臺(tái)計(jì)算機(jī)，所

有計(jì)算機(jī)花費(fèi)的時(shí)間之和為22?6

年。

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

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

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

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

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

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

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

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

間是固定的，只要機(jī)器移動(dòng)時(shí)間的總量上可變的），在這

里，電路上要鉆的孔相當(dāng)于TSP中的“旅行費(fèi)用”。在大

規(guī)

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

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

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

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

機(jī)刊藝"佯在玄

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

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

路徑：ABCDA

總距離：13

路徑：ABDCA

總距曷:14

路徑:ACBDA

總距離：19

路徑：ACDBA

總距曷:14

路徑：ADCBA

總距離：13

路徑：ADBCA

總距離：19

組合路徑問題

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

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

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

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

戴克斯拉針對(duì)多進(jìn)程互斥地訪問有限資源的問題提出并

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

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

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

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

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

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

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

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

需要左手拿一只筷子，右手拿一只筷子，然后開始進(jìn)餐。吃

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

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

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

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

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

⑴思考問題

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

持有它，則需等待）；

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

等待）；

⑷進(jìn)餐；

⑸放右手筷子；

⑹放左手筷子；

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

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

得每一個(gè)哲學(xué)家最終都可以進(jìn)餐。

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

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

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

考慮下面的兩種情況：

⑴按哲學(xué)家的活動(dòng)進(jìn)程，當(dāng)所有的哲學(xué)家都同時(shí)拿起左

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

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

⑵將哲學(xué)家的活動(dòng)進(jìn)程修改一下，變?yōu)楫?dāng)右手的筷子拿

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

問題？不一定，因?yàn)榭赡茉谝凰查g，所有的哲學(xué)家都

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

是都同時(shí)放下左手的筷子，等一會(huì)，又同時(shí)拿起左手

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

樣都吃不到飯。

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

T隊(duì)導(dǎo)論

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

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

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

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

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

的n個(gè)進(jìn)程和m個(gè)共享資源的問題，并在研究過程中給出了

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

語言等工具。

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

讀一

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

題(SleepingBarderProblem)等。

BACK

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

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

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

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