计算理论2013-12题

2013年试题一．填空题1.语言类P、PSPACE、NP、NPSPACE、EXPTIME之间的关系为（EXPTIMENPSPACEPSPACENPP）。2.产生语言{12n03n|n≥0}的上下文无关文法是（00011|AA）。3.命题“利用递归定理，一个TMM可以得到自己的描述M”是（正确的）。（正确的、错误的）4.命题“A≤MB和BAM含义相同”是（正确的）。（正确的、错误的）5.上下文无关文法为乔姆斯基范式，是指其中的每一个规则具有如下形式（aABCA,）。6.萨维奇定理指出：对于任何函数f:N→R+,其中f(n)≥n,（))(())((2nfSPACEnfNSPACE）7.空间层次定理证明了空间复杂性类不全相同，它们形成一个层次结构，其中（时空界限较大的类比时空界限较小的类）包含更多的语言。8.语言B是NL完全的，如果（1）NLB并且（2）NL中的每个A（对数空间）可规约到B，例如（PATH）是NL完全的。9.如果一个最小化问题的近似算法总能找到不超过最优解k倍的可行解，则称这个算法是（k-优）的。10.根据概率错误，定义RP是多项式时间概率图灵机识别的语言类，其中，不在语言中的输入以概率（1）被拒绝。二．问答题1.说明有穷自动机、正则表达式、下推自动机、图灵机的异同点。2.对于图示的DFAM，回答下列问题，并说明理由（1）?0100,DFAAM是，DFAM接受0100（2）?011,DFAAM否，M不接受011（3）?DFAAM否，输入不完全，因此形式不正确（4）?0100,REXAM否，前半部分不是正则表达式，因此形式不正确（5）?DFAEM否，M的语言非空（6）?,DFAEQMM是，M接受和它自身相同的语言3.非确定性图灵机、概率图灵机和交错式图灵机是如何体现非确定性的？三．构造题1.构造PDA。使其接受语言{0n1n+1|n≥0}。要求给出相应的形式描述和状态转移图。2.构造一个可判定语言A={0n1n0n|n≥0}的图灵机M，并分析该图灵机算法的时间复杂性。q0q1q200110,1四．证明题1.证明P在并、连接和补运算下封闭。NP在并和连接运算下封闭。答案：P在并、链接和补运算下封闭。(1)并：对任意L1,L2P，设有na时间图灵机M1和nb时间图灵机M2判定它们，且c=max{a,b}。对L1L2构造判定器M:M=“对于输入字符串w:1)在w上运行M1，在w上运行M2。2)若有一个接受则接受，否则拒绝。”时间复杂度：设M1为O(na),M2为O(nb)。令c=max{a,b}。第一步用时O(na+nb)，因此总时间为O(na+nb)=O(nc),所以L1L2属于P类，即P在并的运算下封闭。(2)连接：对任意L1,L2属于P类，设有na时间图灵机M1和nb时间图灵机M2判定它们，且c=max{a,b}。对L1L2构造判定器M:M=“对于输入字符串w=w1,w2,…,wn，1)对k=0,1,2,…,n重复下列步骤。2)在w1w2…wk上运行M1，在wk+1wk+2…wn上运行M2。3)若都接受，则接受。否则继续。4)若对所有分法都不接受则拒绝。“时间复杂度：(n+1)×(O(na)+O(nb))=O(na+1)+O(nb+1)=O(nc+1)，所以L1L2属于P类，即P在连接的运算下封闭。(3)补：对任意L1属于P类，设有时间O(na)判定器M1判定它，对1L构造判定器M:M=“对于输入字符串w:(1)在w上运行M1。(2)若M1接受则拒绝，若M1拒绝则接受。”时间复杂度为：O(na)。所以1L属于P类，即P在补的运算下封闭。NP在并和连接运算下封闭(1)并：对任意L1,L2NP，设分别有na时间非确定图灵机M1和nb时间非确定图灵机M2判定它们，且c=max{a,b}。构造判定L1L2的非确定图灵机M:M=“对于输入字符串w:1)在w上运行M1，在w上运行M2。2)若有一个接受则接受，否则拒绝。”对于每一个非确定计算分支，第一步用时为O(na)+O(nb)，因此总时间为O(na+nb)=O(nc)。所以L1L2NP，即NP在并的运算下封闭。(2)连接：对任意L1,L2NP，设分别有na时间非确定图灵机M1和nb时间非确定图灵机M2判定它们，且c=max{a,b}。构造判定L1L2的非确定图灵机M:M=“对于输入字符串w:1)非确定地将分成两段x,y，使得w=xy。2)在x上运行M1，在y上运行M2。3)若都接受则接受，否则拒绝。”对于每一个非确定计算分支，第一步用时O(n),第二步用时为O(na)+O(nb)，因此总时间为O(na+nb)=O(nc)。所以L1L2NP，即NP在连接运算下封闭。2.设T={M|M是一个TM，且每当M接受w时，M也转变w}，证明T是不可判定的。3.证明：CLIQUE是NP完全的。答案：首先证明CLIQUE属于NP下面是CLIQUE的验证机VV=“对输入G,k,c：1）检查c是否是G中k个节点的集合。2）检查G是否包含连接c中结点的所有边。3）若两项检查都通过，则接受；否则，拒绝。”再证明3SAT多项式时间可归约到CLIQUE。（书P168）因为3SAT是NP完全的，所以CLIQUE也是NP完全的。2012年试题一．判断题1.通用电子计算机（基于布尔电路）与图灵机可以互相模拟。（错）2.任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。（对）3.如果一个语言不是图灵可识别的，则其不是图灵可判定的。（对）4.DFA与NFA、PDA与NPDA（非确定下推自动机），TM与NTM在本质上计算能力均相同。（错）5.任何机器都不能自再生。（错）二．填空题1.设M=（Q,,,0q，F）为一台有穷自动机，w=w1w2...wn是一个字符串且其中wi是字母表的成员。如果存在Q中的状态序列r0,r1,...,rn满足（1）r0=0q（2）（11,iiirwr），i=0，...，n-1（3）Frn则M接受w2.对于文法G：aEXPREXPREXPREXPREXPREXPR|||，这个文法可以（2）种方式产生字符串a+a×a。3.BPP是多项式时间的概率图灵机以错误概率（1/3）识别的语言类。4.语言的电路（规模）复杂度是该语言的（极小电路族）的规模复杂度。5.按Kolmogorov理论，不可压缩串看起来就像是（随机抛硬币）得到的串。三．简答题1.论述递归定理定义其在涉及“自引用”计算过程中的重要作用。答：递归定理提供了以任意程序设计语言实现自引用词“这个”的能力。利用这个能力，任何程序设计语言都有引用它自己的描述的能力。递归定理扩展了在构造SELF时使用过得技术，使得一个程序不仅能得到它自己的描述，而且还能用这个描述继续进行计算，而不仅仅将之打印出来。2.尽可能全面描述DFA和NFA的区别和联系。3.论述：为什么对角化方法可以区分可计算与不可计算4.论述空间层次定理的基本思想。四．构造题1.构造识别语言{wwR|w{0,1}*}的PDA，注意wR表示倒写的w。2.构造一个判定语言A={0n1n|n≥0}的图灵机M，并分析该图灵机的时空复杂度。五．证明题1.证明：ATM是不可判定的2.考虑这样的问题：一个双带图灵机，检查在计算任意输入串的过程中，它是否在第二条带上写下一个非空白符，将这个问题形式化为一个语言，并证明它是不可判定的。（P1325.11）证明：设C={M|M是双带TM，当它运行在某输入上时，它在其第二个带上写一个非空白符}。证明ATM可规约到C。为了得到矛盾设TMR可判定C，构造TMS，它用R来判定ATM。S=“对于输入M,w:1）用M和w构造下面的双带TMTw。TW=“对于任何输入：a.在w上用第一个带模拟M。b.若果模拟表明M接受，则在第二个带上写一个非空白符。”2)在TW上运行R，确定Tw是否在第二个带上写了一个非空白符。3）如果R接受，则M接受w，因此接受；否则拒绝。”3.思考下述计划安排问题。有一份期末考试清单F1，...，Fk需要安排时间，以及学生清单S1，...，Sl。每个学生都选择了这些考试的某个子集。必须将这些考试安排到各时段中，使得同一时段中不会有某个学生同时需要参加两门考试。试问，如果只用h个时段，是否存在合乎要求的计划。将这个问题形式化为一个语言，并证明它是NP完全的。（P1837.29）