計算機領(lǐng)域的典型問題

計算機領(lǐng)域的典型問題第一頁，共三十九頁，編輯于2023年，星期五8.1圖論問題歌尼斯堡七橋問題哈密爾頓回路問題中國郵路問題

第二頁，共三十九頁，編輯于2023年，星期五8.1.1歌尼斯堡七橋問題問題描述一個人怎樣不重復(fù)地走完七座橋，最后還能回到原出發(fā)地點？

第三頁，共三十九頁，編輯于2023年，星期五8.1.1歌尼斯堡七橋問題歐拉對哥尼斯堡七橋問題進行了研究1736年，歐拉論證了該問題無解。從一點出發(fā)不重復(fù)地走遍7座橋，最后又回到原來出發(fā)點是不可能的。歐拉對了問題進行了抽象描述：用4個字母A、B、

C、D代表4個城區(qū)，并用

7條邊表示7座橋。第四頁，共三十九頁，編輯于2023年，星期五歐拉的3條判定規(guī)則如果通奇數(shù)座橋的地方不止兩個，滿足要求的路徑是找不到的。如果只有兩個地方通奇數(shù)座橋，可以從這兩個地方之一出發(fā)，找到所要求的路徑。如果沒有一個地方是通奇數(shù)座橋的，則無論從哪里出發(fā)，所要求的路徑都能實現(xiàn)。8.1.1歌尼斯堡七橋問題第五頁，共三十九頁，編輯于2023年，星期五歐拉的研究工作奠定了圖論的基礎(chǔ)涉及到的后續(xù)課程。離散數(shù)學(xué)。數(shù)據(jù)結(jié)構(gòu)。應(yīng)用領(lǐng)域。計算機網(wǎng)絡(luò)性能分析。交通運輸網(wǎng)絡(luò)調(diào)度。地下管網(wǎng)配置。8.1.1歌尼斯堡七橋問題航空網(wǎng)絡(luò)第六頁，共三十九頁，編輯于2023年，星期五8.1.2哈密頓回路問題問題描述（周游世界游戲）找一條從某個城市出發(fā)，經(jīng)過每個城市恰好一次，最后回到出發(fā)地的路徑。第七頁，共三十九頁，編輯于2023年，星期五哈密頓回路與歐拉回路的區(qū)別哈密頓回路問題是訪問每個頂點一次，而歐拉回路問題是訪問每條邊一次。對于一個圖是否存在歐拉回路，已給出充要條件；而對于一個圖是否存在哈密頓回路至今仍未找到充要條件。8.1.2哈密頓回路問題第八頁，共三十九頁，編輯于2023年，星期五問題描述一個郵遞員應(yīng)如何選擇一條路線，使他能夠從郵局出發(fā)，走遍他負責(zé)送信的所有街道，最后回到郵局，并且所走的路程最短。歸結(jié)為圖論問題：給定一個連通無向圖，求該圖的一條經(jīng)過每條邊至少一次的最短回路。對于歐拉圖，找到一條歐拉回路即可。對于非歐拉圖，才是中國郵路問題的研究重點。8.1.3中國郵路問題第九頁，共三十九頁，編輯于2023年，星期五8.2算法復(fù)雜性問題漢諾塔問題旅行商問題NP完全問題第十頁，共三十九頁，編輯于2023年，星期五8.2.1漢諾塔問題問題描述將第一根柱子上的64個盤子借助第二根柱子全部移到第三根柱子上。64個盤子63個盤子第十一頁，共三十九頁，編輯于2023年，星期五8.2.1漢諾塔問題移動規(guī)則每次只能移動一個盤子。盤子只能在三根柱子上移動，不能放在他處。在移動過程中，三根柱子上的盤子必須始終保持大盤在下，小盤在上。第十二頁，共三十九頁，編輯于2023年，星期五遞歸思想將一個較大的問題的求解歸約為一個或多個子問題的求解。而這些子問題比原問題簡單，且在結(jié)構(gòu)上與原問題相同。8.2.1漢諾塔問題第十三頁，共三十九頁，編輯于2023年，星期五8.2.1漢諾塔問題用遞歸方法求解移動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)+22+2+1=……=2nh(0)+2n-1+…+22+2+1=2n-1+…+22+2+1=2n-1第十四頁，共三十九頁，編輯于2023年，星期五8.2.1漢諾塔問題用遞歸方法求解每次只能移動一個盤子，要完成漢諾塔的搬遷，需要移動盤子的次數(shù)為：

264-1=18446744073709551615每秒移動一次，需要大約5849億年的時間。第十五頁，共三十九頁，編輯于2023年，星期五8.2.2

旅行商問題問題描述一旅行商從某城市出發(fā)，必須經(jīng)過每個城市且只能經(jīng)過一次，最后回到原出發(fā)城市。要求找到一條距離最短的路徑（或費用最少的路徑）。原始的解決辦法列出每條可能的路徑。從中選擇距離最短的路徑。第十六頁，共三十九頁，編輯于2023年，星期五8.2.2旅行商問題遇到的困難城市個數(shù)較多時難以實現(xiàn)。組合爆炸問題?？尚械慕鉀Q辦法啟發(fā)式算法。近似算法。第十七頁，共三十九頁，編輯于2023年，星期五8.2.3NP完全問題P類問題將所有可以在多項式時間內(nèi)求解的問題稱為P類問題。NP類問題將所有在多項式時間內(nèi)可以驗證的問題稱為NP類問題。NP完全問題在NP類問題中，某些問題的復(fù)雜性與整個類的復(fù)雜性有關(guān)，如果這些問題中的任意一個能在多項式的時間內(nèi)求解，則所有NP類問題都能在多項式時間內(nèi)求解，這些NP類問題稱為NP完全問題。第十八頁，共三十九頁，編輯于2023年，星期五8.3計算機智能問題圖靈測試西爾勒中文小屋博弈問題第十九頁，共三十九頁，編輯于2023年，星期五8.3.1圖靈測試機器能思維嗎？第二十頁，共三十九頁，編輯于2023年，星期五8.3.1圖靈測試圖靈測試游戲游戲的參與者一個男人、一個女人和一個不限性別的提問者。游戲目標提問者通過對其他兩人的提問，來鑒別其中的男女。游戲要求提問者呆在與其他兩個游戲者相隔離的房間里。提問者和兩游戲者之間通過電傳打字機進行溝通。第二十一頁，共三十九頁，編輯于2023年，星期五8.3.1圖靈測試圖靈測試游戲把游戲中的男人換成機器。若提問者在與機器、女人的游戲中作出的錯誤判斷與在男人、女人之間的游戲中作出的錯誤判斷，其次數(shù)相同或更多，則判定這部機器能夠思維。根據(jù)圖靈當(dāng)時的預(yù)測，到2000年能有機器通過這樣的測試。有人認為，在1997年戰(zhàn)勝國際象棋大師卡斯帕羅夫的深藍計算機可以看作通過了圖靈測試。第二十二頁，共三十九頁，編輯于2023年，星期五8.3.2西爾勒中文小屋問題描述西爾勒被關(guān)在一個小屋中，屋子里有序地堆放著足夠的中文字符，而他對中文一竅不通。屋外的人遞進一串中文字符，同時還附有一本用英文編寫的處理中文字符的規(guī)則，這些規(guī)則將遞進來的字符和小屋中的字符之間的轉(zhuǎn)換作了形式化的規(guī)定。西爾勒按照規(guī)則對這些字符進行處理后，將一串新的中文字符送出屋外。第二十三頁，共三十九頁，編輯于2023年，星期五8.3.2西爾勒中文小屋問題描述實際上，送進來的字符串就是屋外人提出的問題，送出去的字符串就是所提出問題的答案。但西爾勒并不清楚自己在做什么？第二十四頁，共三十九頁，編輯于2023年，星期五8.3.2西爾勒中文小屋西爾勒的觀點形式化的計算機僅有語法，沒有語義，只是按規(guī)則辦事，并不理解規(guī)則的含義及自己在做什么？機器永遠也不可能代替人腦。圖靈的觀點不要求機器與人腦在內(nèi)部構(gòu)造上一樣，只要與人腦有相同的功能就認為機器有思維。第二十五頁，共三十九頁，編輯于2023年，星期五人工智能的含義研究、開發(fā)用于模擬、延伸和擴展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué)。人工智能研究的目標使機器能夠勝任一些通常需要人類智能才能完成的復(fù)雜工作。

8.3.2西爾勒中文小屋第二十六頁，共三十九頁，編輯于2023年，星期五人工智能的不同觀點符號主義：認為人的認知基元是符號，認為人是一個物理符號系統(tǒng)，計算機也是一個物理符號系統(tǒng)，因而能夠用計算機來模擬人的智能行為。連接主義：認為人的思維基元是神經(jīng)元，而不是符號處理過程。認為人腦不同于電腦，主張人工智能應(yīng)著重于結(jié)構(gòu)模擬。行為主義：認為智能取決于感知和行動，提出智能行為的感知－動作模式。8.3.2西爾勒中文小屋第二十七頁，共三十九頁，編輯于2023年，星期五人工智能的展望目前人們對心理學(xué)和生物學(xué)的認識還很不成熟，對人腦的結(jié)構(gòu)還沒有真正了解，無法建立起人腦思維完整的數(shù)學(xué)模型。讓計算機具有和人腦完全一樣的智能，不是短期內(nèi)能夠?qū)崿F(xiàn)的。在相當(dāng)長的時間內(nèi)，只能從不同的側(cè)面、以不同的方式讓計算機具有某些類似人的智能。8.3.2西爾勒中文小屋第二十八頁，共三十九頁，編輯于2023年，星期五8.3.3博弈問題博弈的含義狹義上講，博弈是指下棋、玩撲克牌、擲骰子等具有輸贏性質(zhì)的游戲。廣義上講，博弈就是對策或斗智。第二十九頁，共三十九頁，編輯于2023年，星期五8.3.3博弈問題雙人完備博弈兩位選手對壘，輪流走步，其中一方完全知道另一方已經(jīng)走過的棋步以及未來可能的棋步。對弈的結(jié)果要么是一方贏（另一方輸），要么是和局。對于任何一種雙人完備博弈，都可以用一個博弈樹來描述，并通過博弈樹搜索策略尋找最佳解。

第三十頁，共三十九頁，編輯于2023年，星期五博弈樹博弈樹類似于狀態(tài)圖和問題求解搜索中使用的搜索樹。搜索樹上的一個結(jié)點對應(yīng)一個棋局，樹的分支表示棋的走步，根結(jié)點表示棋局的開始，葉結(jié)點表示棋局的結(jié)束。博弈樹是非常大的，國際象棋有10120個結(jié)點，中國象棋來有10160個結(jié)點。8.3.3博弈問題第三十一頁，共三十九頁，編輯于2023年，星期五8.4并發(fā)控制問題生產(chǎn)者-消費者問題哲學(xué)家共餐問題第三十二頁，共三十九頁，編輯于2023年，星期五8.4.1生產(chǎn)者-消費者問題問題描述有n個生產(chǎn)者和m個消費者，在生產(chǎn)者和消費者之間設(shè)置了一個能存放k個產(chǎn)品的貨架。只要貨架未滿，生產(chǎn)者pi生產(chǎn)的產(chǎn)品就可以放入貨架，每次放入一個產(chǎn)品；只要貨架非空，消費者cj就可以貨架取走產(chǎn)品消費，每次取走一個。所有生產(chǎn)者的產(chǎn)品生產(chǎn)和消費者的產(chǎn)品消費都可以按自己的意愿進行，即相互之間是獨立的。第三十三頁，共三十九頁，編輯于2023年，星期五8.4.1生產(chǎn)者-消費者問題約束條件不允許消費者從空貨架取產(chǎn)品，現(xiàn)實中也是取不到的。不允許生產(chǎn)者向一個已裝滿產(chǎn)品的貨架中再放入產(chǎn)品。應(yīng)用背景是對操作系統(tǒng)中并發(fā)進程同步的一種抽象描述，多個進程雖然看起來是按異步方式執(zhí)行的，但相互有關(guān)的進程應(yīng)有一種協(xié)調(diào)機制。

第三十四頁，共三十九頁，編輯于2023年，星期五8.4.2哲學(xué)家共餐問題問題描述哲學(xué)家的生活除了吃面條就是思考問題。吃面條的時候需要左、右手各拿起一支筷子。吃完后將筷子放回原處，繼續(xù)思考問題。第三十五頁，共三十九頁，編輯于2023年，星期五8.4.2哲學(xué)家共餐問題一個哲學(xué)家的活動進程表示思考問題。餓了停止思考，左手拿一支筷子（拿不到就等）。右手拿一支筷子（拿不到就等）。進餐。放右手筷子。放左手筷子。重新回到思考問題狀態(tài)。第三十六頁，共三十九頁，編輯于2023年，星期五8.4.2哲學(xué)家共餐問題可能出現(xiàn)的問題當(dāng)所有的哲學(xué)家都同時拿起左手筷子時，則所有的哲學(xué)家都將拿不到右手的筷子，并處于等待狀態(tài)，那么哲學(xué)家都將無法進餐，最終餓死。將哲學(xué)家的活動進程修改一下，變?yōu)楫?dāng)右手的筷子拿不到時，就放下左手的筷子。可能在一個瞬間，所有的哲學(xué)家都同時拿起左手的筷子，則自然拿不到右手的筷子，于是都同時放下左手的筷子，等一會，又同時拿起左手的筷子，如此這樣永遠重復(fù)下去，則所有的哲學(xué)家仍然無法進餐。第三十七頁，共三十九頁，編輯于2023年，星期五8.4.2哲學(xué)家共餐問題應(yīng)用背景描述了多個進程以互斥方式訪問有限資源的問題。計算機系統(tǒng)不可能總是提供足夠多的資源，但又想盡可能多地同時滿足多個用戶的使用要求。研究人員已經(jīng)采取了一些非常有效的方法來盡量