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

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

哥尼斯堡七橋問題

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

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

哥尼斯堡七橋問題

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

哥尼斯堡七橋問題

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

哥尼斯堡七橋問題

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

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

第12頁，共47頁，2023年，2月20日，星期四按照上面的算法，n個(gè)盤子的漢諾塔問題需要移動(dòng)的盤子數(shù)是n-1個(gè)盤子的漢諾塔問題需要移動(dòng)的盤子數(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日，星期四

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

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

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

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

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

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

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

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

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

哲學(xué)家共餐問題

第23頁，共47頁，2023年，2月20日，星期四哲學(xué)家的生活進(jìn)程思考問題餓了停止思考，左手拿一支筷子（拿不到就等）右手拿一支筷子（拿不到就等）進(jìn)餐放右手筷子放左手筷子重新回到思考問題的狀態(tài)1第24頁，共47頁，2023年，2月20日，星期四哲學(xué)家的生活進(jìn)程的極端情況：當(dāng)所有哲學(xué)家都同時(shí)拿起左手筷子時(shí)，則所有哲學(xué)家都拿不到右手的筷子，并處于等待狀態(tài)，則哲學(xué)家將都無法進(jìn)餐，最終餓死；改變進(jìn)程，如拿不到右手筷子則放下左手筷子。在某一瞬可能所有的哲學(xué)家都拿起左手的筷子，因拿不到右手的筷子又都同時(shí)放下左手的筷子，如此下去，所有的哲學(xué)家同樣無法進(jìn)餐。哲學(xué)家進(jìn)餐問題在計(jì)算機(jī)科學(xué)中所反映的問題：程序并發(fā)執(zhí)行時(shí)進(jìn)程同步的問題：死鎖（Deadlock）和饑餓（Starvation）為了提高系統(tǒng)的處理能力和機(jī)器的利用率，并法程序被廣泛地使用，因此必須徹底解決并發(fā)進(jìn)程中的死鎖和饑餓問題第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，簡(jiǎn)稱TSP）是威廉·哈密爾頓（W.R.Hamilton）爵士和英國數(shù)學(xué)家克克曼（T.P.Kirkman）于19世紀(jì)初提出的一個(gè)數(shù)學(xué)問題。這是一個(gè)典型的NP完全性問題。其大意是：有若干個(gè)城市，任何兩個(gè)城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)，必須經(jīng)過每一個(gè)城市且只能在每個(gè)城市逗留一次，最后回到原出發(fā)城市。問如何事先確定好一條最短的路線，使其旅行的費(fèi)用最少。第30頁，共47頁，2023年，2月20日，星期四

人們?cè)诳紤]解決這個(gè)問題時(shí)，一般首先想到的最原始的一種方法是：列出每一條可供選擇的路線（即對(duì)給定的城市進(jìn)行排列組合），計(jì)算出每條路線的總里程，最后從中選出一條最短的路線。假設(shè)現(xiàn)在給定的4個(gè)城市分別為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í)，那么組合路徑數(shù)則為（n-1）！。很顯然，當(dāng)城市數(shù)目不多時(shí)要找到最短距離的路線并不難，但隨著城市數(shù)目的不斷增大，組合路線數(shù)將呈指數(shù)級(jí)急劇增長(zhǎng)，以至達(dá)到無法計(jì)算的地步，這就是所謂的“組合爆炸問題”。假設(shè)現(xiàn)在城市的數(shù)目增為20個(gè)，組合路徑數(shù)則為（20-1）！≈1.216×1017，如此龐大的組合數(shù)目，若計(jì)算機(jī)以每秒檢索1000萬條路線的速度計(jì)算，也需要花上386年的時(shí)間。第33頁，共47頁，2023年，2月20日，星期四

圖靈測(cè)試問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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