算法設(shè)計(jì)(第9章計(jì)算復(fù)雜性與NP理論)課件

1、第9章 計(jì)算復(fù)雜性與NP理論9.1 多項(xiàng)式規(guī)約9.2 計(jì)算模型9.3 P和NP類(lèi)問(wèn)題9.4 NP完全問(wèn)題2021/8/171第9章 計(jì)算復(fù)雜性與NP理論9.1 多項(xiàng)式規(guī)約2021/89.1 多項(xiàng)式規(guī)約規(guī)約：如果存在兩個(gè)問(wèn)題Q和Q，對(duì)于Q的任何一個(gè)實(shí)例q，都能找到Q的一個(gè)實(shí)例q，并能夠?qū)的解a轉(zhuǎn)換為q的解a，則稱問(wèn)題Q可以被歸約到問(wèn)題QQQqqaa2021/8/1729.1 多項(xiàng)式規(guī)約規(guī)約：如果存在兩個(gè)問(wèn)題Q和Q，對(duì)于Q的任9.1 多項(xiàng)式規(guī)約規(guī)約：如果存在兩個(gè)問(wèn)題Q和Q，對(duì)于Q的任何一個(gè)實(shí)例q，都能找到Q的一個(gè)實(shí)例q，并能夠?qū)的解a轉(zhuǎn)換為q的解a，則稱問(wèn)題Q可以被歸約到問(wèn)題Q多項(xiàng)式規(guī)約：可在

2、多項(xiàng)式時(shí)間內(nèi)完成的規(guī)約QQqqaa2021/8/1739.1 多項(xiàng)式規(guī)約規(guī)約：如果存在兩個(gè)問(wèn)題Q和Q，對(duì)于Q的任9.1 多項(xiàng)式規(guī)約問(wèn)題示例ax2 + bx + c = 0ax3 + bx2 + cx + d = 02021/8/1749.1 多項(xiàng)式規(guī)約問(wèn)題示例ax2 + bx + c = 0a9.1 多項(xiàng)式規(guī)約問(wèn)題示例G=最大獨(dú)立集G=最小頂點(diǎn)覆蓋V/C是G的最大獨(dú)立集C是G的最小頂點(diǎn)覆蓋2021/8/1759.1 多項(xiàng)式規(guī)約問(wèn)題示例G=G=V/C9.2 計(jì)算模型形式語(yǔ)言與問(wèn)題編碼形式語(yǔ)言: 字母表 是符號(hào)的有限集合，上的語(yǔ)言L是由中的符號(hào)所組成的串的任意集合 = 0,1L1 = 0, 1,

3、10, 11, 100, 101, 110, 111, 1000, 1001L2 = 0, 10, 100, 110, 1000, 1010, 2021/8/1769.2 計(jì)算模型形式語(yǔ)言與問(wèn)題編碼 = 0,1L1 =9.2 計(jì)算模型形式語(yǔ)言與問(wèn)題編碼形式語(yǔ)言: 字母表 是符號(hào)的有限集合，上的語(yǔ)言L是由中的符號(hào)所組成的串的任意集合問(wèn)題編碼：?jiǎn)栴}Q的任意一個(gè)輸入都會(huì)被編碼為一個(gè)二進(jìn)制串s。設(shè)問(wèn)題的輸入集合為I，其編碼就是一個(gè)映射e: I 0,1*2021/8/1779.2 計(jì)算模型形式語(yǔ)言與問(wèn)題編碼2021/8/1779.2 計(jì)算模型形式語(yǔ)言與問(wèn)題編碼形式語(yǔ)言: 字母表 是符號(hào)的有限集合，上的語(yǔ)

4、言L是由中的符號(hào)所組成的串的任意集合問(wèn)題編碼：?jiǎn)栴}Q的任意一個(gè)輸入都會(huì)被編碼為一個(gè)二進(jìn)制串s。設(shè)問(wèn)題的輸入集合為I，其編碼就是一個(gè)映射e: I 0,1*問(wèn)題算法：設(shè)A是問(wèn)題Q的一個(gè)算法，那么A應(yīng)當(dāng)接受輸入s，算法運(yùn)行得到的結(jié)果記為A(s)。當(dāng)Q是一個(gè)判定形式的問(wèn)題，則對(duì)于任意輸入A(s) yes, no2021/8/1789.2 計(jì)算模型形式語(yǔ)言與問(wèn)題編碼2021/8/1789.2 計(jì)算模型圖靈機(jī)在當(dāng)前方格中寫(xiě)入新字符讀寫(xiě)頭左移(L)、右移(R)或不動(dòng)(S)改變狀態(tài)控制器中的當(dāng)前狀態(tài)2021/8/1799.2 計(jì)算模型圖靈機(jī)2021/8/1799.2 計(jì)算模型圖靈機(jī)形式定義：一個(gè)七元組M =

5、(Q, , , b, , q0, F)，其中Q是有限狀態(tài)集，是字母表，是讀寫(xiě)帶上的字符集，b是空白字符(b但b)，: Q QL,R,S是動(dòng)作轉(zhuǎn)移函數(shù)，q0Q是初始狀態(tài)，F(xiàn)Q是終止?fàn)顟B(tài)集。2021/8/17109.2 計(jì)算模型圖靈機(jī)2021/8/17109.2 計(jì)算模型圖靈機(jī)M = (Q, , , b, , q0, F)將輸入符號(hào)串s = a0a1an 依此填在紙帶的第0,1, n號(hào)格子上，讀寫(xiě)頭指向第0號(hào)格子，機(jī)器處于狀態(tài)q0當(dāng)前狀態(tài)qiF則停機(jī)把掃描到的符號(hào)xi傳送到狀態(tài)控制器，控制器再根據(jù)當(dāng)前狀態(tài)qi計(jì)算動(dòng)作轉(zhuǎn)移函數(shù)，并根據(jù)函數(shù)值決定下一步的操作2021/8/17119.2 計(jì)算模型圖靈機(jī)

6、M = (Q, , , b, ,9.2 計(jì)算模型圖靈機(jī)M = (Q, , , b, , q0, F)終止?fàn)顟B(tài)qa表示接受輸入字符串,qr表示拒絕動(dòng)作轉(zhuǎn)移函數(shù)允許是一個(gè)部分函數(shù)，當(dāng)(qi, xi)上無(wú)定義時(shí)也將停機(jī)2021/8/17129.2 計(jì)算模型圖靈機(jī)M = (Q, , , b, ,9.2 計(jì)算模型圖靈機(jī)M = (Q, , , b, , q0, F)問(wèn)題：判斷一個(gè)二進(jìn)制串中有奇數(shù)個(gè)還是偶數(shù)個(gè)1qixiqi+1xi+1動(dòng)作False0FalsebRTrue0TruebRFalse1TruebRTrue1FalsebRFalsebqr0STruebqa1S2021/8/17139.2 計(jì)算模型

7、圖靈機(jī)M = (Q, , , b, ,9.2 計(jì)算模型圖靈機(jī)M = (Q, , , b, , q0, F)k帶圖靈機(jī): Qk Q(L,R,S)k2021/8/17149.2 計(jì)算模型圖靈機(jī)M = (Q, , , b, ,9.2 計(jì)算模型圖靈機(jī)M = (Q, , , b, , q0, F)k帶圖靈機(jī)不確定圖靈機(jī)2021/8/17159.2 計(jì)算模型圖靈機(jī)M = (Q, , , b, ,9.2 計(jì)算模型圖靈機(jī)與可計(jì)算性設(shè)f是一個(gè)函數(shù)，如果能通過(guò)一個(gè)圖靈機(jī)M來(lái)完成f的計(jì)算，則稱f是部分可計(jì)算的；如果M能夠完成f的計(jì)算，且對(duì)于f定義域上的任意一個(gè)輸入s，M都能保證停機(jī)，則稱f是可計(jì)算的，或者說(shuō)f是一個(gè)

8、可計(jì)算函數(shù)。設(shè)L是一個(gè)語(yǔ)言，如果它能夠被一個(gè)圖靈機(jī)M接受，則稱L是一個(gè)遞歸可枚舉語(yǔ)言；如果M能夠接受L，且對(duì)于輸入sL，M都能保證停機(jī)，則稱L是一個(gè)遞歸語(yǔ)言。2021/8/17169.2 計(jì)算模型圖靈機(jī)與可計(jì)算性2021/8/17169.2 計(jì)算模型圖靈機(jī)與可計(jì)算性稱語(yǔ)言L1可被多項(xiàng)式時(shí)間歸約到語(yǔ)言L2，如果存在一個(gè)多項(xiàng)式時(shí)間可計(jì)算的函數(shù)f: 0,1* 0,1*，其對(duì)任意的x 0,1*都有：x L1當(dāng)且僅當(dāng)x L22021/8/17179.2 計(jì)算模型圖靈機(jī)與可計(jì)算性2021/8/17179.2 計(jì)算模型一個(gè)算法就是一個(gè)確定的、對(duì)任意合法輸入都停機(jī)的圖靈機(jī)對(duì)于每個(gè)長(zhǎng)度為n的輸入，如果圖靈機(jī)M在

9、計(jì)算過(guò)程中的讀寫(xiě)頭移動(dòng)次數(shù)不超過(guò)T(n)，則稱M是以T(n)為時(shí)間上界（簡(jiǎn)稱時(shí)間界）的圖靈機(jī)給定一個(gè)問(wèn)題Q，如果存在一個(gè)時(shí)間界為T(mén)(n)的圖靈機(jī)對(duì)其進(jìn)行計(jì)算，則稱Q的時(shí)間復(fù)雜度為T(mén)(n)2021/8/17189.2 計(jì)算模型一個(gè)算法就是一個(gè)確定的、對(duì)任意合法輸入都停機(jī)9.3 P和NP類(lèi)問(wèn)題P類(lèi)問(wèn)題：存在多項(xiàng)式時(shí)間算法的計(jì)算問(wèn)題能夠用確定性圖靈機(jī)在多項(xiàng)式時(shí)間界內(nèi)求解的問(wèn)題稱為P類(lèi)問(wèn)題P = L 0,1*| 存在一個(gè)確定性圖靈機(jī)M能夠在多項(xiàng)式時(shí)間內(nèi)接受LP2021/8/17199.3 P和NP類(lèi)問(wèn)題P類(lèi)問(wèn)題：存在多項(xiàng)式時(shí)間算法的計(jì)算問(wèn)題NP9.3 P和NP類(lèi)問(wèn)題NP類(lèi)問(wèn)題能夠用不確定性圖靈機(jī)在多項(xiàng)式時(shí)間界內(nèi)求解的問(wèn)題稱為NP類(lèi)問(wèn)題NP = L 0,1*| 存在一個(gè)不