1、第第2章章 計算學科的基本問題計算學科的基本問題內(nèi)容提要內(nèi)容提要n 對問題進行抽象的一個實例對問題進行抽象的一個實例n 可計算問題與不可計算問題可計算問題與不可計算問題n 計算學科中的其他典型科學問題計算學科中的其他典型科學問題n 計算學科的主領(lǐng)域及其基本問題計算學科的主領(lǐng)域及其基本問題1、對問題進行抽象的一個實例、對問題進行抽象的一個實例哥尼斯堡七橋問題哥尼斯堡七橋問題 17世紀在哥尼斯堡城世紀在哥尼斯堡城 ( 今俄羅斯今俄羅斯加里寧格勒加里寧格勒 ) 的普萊格爾河上有的普萊格爾河上有 7 座座橋，將河中的兩個島和河岸連結(jié)，城橋，將河中的兩個島和河岸連結(jié)，城中的居民經(jīng)常沿河過橋散步，于是提中

2、的居民經(jīng)常沿河過橋散步，于是提出了一個問題：能否一次走遍出了一個問題：能否一次走遍 7 座橋，座橋，而每座橋只許通過一次，最后仍回到而每座橋只許通過一次，最后仍回到起始地點。這就是七橋問題，一個著起始地點。這就是七橋問題，一個著名的圖論問題。名的圖論問題。 七橋問題也困繞著哥尼斯堡大學的學生們，七橋問題也困繞著哥尼斯堡大學的學生們，在屢遭失敗之后，他們請當時在屢遭失敗之后，他們請當時28歲的著名數(shù)學歲的著名數(shù)學家家歐拉歐拉解決這個問題。解決這個問題。 哥尼斯堡七橋問題哥尼斯堡七橋問題 歐拉圖歐拉圖對現(xiàn)實問題的抽象對現(xiàn)實問題的抽象 歐拉解決問題采用了歐拉解決問題采用了“數(shù)學模型數(shù)學模型”法。法。

3、歐拉認為，既然島與陸地是靠橋來接連的，歐拉認為，既然島與陸地是靠橋來接連的，那么不妨把那么不妨把4片陸地縮?。ǔ橄螅┏善懙乜s?。ǔ橄螅┏?個點，個點，并把七座橋表示（抽象）成并把七座橋表示（抽象）成7條邊，從而得條邊，從而得到了七橋問題的模擬圖，這樣當然未改變到了七橋問題的模擬圖，這樣當然未改變問題的實質(zhì)，于是人們試圖一次無重復地問題的實質(zhì)，于是人們試圖一次無重復地走過走過7座橋的問題就等價于一筆畫出模擬圖座橋的問題就等價于一筆畫出模擬圖型的問題。型的問題。歐拉經(jīng)過三種抽象：歐拉經(jīng)過三種抽象：o 具體事物抽象成幾何對象具體事物抽象成幾何對象o 實際關(guān)系抽象成幾何關(guān)系實際關(guān)系抽象成幾何關(guān)系o

4、問題的要求抽象成一筆畫的條件問題的要求抽象成一筆畫的條件 是否存在是否存在 “歐拉歐拉 回路回路” 通過這種抽象，顯現(xiàn)出問題的本質(zhì)，將實際問題轉(zhuǎn)化通過這種抽象，顯現(xiàn)出問題的本質(zhì)，將實際問題轉(zhuǎn)化成數(shù)學問題，使研究的對象和對象間的關(guān)系準確無誤地表成數(shù)學問題，使研究的對象和對象間的關(guān)系準確無誤地表述出來，就可以先在已有的數(shù)學方法、理論中尋求解法。述出來，就可以先在已有的數(shù)學方法、理論中尋求解法。在現(xiàn)有方法、理論中還未有解法時，就促使人們?nèi)ふ倚略诂F(xiàn)有方法、理論中還未有解法時，就促使人們?nèi)ふ倚碌臄?shù)學方法和理論，甚至開拓出數(shù)學新的分支和領(lǐng)域。的數(shù)學方法和理論，甚至開拓出數(shù)學新的分支和領(lǐng)域。 歐拉對歐拉

5、對“七橋問題七橋問題”的研究是圖論研究的開始，同時的研究是圖論研究的開始，同時也為拓撲學的研究提供了一個初等的例子。也為拓撲學的研究提供了一個初等的例子。哈密爾頓回路問題哈密爾頓回路問題 哈密爾頓圖起源于一種游戲，英國數(shù)學家哈哈密爾頓圖起源于一種游戲，英國數(shù)學家哈密爾頓于密爾頓于1859年提出的年提出的“周游世界游戲周游世界游戲”。用一。用一個正十二面體的個正十二面體的20個頂點代替?zhèn)€頂點代替20個城市個城市(圖圖1，同，同構(gòu)于一個平面圖，圖構(gòu)于一個平面圖，圖2)，要求沿著正十二面體的，要求沿著正十二面體的棱從一個城市出發(fā)，經(jīng)過每個城市恰好一次，然棱從一個城市出發(fā)，經(jīng)過每個城市恰好一次，然后回

6、到出發(fā)點，稱為后回到出發(fā)點，稱為哈密爾頓回路哈密爾頓回路。 抽象：抽象：在任一給定的圖中，在任一給定的圖中，能不能找到這樣的路徑，即從一能不能找到這樣的路徑，即從一點出發(fā)不重復地走過所有的結(jié)點點出發(fā)不重復地走過所有的結(jié)點（不必通過圖中每一條邊），最（不必通過圖中每一條邊），最后又回到原出發(fā)點。后又回到原出發(fā)點。哈密爾頓回路問題哈密爾頓回路問題 該問題進一步被發(fā)展成為所謂的該問題進一步被發(fā)展成為所謂的“貨郎擔問題貨郎擔問題”或或“旅行貨郎問題旅行貨郎問題”TSP，即，即賦權(quán)漢密爾頓回路最小賦權(quán)漢密爾頓回路最小化問題化問題。這兩個問題成為數(shù)學史上著名的難題，而后者。這兩個問題成為數(shù)學史上著名的難題

7、，而后者在工程優(yōu)化、現(xiàn)場管理等現(xiàn)實生活中有重要作用。以電在工程優(yōu)化、現(xiàn)場管理等現(xiàn)實生活中有重要作用。以電站建設(shè)為例，如何使若干供貨點的總運費最小，施工現(xiàn)站建設(shè)為例，如何使若干供貨點的總運費最小，施工現(xiàn)場如何使供貨時間最短等等，最終都歸結(jié)為賦權(quán)漢密爾場如何使供貨時間最短等等，最終都歸結(jié)為賦權(quán)漢密爾頓問題。頓問題。哈密爾頓回路問題與歐拉回路問題哈密爾頓回路問題與歐拉回路問題o “哈密爾頓回路問題哈密爾頓回路問題”與與“歐拉回路問題歐拉回路問題”十分相似，十分相似，但卻是完全不同的兩個問題。但卻是完全不同的兩個問題?！肮軤栴D回路問題哈密爾頓回路問題”是是訪問除原出發(fā)結(jié)點以外的訪問除原出發(fā)結(jié)點以外的

8、每個結(jié)點每個結(jié)點一次且僅一次，而一次且僅一次，而“歐拉回路問題歐拉回路問題”是訪問是訪問每條邊每條邊一次且僅一次。一次且僅一次。o 對任一給定的圖是否存在對任一給定的圖是否存在“歐拉回路歐拉回路”，歐拉已給出了，歐拉已給出了充分必要條件充分必要條件(P23)；而對任一給定的圖是否存在；而對任一給定的圖是否存在“哈密哈密爾頓回路爾頓回路”，至今仍未找到滿足該問題的充分必要條件。，至今仍未找到滿足該問題的充分必要條件。2、可計算問題與不可計算問題、可計算問題與不可計算問題梵天塔（又稱漢諾塔）問題梵天塔（又稱漢諾塔）問題 在印度有這么一個古老的傳說：印度教的天神梵天在創(chuàng)造地球在印度有這么一個古老的傳

9、說：印度教的天神梵天在創(chuàng)造地球時建了一座神廟，神廟里豎有時建了一座神廟，神廟里豎有3根寶石柱子。梵天將根寶石柱子。梵天將64個直徑大小個直徑大小不一的金盤子，按照從大到小的順序依次套放在第一根柱子上，形不一的金盤子，按照從大到小的順序依次套放在第一根柱子上，形成一座金塔，即所謂梵天塔。天神讓廟里的僧侶們將第一根柱子上成一座金塔，即所謂梵天塔。天神讓廟里的僧侶們將第一根柱子上的的64個盤子借助第個盤子借助第2根柱子全部移到第根柱子全部移到第3根柱子上，將整個塔遷移。根柱子上，將整個塔遷移。遷移時滿足以下遷移時滿足以下3條規(guī)則：條規(guī)則： 每次只能移動一個盤子；每次只能移動一個盤子； 盤子只能在三根

10、柱子上來回移動，不能放在他處；盤子只能在三根柱子上來回移動，不能放在他處； 在移動過和中，三根柱子上的盤子必須始終保持大盤在下，在移動過和中，三根柱子上的盤子必須始終保持大盤在下，小盤在上。小盤在上。 天神說：天神說：“當這當這64個盤子全部移到第三根柱子上后，世界末日個盤子全部移到第三根柱子上后，世界末日就要到了就要到了”。 ？算法：算法：C語言描述語言描述hanoi(int n, char left, char middle, char right) if(n=1) move(1, left, right); else hanoi(n-1, left, right, middle); mo

11、ve(1, left, right); hanoi(n-1, middle, left, right); 當當n=64時，移動次數(shù)時，移動次數(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ù)為：需要移動盤子的次數(shù)為： 264-1=18446744073709551615o假定假定每秒移動一次每秒移動一次，一年有，一年有31536000秒，則僧侶們秒，則僧侶們 一刻不停地來回搬動，也需要花費大約一刻

12、不停地來回搬動，也需要花費大約5849億年億年的時間。的時間。o假定計算機以假定計算機以每秒每秒1000萬萬個盤子的速度進行搬遷，則需要花費個盤子的速度進行搬遷，則需要花費大約大約58490年年的時間。的時間。o梵天塔問題算法的時間復雜度可以用一個指數(shù)函數(shù)梵天塔問題算法的時間復雜度可以用一個指數(shù)函數(shù)O(2n)來表示，來表示，顯然，當顯然，當n很大時，計算機是無法處理的。當算法的時間復雜很大時，計算機是無法處理的。當算法的時間復雜度的表示函數(shù)是一個多項式，則可以處理。度的表示函數(shù)是一個多項式，則可以處理。o一個問題求解算法的時間復雜度大于多項式（如指數(shù)函數(shù)）時，一個問題求解算法的時間復雜度大于多

13、項式（如指數(shù)函數(shù)）時，算法的執(zhí)行時間將隨算法的執(zhí)行時間將隨n的增加而急劇增長，以致即使是中等規(guī)的增加而急劇增長，以致即使是中等規(guī)模的問題也不能求解出來，在計算復雜性中將這一類問題稱為模的問題也不能求解出來，在計算復雜性中將這一類問題稱為難解性問題。難解性問題。o理論上可以計算的問題，實際上并不一定能行。理論上可以計算的問題，實際上并不一定能行。梵天塔問題梵天塔問題o 算法復雜性的數(shù)量級算法復雜性的數(shù)量級(Order)n O(1) 稱為常數(shù)級稱為常數(shù)級n O(logn) 稱為對數(shù)級稱為對數(shù)級n O(n) 稱為線性級稱為線性級n O(nc) 稱為多項式級（稱為多項式級（c為常數(shù)為常數(shù))，如，如O(

14、n2)n O(cn)稱為指數(shù)級（稱為指數(shù)級（c為常數(shù)為常數(shù))，如，如O(2n)n O(n!) 稱為階乘級稱為階乘級當時間復雜性當時間復雜性多項式時，算法的執(zhí)行時間隨多項式時，算法的執(zhí)行時間隨n增加而急劇增長。增加而急劇增長。o 可計算問題：存在算法可解的問題可計算問題：存在算法可解的問題o 不可計算的問題：不存在可解算法的問題不可計算的問題：不存在可解算法的問題 一個不可計算的問題：停機問題一個不可計算的問題：停機問題，P32 這個問題是由圖靈提出的一個不可解問題，即無法這個問題是由圖靈提出的一個不可解問題，即無法在有限的時間內(nèi)得到解的問題。停機問題就是能否設(shè)計在有限的時間內(nèi)得到解的問題。停機

15、問題就是能否設(shè)計一個算法，判斷任意一個程序是否會在有限的時間之內(nèi)一個算法，判斷任意一個程序是否會在有限的時間之內(nèi)結(jié)束運行?；蛘哒f，能否找到這樣結(jié)束運行?；蛘哒f，能否找到這樣一個測試程序，它能購判斷出任意一個測試程序，它能購判斷出任意的程序在接收了輸入并執(zhí)行后能不的程序在接收了輸入并執(zhí)行后能不能自動終止。能自動終止。一個不可計算的問題：停機問題一個不可計算的問題：停機問題證明：證明： 設(shè)停機問題有解，即：存在過程設(shè)停機問題有解，即：存在過程H(P, I)可以給出程序可以給出程序P在輸入在輸入I的情況下是否可停機。假設(shè)若的情況下是否可停機。假設(shè)若P在輸入在輸入I時可停機，時可停機，H輸出輸出“停機

16、停機”，反之輸出反之輸出“死循環(huán)死循環(huán)”，即可導出矛盾：，即可導出矛盾： 顯然，程序本身可以被視作數(shù)據(jù)，因此它可以被作為輸入，故顯然，程序本身可以被視作數(shù)據(jù)，因此它可以被作為輸入，故H應該可以判定當將應該可以判定當將P作為作為P的輸入時，的輸入時，P是否會停機。我們設(shè)過程是否會停機。我們設(shè)過程K(P)的流程如下：首先調(diào)用的流程如下：首先調(diào)用H(P, P)，如果，如果H(P, P)輸出輸出“死循環(huán)死循環(huán)”，則則K(P)停機，反之停機，反之K(P)死循環(huán)。即死循環(huán)。即K(P)做與做與H(P, P)的輸出相反的的輸出相反的動作。動作。 因此，因此，H不是總能給出正確答案，故而不存在解決停機問題的不是

17、總能給出正確答案，故而不存在解決停機問題的方法。方法。o 難解性問題、難解性問題、P類問題和類問題和NP類問題類問題n 難解性問題：當時間復雜性難解性問題：當時間復雜性多項式時多項式時n P類問題：可以在多項式時間內(nèi)類問題：可以在多項式時間內(nèi)求解求解的問題的問題n NP類問題：可以在多項式時間內(nèi)類問題：可以在多項式時間內(nèi)驗證驗證的問題的問題n P類問題采用的是類問題采用的是確定性算法確定性算法，NP類問題采用的類問題采用的是非確定性算法是非確定性算法（如通過猜算）。（如通過猜算）。PNP。o NP完全問題完全問題：NP=P？n 是世界七大數(shù)學難題之一（首位）是世界七大數(shù)學難題之一（首位）o 哈

18、密頓路徑問題：可以在多項式時間類哈密頓路徑問題：可以在多項式時間類判斷判斷一個回一個回路是否是哈密頓回路，但目前沒有多項式時間類算路是否是哈密頓回路，但目前沒有多項式時間類算法直接法直接求解求解出哈密頓回路。出哈密頓回路。3、計算學科中的其他典型科學問題（計算學科中的其他典型科學問題（1 1） 證比求易算法證比求易算法n 求出求出48 770 428 433 377 171的一個真因子的一個真因子 n 給出數(shù)進行驗證：給出數(shù)進行驗證：順序算法順序算法n 多人參加驗證：多人參加驗證：并行算法并行算法n 時間復雜性時間復雜性 空間復雜性空間復雜性n 但并行運算也存在但并行運算也存在“瓶頸瓶頸”問題

19、：問題：阿姆達爾定律阿姆達爾定律 1 Sp - （倍）（倍） 加速能力加速能力 1 - f f + - pn 設(shè)設(shè)f=1%, p ，Sp=100，最大，最大100倍倍o 直覺上認為順序算法解決不了的問題完全可以用并直覺上認為順序算法解決不了的問題完全可以用并行算法來解決，并且，并行計算機系統(tǒng)求解問題的行算法來解決，并且，并行計算機系統(tǒng)求解問題的速度將隨著處理器數(shù)目的不斷增加而不斷提高，從速度將隨著處理器數(shù)目的不斷增加而不斷提高，從而解決難解性問題。這是一種誤解。而解決難解性問題。這是一種誤解。o 阿姆達爾定律阿姆達爾定律說明：當將一個問題分解到多個處理說明：當將一個問題分解到多個處理器上解決時

20、，由于算法中不可避免地存在必須串行器上解決時，由于算法中不可避免地存在必須串行執(zhí)行的操作，從而大大地限制了并行計算機系統(tǒng)的執(zhí)行的操作，從而大大地限制了并行計算機系統(tǒng)的加速能力。加速能力。3、計算學科中的其他典型科學問題（、計算學科中的其他典型科學問題（2） 旅行商問題與組合爆炸問題旅行商問題與組合爆炸問題n 旅行商問題旅行商問題（Traveling Salesman Problem，TSP）：一個旅行商從某）：一個旅行商從某城市出發(fā)，必須經(jīng)過每個城市一次切城市出發(fā)，必須經(jīng)過每個城市一次切僅一次，最后回到原出發(fā)城市。如何僅一次，最后回到原出發(fā)城市。如何確定一條最短的路線，使其旅行的費確定一條最短

21、的路線，使其旅行的費用最少。用最少。n 是典型的是典型的NP完全問題完全問題：本質(zhì)上難以：本質(zhì)上難以求解。求解。n 是最有代表性的優(yōu)化組合問題之一：是最有代表性的優(yōu)化組合問題之一：割平面法與分支限界法相結(jié)合。割平面法與分支限界法相結(jié)合。旅行商問題與組合爆炸問題旅行商問題與組合爆炸問題旅行商問題與組合爆炸問題旅行商問題與組合爆炸問題o 如果有如果有3個城市個城市A、B和和C，則有，則有6種訪問每個城市的次序：種訪問每個城市的次序：ABC，ACB，BAC，BCA，CAB，CBA；如果有；如果有4個城個城市，則有市，則有24種次序，可以用階乘來表示：種次序，可以用階乘來表示：4！=24；若有；若有5

22、個城市，則有個城市，則有5！=54！=120。o 如果如果n個城市，則有個城市，則有n??；??；20個城市：個城市：20！=1.2X1017。o 即使用計算機來計算，這種急劇增長的數(shù)字也遠遠超過即使用計算機來計算，這種急劇增長的數(shù)字也遠遠超過計算資源的處理能力。計算資源的處理能力。Cook評論：評論：“如果有如果有100個城市，個城市，需要求出需要求出100！條路線的費用，沒有哪一臺計算機能夠！條路線的費用，沒有哪一臺計算機能夠勝任這一任務。打個比方，讓太陽系中所有的電子以它勝任這一任務。打個比方，讓太陽系中所有的電子以它旋轉(zhuǎn)的頻率來計算，就算太陽燒盡了也算不完。旋轉(zhuǎn)的頻率來計算，就算太陽燒盡了

23、也算不完?！眔 組合路線數(shù)呈指數(shù)階急劇增長組合路線數(shù)呈指數(shù)階急劇增長組合爆炸問題組合爆炸問題。o 將將割平面法割平面法與與分支限界法分支限界法相結(jié)合，相結(jié)合，1998年科學家們成功年科學家們成功地解決了美國地解決了美國13509個城市之間的個城市之間的TSP問題，問題，o 2001年又解決了德國年又解決了德國15112個城市之間的個城市之間的TSP問題。但問題。但這一工程代價也是巨大的：共使用了美國這一工程代價也是巨大的：共使用了美國Rice大學和普大學和普林斯頓大學之間網(wǎng)絡互連的、由速度為林斯頓大學之間網(wǎng)絡互連的、由速度為500MHz 的處理的處理器組成的器組成的110臺計算機，所有計算機花

24、費的時間之和為臺計算機，所有計算機花費的時間之和為22.6年。年。o 由于由于TSP會產(chǎn)生組合爆炸的問題，因此尋找切實可行的會產(chǎn)生組合爆炸的問題，因此尋找切實可行的簡化求解方法就成為問題的關(guān)鍵。簡化求解方法就成為問題的關(guān)鍵。o TSP應用：鉆孔調(diào)度問題，運輸問題，后勤服務問題。應用：鉆孔調(diào)度問題，運輸問題，后勤服務問題。旅行商問題與組合爆炸問題旅行商問題與組合爆炸問題3、計算學科中的其他典型科學問題（、計算學科中的其他典型科學問題（3）o 找零問題找零問題：設(shè)有不同面值的鈔票，要求用最小數(shù)量的鈔：設(shè)有不同面值的鈔票，要求用最小數(shù)量的鈔票給顧客找某數(shù)額的零錢。票給顧客找某數(shù)額的零錢。o 背包問題

25、背包問題：給定：給定n種物品和一個背包，要求在重量容量種物品和一個背包，要求在重量容量的限制下，使裝入的物品總價值最大。的限制下，使裝入的物品總價值最大。o 找零問題、背包問題等是一類可以用貪心法來處理的典找零問題、背包問題等是一類可以用貪心法來處理的典型問題。型問題。o 貪心法貪心法：是一種傳統(tǒng)的啟發(fā)式算法，它采用逐步構(gòu)造最：是一種傳統(tǒng)的啟發(fā)式算法，它采用逐步構(gòu)造最優(yōu)解的方法，即在算法的每個階段，都作出在當時看上優(yōu)解的方法，即在算法的每個階段，都作出在當時看上去最好的決策，以獲得最大的去最好的決策，以獲得最大的“好處好處”；換言之，就是；換言之，就是在每一個決策過程中都要盡可能的在每一個決策

26、過程中都要盡可能的“貪貪”，直到算法中，直到算法中的某一步不能繼續(xù)前進時，算法才停止。的某一步不能繼續(xù)前進時，算法才停止。3、計算學科中的其他典型科學問題（、計算學科中的其他典型科學問題（4） 計算機資源管理計算機資源管理n 生產(chǎn)者生產(chǎn)者消費者問題：使用資源，釋放資源消費者問題：使用資源，釋放資源o 使用共享資源的多進程同步問題使用共享資源的多進程同步問題o 使用使用“信號燈信號燈”的概念解決進程間的互斥的概念解決進程間的互斥n “哲學家共餐哲學家共餐”問題問題o 程序并發(fā)執(zhí)行時進程同步的程序并發(fā)執(zhí)行時進程同步的問題：問題：“死鎖死鎖”和和“饑餓饑餓”o 解決：并發(fā)程序語言、解決：并發(fā)程序語言

27、、Petri網(wǎng)網(wǎng) 在計算學科誕生后，為解決人工智能中一些激烈爭在計算學科誕生后，為解決人工智能中一些激烈爭論的問題，圖靈和西爾勒又分別提出了能反映人工智能論的問題，圖靈和西爾勒又分別提出了能反映人工智能本質(zhì)特征的兩個著名的哲學問題，即圖靈測試和西爾勒本質(zhì)特征的兩個著名的哲學問題，即圖靈測試和西爾勒的的“中文屋子中文屋子”。 沿著圖靈等人對沿著圖靈等人對“智能智能”的理解，人們在人工智能的理解，人們在人工智能領(lǐng)域取得了長足的進展，其中，領(lǐng)域取得了長足的進展，其中，“深藍深藍”戰(zhàn)勝國際象棋大師卡戰(zhàn)勝國際象棋大師卡斯帕羅夫就是一個很好的例證。斯帕羅夫就是一個很好的例證。3、計算學科中的其他典型科學問

28、題（、計算學科中的其他典型科學問題（5） 人工智能中的哲學問題人工智能中的哲學問題 圖靈測試（圖靈測試（Turing Test)n 1950年，圖靈提出：機器能思維嗎？年，圖靈提出：機器能思維嗎？n 一個人在不接觸對象的情況下，進行一系列的提問，一個人在不接觸對象的情況下，進行一系列的提問，如果他根據(jù)這些回答無法判斷對象是人還是機器，如果他根據(jù)這些回答無法判斷對象是人還是機器，則這種計算機具有與人相當?shù)闹橇?。則這種計算機具有與人相當?shù)闹橇Α 模仿游戲的試驗模仿游戲的試驗稱之為圖靈測試稱之為圖靈測試 n 人類思維的本質(zhì)？思維就是計算。人類思維的本質(zhì)？思維就是計算。n 機器思維的定義？從功能的角

29、度來判定機器是否能機器思維的定義？從功能的角度來判定機器是否能思維，也就是從行為主義思維，也就是從行為主義這個角度對這個角度對“機器思維機器思維”進進行定義。行定義。 西爾勒（西爾勒（J.R.Searle）的）的“中文屋中文屋”n 1980年西爾勒在年西爾勒在行為科學和腦科學行為科學和腦科學雜志上發(fā)表雜志上發(fā)表論文，在文中他以自己為主角設(shè)計了一個中文屋論文，在文中他以自己為主角設(shè)計了一個中文屋子的假想試驗，反駁了強子的假想試驗，反駁了強AI的觀點。的觀點。n 西爾勒給出的漢字符號與一個地道的中國人作出西爾勒給出的漢字符號與一個地道的中國人作出的答案沒什么不同。但是，我們能說西爾勒真的的答案沒什

30、么不同。但是，我們能說西爾勒真的懂中文嗎？懂中文嗎？n 結(jié)論：機器永遠也不能結(jié)論：機器永遠也不能代替大腦代替大腦形式化的計形式化的計算機僅有語法，沒有算機僅有語法，沒有語義語義。人機博弈問題人機博弈問題n 轉(zhuǎn)折點：轉(zhuǎn)折點：1997年年“深藍（深藍（Deep Blue)”與卡斯帕羅夫之戰(zhàn)。與卡斯帕羅夫之戰(zhàn)。 前者前者二勝一負三平戰(zhàn)勝后者。深藍由二勝一負三平戰(zhàn)勝后者。深藍由256（32 node*8）個專用處理）個專用處理器組成，每秒可計算器組成，每秒可計算2億步棋。億步棋。n 使用博弈樹搜索，尋找最佳解。國際象棋使用博弈樹搜索，尋找最佳解。國際象棋10120個結(jié)點（棋局總個結(jié)點（棋局總數(shù)），中國

31、象棋數(shù)），中國象棋10160個結(jié)點，圍棋個結(jié)點，圍棋10768個結(jié)點個結(jié)點難解性問題。難解性問題。n 2006年在北京奧體中心進行的首屆年在北京奧體中心進行的首屆“浪潮杯浪潮杯”中國象棋中國象棋“人機人機大戰(zhàn)大戰(zhàn)”，電腦勝出，電腦勝出。o 機器智力和人的智力是二回事。機器智力和人的智力是二回事。 o 人要在計算能力上超過機器是不現(xiàn)實的。人要在計算能力上超過機器是不現(xiàn)實的。o 人腦：最后最偉大的研究前沿人腦：最后最偉大的研究前沿是宇宙中已知的最復是宇宙中已知的最復 雜的物質(zhì)。雜的物質(zhì)。 詹母斯詹母斯.華生華生(James Watson)o GOTO語句的問題以及程序設(shè)計方法學語句的問題以及程序設(shè)

32、計方法學n 1968，Dijkstra首次提出首次提出“GOTO語句是有害的語句是有害的”n 任何程序的邏輯結(jié)構(gòu)都可用任何程序的邏輯結(jié)構(gòu)都可用3種基本結(jié)構(gòu)表示：種基本結(jié)構(gòu)表示： 順序順序 選擇選擇 循環(huán)循環(huán)n 導致結(jié)構(gòu)化程序設(shè)計導致結(jié)構(gòu)化程序設(shè)計程序設(shè)計方法學程序設(shè)計方法學o 網(wǎng)絡協(xié)議的復雜性和分層結(jié)構(gòu)：網(wǎng)絡協(xié)議的復雜性和分層結(jié)構(gòu)： 兩軍問題，兩軍問題，ISO/OSI參考模型，參考模型，TCP/IP協(xié)議協(xié)議ABABAPp3、計算學科中的其他典型科學問題（、計算學科中的其他典型科學問題（6）4、計算學科的主領(lǐng)域及其基本問題、計算學科的主領(lǐng)域及其基本問題o 計算學科中的一些基本問題計算學科中的一些

33、基本問題n 計算過程的計算過程的能行與效率能行與效率問題問題n 計算的正確性問題計算的正確性問題n 計算的平臺與環(huán)境問題計算的平臺與環(huán)境問題o 如何用科學哲學觀點看待和解釋如何用科學哲學觀點看待和解釋n P=?NPn 資源共享資源共享 哲學家共餐問題哲學家共餐問題n 圖靈測試圖靈測試 人工智能人工智能n “中文屋子中文屋子” 機器永遠代替不了人腦機器永遠代替不了人腦n 人機對弈人機對弈 智力與計算能力，智商（智力與計算能力，智商（IQ）與情）與情商（商（EQ）數(shù)據(jù)、信息及其關(guān)系數(shù)據(jù)、信息及其關(guān)系o數(shù)據(jù)數(shù)據(jù)(Data)n數(shù)據(jù)是一組表示數(shù)量、行動和目標等事實數(shù)據(jù)是一組表示數(shù)量、行動和目標等事實(fact)的可鑒別的可鑒別的非隨機符號。它可以是字母、數(shù)字或其它符號，也可的非隨機符號。它可