资源描述：
《北京大学屈婉玲算法设计与分析最新课件07.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第7章NP完全性主要内容Turing机计算复杂性理论NP完全性理论的基本概念用NP完全性理论分析问题NP难度1Turing机的定义基本模型双向无限带的Turing机M=<=,其中0Q有穷状态集Γ有穷带字符集∑输入字符集∑⊂ΓB空白字符,B∈Γ－∑q初始状态,q∈Q00F终结状态集,F⊂Q,q,q∈FYNδ:(:(Q－F)×Γ→Q×Γ×{LRL,R}状态转移函数Bxxx…xB带123n读写头有限状态控制器FSC2瞬时描述-格局(ID)αqα表示此刻Turing机的FSC处于状态q,读写头指在串α122的第一个字符.例如Turing机M的某时刻的状
2、态转移函数是δ(q,x)=(p,Y,L)i带上的字符串为xx...x...x,读写头指向字符x,则它的12ini瞬间描述是:xx...xqx...xٟxx...xpxYx...x12i-1in12i-2i-1i+1nٟ表示由左边的ID一步达到右边的IDٟ*表示由左边的ID经有限步达到右边的ID3实例设L={0n1n
3、n≥1},设计接受L的Turing机如下:M=0Q={q,q,q,q,q,q},0123YN∑={01}{0,1},Γ={0,1,X,Y,B},F={q,q}YN初始将字符串放在从1到n方格中,FSC处在状态q,读写头0指向方格1.将第
4、一个0改写成X,然后带头向右扫描.遇到第一个1,将1改为Y,然后带头向左扫描.遇到第一个X改为向右扫描.这时进入下一个巡回.每个巡回将一对0和1改为X和Y,直到接受或拒斥停机.4实例（续）转移函数如下01XYBq(q,X,R)qq(q,Y,R)q01NN3Nq(q,0,R)(q,Y,L)q(q,Y,R)q112N1Nq(q,0,L)q(q,X,R)(q,Y,L)q22N02Nqqqq(q,Y,R)q3NNN3Y例如输入0011,TiTuring机动作如下：q0011ٟ1Y0Xqٟ11q0Xٟ011XqٟqX0Y101122ٟXq0Y1ٟXXqY1ٟXXYq1ٟXXqYYٟX
5、qXYY01122ٟXXYYqٟYXXYqٟYYXXqٟXXYYq033Y5Turing机接受语言被M接受的语言记作L(M)，是∑*上的字的集合.当这些字左端对齐方格1放在带上,M处于状态q,M的带0头指向方格1时,经过有限步M将停机在接受状态q,即YL(M)={ω
6、ω∈∑*,∃α,α∈Γ*(qωٟ*αqα)}1201Y2如果字ω不是L(M)中的字,M可以不停机或停机在拒斥状态q.N基本Turing机可以推广为k条带的Turing机DTM.确定型Turing机可以推广到非确定型Turing机NDTM.6基本Turing机的变种单向无限带的Turing机带方格从1开始,向右无
7、限长.其它与基本Turing机相同.多带的Turing机k条双向带,k个读写头,其中k为大于1的常数.初始将输入写在第一条带的方格1到n内.其它带为空.每个读写头扫描一条带,可以改写被扫描方格的字符,读写头然后向左或向右移动一个方格.读写头的动作由FSC的状态及k条带所扫描的k个字符来决定.FSC7实例例1L={wcwR
8、w为0-1字符串},设计接受L的Turing机M1和M,使得M的时间复杂度为O(n),M的空间复杂度为212O(logn).M有2条带,把c左边的w复制到第2条带上.当发现c时第12条带的读写头向左,输入带的读写头向右.比较两个带头的符号,如果符号一样,字
9、符个数一样,M接受x.M至多作11n+1个动作.时间复杂度为n+1.空间复杂度为⎡(n-1)/2⎤+1.M有2条带,第2条带作为二进制的计数器.首先检查输入是2否只有1个c,以及c左边和右边的符号是否一样多.然后逐个比较c左边和右边的字符,用上述计数器找到对应的字符.如果所有的字符都一样,M接受停机.空间复杂度为二进制2的计数器的占用空间,即O(logn).时间复杂度为O(n2).8计算复杂性理论空间和时间复杂度的形式定义确定型Turing机计算复杂度的有关结果带压缩线性加速带数目的减少9确定型Turing机空间复杂度的形式定义$&FSC离线的Turing机M,1条具有端记
10、号的只读输入带,k条半无限存储带.如果对每个长为n的输入串,M在任一条存储带上都至多扫视S(n)个单元,那么称M在最坏情况下的空间复杂度为S(n).10确定型Turing机时间复杂度的形式定义k条双向带的Turing机M,一条带包含输入.如果对于每个长为n的输入串,M在停机前至多做T(n)个动作,那么称M在最坏情况下的时间复杂度为T(n).两条假设：空间复杂性至少需要1时间复杂性至少需要读入输入的时间因此这里作如下规定:对一切n,S(n)≥1,logn是max{1,⎡logn⎤}的缩写.对一切n,T(n)≥n+1,
