計算學(xué)科中.ppt

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

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

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

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

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

6、,希爾伯特綱領(lǐng),希爾伯特（D.Hilbert）在數(shù)學(xué)基礎(chǔ)的研究中提出了一個設(shè)想 將每一門數(shù)學(xué)的分支形式化，構(gòu)成形式系統(tǒng)或形式理論，并在以此為對象的元理論即元數(shù)學(xué)中，證明每一個形式系統(tǒng)的相容性，從而導(dǎo)出全部數(shù)學(xué)的相容性。 目標(biāo)是要尋找通用的形式邏輯系統(tǒng)，該系統(tǒng)應(yīng)當(dāng)是完備的，即在該系統(tǒng)中，可以機械地判定任何給定命題的真?zhèn)巍?庫爾特哥德爾（KGodel）,認為數(shù)學(xué)原理所定義的系統(tǒng)既是一致的，也是完備的 任何系統(tǒng)的完備和一致性，可以由系統(tǒng)本身得到證明。 1931年，“希爾伯特綱領(lǐng)”被奧地利邏輯學(xué)家Godel搠出一個大窟窿 Godel認為沒有一種公理系統(tǒng)可以導(dǎo)出數(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)機 希爾伯特綱領(lǐng)的提出使元數(shù)學(xué)得到了確立和發(fā)展 希爾伯特綱領(lǐng)的失敗啟發(fā)人們應(yīng)避免花費大量的精力去證明那些不能判定的問題，而應(yīng)把精力集中

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

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

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

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

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

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

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

15、世界末日就要到了”。這就是著名的梵天塔問題。,(3) 梵天塔問題,將64個直徑大小不一的金盤子，按照從大到小的順序依次套放在第一根柱子上，形成一座金塔，天神讓廟里的僧侶們將第一根柱子上的64個盤子借助第二根柱子全部移到第三根柱子上，既將整個塔遷移，同時定下3條規(guī)則： 每次只能移動一個盤子； 盤子只能在三根柱子上來回移動，不能放在他處； 在移動過程中，三根柱子上的盤子必須始終保持大盤在下，小盤在上。,算法：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ù)=？花費時間=？,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 需要移動盤子的次數(shù)為： 264-1=18446744073709551615,假定每秒移動一次，一年有31536000秒，則僧侶們一刻不停地來回搬動，也需要花費大約5849億年的時間。 假定計算機以每秒1000

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

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

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

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

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

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

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

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

25、活動進程，當(dāng)所有的哲學(xué)家都同時拿起左手筷子時，則所有的哲學(xué)家都將拿不到右手的筷子，并處于等待狀態(tài)，那么哲學(xué)家都將無法進餐，最終餓死。 將哲學(xué)家的活動進程修改一下，變?yōu)楫?dāng)右手的筷子拿不到時，就放下左手的筷子，這種情況是不是就沒有問題？不一定，因為可能在一個瞬間，所有的哲學(xué)家都同時拿起左手的筷子，則自然拿不到右手的筷子，于是都同時放下左手的筷子，等一會，又同時拿起左手的筷子，如此這樣永遠重復(fù)下去，則所有的哲學(xué)家一樣都吃不到飯。,程序并發(fā)執(zhí)行時進程同步有關(guān)的經(jīng)典問題還有：讀寫者問題（ReaderWriter Problem）、理發(fā)師睡眠問題（Sleeping Barber Problem）等。,GO

26、TO語句的問題以及程序設(shè)計方法學(xué),1966年，C.Bhm和G.Jacopini發(fā)表了關(guān)于“程序結(jié)構(gòu)”的重要論文帶有兩種形成規(guī)則的圖靈機和語言的流程圖（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年，著名計算機科學(xué)家、圖靈獎獲得者克努特（D.E.Knuth）教授在他發(fā)表的有影響力的論文帶有GOTO語句的結(jié)構(gòu)化程序設(shè)計（Structured Programming with

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

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

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

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

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

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

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

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

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

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

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