計(jì)算學(xué)科中.ppt

1、第二章 計(jì)算學(xué)科中 的科學(xué)問題,李陶深 ,本章要回答的問題,1 科學(xué)問題的定義與基本特征 2 什么是計(jì)算科學(xué)？ 3 計(jì)算學(xué)科本質(zhì)的根本問題 4 計(jì)算學(xué)科各領(lǐng)域的基本問題 5 計(jì)算學(xué)科中起重要作用的典型問題 6 人工智能中的若干哲學(xué)問題,2.1 科學(xué)問題與計(jì)算學(xué)科,科學(xué)問題的定義與基本特征 科學(xué)問題的方法論作用,2.1.1 科學(xué)問題的定義與主要特征,首先介紹三個(gè)基本術(shù)語，它們是科學(xué)、技術(shù)和工程。 -科學(xué)是關(guān)于自然、社會(huì)和思維的發(fā)展與變化規(guī)律的知識體系。 -技術(shù)是泛指根據(jù)生產(chǎn)實(shí)踐經(jīng)驗(yàn)和科學(xué)原理而發(fā)展形成的各種工藝操作方法、技能和技巧。 -工程是指將科學(xué)原理應(yīng)用到工農(nóng)業(yè)生產(chǎn)部門中去而形成的各門學(xué)科的

2、總稱。,2.1.1 科學(xué)問題的定義與主要特征,科學(xué)問題是指一定時(shí)代的科學(xué)認(rèn)識主體，在已完成的科學(xué)知識和科學(xué)實(shí)踐的基礎(chǔ)上，提出的需要解決且有可能解決的問題。它包含一定的求解目標(biāo)和應(yīng)答域，但尚無確定的答案。(例如IPv4IPv6） 能否在所從事的工作中提出關(guān)鍵和重要的科學(xué)問題，對我們每個(gè)人來說都是一個(gè)挑戰(zhàn)。 方法論的學(xué)習(xí)有助于我們自覺地、主動(dòng)地去迎接這種挑戰(zhàn)。,科學(xué)問題的主要特征,時(shí)代性：從歷史的觀點(diǎn)來看，任何一個(gè)科學(xué)問題都具有它的時(shí)代特性。每一個(gè)時(shí)代都有它自己的科學(xué)問題，而這些問題的解決對科學(xué)的發(fā)展具有深遠(yuǎn)的意義。 混沌性：科學(xué)問題顯示了人們對已有知識的不滿，并渴望對新知識的追求，但這種追求開始

3、的時(shí)候是模糊不清的。 可解決性：科學(xué)問題是由于決心解決而又有可能解決才提出的，提出科學(xué)問題后便要力圖解決它。,科學(xué)問題的主要特征,可變異性：相對科學(xué)問題的可解決性而言，如果一個(gè)問題未能解決，似乎就不是科學(xué)問題，其實(shí)不然，如果它還能引出另外具有可解決性的科學(xué)問題，則原問題仍屬于科學(xué)問題。 可待解性：由于尚不具備解決問題的全部條件，因此許多科學(xué)問題在當(dāng)前一段時(shí)間里還很難解決或無法解決，但絕非永遠(yuǎn)不可解決。,2.1.2 科學(xué)問題的方法論作用,科學(xué)問題的裂變式作用 對于一門學(xué)科而言，原先科學(xué)問題的提出與解決，會(huì)誘發(fā)出新的科學(xué)問題，而新的科學(xué)問題的解決又會(huì)誘發(fā)更新的科學(xué)問題，這種父子型、子孫型科學(xué)問題的

4、連續(xù)出現(xiàn)和相繼解決，可以導(dǎo)致該門學(xué)科的重大理論突破。例如對“數(shù)學(xué)基礎(chǔ)問題”的研究，導(dǎo)致了“形式系統(tǒng)相容性問題”的研究，最后出現(xiàn)“能行性問題”的研究，并最終于20世紀(jì)30年代由圖靈、哥德爾、丘奇和波斯特等人共同奠定了計(jì)算學(xué)科的理論基礎(chǔ)，實(shí)現(xiàn)了人類對計(jì)算認(rèn)識問題的重大突破。,2.1.2 科學(xué)問題的方法論作用,科學(xué)問題的聚變式作用殊途同歸 對不同科學(xué)問題的研究最終導(dǎo)致同一科學(xué)問題的發(fā)現(xiàn)，這種殊途同歸的結(jié)果，就是科學(xué)問題聚變式作用的結(jié)果。 科學(xué)問題的激勵(lì)作用 新的重大科學(xué)問題的確定總是在以往時(shí)代科學(xué)問題結(jié)束之際到來的，它猶如一面旗幟，象征著人類科學(xué)認(rèn)識進(jìn)入到一個(gè)嶄新的階段，它召喚和激勵(lì)著人們?yōu)榻鉀Q這些

5、富有挑戰(zhàn)性的問題而勇往直前。,2.1.2 科學(xué)問題的方法論作用,在科學(xué)哲學(xué)中，從不同角度出發(fā)，科學(xué)問題有不同的分類方法，本章不對這些分類方法進(jìn)行討論，僅對反映計(jì)算學(xué)科本質(zhì)的根本問題、學(xué)科各領(lǐng)域的基本問題、在學(xué)科中起重要作用的典型問題，以及人工智能中的若干哲學(xué)問題進(jìn)行分析。,2.2 計(jì)算學(xué)科中的科學(xué)問題,計(jì)算的本質(zhì) 計(jì)算學(xué)科的定義和根本問題,2.2.1 前人的工作,形式化方法和理論的研究起源于對數(shù)學(xué)的基礎(chǔ)研究。 康托爾（G.Cantor，18451918）從1874年開始，對數(shù)學(xué)基礎(chǔ)作了新的探討，發(fā)表了一系列集合論方面的著作，從而創(chuàng)立了集合論。 “羅素悖論”，從而導(dǎo)致了數(shù)學(xué)發(fā)展史上的第三次危機(jī)。

6、,希爾伯特綱領(lǐng),希爾伯特（D.Hilbert）在數(shù)學(xué)基礎(chǔ)的研究中提出了一個(gè)設(shè)想 將每一門數(shù)學(xué)的分支形式化，構(gòu)成形式系統(tǒng)或形式理論，并在以此為對象的元理論即元數(shù)學(xué)中，證明每一個(gè)形式系統(tǒng)的相容性，從而導(dǎo)出全部數(shù)學(xué)的相容性。 目標(biāo)是要尋找通用的形式邏輯系統(tǒng)，該系統(tǒng)應(yīng)當(dāng)是完備的，即在該系統(tǒng)中，可以機(jī)械地判定任何給定命題的真?zhèn)巍?庫爾特哥德爾（KGodel）,認(rèn)為數(shù)學(xué)原理所定義的系統(tǒng)既是一致的，也是完備的 任何系統(tǒng)的完備和一致性，可以由系統(tǒng)本身得到證明。 1931年，“希爾伯特綱領(lǐng)”被奧地利邏輯學(xué)家Godel搠出一個(gè)大窟窿 Godel認(rèn)為沒有一種公理系統(tǒng)可以導(dǎo)出數(shù)論中所有的真實(shí)命題，除非這種系統(tǒng)本身就有

7、悖論。 推翻“希爾伯特綱領(lǐng)”，還直逼數(shù)學(xué)原理，說它本身就是不一致的。,希爾伯特綱領(lǐng),“希爾伯特綱領(lǐng)”的研究基礎(chǔ)是邏輯和代數(shù)，即布爾代數(shù) Gdel提出的關(guān)于形式系統(tǒng)的“不完備性定理”中指出 這種形式系統(tǒng)是不存在的，從而宣告了著名的“希爾伯特綱領(lǐng)”的失敗。 表明形式系統(tǒng)不能窮盡全部數(shù)學(xué)命題，任何形式系統(tǒng)中都存在著該系統(tǒng)所不能判定其真?zhèn)蔚拿}。,希爾伯特綱領(lǐng)的歷史意義,“希爾伯特綱領(lǐng)”是在保存全部古典數(shù)學(xué)的前提下去排除集合論悖論的，它給數(shù)學(xué)基礎(chǔ)問題的研究帶來了全新的轉(zhuǎn)機(jī) 希爾伯特綱領(lǐng)的提出使元數(shù)學(xué)得到了確立和發(fā)展 希爾伯特綱領(lǐng)的失敗啟發(fā)人們應(yīng)避免花費(fèi)大量的精力去證明那些不能判定的問題，而應(yīng)把精力集中

8、于解決具有能行性的問題。,2.2.2 圖靈對計(jì)算本質(zhì)的揭示,“哥德爾定理”的提出使整個(gè)邏輯和數(shù)學(xué)領(lǐng)空中陰云四布。 天才的圖靈在數(shù)理邏輯大本營的劍橋大學(xué)提出一個(gè)設(shè)想：能否有這樣一臺(tái)機(jī)器，通過某種一般的機(jī)械步驟，能在原則上一個(gè)接一個(gè)地解決所有的數(shù)學(xué)問題。 圖靈從計(jì)算一個(gè)數(shù)的一般過程入手對計(jì)算的本質(zhì)進(jìn)行了研究，從而實(shí)現(xiàn)了對計(jì)算本質(zhì)的真正認(rèn)識。,2.2.2 圖靈對計(jì)算本質(zhì)的揭示,圖靈用形式化方法成功地表述了計(jì)算這一過程的本質(zhì)：所謂計(jì)算就是計(jì)算者（人或機(jī)器）對一條兩端可無限延長的紙帶上的一串0和1執(zhí)行指令，一步一步地改變紙帶上的0或1，經(jīng)過有限步驟，最后得到一個(gè)滿足預(yù)先規(guī)定的符號串的變換過程。 圖靈機(jī)反

9、映的是一種具有能行性的用數(shù)學(xué)方法精確定義的計(jì)算模型，而現(xiàn)代計(jì)算機(jī)正是這種模型的具體實(shí)現(xiàn)。,2.2.3 什么是計(jì)算科學(xué)？,計(jì)算科學(xué)是對描述和變換信息的算法過程進(jìn)行的系統(tǒng)研究，包括其理論、分析、設(shè)計(jì)、效率分析、實(shí)現(xiàn)和應(yīng)用的系統(tǒng)的研究。 計(jì)算科學(xué)來源于對算法理論、數(shù)理邏輯、計(jì)算模型、自動(dòng)計(jì)算機(jī)器的研究，并與存儲(chǔ)式電子計(jì)算機(jī)的發(fā)明一起形成于20世紀(jì)40年代初期。 現(xiàn)在，計(jì)算已成為繼理論、實(shí)驗(yàn)之后的第三種科學(xué)形態(tài)和科學(xué)方法。,2.2.4 計(jì)算學(xué)科的根本問題,計(jì)算學(xué)科的根本問題是：什么能被（有效地）自動(dòng)進(jìn)行。 “能行性”這個(gè)計(jì)算學(xué)科的根本問題決定了計(jì)算機(jī)本身的結(jié)構(gòu)和它處理的對象都是離散型的，甚至許多連續(xù)型

10、的問題也必須在轉(zhuǎn)化為離散型問題以后才能被計(jì)算機(jī)處理。例如，計(jì)算定積分就是把它變成離散量，再用分段求和的方法來處理的。 計(jì)算學(xué)科所有分支領(lǐng)域的根本任務(wù)就是進(jìn)行計(jì)算，其實(shí)質(zhì)就是字符串的變換。,從計(jì)算的角度認(rèn)知思維、視覺和生命過程,以1975年圖靈獎(jiǎng)共同獲得者西蒙（H.A.Simon）和紐厄爾（A.Newell）為代表的符號主義者認(rèn)為：認(rèn)知是一種符號處理過程。他們還提出了人類思維過程也可用某種符號來描述的思想，即思維就是計(jì)算（認(rèn)知就是計(jì)算）的思想。除了思維、認(rèn)知之外，有關(guān)視覺認(rèn)知理論的學(xué)者也把視覺看作是一種計(jì)算。 1994年11月美國科學(xué)家L.M.Adleman在 Science 上發(fā)表了論文“Mo

11、lecular Computation of Solutions to Combinatorial Problems” ，論證了DNA（脫氧核糖核酸）計(jì)算技術(shù)的可行性，并用DNA計(jì)算機(jī)解決了一個(gè)簡單的有向哈密爾頓路徑問題,2002年，阿德勒曼教授應(yīng)用DNA計(jì)算機(jī)可以解決具有100萬種可能結(jié)果的有向哈密爾頓路徑問題，阿德勒曼的工作從一個(gè)側(cè)面探討了生命過程就是一種計(jì)算的思想。,2.3 計(jì)算學(xué)科中的科學(xué)問題,計(jì)算學(xué)科中的典型問題 及其相關(guān)內(nèi)容,(1) 哥尼斯堡七橋問題,17世紀(jì)的東普魯士有一座哥尼斯堡城，城中有一座奈佛夫島，普雷格爾河的兩條支流環(huán)繞其旁，并將整個(gè)城市分成北區(qū)、東區(qū)、南區(qū)和島區(qū)4個(gè)區(qū)域

12、，全城共有7座橋?qū)?個(gè)城區(qū)相連起來。 通過這7座橋到各城區(qū)游玩，問題：尋找走遍這7座橋的路徑，要求過每座橋只許走一次，最后又回到原出發(fā)點(diǎn)。,問題的抽象,1736年，大數(shù)學(xué)家列昂納德歐拉（L.Euler）發(fā)表了關(guān)于“哥尼斯堡七橋問題”的論文。 他抽象出問題最本質(zhì)的東西，忽視問題非本質(zhì)的東西（如橋的長度等），從而將哥尼斯堡七橋問題抽象為一個(gè)數(shù)學(xué)問題，即經(jīng)過圖中每邊一次且僅一次的回路問題了。,歐拉回路,歐拉給出了哥尼斯堡七橋問題 的證明，還用數(shù)學(xué)方法給出了三條判定規(guī)則： 如果通奇數(shù)座橋的地方不止兩個(gè)，滿足要求的路線是找不到的。 如果只有兩個(gè)地方通奇數(shù)座橋，可以從這兩個(gè)地方之一出發(fā)，找到所要求的路線。

13、 如果沒有一個(gè)地方是通奇數(shù)座橋的，則無論從哪里出發(fā)，所要求的路線都能實(shí)現(xiàn)。,(2) 哈密爾頓回路問題,問題：在某個(gè)圖G中，能不能找到這樣的路徑，即從一點(diǎn)出發(fā)不重復(fù)地走過所有的結(jié)點(diǎn)，最后又回到原出發(fā)點(diǎn)。 “哈密爾頓回路問題”與“歐拉回路問題”的不同點(diǎn) “哈密爾頓回路問題”是訪問每個(gè)結(jié)點(diǎn)一次，而“歐拉回路問題”是訪問每條邊一次。 對圖G是否存在“歐拉回路”前面已給出充分必要條件，而對圖G是否存在“哈密爾頓回路”至今仍未找到滿足該問題的充分必要條件。,圖論的形成和發(fā)展,歐拉的論文為圖論的形成奠定了基礎(chǔ)。 圖論已廣泛地應(yīng)用于 計(jì)算學(xué)科 運(yùn)籌學(xué) 信息論 控制論等學(xué)科 圖論已成為我們對現(xiàn)實(shí)問題進(jìn)行抽象的一

14、個(gè)強(qiáng)有力的數(shù)學(xué)工具。 圖論在計(jì)算學(xué)科中的作用越來越大，圖論本身也得到了充分的發(fā)展。,(3) 梵天塔問題,相傳印度教的天神梵天在創(chuàng)造地球這一世界時(shí)，建了一座神廟，神廟里豎有三根寶石柱子，柱子由一個(gè)銅座支撐。梵天將64個(gè)直徑大小不一的金盤子，按照從大到小的順序依次套放在第一根柱子上，形成一座所謂的梵天塔。天神讓廟里的僧侶們將第一根柱子上的64個(gè)盤子借助第二根柱子全部移到第三根柱子上，既將整個(gè)塔遷移，同時(shí)定下3條規(guī)則： 每次只能移動(dòng)一個(gè)盤子； 盤子只能在三根柱子上來回移動(dòng)，不能放在他處； 在移動(dòng)過程中，三根柱子上的盤子必須始終保持大盤在下，小盤在上。 天神說：“當(dāng)這64個(gè)盤子全部移到第三根柱子上后，

15、世界末日就要到了”。這就是著名的梵天塔問題。,(3) 梵天塔問題,將64個(gè)直徑大小不一的金盤子，按照從大到小的順序依次套放在第一根柱子上，形成一座金塔，天神讓廟里的僧侶們將第一根柱子上的64個(gè)盤子借助第二根柱子全部移到第三根柱子上，既將整個(gè)塔遷移，同時(shí)定下3條規(guī)則： 每次只能移動(dòng)一個(gè)盤子； 盤子只能在三根柱子上來回移動(dòng)，不能放在他處； 在移動(dòng)過程中，三根柱子上的盤子必須始終保持大盤在下，小盤在上。,算法：C語言描述,hanoi(int n,char left,char middle,char right) if(n=1) move(1,one,_,three); else hanoi(n-1,

16、left,right,middle); move(1,left,_,right); hanoi(n-1,middle,left,right); ,當(dāng)n=64時(shí)，移動(dòng)次數(shù)=？花費(fèi)時(shí)間=？,h(n)=2h(n-1)+1 = 2(2h(n-2)+1)+1=22h(n-2)+2+1 = 23h(n-3)+22+2+1 =2nh(0)+2n-1+22+2+1 = 2n-1+22+2+1=2n-1 需要移動(dòng)盤子的次數(shù)為： 264-1=18446744073709551615,假定每秒移動(dòng)一次，一年有31536000秒，則僧侶們一刻不停地來回搬動(dòng)，也需要花費(fèi)大約5849億年的時(shí)間。 假定計(jì)算機(jī)以每秒1000

17、萬個(gè)盤子的速度進(jìn)行搬遷，則需要花費(fèi)大約58490年的時(shí)間。 理論上可以計(jì)算的問題，實(shí)際上并不一定能行，這屬于算法復(fù)雜性方面的研究內(nèi)容。,算法復(fù)雜性中的難解性問題、P類問題和NP類問題,空間復(fù)雜性問題 關(guān)于梵天塔問題算法的時(shí)間復(fù)雜度， 用O(2n)來表示 當(dāng)算法的時(shí)間復(fù)雜度的表示函數(shù)是一個(gè)多項(xiàng)式，如O(n2)時(shí)，則可以處理。 一個(gè)問題求解算法的時(shí)間復(fù)雜度大于多項(xiàng)式（如指數(shù)函數(shù)）時(shí)，算法的執(zhí)行時(shí)間將隨n的增加而急劇增長， 以致即使是中等規(guī)模的問題也不能求解出來，于是在計(jì)算復(fù)雜性中，將這一類問題稱為難解性問題。,時(shí)間復(fù)雜性問題 人工智能領(lǐng)域中的狀態(tài)圖搜索問題（解空間的表示或狀態(tài)空間搜索問題）就是一類

18、典型的難解性問題。 在計(jì)算復(fù)雜性理論中，將所有可以在多項(xiàng)式時(shí)間內(nèi)求解的問題稱為P類問題，而將所有在多項(xiàng)式時(shí)間內(nèi)可以驗(yàn)證的問題稱為NP類問題。由于P類問題采用的是確定性算法，NP類問題采用的是非確定性算法，而確定性算法是非確定性算法的一種特例，因此，可以斷定PNP。,(4) 證比求易算法,艾述國王向鄰國秋碧貞楠公主求婚。公主出了一道題： 求出48 770 428 433 377 171的一個(gè)真因子。若國王能在一天之內(nèi)求出答案，公主便接受他的求婚。 國王回去后立即開始逐個(gè)數(shù)地進(jìn)行計(jì)算，他從早到晚，共算了三萬多個(gè)數(shù)，最終還是沒有結(jié)果。國王向公主求情，公主將答案相告：223 092 827是它的一個(gè)真

19、因子。國王很快就驗(yàn)證了這個(gè)數(shù)確能除盡48 770 428 433 377 171。,公主說：“我再給你一次機(jī)會(huì)” 國王立即回國，并向時(shí)任宰相的大數(shù)學(xué)家孔喚石求教，大數(shù)學(xué)家在仔細(xì)地思考后認(rèn)為這個(gè)數(shù)為17位，則最小的一個(gè)真因子不會(huì)超過9位， 他給國王出了一個(gè)主意：按自然數(shù)的順序給全國的老百姓每人編一個(gè)號發(fā)下去，等公主給出數(shù)目后，立即將它們通報(bào)全國，讓每個(gè)老百姓用自己的編號去除這個(gè)數(shù)，除盡了立即上報(bào)，賞金萬兩。,順序算法和并行算法,國王最先使用的是一種順序算法，其復(fù)雜性表現(xiàn)在時(shí)間方面， 后面由宰相提出的是一種并行算法，其復(fù)雜性表現(xiàn)在空間方面。 直覺上，我們認(rèn)為順序算法解決不了的問題完全可以用并行算法

20、來解決，甚至?xí)耄⑿杏?jì)算機(jī)系統(tǒng)求解問題的速度將隨著處理器數(shù)目的不斷增加而不斷提高，從而解決難解性問題，其實(shí)這是一種誤解。 當(dāng)將一個(gè)問題分解到多個(gè)處理器上解決時(shí)，由于算法中不可避免地存在必須串行執(zhí)行的操作，從而大大地限制了并行計(jì)算機(jī)系統(tǒng)的加速能力。,P？NP,P類問題存在多項(xiàng)式時(shí)間的算法的一類問題； NP類問題非多項(xiàng)式時(shí)間算法解的一類問題。像梵塔問題、推銷員旅行問題、（命題表達(dá)式）可滿足問題這類，至今沒有找到多項(xiàng)式時(shí)間算法解的一類問題。 PNP？如果P=NP，則所有在多項(xiàng)式時(shí)間內(nèi)可驗(yàn)證的問題都將是在多項(xiàng)式時(shí)間內(nèi)可求解（或可判定）的問題。 要證明PNP，目前還無法做到這一點(diǎn) 。,在P?NP問題上

21、，庫克（S.A.Cook）等人認(rèn)為NP類中的某些問題的復(fù)雜性與整個(gè)類的復(fù)雜性有關(guān)，當(dāng)這些問題中的任何一個(gè)存在多項(xiàng)式時(shí)間算法時(shí)，則所有這些NP問題都是多項(xiàng)式時(shí)間可解的，這些問題被稱為NP完全性問題。 多達(dá)數(shù)千個(gè)的NP完全性問題。有代表性的有：哈密爾頓回路問題、旅行商問題（也稱貨郎擔(dān)問題）、劃分問題、帶優(yōu)先級次序的處理機(jī)調(diào)度問題、頂點(diǎn)覆蓋問題等。,旅行商問題與組合爆炸問題,旅行商問題與組合爆炸問題,(5) 旅行商問題與組合爆炸問題,如果有3個(gè)城市A，B和C，互相之間都有往返的飛機(jī)，而且起始城市是任意的，則有6種訪問每個(gè)城市的次序：ABC,ACB,BAC,BCA,CAB,CBA。如果有4個(gè)城市，則有

22、24種次序，可以用階乘來表示：4！=43！=4321=24； 若有5個(gè)城市，則有5！=54！=120，類似的有6！=720等等。即使用計(jì)算機(jī)來計(jì)算，這種急劇增長的可能性的數(shù)目也遠(yuǎn)遠(yuǎn)超過計(jì)算資源的處理能力， Cook評論：“如果有100個(gè)城市，需要求出100！條路線的費(fèi)用，沒有哪一臺(tái)計(jì)算機(jī)能夠勝任這一任務(wù)。打個(gè)比方，讓太陽系中所有的電子以它旋轉(zhuǎn)的頻率來計(jì)算，就算太陽燒盡了也算不完。 問題的關(guān)鍵是某些東西在實(shí)踐中行不通。,1998年，科學(xué)家們成功地解決了美國13509個(gè)城市之間的TSP問題， 2001年又解決了德國15112個(gè)城市之間的TSP問題。但這一工程代價(jià)也是巨大的 解決15112個(gè)城市之間

23、的TSP問題，共使用了美國Rice大學(xué)和普林斯頓大學(xué)之間網(wǎng)絡(luò)互連的、由速度為500MHz 的Compaq EV6 Alpha 處理器組成的110臺(tái)計(jì)算機(jī)，所有計(jì)算機(jī)花費(fèi)的時(shí)間之和為22.6年。,TSP的應(yīng)用,一個(gè)典型的例子就是機(jī)器在電路板上鉆孔的調(diào)度問題（注：在該問題中，鉆孔的時(shí)間是固定的，只有機(jī)器移動(dòng)時(shí)間的總量是可變的），在這里，電路板上要鉆的孔相當(dāng)于TSP中的“城市”，鉆頭從一個(gè)孔移到另一個(gè)孔所耗的時(shí)間相當(dāng)于TSP中的“旅行費(fèi)用”。 運(yùn)輸業(yè)、 后勤服務(wù)業(yè)等 然而，由于TSP會(huì)產(chǎn)生組合爆炸的問題，因此尋找切實(shí)可行的簡化求解方法就成為問題的關(guān)鍵。,生產(chǎn)者消費(fèi)者問題,一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者以及一

24、個(gè)硬件資源。 所謂消費(fèi)者是指使用某一軟硬件資源時(shí)的進(jìn)程，而生產(chǎn)者是指提供（或釋放）某一軟硬件資源時(shí)的進(jìn)程。 一個(gè)重要的概念，即信號燈，它借用了火車信號系統(tǒng)中的信號燈來表示進(jìn)程之間的互斥。,“哲學(xué)家共餐”問題,5個(gè)哲學(xué)家圍坐在一張圓桌旁，每個(gè)人的面前擺有一碗面條，碗的兩旁各擺有一只筷子 一個(gè)哲學(xué)家的生活進(jìn)程可表示為： （1）思考問題； （2）餓了停止思考，左手拿一只筷子（拿不到就等）； （3）右手拿一只筷子（拿不到就等） ； （4）進(jìn)餐；（5）放右手筷子； （6）放左手筷子； （7）重新回到思考問題狀態(tài)（1）。 問題是：如何協(xié)調(diào)5個(gè)哲學(xué)家的生活進(jìn)程， 使得每一個(gè)哲學(xué)家最終都可以進(jìn)餐。,按哲學(xué)家的

25、活動(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é)家一樣都吃不到飯。,程序并發(fā)執(zhí)行時(shí)進(jìn)程同步有關(guān)的經(jīng)典問題還有：讀寫者問題（ReaderWriter Problem）、理發(fā)師睡眠問題（Sleeping Barber Problem）等。,GO

26、TO語句的問題以及程序設(shè)計(jì)方法學(xué),1966年，C.Bhm和G.Jacopini發(fā)表了關(guān)于“程序結(jié)構(gòu)”的重要論文帶有兩種形成規(guī)則的圖靈機(jī)和語言的流程圖（Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules），給出了任何程序的邏輯結(jié)構(gòu)都可以用3種最基本的結(jié)構(gòu)，即順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)來表示的證明。,GOTO語句,1974年，著名計(jì)算機(jī)科學(xué)家、圖靈獎(jiǎng)獲得者克努特（D.E.Knuth）教授在他發(fā)表的有影響力的論文帶有GOTO語句的結(jié)構(gòu)化程序設(shè)計(jì)（Structured Programming with

27、Goto Statements）中對這場爭論作了較為全面而公正的論述： 濫用GOTO語句是有害的，完全禁止也不明智， 在不破壞程序良好結(jié)構(gòu)的前提下，有控制地使用一些GOTO語句，就有可能使程序更清晰，效率也更高， 關(guān)于“GOTO語句”的爭論，其焦點(diǎn)應(yīng)當(dāng)放在程序的結(jié)構(gòu)上，好的程序應(yīng)該邏輯正確、結(jié)構(gòu)清晰、樸實(shí)無華。,關(guān)于“GOTO語句”問題的爭論直接導(dǎo)致了一個(gè)新的學(xué)科分支領(lǐng)域，即程序設(shè)計(jì)方法學(xué)的產(chǎn)生。程序設(shè)計(jì)方法學(xué)是對程序的性質(zhì)及其設(shè)計(jì)的理論和方法進(jìn)行研究的學(xué)科，它是計(jì)算學(xué)科發(fā)展的必然產(chǎn)物，也是計(jì)算機(jī)科學(xué)與技術(shù)方法論中的重要內(nèi)容。,CH02 計(jì)算學(xué)科中的科學(xué)問題,人工智能中的若干哲學(xué)問題,圖靈測試

28、,1950年在英國 Mind雜志上發(fā)表了 Computing Machinery and Intelligence 比賽規(guī)則是 讓一臺(tái)計(jì)算機(jī)與人進(jìn)行各種話題的文本式聊天，這名參加聊天的人將不知道自己聊天的對象是另外一個(gè)人還是一臺(tái)計(jì)算機(jī)。 如果這臺(tái)計(jì)算機(jī)“足夠聰明”，也即它上面運(yùn)行的程序“足夠智能”，能夠讓與它聊天的對象相信它是一個(gè)“人”那么它就 “會(huì)思考”圖靈本人更愿意將計(jì)算機(jī)的這種能力稱之為“會(huì)摹仿”。 圖靈的天才預(yù)言終于在IBM的“深藍(lán)”上得到徹底實(shí)現(xiàn)。,圖靈測試,不要求接受測試的思維機(jī)器在內(nèi)部構(gòu)造上與人腦一樣， 只是從功能的角度來判定機(jī)器是否能思維，也就是從行為主義這個(gè)角度來對“機(jī)器思維

29、”進(jìn)行定義。 盡管圖靈對“機(jī)器思維”的定義是不夠嚴(yán)謹(jǐn)?shù)?，但他關(guān)于“機(jī)器思維”定義的開創(chuàng)性工作對后人的研究具有重要意義， 一些學(xué)者認(rèn)為，圖靈發(fā)表的關(guān)于“圖靈測試”的論文標(biāo)志著現(xiàn)代機(jī)器思維問題討論的開始。,羅布諾獎(jiǎng),一年一度的“羅布諾獎(jiǎng)”計(jì)算機(jī)與人聊天賽于當(dāng)?shù)貢r(shí)間9月19日上午10時(shí)在美國紐約舉行 “羅布諾獎(jiǎng)”發(fā)起人休羅布諾挑選了4臺(tái)計(jì)算機(jī)參加決賽。 這4臺(tái)擁有智能程序的計(jì)算機(jī)將和一個(gè)“陪考人”呆在一個(gè)房間里，至少一名“主考官”將從隔壁房間內(nèi)通過電腦打字與4臺(tái)計(jì)算機(jī)和“陪考人”自由聊天他不知道與自己聊天的對象到底是人還是機(jī)器， 如果有臺(tái)計(jì)算機(jī)能在聊天中讓“主考官”相信它是“人”，那么這臺(tái)計(jì)算機(jī)和發(fā)

30、明它的主人將奪得10萬美元的大獎(jiǎng)。,符號主義者認(rèn)為認(rèn)知是一種符號處理過程，人類思維過程也可用某種符號來描述，即思維就是計(jì)算（認(rèn)知就是計(jì)算），這種思想構(gòu)成了人工智能的哲學(xué)基礎(chǔ)之一。其實(shí)，歷史上把推理作為人類精神活動(dòng)的中心，把一切推理都?xì)w結(jié)于某種計(jì)算的想法一直吸引著西方的思想家。然而，由于人們對心理學(xué)和生物學(xué)的認(rèn)識還很不成熟，對人腦的結(jié)構(gòu)還沒有真正的了解，更無法建立起人腦思維完整的數(shù)學(xué)模型。因此，到目前為止，人們對人工智能的研究并無實(shí)質(zhì)性的突破。 在未來，如果我們能像圖靈揭示計(jì)算本質(zhì)那樣揭示人類思維的本質(zhì)，即“能行”思維，那么制造真正思維機(jī)器的日子也就不長了。可惜要對人類思維的本質(zhì)進(jìn)行描述，還是相

31、當(dāng)遙遠(yuǎn)的事情。,西爾勒的“中文屋子”,美國哲學(xué)家約翰西爾勒（J.R.Searle）將有關(guān)人工智能的研究劃分為強(qiáng)人工智能（Strong Artificial Intelligence，簡稱強(qiáng)AI）和弱人工智能（Soft Artificial Intelligence，簡稱弱AI）兩個(gè)派別。 弱AI認(rèn)為：計(jì)算機(jī)的主要價(jià)值在于它為我們提供了一個(gè)強(qiáng)大的工具； 強(qiáng)AI的觀點(diǎn)則是：計(jì)算機(jī)不僅是一個(gè)工具，形式化的計(jì)算機(jī)是具有意識的。 1980年，西爾勒在Behavioral and Brain Sciences雜志上發(fā)表了 Minds、Brains and Programs的論文，在文中，他以自己為主角設(shè)計(jì)

32、了一個(gè)“中文屋子（Chinese Room）”的假想試驗(yàn)來反駁強(qiáng)AI的觀點(diǎn)：,電腦博弈傳奇,1997年5月11日，人機(jī)世紀(jì)大戰(zhàn)終于降下了帷幕，隨著國際象棋世界冠軍卡斯帕羅夫敗給了IBM公司的一臺(tái)機(jī)器 “深藍(lán)” ,全世界都永遠(yuǎn)不會(huì)忘記那震驚世界的9天的“搏殺”。 卡斯帕羅夫在1988年曾：2000年前電腦絕不會(huì)戰(zhàn)勝特級象棋大師，雖然卡斯帕羅夫也承認(rèn)，電腦有可能擊敗一般的特級大師，但是他斬釘截鐵地強(qiáng)調(diào)指出：“不包括卡爾波夫和我！”,卡斯帕羅夫,1963.4.13:阿塞拜疆的首都巴庫。 1980年他獲得世界少年組冠軍， 1981年他并列奪得蘇聯(lián)冠軍，隨后他又在一系列的國際大賽里頻頻奪冠。 1984年

33、他一路過關(guān)斬將贏得向當(dāng)時(shí)的世界冠軍卡爾波夫挑戰(zhàn)的資格。 1985年22歲的卡斯帕羅夫成為歷史上最年輕的國際象棋冠軍。 從那以后連續(xù)三次擊敗俄羅斯的卡爾波夫，分別各一次擊敗英國的肖特和印度的阿南德，捍衛(wèi)了自己的冠軍頭銜。,棋盤一側(cè)是卡斯帕羅夫，棋盤的另一側(cè)是許峰雄博士 許峰雄將通過另一臺(tái)帶有液晶顯示屏的黑色電腦，負(fù)責(zé)操縱“深藍(lán)”迎戰(zhàn)人類世界冠軍。,5月3日到5月11日， “深藍(lán)”終以3.5比2.5的總比分將卡斯帕羅夫逼下了世界冠軍的王座。 當(dāng)卡斯帕羅夫的棋局處于不利的時(shí)候，他仍然習(xí)慣地睜大雙眼瞪著許峰雄，似乎認(rèn)為這個(gè)人才是自己的對手，必須用目光給對方造成心理上的壓力。,許峰雄,許峰雄設(shè)計(jì)的第一臺(tái)

34、能下棋的電腦叫“蕊驗(yàn)”。 1987年，他設(shè)計(jì)的電腦在與其它電腦的角逐中獲得冠軍， 1988年，他把“蕊驗(yàn)”電腦升級為“深思”，首次戰(zhàn)勝了國際象棋特級大師本特拉爾森，贏得電腦界同行一片喝彩聲。 1989年，許峰雄和他的兩名助手帶著有250多個(gè)芯片，每秒能計(jì)算750萬步棋的“深思”電腦，來到IBM公司設(shè)在紐約的電腦研究中心,Deep blue,1995年，“學(xué)名”為“IBM AS/6000 SP大規(guī)模多用途并行處理機(jī)”正式誕生，計(jì)算速度達(dá)到了每秒鐘1億棋步。 最大特點(diǎn)是32個(gè)處理器采用“并行處理”的方式解決復(fù)雜問題。,1996年2月，在美國費(fèi)城，許峰雄指揮“深藍(lán)”與卡斯帕羅夫再次交鋒。 卡斯帕洛夫

35、到底不愧為“有史以來最偉大的棋手”，他穩(wěn)扎穩(wěn)打，以3勝2平1負(fù)的戰(zhàn)績再次戰(zhàn)勝了電腦。 雙方作戰(zhàn)的過程十分艱難，許峰雄從“深藍(lán)”的進(jìn)步中看到了曙光。 在以后的一年里，許峰雄和另外四位電腦科學(xué)家決心給電腦輸入了近兩百萬局國際象棋程序，再次提高了它的運(yùn)算速度，使它每秒能分析2億步棋。由國際象棋特級大師本杰明為它當(dāng)“陪練”，找出某些棋局的弱點(diǎn)，然后再修改程序。,阿蘭圖林的“紙上下棋機(jī)”,人問： 你下國際象棋嗎？ 機(jī)答： 是。 人問： 我在我的K1處有棋子K；你僅在K6處有棋子K，在R1處有棋子R?，F(xiàn)在輪到你走，你應(yīng)該下那步棋？ 機(jī)答： （在15秒鐘后）棋子R走到R8處，將軍！ 1953年，圖林一篇論文

36、數(shù)字計(jì)算機(jī)用于競賽：象棋中， 初步論述如何編制計(jì)算機(jī)下棋程序，并詳細(xì)講解了機(jī)器同一名中等水平棋手實(shí)際對局的走法。然而，那時(shí)的電腦還不足以用來支持圖林的理論，于是，“愚笨”的圖林竟然想到去發(fā)明“一臺(tái)”紙上下棋機(jī)，以驗(yàn)證自己的設(shè)想。,“紙機(jī)器”實(shí)際是一種程序算法,每一步棋都用人工手算后決定實(shí)際著法。 把“兵”向前移動(dòng)一步后，圖林就按事先擬定的算法費(fèi)力地在紙上計(jì)算大約半小時(shí)，然后才決定是走他的“馬”還是走“車”來對付你的“兵”。 有資料記載說，1952年，圖林用“紙機(jī)器”與一位名叫格倫尼的大學(xué)生對弈，開局走得相當(dāng)精彩，直到第29步時(shí)，“紙機(jī)器”算出格倫尼似乎沒有什么殺著，貪婪地用“后”吃掉了對方的“

37、兵”，結(jié)果使自己的門戶大開，被格倫尼一著將死。,學(xué)科誕生,他需要計(jì)算雙方的兵力優(yōu)勢，為不同種類的棋子賦予一定的分值，例如，“兵”1、“馬”3、“士”3.5、“車”5、“后”10，“王”則具有最高分，例如1000，因?yàn)樗^對不能被吃掉。 他需要計(jì)算雙方的棋局優(yōu)勢，在哪些地方布防哪類棋子具有更大的威懾力。 把兵力優(yōu)勢和棋局優(yōu)勢用加權(quán)求和的數(shù)學(xué)式聯(lián)系起來，構(gòu)成某種形式的“估值函數(shù)”。 用“估值函數(shù)”來計(jì)算每一可能的合法棋步，尋找函數(shù)值最大即對自己最有利的那一步著法，,Shannon,1950年，美國貝爾實(shí)驗(yàn)室Shannon的論文國際象棋與機(jī)器。 要想全部得到一方“馬”的所有可能動(dòng)作以及對方“馬”的動(dòng)作，人工計(jì)算決定開局棋步需要的年數(shù)是10的95次方，如果用機(jī)器運(yùn)算，僅需要人工時(shí)間的百分之一。 1956年， Shannon與麥卡錫、明斯基、