計(jì)算理論復(fù)習(xí)

1、計(jì)算理論復(fù)習(xí)題1、什么是圖靈機(jī)，圖靈機(jī)的構(gòu)造技術(shù)以及三種描述方式是什么?圖靈機(jī)：一個(gè)圖靈機(jī)是一個(gè)7元組(Q，I,，q。，qaccept，qreject)，其中Q,都是有窮集合，并且O Q是狀態(tài)集；匕是輸入字母表，不包括特殊空白符號(hào):是字母表，其中，：二廠；O Q'：i Q丨L,R ；Oq Q是起始狀態(tài)；C6 qaccept * Q 是接受狀態(tài)；O7 qreject * Q 是拒絕狀態(tài)，且Cjreject = qaccept。(2) 構(gòu)造技術(shù)：O1有限控制器的存儲(chǔ)構(gòu)造 TM檢查第一個(gè)輸入是不是出現(xiàn)在輸入的其他地方；O多道；O查詢符號(hào)(打標(biāo)記)；O移動(dòng)：如把一個(gè)字符串整體后移 ；O調(diào)用子程

2、序。(3) 描述方式：。1形式描述，即詳盡地寫出圖靈機(jī)的狀態(tài)、轉(zhuǎn)移函數(shù)等，這是最低、最詳細(xì)程度的描述；O 2實(shí)現(xiàn)描述，這種方法使用日常語言來描述圖靈機(jī)的運(yùn)行，如怎么移動(dòng)讀寫 頭，怎么在帶上存儲(chǔ)數(shù)據(jù)等，沒有給出狀態(tài)和轉(zhuǎn)移函數(shù)的細(xì)節(jié)；O 3高水平描述，它也是使用日常語言來描述算法， 但忽略了實(shí)現(xiàn)的模型， 不再需要提及機(jī)器是怎么管理它的帶子或讀 寫頭。2、什么是圖靈機(jī)的格局，圖靈可識(shí)別，圖靈可判定？(1) 圖靈機(jī)計(jì)算過程中，當(dāng)前狀態(tài)、當(dāng)前帶內(nèi)容和讀寫頭當(dāng)前位置組合在一起，稱為圖 靈機(jī)的格局，也即是瞬間狀態(tài)。(2) 如果一個(gè)語言能被某一圖靈機(jī)識(shí)別，則稱該語言是圖靈可識(shí)別的。(3) 如果一個(gè)語言能被某一

3、圖靈機(jī)判定，則稱它是圖靈可判定的。3、什么是多帶圖靈機(jī)，非確定型圖靈機(jī)，枚舉器，遞歸可枚舉語言？(1) 多帶圖靈機(jī)很像普通圖靈機(jī)，只是有多個(gè)帶子，每個(gè)帶子都有自己的讀寫頭，用于讀和寫。開始時(shí)，輸入出現(xiàn)在第一個(gè)帶子上，其它的帶子都是空白。轉(zhuǎn)移函數(shù)改為允許同時(shí)k進(jìn)行讀、寫和移動(dòng)讀寫頭，其形式為：S : Q - k > Q - k此處k是帶子的個(gè)數(shù)。表達(dá)式s ( qi， a1，ak)=( qj， b，bk，l，r,， L)指的是：若機(jī)器處于狀態(tài) qj，讀寫頭1到k所讀的符號(hào)分別是 a1，ak，則轉(zhuǎn)移 到狀態(tài)qj，寫下符號(hào) b，。匕，且按此式所指示的那樣移動(dòng)每個(gè)讀寫頭。推論1：每個(gè)多帶圖靈機(jī)都有

4、一個(gè)與之等價(jià)的單帶圖靈機(jī)。推論2： 一個(gè)語言是圖靈可識(shí)別的，當(dāng)且僅當(dāng)有多帶圖靈機(jī)識(shí)別它。(2) 非確定型圖靈機(jī)：非確定型圖靈機(jī)在計(jì)算的任何時(shí)刻，機(jī)器可以在多種可能性中選擇一種繼續(xù)進(jìn)行。它的轉(zhuǎn)移函數(shù)具有如下形式：s : Q一；3 (Q r L，R, S)其計(jì)算是一棵樹，不同分枝對(duì)應(yīng)著機(jī)器不同的可能性。如果計(jì)算的某個(gè)分枝導(dǎo)致接受狀態(tài)， 則接受該輸入。推論1每個(gè)非確定型圖靈機(jī)都有一個(gè)與之等價(jià)的確定型圖靈機(jī)。推論2: 個(gè)語言的是圖靈可識(shí)別的，當(dāng)且僅當(dāng)有非確定型的圖靈機(jī)識(shí)別它。推論3: 個(gè)語言是可判定的，當(dāng)且僅當(dāng)存在非確定型圖靈機(jī)判定它。(2) 枚舉器：它是圖靈機(jī)的一種變形，是帶有打印機(jī)的圖靈機(jī)。每當(dāng)圖

5、靈機(jī)想在打印序 列中增加一個(gè)串時(shí)，就把串送到打印機(jī)。推論：一個(gè)語言是圖靈可識(shí)別的，當(dāng)且僅當(dāng)有枚舉器枚舉它。(3) 遞歸可枚舉語言：能夠被圖靈機(jī)識(shí)別的語言稱為遞歸可枚舉語言。4、什么是丘奇 -圖靈論題,可判定語言，接受計(jì)算歷史？(1) 丘奇-圖靈論題：丘奇使用 -演算的記號(hào)系統(tǒng)定義算法，圖靈使用機(jī)器定義算法，這兩個(gè)定義是等價(jià)的，算法的非形式概念和精確定義的聯(lián)系被稱為丘奇-圖靈論題，即算法的直接概念等于圖靈機(jī)算法。(2) 可判定語言：如果一個(gè)語言，存在某圖靈機(jī)判定它，則稱這個(gè)語言是圖靈可判定的 或可判定的。(3) 接受計(jì)算歷史：設(shè) M是一個(gè)圖靈機(jī)，.是一個(gè)串。M在 上的一個(gè)接受計(jì)算歷史 是一個(gè)格局

6、序列 G，C|，其中：C是M在，上的起始格局，C|是M的一個(gè)接受格局, 且每個(gè)C都是C的合法結(jié)果。5、判斷下列語言是否可判定，證明其中一個(gè)？注：(i) Atm有時(shí)稱為停機(jī)問題真正的停機(jī)問題是HALTtm(ii) ATM不是圖靈可識(shí)別的。(1) Adfa=：B，IB是DFA, 是串，B接受可判定A；fg =: Gj G是CFG，是串，G派生可判定 HALTtm，Atm = f ： M，- |M是TM，是串，M接受,不可判定(4) Edfa 叫:A |A是DFA，且L(A) -： 可判定Etm 乂: M |M是一個(gè)TM,且L(M)=：不可判定PCP二：P |P是波斯特對(duì)應(yīng)問題的一個(gè)實(shí)例，且 P有匹

7、配不可判定E tm ， REGULAR tm , EQtm，都是不可判定的。(8) AnafB |B是NFA, 是串，B接受可判定(9) Arex = R | R是正則表達(dá)示，是串，R派生可判定(10) EQdfa =- A,B |A和B都是DFA且L(A)二 L(B)可判定(11) Acfg = ：G,l、|G是CFG, 是串，G派生可判定(12) Ecfg =：G |G 是一個(gè) CFG 且 L(G)=_，且 L(A)： 可判定(13) EQcfg = ：G,HG和H是CFG且L(G)二 L(H)不可判定(14) Aba可判定，Elba和ALLcfG不可判定:證明 Atm = M，門，|M是

8、TM，是串，M接受是不可判定的。證明：假設(shè) Atm是可判定的。設(shè) H是 Atm的判定器。令 M是一個(gè)TM，.是一個(gè)串。在 輸入<M,o >上，如果M接受co，則H就停機(jī)且接受怕;如果M不接受3,則H也會(huì)停 機(jī)，但拒絕 。即H是一個(gè)TM使得：接受，如果M接受灼H(<M,C0 >)=丿拒絕，如果M不接受豹現(xiàn)在來構(gòu)造一個(gè)新的圖靈機(jī)D，它以H作為子程序。當(dāng)M被輸入它自己的描述<M>時(shí),TM D就調(diào)用H，以了解M作什么。一旦得到這個(gè)消息，D就反著做，即：如果 M接受，它就拒絕；如果 M不接受，它就接受。下面是D的描述：D= “對(duì)于輸入<M>,其中M是一個(gè)

9、TM :1) 在輸入<M,<M>>上運(yùn)行H。2) 輸入H輸出的相反結(jié)論，即，如果H接受，就拒絕；如果 H拒絕，就接受?！?得出：接受，如果M不接受VM >D(<M>)=丿一拒絕，如果M接受vM >當(dāng)以D的描述<D>作為輸入來運(yùn)行 D自身時(shí)，得到：接受，如果D不接受cD >D(<D>)=一拒絕，如果D接受£D >不論D做什么，它都被迫相反地做，這顯然是一個(gè)矛盾。6、證明一個(gè)語言是可判定的，當(dāng)且僅當(dāng)它既是圖靈可識(shí)別的，也是補(bǔ)圖靈可識(shí)別的。 證明：(i) 必要性：如果 A是可判定的，任何可判定語言都是圖靈可

10、識(shí)別的，且任何可判定語言的補(bǔ)也是可判定的，所以 A和它的補(bǔ)A都是圖靈可識(shí)別的(ii) 充分性：令 M1是A的識(shí)別器，M2是A的識(shí)別器。下列圖靈機(jī) M是A的判定器：M="對(duì)于輸入:1)在輸入上并行運(yùn)行M 1和M 2。并行地運(yùn)行兩個(gè)機(jī)器指地是：M有兩個(gè)帶，一個(gè)模擬 M 1 一個(gè)模擬M 2。此時(shí)，M交替地模擬兩個(gè)機(jī)器的一步。一直持續(xù)到其中之一停機(jī)。現(xiàn)在證明M確實(shí)判定A。任一個(gè)串-要么在A中，要么在 A中。所以，M j和M 2必定有一個(gè)接受因?yàn)橹灰?Mj或M2接受，M就停機(jī)，所以 M總會(huì)停機(jī)，因而是個(gè)判定 器。還有，M接受所有在A中的串，拒絕所有不在 A中的串。故M是A的判定器。因而A 是可

11、判定的。7、什么是線性界限自動(dòng)機(jī)(LBA )，映射可歸約性，可計(jì)算函數(shù)，多項(xiàng)式時(shí)間可歸約性？(1) 線性界限自動(dòng)機(jī)(LBA )是一種受到限制的圖靈機(jī)，它不允許其讀寫頭離開包含輸入的帶區(qū)域。如果此機(jī)器試圖將它的讀寫頭移出輸入的兩個(gè)端點(diǎn)，則讀寫頭就待在原地不動(dòng)。這與普通圖靈機(jī)的讀寫頭不會(huì)離開帶子的左端點(diǎn)的方式是一樣的。(2) 將一個(gè)問題歸約為另一個(gè)問題的概念可以用多種方式來形式定義，選擇使用哪種方法要根據(jù)具體應(yīng)用情況。我們的選擇是一種簡(jiǎn)單方式的可歸約性叫映射可歸約性。語言A是映射可歸約到語言B的，如果存在可計(jì)算函數(shù)f : 2*> 2*使得對(duì)每個(gè)， A二f () B，記A<m B，稱函數(shù)

12、f為A到B的歸約。(3) 可計(jì)算函數(shù)：函數(shù) f: 2* ； 2*是一個(gè)可計(jì)算函數(shù)，如果有某個(gè)圖靈機(jī)M，使得在每個(gè)輸入- 上, M停機(jī)，且此時(shí)只有f.)出現(xiàn)在帶上。(4) 多項(xiàng)式時(shí)間可歸約性：語言 A多項(xiàng)式時(shí)間可歸約到 B,記為AW pB，若存在多項(xiàng) 式時(shí)間可計(jì)算函數(shù) f :二r二 ，對(duì)于每一個(gè) w，有w A= f w 三B，函數(shù)f稱為 A到B的多項(xiàng)式時(shí)間歸約。8、證明如果 A乞m B且B是可判定的，貝U A也是可判定的。注：關(guān)于可歸約性的其它一些類似推論證明見課本130131證明：設(shè)M是B的判定器，f是從A到B的歸約。A的判定器N的描述如下：N="對(duì)于輸入:1) 計(jì)算 f( )。2)

13、 在f( * )上運(yùn)行M，輸出M的輸出?！憋@然，如果A,則fC ) - B，因?yàn)閒是從A到B的歸約。因此，只要A，則M接 受f( )。故N的運(yùn)行正如所求。9、什么是時(shí)間復(fù)雜度， P類，NP類，NP完全性?(1) 時(shí)間復(fù)雜度：令 M是一個(gè)在所有輸入上都停機(jī)的確定型圖靈機(jī)。M的運(yùn)行時(shí)間或者時(shí)間復(fù)雜度，是一個(gè)函數(shù) f : N r N,其中N是非負(fù)整數(shù)集合，f (n)是M在所有長度為n的輸入上運(yùn)行時(shí)所經(jīng)過的最大步數(shù)。若f (n)是M運(yùn)行時(shí)間，則稱 M在時(shí)間f (n)內(nèi)運(yùn)行,M是f (n)時(shí)間圖靈機(jī)。(2) P類是確定型單帶圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)可判定的語言類。換言之，p 二 TIME nkk在理論中，P

14、類扮演核心的角色，它的重要性在于：1)對(duì)于所有與確定型單帶圖靈機(jī)多項(xiàng)式等價(jià)的計(jì)算模型來說，P是不變的；2) P大致對(duì)應(yīng)于在計(jì)算機(jī)上實(shí)際可解的那一類問題。(3) NP是具有多項(xiàng)式時(shí)間驗(yàn)證機(jī)的語言類。(4) NP完全性：如果語言 B滿足下面兩個(gè)條件，就成為NP完全的：(1)B屬于NP，并且(2)NP中的每個(gè)A都多項(xiàng)式時(shí)間可歸約到 B。10、證明3SAT多項(xiàng)式時(shí)間可歸約到 CLIQUE。注：題中涉及的圖見課本 168頁證明：設(shè)是k個(gè)子句的公式，如=(a1 b, c1) (a2 b2 c2).(a3 b3 q)歸約f生成字符串G,k，其中G是如下定義的無向圖。G中的結(jié)點(diǎn)分成k組t1,t2,t3.tk，

15、 每組是三個(gè)結(jié)點(diǎn)的三無組。每個(gè)三元組對(duì)應(yīng)于 '中的一個(gè)子句，三元組中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于相應(yīng)子句的一個(gè)文字。G的每個(gè)結(jié)點(diǎn)用它對(duì)應(yīng)的 中的文字做標(biāo)記。除兩種情形以外，G的邊連接了所有的結(jié)點(diǎn)對(duì)。同一個(gè)三元組內(nèi)的結(jié)點(diǎn)無邊相連，相反標(biāo)記的兩個(gè)結(jié)點(diǎn)無邊相連。要證明原命題，即證 '是可滿足的當(dāng)且僅當(dāng) G有k-團(tuán)。(1)假定 有滿足賦值。在滿 足賦值下，每個(gè)子句中至少一個(gè)文字為真。 在G的每個(gè)三元組中，選擇在該滿足賦值下為真 的文字對(duì)應(yīng)的結(jié)點(diǎn)共 K個(gè)，這K個(gè)結(jié)點(diǎn)形成一個(gè)k團(tuán)。所以G包含k團(tuán)。(2)假定G有k 團(tuán)。因?yàn)樵谕粋€(gè)三元組中的結(jié)點(diǎn)都無邊相連，所以團(tuán)中的任何兩個(gè)結(jié)點(diǎn)都不在同一個(gè)三元組中。因

16、此k個(gè)三元組中的每一個(gè)都恰好包含團(tuán)的一個(gè)結(jié)點(diǎn)。給 '的變量賦真值，使得標(biāo)記團(tuán)結(jié)點(diǎn)的每一個(gè)文字都為真，因?yàn)榫哂邢喾礃?biāo)記的兩個(gè)結(jié)點(diǎn)無邊相連，所以不可能兩個(gè)都在團(tuán)中。給變量的這種賦值滿足，因?yàn)槊總€(gè)三元組包含一個(gè)團(tuán)結(jié)點(diǎn)，所以每個(gè)子句包含一個(gè)賦值為TRUE的文字。 '可滿足。11、VERTEX-COVER(頂點(diǎn)覆蓋)是NP完全的。證明：這里給出一個(gè)從3SAT到VERTEX-COVER 的在多項(xiàng)式時(shí)間內(nèi)運(yùn)算的規(guī)約的細(xì)節(jié)內(nèi)容， 該規(guī)約把布爾公式 '映射為一個(gè)圖G和值k。對(duì)于中的每個(gè)變量x,產(chǎn)生一條連接著兩個(gè) 結(jié)點(diǎn)的邊。把這個(gè)構(gòu)件中的兩個(gè)結(jié)點(diǎn)標(biāo)記為X和X。把x賦值為TRUE對(duì)應(yīng)于頂點(diǎn)覆

17、蓋選擇該邊的左結(jié)點(diǎn)，而賦值為 FALSE對(duì)應(yīng)于右結(jié)點(diǎn)。每個(gè)子句的構(gòu)件使用該子句的三個(gè)文字標(biāo)記的三個(gè)節(jié)點(diǎn)組成的三元組。這三個(gè)節(jié)點(diǎn)互相連接，并且與變量構(gòu)件中間具有相同標(biāo)記的節(jié)點(diǎn)相連接。因此出現(xiàn)在G中的節(jié)點(diǎn)總數(shù)是2m - 31，其中有m個(gè)變量和丨個(gè)子句。令k = m 21 。為證明該規(guī)約滿足要求，需要證明可滿足當(dāng)且僅當(dāng)G有k個(gè)結(jié)點(diǎn)的頂點(diǎn)覆蓋。從一個(gè)滿足賦值開始，首先把變量構(gòu)件中對(duì)于賦值中真文字的結(jié)點(diǎn)放入頂點(diǎn)覆蓋中。然后，在每個(gè)子句中挑選一個(gè)真文字，把每個(gè)子句構(gòu)件中剩下的兩個(gè)結(jié)點(diǎn)放入頂點(diǎn)覆蓋中，現(xiàn)在共有k個(gè)結(jié)點(diǎn)。它們覆蓋所有的邊，因?yàn)轱@然每個(gè)變量構(gòu)件的邊被覆蓋了，在每個(gè)子句構(gòu)件中的所有三條邊也被覆蓋了

18、，所有介于變量構(gòu)件和子句構(gòu)件之間的邊也被覆蓋了。所以G有k個(gè)結(jié)點(diǎn)的頂點(diǎn)覆蓋。其次，如果 G有k個(gè)結(jié)點(diǎn)的頂點(diǎn)覆蓋，通過構(gòu)造滿足賦值來證明是可滿足的。為了覆蓋變量構(gòu)件的邊和子句構(gòu)件的三條邊，頂點(diǎn)覆蓋必須包含每個(gè)變量構(gòu)件的一個(gè)結(jié)點(diǎn)以及每個(gè)子句構(gòu)件中的兩個(gè)結(jié)點(diǎn)。這就占用了全部頂點(diǎn)覆蓋的結(jié)點(diǎn)，沒有剩余的份額。選取變量構(gòu)件中在頂點(diǎn)覆蓋中的結(jié)點(diǎn)，把相應(yīng)的文字賦值為真。這個(gè)賦值滿足 二因?yàn)檫B接變量構(gòu)件和每個(gè)子句構(gòu)件的三條邊都被覆蓋了，而子句構(gòu)件中只有兩個(gè)結(jié)點(diǎn)在頂點(diǎn)覆蓋中，所以其中一條邊必定被變量構(gòu)件中的一個(gè)結(jié)點(diǎn)覆蓋，因此賦值滿足相應(yīng)的子句。12、判斷下列語言所屬類別(P, NP, NP完全)？(1)PATH屬

19、于P類PELPRIME(互素問題)屬于P類(3) CLIQUE屬于NP完全問題和NP類(4) SUBSET_SUM1于NP完全問題和NP類(5) HAMPATH屬于NP完全問題和NP類(6) 每一個(gè)上下文無關(guān)語言(CFL)者是P類的成員(7) SAT，VERTEX-COVERUHAMPAT屬于 NP完全問題和 NP類13、 什么是空間復(fù)雜度，薩維奇定理結(jié)論，PSPACE類，PSPACE完全性，三個(gè) PSPACE完 全性問題例子？(1)空間復(fù)雜度：令 M是一個(gè)在所有輸入上都停機(jī)的確定型圖靈機(jī)。M的空間復(fù)雜度是一個(gè)函數(shù)f : N > N，其中f ( n)是M在任何長為n的輸入上掃描帶方格的最

20、大數(shù)。(2) 薩維奇定理表明確定型機(jī)器可以用非常少的空間模擬非確定型機(jī)器。對(duì)于時(shí)間復(fù)雜性，這種模擬似乎需要指數(shù)倍地增加時(shí)間。對(duì)于空間復(fù)雜性，任何消耗f (n)空間的非確定型TM都可以轉(zhuǎn)變?yōu)閮H消耗 f2(n)空間的確定TM。(3) PSPACE是在確定性圖靈機(jī)上，在多項(xiàng)式空間內(nèi)可判定的語言類，換言之，PSPACE 二 SPACE 門*。k(4) PSPACE完全性：語言 B是PSPACE完全的，若它滿足下面兩個(gè)條件：1)B屬于PSPACEo 2)PSPACE中的每一個(gè)語言 A都多項(xiàng)式時(shí)間可歸約到 B。(5) TQBF , FORMULA-GAME , GG 是 PSPACE 完全的14、什么是 L類,NL類,NL完全性：coNL類?(1) L是確定型圖靈機(jī)在對(duì)數(shù)空間內(nèi)可判定的語言類。換言之，L = SPACE log nNL是非確定型圖靈機(jī)在對(duì)數(shù)空間內(nèi)可判定的語言類。換言之，NL =NSPACEIog n(3) NL完全性：語