計算機科學(xué)典型問題示例

計算機科學(xué)典型問題示例第1頁，共47頁，2023年，2月20日，星期四計算機科學(xué)典型問題示例

哥尼斯堡七橋問題

尋找走遍這7座橋且只許走過每座橋一次，最后又回到原出發(fā)點的路徑

第2頁，共47頁，2023年，2月20日，星期四計算機科學(xué)典型問題示例

哥尼斯堡七橋問題

兩岸的陸地與河中的小島，都是橋梁的連接點，它們的大小、形狀均與問題本身無關(guān)。因此，把它們看作是4個點；7座橋是7條必須經(jīng)過的路線，它們的長短、曲直，也與問題本身無關(guān)。因此，任意畫7條線來表示它們。第3頁，共47頁，2023年，2月20日，星期四歐拉將七橋問題抽象成了一個“一筆畫”問題。怎樣不重復(fù)地通過7座橋，變成了怎樣不重復(fù)地畫出一個幾何圖形的問題。原先，人們是要求找出一條不重復(fù)的路線，歐拉接下來著手判斷：這種不重復(fù)的路線究竟存在不存在？由于這么改變了一下提問的角度，歐拉抓住了問題的實質(zhì)。歐拉發(fā)現(xiàn)，凡是能用一筆畫成的圖形，都有這樣一個特點：每當(dāng)你用筆畫一條線進入中間的一個點時，你還必須畫一條線離開這個點。否則，整個圖形就不可能用一筆畫出。也就是說，單獨考察圖中的任何一個點（除起點和終點外），它都應(yīng)該與偶數(shù)條線相連；如果起點與終點重合，那么，連這個點也應(yīng)該與偶數(shù)條線相連。計算機科學(xué)典型問題示例

哥尼斯堡七橋問題

第4頁，共47頁，2023年，2月20日，星期四計算機科學(xué)典型問題示例

哥尼斯堡七橋問題

結(jié)論（1）如果通奇數(shù)座橋的地方不止兩個，滿足要求的路線是找不到的；（2）如果只有兩個地方通奇數(shù)座橋，可以從這兩個地方之一出發(fā)，找到所要求的路線；（3）如果沒有一個地方是通奇數(shù)座橋的，則無論從哪里出發(fā)，所要求的路線都能實現(xiàn)。第5頁，共47頁，2023年，2月20日，星期四歐拉的論文為圖論的形成奠定了基礎(chǔ)。今天，圖論已廣泛地應(yīng)用于計算機科學(xué)、運籌學(xué)、信息論、控制論等科學(xué)之中，并已成為我們對現(xiàn)實問題進行抽象的一個強有力的數(shù)學(xué)工具。隨著計算機科學(xué)的發(fā)展，圖論在計算機科學(xué)中的作用越來越大，同時，圖論本身也得到了充分的發(fā)展。第6頁，共47頁，2023年，2月20日，星期四漢諾塔問題1）每次只能移動一個盤子；2）盤子只能在三根柱子上來回移動不能放在他處；3）在移動過程中三根柱子上的盤子必須始終保持大盤在下小盤在上天神說，當(dāng)這64個盤子全部移到第三根柱子上后，世界末日就要到了。

第7頁，共47頁，2023年，2月20日，星期四用計算機求解一個實際問題，首先要從這個實際問題中抽象出一個數(shù)學(xué)模型，然后設(shè)計一個解此數(shù)學(xué)模型的算法，最后根據(jù)算法編寫程序，經(jīng)過調(diào)試和運行，從而完成該問題的求解。從實際問題抽象出一個數(shù)學(xué)模型的實質(zhì)，其實就是要用數(shù)學(xué)的方法抽取問題主要的、本質(zhì)的內(nèi)容，最終實現(xiàn)對該問題的正確認(rèn)識。第8頁，共47頁，2023年，2月20日，星期四漢諾塔問題是一個典型的用遞歸方法來解決的問題。遞歸是計算機學(xué)科中的一個重要概念。所謂遞歸，就是將一個較大的問題歸約為一個或多個子問題的求解方法。而這些子問題比原問題簡單，且在結(jié)構(gòu)上與原問題相同。第9頁，共47頁，2023年，2月20日，星期四根據(jù)遞歸方法，我們可以將64個盤子的漢諾塔問題轉(zhuǎn)化為求解63個盤子的漢諾塔問題，如果63個盤子的漢諾塔問題能夠解決，則可以將63個盤子先移動到第二個柱子上，再將最后一個盤子直接移動到第三個柱子上，最后又一次將63個盤子從第二個柱子移動到第三個柱子上。第10頁，共47頁，2023年，2月20日，星期四漢諾塔問題示意圖第11頁，共47頁，2023年，2月20日，星期四63個盤子的漢諾塔求解問題可以轉(zhuǎn)化為62個盤子的漢諾塔求解問題，62個盤子的漢諾塔求解問題又可以轉(zhuǎn)化為61個盤子的漢諾塔求解問題，直到1個盤子的漢諾塔求解問題。再由1個盤子的漢諾塔的解求出2個盤子的漢諾塔，直到解出64個盤子的漢諾塔問題。

第12頁，共47頁，2023年，2月20日，星期四按照上面的算法，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第13頁，共47頁，2023年，2月20日，星期四

因此，要完成漢諾塔的搬遷，需要移動盤子的次數(shù)為：264-1=18446744073709551615如果每秒移動一次，一年有31536000秒，則僧侶們一刻不停地來回搬動，也需要花費大約5849億年的時間。假定計算機以每秒1000萬個盤子的速度進行搬遷，則需要花費大約58490年的時間。第14頁，共47頁，2023年，2月20日，星期四證比求易算法問題

算法分析是計算機科學(xué)的一項主要工作。為了進行算法比較，我們必須給出算法效率的某種衡量標(biāo)準(zhǔn)。第15頁，共47頁，2023年，2月20日，星期四

很久以前，有一個年輕的國王，名叫艾述。他酷愛數(shù)學(xué)，聘請了當(dāng)時最有名的數(shù)學(xué)家孔喚石當(dāng)宰相。鄰國有一位聰明美麗的公主，名字叫秋碧貞楠。艾述國王愛上了這位鄰國公主，便親自登門求婚。公主說：“你如果向我求婚，請你先求出48770428433377171的一個真因子，一天之內(nèi)交卷?！卑雎犃T，心中暗喜，心想：我從2開始，一個一個地試，看看能不能除盡這個數(shù)，還怕找不到這個真因子嗎？第16頁，共47頁，2023年，2月20日，星期四

艾述國王十分精于計算，他一秒鐘就算完一個數(shù)?？墒?，他從早到晚，共算了三萬多個數(shù)，最終還是沒有結(jié)果。國王向公主求情，公主將答案相告：223092827是它的一個真因子。國王很快就驗證了這個數(shù)確能除盡48770428433377171。第17頁，共47頁，2023年，2月20日，星期四

公主說：“我再給你一次機會，如果還求不出，將來你只好做我的證婚人了”。國王立即回國，召見宰相孔喚石，大數(shù)學(xué)家在仔細(xì)地思考后認(rèn)為這個數(shù)為17位，如果這個數(shù)可以分成兩個真因子的乘積，則最小的一個真因子不會超過9位。于是他給國王出了一個主意：按自然數(shù)的順序給全國的老百姓每人編一個號發(fā)下去，等公主給出數(shù)目后，立即將它們通報全國，讓每個老百姓用自己的編號去除這個數(shù)，除盡了立即上報，賞黃金萬兩。第18頁，共47頁，2023年，2月20日，星期四

于是，國王發(fā)動全國上下的民眾，再度求婚，終于取得成功。在“證比求易算法”的故事中，國王最先使用的是一種順序算法，其復(fù)雜性表現(xiàn)在時間方面，后來由宰相提出的是一種并行算法，其復(fù)雜性表現(xiàn)在空間方面。直覺上，我們認(rèn)為順序算法解決不了的問題完全可以用并行算法來解決，甚至?xí)?，并行計算機系統(tǒng)求解問題的速度將隨著處理器數(shù)目的不斷增加而不斷提高，從而解決難解性問題，其實這是一種誤解。第19頁，共47頁，2023年，2月20日，星期四

國王有眾多百姓的幫助，求親成功是自然的事。但是，如果換成是一個貧民百姓的小伙子去求婚，那就困難了。不過，小伙子可以從國王求親取得成功所采用的并行算法中得到一個啟發(fā)，那就是：他可以隨便猜一個數(shù)，然后驗證這個數(shù)。當(dāng)然，這樣做成功的可能性很小，不過，萬一小伙子運氣好猜著了呢？由于一個數(shù)和它的因子之間存在一些有規(guī)律的聯(lián)系，因此，數(shù)論知識水平較高的人猜中的可能性就大。第20頁，共47頁，2023年，2月20日，星期四

在算法計算復(fù)雜性的研究中，將所有可以在多項式時間內(nèi)求解的問題稱為P類問題，而將所有在多項式時間內(nèi)可以驗證的問題稱為NP類問題，由于P類問題采用的是確定性算法，NP類問題采用的是非確定性算法，確定性算法是非確定性算法的一個特例，因此P?NP。第21頁，共47頁，2023年，2月20日，星期四

對于大多數(shù)實際問題來說，找到一個解可能很難，檢驗一個解常常比較容易，所以都屬于NP類問題?，F(xiàn)在計算機科學(xué)研究中一個懸而未決的重要問題是P=?NP。到目前為止，已經(jīng)發(fā)現(xiàn)了一批可計算但有相當(dāng)難度的問題是屬于NP類問題，并且常通過證明一個問題與已知屬于NP類中的某個問題等價，將其歸入NP類問題。第22頁，共47頁，2023年，2月20日，星期四計算機科學(xué)典型問題示例

哲學(xué)家共餐問題

第23頁，共47頁，2023年，2月20日，星期四哲學(xué)家的生活進程思考問題餓了停止思考，左手拿一支筷子（拿不到就等）右手拿一支筷子（拿不到就等）進餐放右手筷子放左手筷子重新回到思考問題的狀態(tài)1第24頁，共47頁，2023年，2月20日，星期四哲學(xué)家的生活進程的極端情況：當(dāng)所有哲學(xué)家都同時拿起左手筷子時，則所有哲學(xué)家都拿不到右手的筷子，并處于等待狀態(tài)，則哲學(xué)家將都無法進餐，最終餓死；改變進程，如拿不到右手筷子則放下左手筷子。在某一瞬可能所有的哲學(xué)家都拿起左手的筷子，因拿不到右手的筷子又都同時放下左手的筷子，如此下去，所有的哲學(xué)家同樣無法進餐。哲學(xué)家進餐問題在計算機科學(xué)中所反映的問題：程序并發(fā)執(zhí)行時進程同步的問題：死鎖（Deadlock）和饑餓（Starvation）為了提高系統(tǒng)的處理能力和機器的利用率，并法程序被廣泛地使用，因此必須徹底解決并發(fā)進程中的死鎖和饑餓問題第25頁，共47頁，2023年，2月20日，星期四

Deadlock第26頁，共47頁，2023年，2月20日，星期四Starvation第27頁，共47頁，2023年，2月20日，星期四Starvation第28頁，共47頁，2023年，2月20日，星期四Starvation第29頁，共47頁，2023年，2月20日，星期四旅行商問題旅行商問題（TravelingSalesmanProblem，簡稱TSP）是威廉·哈密爾頓（W.R.Hamilton）爵士和英國數(shù)學(xué)家克克曼（T.P.Kirkman）于19世紀(jì)初提出的一個數(shù)學(xué)問題。這是一個典型的NP完全性問題。其大意是：有若干個城市，任何兩個城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)，必須經(jīng)過每一個城市且只能在每個城市逗留一次，最后回到原出發(fā)城市。問如何事先確定好一條最短的路線，使其旅行的費用最少。第30頁，共47頁，2023年，2月20日，星期四

人們在考慮解決這個問題時，一般首先想到的最原始的一種方法是：列出每一條可供選擇的路線（即對給定的城市進行排列組合），計算出每條路線的總里程，最后從中選出一條最短的路線。假設(shè)現(xiàn)在給定的4個城市分別為A、B、C和D，各城市之間的距離為已知數(shù)，如圖a、圖b所示。從圖中可以看到，可供選擇的路線共有6條，從中很快可以選出一條總距離最短的路線。第31頁，共47頁，2023年，2月20日，星期四ABCD256424圖a城市交通圖A265BCD244442BDCCBD224444ACCBDBD522665圖b組合路徑圖第32頁，共47頁，2023年，2月20日，星期四

設(shè)城市數(shù)目為n時，那么組合路徑數(shù)則為（n-1）！。很顯然，當(dāng)城市數(shù)目不多時要找到最短距離的路線并不難，但隨著城市數(shù)目的不斷增大，組合路線數(shù)將呈指數(shù)級急劇增長，以至達到無法計算的地步，這就是所謂的“組合爆炸問題”。假設(shè)現(xiàn)在城市的數(shù)目增為20個，組合路徑數(shù)則為（20-1）！≈1.216×1017，如此龐大的組合數(shù)目，若計算機以每秒檢索1000萬條路線的速度計算，也需要花上386年的時間。第33頁，共47頁，2023年，2月20日，星期四

圖靈測試問題

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

第34頁，共47頁，2023年，2月20日，星期四

圖靈于1950年在英國《Mind》雜志上發(fā)表了《Computing

MachineryandIntelligence》一文，文中提出了“機器能思維嗎？”這樣一個問題，并給出了一個被后人稱之為“圖靈測試（TuringTest）”的模仿游戲。第35頁，共47頁，2023年，2月20日，星期四

這個游戲由3個人來完成：一個男人（A），一個女人（B），一個性別不限的提問者（C）。提問者（C）呆在與其他兩個游戲者相隔離的房間里。游戲的目標(biāo)是讓提問者通過對其他兩人的提問來鑒別其中哪個是男人，哪個是女人。為了避免提問者通過他們的聲音、語調(diào)輕易地作出判斷，最好是在提問者和兩游戲者之間通過一臺電傳打字機來進行溝通。提問者只被告知兩個人的代號為X和Y，游戲的最后他要作出“X是A，Y是B”或“X是B，Y是A”的判斷。

第36頁，共47頁，2023年，2月20日，星期四

現(xiàn)在，把上面這個游戲中的男人（A）換成一部機器來扮演，如果提問者在與機器、女人的游戲中作出的錯誤判斷與在男人、女人之間的游戲中作出錯誤判斷的次數(shù)是相同的，那么，就可以判定這部機器是能夠思維的。圖靈關(guān)于“圖靈測試”的論文發(fā)表后引發(fā)了很多的爭論，以后的學(xué)者在討論機器思維時大多都要談到這個游戲。

第37頁，共47頁，2023年，2月20日，星期四

“圖靈測試”只是從功能的角度來判定機器是否能思維，也就是從行為主義角度來對“機器思維”進行定義。盡管圖靈對“機器思維”的定義是不夠嚴(yán)謹(jǐn)?shù)模P(guān)于“機器思維”定義的開創(chuàng)性工作對后人的研究具有重要意義，因此，一些學(xué)者認(rèn)為，圖靈發(fā)表的關(guān)于“圖靈測試”的論文標(biāo)志著現(xiàn)代機器思維問題討論的開始。第38頁，共47頁，2023年，2月20日，星期四

根據(jù)圖靈的預(yù)測，到2000年，此類機器能通過測試。現(xiàn)在，在某些特定的領(lǐng)域，如博弈領(lǐng)域，“圖靈測試”已取得了成功，1997年，IBM公司研制的計算機“深藍(lán)”就戰(zhàn)勝了國際象棋冠軍卡斯帕羅夫。第39頁，共47頁，2023年，2月20日，星期四

在未來，如果我們能像圖靈揭示計算本質(zhì)那樣揭示人類思維的本質(zhì)，即“能行”思維，那么制造真正思維機器的日子也就不長了。可惜要對人類思維的本質(zhì)進行描述，還是相當(dāng)遙遠(yuǎn)的事情。第40頁，共47頁，2023年，2月20日，星期四搏弈問題

博弈問題屬于人工智能中一個重要的研究領(lǐng)域。從狹義上講，博弈是指下棋、玩撲克牌、擲骰子等具有輸贏性質(zhì)的游戲；從廣義上講，博弈就是對策或斗智。計算機中的博弈問題，一直是人工智能領(lǐng)域研究的重點內(nèi)容之一。

第41頁，共47頁，2023年，2月20日，星期四

1913年，數(shù)學(xué)家策墨洛（E.Zermelo）在第五屆國際數(shù)學(xué)會議上發(fā)表了《關(guān)于集合論在象棋博弈理論中的應(yīng)用》（OnanApplicationofSetTheorytoGameofChess）的著名論文，第一次把數(shù)學(xué)和象棋聯(lián)系起來，從此，現(xiàn)代數(shù)學(xué)出現(xiàn)了一個新的理論，即博弈論。1950年，“信息論”創(chuàng)始人香農(nóng)（A.Shannon）發(fā)表了《國際象棋與機器》（AChess－PlayingMachine）一文，并闡述了用計算機編制下棋程序的可能性。第42頁，共47頁，2023年，2月20日，星期四

1956年夏天，由麥卡錫（J.McCarthy）和香農(nóng)等人共同發(fā)起的，在美國達特茅斯（Dartmouth）大學(xué)舉行的夏季學(xué)術(shù)討論會上，第一次正式使用了“人工智能”這一術(shù)語，該次會議的召開對人工智能的發(fā)展起到了極大的推動作用。第43頁，共47頁，2023年，2月20日，星期四

當(dāng)時，IBM公司的工程師塞繆爾（A.Samuel）也被邀請參加了“達特茅斯”會議，塞繆爾的研究專長正是電腦下棋。早在1952年，塞繆爾就運用博弈理論和狀態(tài)空間搜索技術(shù)成功地研制了世界上第一個跳棋程序