浙江大學(xué)研究生計(jì)算理論11年真題及答案

1、這是我們（32舍388）參考老師的課堂內(nèi)容整理的11年的答案，附帶解析。由于時(shí)間倉促，錯(cuò)誤必定不少，請(qǐng)各位見諒并吐槽指正。G版(a) F 不一定。因?yàn)榧僭O(shè)A是*，B是M在“M”上不停機(jī)，符合題目要求，B不是可判定的。(b) T 如果A可以歸約到B，根據(jù)歸約的定義，xA的時(shí)候t(x)B，反之，xA，即xA的補(bǔ)的時(shí)候t(x)B，即t(x)B的補(bǔ)。(c) F 因?yàn)镈FA總有停機(jī)的時(shí)候，對(duì)于一個(gè)DFA輸入“M”，這個(gè)DFA總會(huì)讀完所有的字符然后給出yes或者no，因此這個(gè)語言是遞歸的。老師課堂上說DDFA是非正則的，這是可以用對(duì)角化定理證明DDFA和每個(gè)正則語言都不一樣，證明和課本165頁中間的相似。

2、(d) T 這個(gè)非遞歸可枚舉的語言就是課本164下面那個(gè)H1的補(bǔ)，M在“M”上不停機(jī)(e) T He可以用通用圖靈機(jī)半判定，但是無法判定。停機(jī)問題，即圖靈機(jī)M在某個(gè)輸入w上是否停機(jī)，無法判定，這里讓w=e即可。(f) F 根據(jù)定理5.4.1，因?yàn)镠不是遞歸的，所以L也不遞歸了。因?yàn)镠L補(bǔ)，所以H補(bǔ)L。如果L是遞歸可枚舉的，那么H補(bǔ)也是遞歸可枚舉，那么H就不是遞歸可枚舉的了，這和H本身是遞歸可枚舉的事實(shí)是相悖的，因此L不是遞歸可枚舉的。(g) T 假設(shè)M1半判定A，M2半判定B，M3半判定AB的補(bǔ)。對(duì)于輸入w，交給M1、M2和M3一起做。如果M1接受，那么wA，M2接受，那么wB，如果M3接受，

3、那么w(AB)，即不是A也不是B。因?yàn)锳和B是不相交的，因此M1、M2和M3的合體可以判定A或者B，因此A和B都是可判定的，遞歸的。(h) T 后面的是NTIME，應(yīng)該是不確定性計(jì)算的所需時(shí)間。所以，我們把nk看作一體的，稱為a，那么確定計(jì)算時(shí)間是指數(shù)ca，非確定計(jì)算只要a，也就是nk了。(i) T B是P，A可以多項(xiàng)式時(shí)間歸約到B，所以A也是P，P對(duì)補(bǔ)封閉，所以命題正確。(j) F 假設(shè)A是這樣一個(gè)問題，給定一個(gè)整數(shù)集合和整數(shù)k，求是否存在k個(gè)元素和大于C。直觀看我們可以用隨機(jī)抽取k個(gè)元素然后算和然后如果其中一次大于C就接受。但是我們也可以通過，例如多項(xiàng)式時(shí)間的冒泡排序，把集合的整數(shù)降序排序

4、，歸約到問題B，前k個(gè)元素的和是否大于C，顯然B是P的。所以，只能說如果B是NP的，A可以歸約到B，那么A也是NP的。(k) T 這個(gè)表述有點(diǎn)糾結(jié)，我們尚且給個(gè)T。因?yàn)镹PC是可計(jì)算的，有算法可解的，是遞歸的，當(dāng)然也是遞歸可枚舉的。(l) F 我們直觀點(diǎn)看，NPC是所有NP問題都可以多項(xiàng)式歸約到的問題，如果命題是正確的，那么NP=NPC了，所有NP問題都可以歸約到任意一個(gè)NP問題上。如果這樣，數(shù)學(xué)家不用花那么多精力尋找更多的NPC問題了。所以這么看命題是錯(cuò)誤的。其實(shí)這個(gè)題目應(yīng)該是個(gè)陷進(jìn)，把L和SAT的位置換一下就對(duì)了。解析：是正則的。因?yàn)檫@相當(dāng)于要求xy中a的個(gè)數(shù)是偶數(shù)就可以了，所以可以構(gòu)造D

5、FA來接受。解析：非正則?？梢杂帽枚ɡ碜C明。解析：其實(shí)這是正則的，只有首尾字母不同并且長度是偶數(shù)就可以了。G=（V，R，S）V=a，b，S，S1，S2=a，bR=下推自動(dòng)機(jī)M=（K，s，F(xiàn)）K=p，q=a，b=a，b，S，S1，S2=(q,a,a),(q,e)(q,b,b),(q,e)S=pF=q好像還是第一次考喬姆斯基范式。生成喬姆斯基范式有三個(gè)階段，把右面是大于2的分解掉，把右面是e的消掉變成右面是1個(gè)的，最后把右面是1個(gè)的消掉實(shí)在是太煩了，還要求閉包，這顯然是給機(jī)器做的通用做法。大家不如用人腦只能直接湊一下吧，反正不是每年?？嫉念}目這是雙帶圖靈機(jī)，字符右上角標(biāo)記表示在第幾條帶操作，諸如a

6、b這樣的表示第一條帶帶頭下是a，第二條的是b。思路是，首先把c前面的內(nèi)容復(fù)制到第二條帶。然后第一條帶帶頭到最左邊，兩條帶同時(shí)移位檢查c前面的內(nèi)容是否對(duì)稱。如果對(duì)稱了，那么檢查后面。圖上的小修改是因?yàn)閚是0也可以，因此要先判斷c后面是不是a，如果是空格那么也是可以的。如果輸入字串的c后面是a，那么把所有a復(fù)制到第二條帶上，然后第一條帶上讀到b的時(shí)候開始檢查a和b的數(shù)量是否相同。解析：composite numbers 就是合數(shù)。（x,y）= (1prime(x)(1prime(y)exp(x+1,y)其中prime(x)就是判斷x是否是質(zhì)數(shù)，exp就是求指數(shù)，是非負(fù)減法。Rem是求余的函數(shù)，eq

7、uals是判斷是否相等的函數(shù)，都是原始遞歸的，所以prime原始遞歸的其中multi是乘法函數(shù)，所以exp也是原始遞歸的。原始遞歸函數(shù)的合成也是原始遞歸的，所以原函數(shù)是原始遞歸的。（a） 設(shè)這個(gè)語言是L，L是遞歸可枚舉但非遞歸的，我們可以用通用圖靈機(jī)M半判定L。為了找到M1和M2都可以停機(jī)的字符串，我們逐輪逐輪來尋找。第一輪，生成w0，然后通用圖靈機(jī)UTM模擬M1和M2在w0上計(jì)算一步。如果都沒有停機(jī)，下一輪。第二輪，生成w1，然后通用圖靈機(jī)UTM模擬M1和M2在w0和w1上計(jì)算兩步。如果都沒有停機(jī)，下一輪。第n輪，生成wn-1，模擬M1和M2在w0到wn-1上計(jì)算n步。木有停機(jī)就下一輪。Wi

8、是按照字典序的*的字符串。因此，如果真的有M1和M2同時(shí)停機(jī)的字符串w的話，那么UTM的模擬最終停止然后接受“M1”“M2”，否則不停機(jī)，因此L是遞歸可枚舉的。這里只是證明了遞歸可枚舉，還沒有證明其不是遞歸的。證明不是遞歸，可以通過把一個(gè)非遞歸的問題歸約到L上，那么L也是非遞歸的。設(shè)He=“M”|圖靈機(jī)M在e上停機(jī)，顯然這是不遞歸的。我們要把L歸約到He上來。考慮圖靈機(jī)C，C啟動(dòng)前木有任何輸入，啟動(dòng)之后首先在帶上面自己寫上“M1”“M2”，只有自己寫上個(gè)w，然后先模擬M1在w上的執(zhí)行，如果停機(jī)了，那么擦掉結(jié)果，再模擬M2在w上的執(zhí)行，如果M1和M2都在w上停機(jī)了，那么顯然，C在e上停機(jī)，否則不

9、停機(jī)。所以，C在空串上停機(jī)當(dāng)且僅當(dāng)M1和M2都在w上停機(jī)。因?yàn)镠e是不可判定的，所以L也是不可判定的。（很繞很惡心，覺得不對(duì)勁的同學(xué)請(qǐng)參看課本上5.4節(jié)定理5.4.2的（b）的、同樣繞同樣惡心的證明。）（b） 設(shè)這個(gè)語言是L1，顯然L1是L的補(bǔ)，L是遞歸可枚舉非遞歸，因此L1不是遞歸可枚舉的。（a） 我們可以設(shè)計(jì)一個(gè)NTM M在多項(xiàng)式時(shí)間之內(nèi)計(jì)算SAT。對(duì)于給定輸入，M首先隨機(jī)生成一串各變量的真值賦值F，然后代入到在O(N)時(shí)間內(nèi)（N為輸入長度）驗(yàn)證F是否滿足每個(gè)子句至少一個(gè)文字為真且至少一個(gè)文字為負(fù)。所以SAT是NP難的。（b） 我們要把3SAT問題多項(xiàng)式時(shí)間歸約到SAT上面。歸約的原始定義

10、，是L1歸約到L2，那么如果xL1當(dāng)且僅當(dāng)t(x)L2。（原諒我們用t替代）因此證明的時(shí)候需要證明當(dāng)和僅當(dāng)。首先是轉(zhuǎn)換t，對(duì)于輸入的3-CNF范式，對(duì)于每個(gè)合取子句，我們這樣轉(zhuǎn)換假設(shè)有n個(gè)析取范式，那么我們?cè)黾觧個(gè)變量zi，b取F，于是得到（上面加一波浪線，各位意淫一下）看下面的答案解析之前，各位哥哥姐姐且聽我等一勸：這題目只占4分，丟卒保車更好。U版（a） F 令y=e，然后整個(gè)語言就成了a，b*，所以是正則的。（b） F 實(shí)在不會(huì)這個(gè)要舉反例，我們都木有想到，各位想到了可以告訴賀劍峰（c） T 可以構(gòu)造一個(gè)PDA來接受。讀到a壓棧，讀到b彈出a或者空棧了壓入b，讀到c彈出b，如果最后?？樟?/p>

11、那么不接受。（d） F 同樣可以構(gòu)造一個(gè)PDA來接受，讀到一個(gè)x的字符壓棧三個(gè)字母，讀到一個(gè)z的字符出棧三個(gè)字母。（e） F PDA同樣有停機(jī)問題，不一定可以停機(jī)，因此不是遞歸的。（f） F 確定型圖靈機(jī)和非確定的都是計(jì)算能力等價(jià)的。（g） T 可以用通用圖靈機(jī)半判定。通用圖靈機(jī)隨機(jī)生成一個(gè)輸入w，然后模擬M(w)，如果接受那么yes，否則就不停機(jī)。（h） T 這句話的意思是，存在非原始遞歸的可計(jì)算函數(shù)，因?yàn)樵歼f歸函數(shù)是遞歸函數(shù)的子集，而遞歸的函數(shù)才是可計(jì)算的函數(shù)，因此表述正確。（i） F 我們可以用有限的字符來對(duì)圖靈機(jī)進(jìn)行編碼，而有限集合的冪集是可數(shù)無窮的，因此圖靈機(jī)的個(gè)數(shù)也是可數(shù)無窮個(gè)。（j） T 語言是遞歸的當(dāng)且僅當(dāng)其本身和其補(bǔ)都是遞歸可枚舉的，因此如果L是遞歸的，那么其本身和其補(bǔ)都是可半判定的。（k） T 課本5.3節(jié)已說明（l） F 和（k）相近，是非遞歸的遞歸可枚舉（a） (aa)*(bb)* (aa)*a(bb)*b(b)根據(jù)泵定理，假設(shè)L2是正則的，存在滿足泵定理的整數(shù)m。對(duì)于wL2，考慮w=amb2ncanb3m，|w|m，令w=xyz，且|xy|m，ye，那么y=ak，顯然xyizL2，所以L2不是正則的。最后得到 101100，中間的格