实例介绍
【实例简介】
计算理论复习总结,但是考试快要结束了，估计大家也没有什么需要了。
28.文法是CFG的推广,任何CFG都是文法。G=(V,∑,R,S) 29.语言被文法生成ⅲ它是re的。 30.所有数值函数都是原始递归的 31.原始递归函数集是递归可枚举的。 32.特殊语言/问题 H={"M"w":M在w上停机} lH={"M"w":M是一台在"w"上不停机的TM} H1={"M":M在“M”上停机} H1={w:要么w不是一台TM的编码, 要么w是M的编码,M是一台在"M"上不停机的TM} H:re.;H1:re.;-H,-H1:非r.e.;2-SAT∈P;SAT∈NP The world as We Dont Know it re Asumming P≠AP Co『e H recursive SAT SAT CO-A伊 II Asumming P=Np r, e Co-r.e recursive NP= cO-Np= p 33没有算法的问题称作不可判定的or不可解的,如TM的停机问题 34.证明不可判定通用图灵机U通过递归函数归约到L如果L是递归的则U是递归的 ic若L1非递归,并存在L1到L2的归约,则L2也非递归。 递归函数是 Turing Computable的 35.语言是图灵可枚举的,证存在枚举它的图灵机。(M通过空格代开始,周期性的经过特 殊状态q来枚举L,任意顺序且可重复) 6.不可判定语言与递归语言互为补集,与rc语言有交集。 37语言是re.,if它是图灵可枚举的;语言是递归的,i它是以字典序 turing可枚举的。 8.P在并交连接和补运算下封闭NP在并、连接运算下封闭。若NP在补下封闭则NP=P 39.H={M"wM在最多2w步后停机}唾P 40.所有正则语言和所有CFL都属于P 41.NP A.机器角度去定义:被多项式界限非确定型图灵机判定的所有语言的类。 B.基于 verifier的定义:NP问题上建立的非确定机包含两步 1)非确定地猜一个解 2〕用一个确定的算法判定该解是否为可行解 判定一个给定猜测值是否满足该问题(可满足性)的算法称作 verifier,一个问题称作NP 问题当且仅当存在一个多项式时间的 verifier 这两个定义是不矛盾的,因为如果一台非确定TM在多项式时间内可以判定一个非确定 选择的翰入是否满足,就是基于 verifier的定义。 P和NP的区别 a problem is in P if we can decide them in polynomial time. It is in NP if we can decide them in polynomial time, if we are given the right certificate 42.若存在计算函数f的多项式界限的图灵机M,则f称为多项式时间可计算的 43.若τ1是L1->l2的多项式归约,τ2是L2->I3的多项式归约,则τ1τ2是L1->l3的多项 式归约 44.证明NP完全 法一、按定义:LΣ*,若 (a)L∈NP,且 (b)对每个语言L∈NP,存在从L到L的多项式归约 则L称为NP完全的。 法二、归约,对于语言L, (a)若L∈NP (b)一个NP完全问题可以在多项式时间规约到L,ie. SAT <nL 则L称为NP完全的 45.L是NP完全语言,则P=NP,ifL∈P 46.SAT是 NP-complete,3-SAT,最大可满足性也是NP完全的 47.覆盖问题, Hamilton圈〔有向无向),旅行商问题,背包问题都是NP- complete 48. a*b*c*-anbncn, n >0 is context-free but not regular 49.L=L1L2,L是CFL,则L1一定是CFL(x 50. Regular-CFL不一定是CFL,如a*b*c*-anbn包含 anben 51. 2-way PDalie PDa whose input heads can move both left and right] are more powerful than 1-way pda 52. Given a PDa M1 and an fa M2, the problem l(M1)cl(M2)is decidable 53.DFA/NFA识别的是 exactly正则语言 54.Re.只在补和差下不封闭,CFL在交下也不封闭 55.非正则语言的可能是正则语言。比如A:[W=w}及所有回文,A=*,为正则语言 56.典型非正则:w=wR 57.正则语言的子集可能非正则,如 anben是a*b*c*的子集;又如Σ*是正则语言,H≌Σ* 58.归约:X到Y的归约可以理解为X到Y问题的映射, reduction可以解释为 at least as difficult as….比如ⅹ可以被Y的算法解决,则 X is no more difficult than yⅩ可以约到 Y,记X≤Y。e.gx2可以归约到任意两数的乘积。 若有A≤B, A是不可判定问题>B不可判定A不递归->B不递归 B可判定>A可判定 B是递归的->A是递归的 59.若X多项式时间归约到Y,Y多项式时间可解,则X多项式时间可解 若X多项式时间归约到Y,Ⅹ多项式时间不可解,则Y多项式时间不可解 60.X多项式时间归约到Y,Y多项式时间归约到Z,则X多项式时间归约到Z 61.PRME( COMPOSITE)多项式时间归约到 Factor,但是 Factor多项式时间不能归约到 PRIME COMPOSITE )o 62.若A≤PB,B∈NP,则A∈NP。 证明 A≤PB→存在确定图灵机X,可将A归约到B。 B∈NP→存在一个非确定图灵机N可判定B。 我们希望构造一个新的TM(ⅹN)是的ⅹ*N非确定多项式时间求解A,则A∈NP Running time of X*N≤1+p(m<A>B>+qp(m)(B多项式时间非确定判定是多项式时间 所以A∈NP 63若AsPB,B∈P,则A∈P 64.若X是NPC的,则X在多项式时间内可解ifP=NP 65.SAT多项式时间归约到3SA(3AT是NPC的) 66.证明语言L是R/Re, Non re a) Intuitively想想有没有半判定(判定)的TM,有则Rc、(R)。若非R执行下一步。 b)用能否由Re.( Non re.)语言归约到该语言,能则Re而非R( Non re) 严格用归约函数定义f:A≤B,r1∈A当且仅当r1∈B eg1<M,w>∈H,M∈L证明Re cg2<Mw>∈非H,iM∈L证明 Non rc 注意方向:是从A的实例经过递归函数推向B的实例。 详细介绍http://www.cs.rice.edu/nakhleh/comp481/finalreviewsp06sol.pdf 67.递归与μ递归等价 68.PDA中,若每一个格局至多有一个格局接在它后面,则为确定型的。确定型CF在补下 封闭 69.M半判定L:w∈L,ifM在w上停机,注意半判定图灵机中不存在“拒绝”状态。只 要不接受w,就不停机。 70. Chomsky hierarchy Elements of the Chomsky Hierarchy Recursively enumerable languages Recursive language Context sensitive languages Context ee languages eterministc context free languages Regular anguages 71.俩证明 7.6证明P在并、交、 Kleene*连接和补运算下封闭 (1)并: 对任意L,LEP,遴n时间图灵机M1和nb时间图灵机M2判定它们且c=max{ab} 对L1L2构造判定器M M=“对于输入字符串w 1)在W上运行M1,在w上运行M2 2)若有一个接受则接受,否则拒绝。 时间复杂度:设M1为0(n)M2为0(m)。令c=max{ab} 第一步用时0(n+n),因此总时间为Oma+n)=0(n9 所以L1L2属于P类,即P在并的运算下封闭。 (2)连接 对任意L1,L2属于P类,设有n时间图灵机M1和m时间图灵机M2判定它们,且 c=max{ab}。对L1l2构造判定器M M=“对于输入字符串w=w2灬,Wn 对k=0,1,21…,n重复下列步骤。 在wW2…wk上运行M1,在wk1wk+2…n上运行M 若都接受,则接受。否则继续。 若对所有分法都不接受则拒绝。 时间复杂度:(n+1x0(n+0m-0(m+4)+0(nb+4=0(nc+),F以L1oL2属于P类,即 P在连接的运算下封闭。 对任意L属于P类,设有时间0(n)判定器M判定它,对构造判定器M M=“对于输入字符串 〔1)在w上运行M1 2)若M1接受则拒绝,若M1拒绝则接受。 时间复杂度为:0(m)。所以属于P类,即P在补的运算下封闭。 77证明NP在并和连接运算下封闭。 1)并 对任意L1,L2∈NP,设分别有n时间非确定图灵机M1和n时间非确定图灵机M2判定它 们,且c=max{a,b}。 构造判定LL2的非确定图灵机M: M=“对于输入字符串w 1)在W上运行M1,在w上运行M2。 2)若有一个接受则接受,否则拒绝。 对于每一个非确定计算分支,第一步用时为O(n-)+O(n),因此总时间为On+n)=0(n。所 以LLz∈NP,即NP在并的运算下封闭 2)连接 对任意L,L2∈NP设分别有na时间非确定图灵机M1和m时间非确定图灵机M2判定它 们,且c=max{ab}。 构造判定L1oL2的非确定图灵机M: M=“对于输入字符串w: 1〕非确定地将分成两段xy,使得w=xy。 2)在x上运行M1,在y上运行M2 3)若都接受则接受,否则拒绝。 对于每一个非确定计算分支,第一步用时O(n,第二步用时为0(n)+0(m),因此总时 间为o(n+m)=0(n。所以L1oL2∈NP,即NP在连接运算下封闭。 专题一一图灵机可判定性问题 判定以下问题是否可判定: 声明:思路—想证明B问题不可解, 1.从一个不可解问题A入手(如停机问题) 2.创建B的—个实例,从中推出如果能解决B,A也就可以解决了 3.所以B是不可解的 1.一个图灵机有至少481个状态。<YFS> 我们可以给出这样一个TMN进行cnc(M) a)数M中状态数,直到481 b)如果达到了481,N就接受,否则拒绝 2.给定图灵机在空串上走了481步还没停机。<YES> 构造2带图灵机N, a)2a带:写481个0 b)1s带在空串上模拟M,每走一步,第2带就删掉一个0 c)如果M在所有0都删掉之后停机,则N接受,否则不接受 给定图灵机,判定它是否在一些输入上经过481步还没停机?<YES> a)按字典序找出所有 length<=481的串x b)在每个x上面runM,看是否在481步以内停机 是则接受,否则 reject 4.给定图灵机,判定在所有输入上是否经过481步还没停机?<YES> a)原因同(3)类似 【实例截图】
【核心代码】
计算理论复习总结,但是考试快要结束了，估计大家也没有什么需要了。
28.文法是CFG的推广,任何CFG都是文法。G=(V,∑,R,S) 29.语言被文法生成ⅲ它是re的。 30.所有数值函数都是原始递归的 31.原始递归函数集是递归可枚举的。 32.特殊语言/问题 H={"M"w":M在w上停机} lH={"M"w":M是一台在"w"上不停机的TM} H1={"M":M在“M”上停机} H1={w:要么w不是一台TM的编码, 要么w是M的编码,M是一台在"M"上不停机的TM} H:re.;H1:re.;-H,-H1:非r.e.;2-SAT∈P;SAT∈NP The world as We Dont Know it re Asumming P≠AP Co『e H recursive SAT SAT CO-A伊 II Asumming P=Np r, e Co-r.e recursive NP= cO-Np= p 33没有算法的问题称作不可判定的or不可解的,如TM的停机问题 34.证明不可判定通用图灵机U通过递归函数归约到L如果L是递归的则U是递归的 ic若L1非递归,并存在L1到L2的归约,则L2也非递归。 递归函数是 Turing Computable的 35.语言是图灵可枚举的,证存在枚举它的图灵机。(M通过空格代开始,周期性的经过特 殊状态q来枚举L,任意顺序且可重复) 6.不可判定语言与递归语言互为补集,与rc语言有交集。 37语言是re.,if它是图灵可枚举的;语言是递归的,i它是以字典序 turing可枚举的。 8.P在并交连接和补运算下封闭NP在并、连接运算下封闭。若NP在补下封闭则NP=P 39.H={M"wM在最多2w步后停机}唾P 40.所有正则语言和所有CFL都属于P 41.NP A.机器角度去定义:被多项式界限非确定型图灵机判定的所有语言的类。 B.基于 verifier的定义:NP问题上建立的非确定机包含两步 1)非确定地猜一个解 2〕用一个确定的算法判定该解是否为可行解 判定一个给定猜测值是否满足该问题(可满足性)的算法称作 verifier,一个问题称作NP 问题当且仅当存在一个多项式时间的 verifier 这两个定义是不矛盾的,因为如果一台非确定TM在多项式时间内可以判定一个非确定 选择的翰入是否满足,就是基于 verifier的定义。 P和NP的区别 a problem is in P if we can decide them in polynomial time. It is in NP if we can decide them in polynomial time, if we are given the right certificate 42.若存在计算函数f的多项式界限的图灵机M,则f称为多项式时间可计算的 43.若τ1是L1->l2的多项式归约,τ2是L2->I3的多项式归约,则τ1τ2是L1->l3的多项 式归约 44.证明NP完全 法一、按定义:LΣ*,若 (a)L∈NP,且 (b)对每个语言L∈NP,存在从L到L的多项式归约 则L称为NP完全的。 法二、归约,对于语言L, (a)若L∈NP (b)一个NP完全问题可以在多项式时间规约到L,ie. SAT <nL 则L称为NP完全的 45.L是NP完全语言,则P=NP,ifL∈P 46.SAT是 NP-complete,3-SAT,最大可满足性也是NP完全的 47.覆盖问题, Hamilton圈〔有向无向),旅行商问题,背包问题都是NP- complete 48. a*b*c*-anbncn, n >0 is context-free but not regular 49.L=L1L2,L是CFL,则L1一定是CFL(x 50. Regular-CFL不一定是CFL,如a*b*c*-anbn包含 anben 51. 2-way PDalie PDa whose input heads can move both left and right] are more powerful than 1-way pda 52. Given a PDa M1 and an fa M2, the problem l(M1)cl(M2)is decidable 53.DFA/NFA识别的是 exactly正则语言 54.Re.只在补和差下不封闭,CFL在交下也不封闭 55.非正则语言的可能是正则语言。比如A:[W=w}及所有回文,A=*,为正则语言 56.典型非正则:w=wR 57.正则语言的子集可能非正则,如 anben是a*b*c*的子集;又如Σ*是正则语言,H≌Σ* 58.归约:X到Y的归约可以理解为X到Y问题的映射, reduction可以解释为 at least as difficult as….比如ⅹ可以被Y的算法解决,则 X is no more difficult than yⅩ可以约到 Y,记X≤Y。e.gx2可以归约到任意两数的乘积。 若有A≤B, A是不可判定问题>B不可判定A不递归->B不递归 B可判定>A可判定 B是递归的->A是递归的 59.若X多项式时间归约到Y,Y多项式时间可解,则X多项式时间可解 若X多项式时间归约到Y,Ⅹ多项式时间不可解,则Y多项式时间不可解 60.X多项式时间归约到Y,Y多项式时间归约到Z,则X多项式时间归约到Z 61.PRME( COMPOSITE)多项式时间归约到 Factor,但是 Factor多项式时间不能归约到 PRIME COMPOSITE )o 62.若A≤PB,B∈NP,则A∈NP。 证明 A≤PB→存在确定图灵机X,可将A归约到B。 B∈NP→存在一个非确定图灵机N可判定B。 我们希望构造一个新的TM(ⅹN)是的ⅹ*N非确定多项式时间求解A,则A∈NP Running time of X*N≤1+p(m<A>B>+qp(m)(B多项式时间非确定判定是多项式时间 所以A∈NP 63若AsPB,B∈P,则A∈P 64.若X是NPC的,则X在多项式时间内可解ifP=NP 65.SAT多项式时间归约到3SA(3AT是NPC的) 66.证明语言L是R/Re, Non re a) Intuitively想想有没有半判定(判定)的TM,有则Rc、(R)。若非R执行下一步。 b)用能否由Re.( Non re.)语言归约到该语言,能则Re而非R( Non re) 严格用归约函数定义f:A≤B,r1∈A当且仅当r1∈B eg1<M,w>∈H,M∈L证明Re cg2<Mw>∈非H,iM∈L证明 Non rc 注意方向:是从A的实例经过递归函数推向B的实例。 详细介绍http://www.cs.rice.edu/nakhleh/comp481/finalreviewsp06sol.pdf 67.递归与μ递归等价 68.PDA中,若每一个格局至多有一个格局接在它后面,则为确定型的。确定型CF在补下 封闭 69.M半判定L:w∈L,ifM在w上停机,注意半判定图灵机中不存在“拒绝”状态。只 要不接受w,就不停机。 70. Chomsky hierarchy Elements of the Chomsky Hierarchy Recursively enumerable languages Recursive language Context sensitive languages Context ee languages eterministc context free languages Regular anguages 71.俩证明 7.6证明P在并、交、 Kleene*连接和补运算下封闭 (1)并: 对任意L,LEP,遴n时间图灵机M1和nb时间图灵机M2判定它们且c=max{ab} 对L1L2构造判定器M M=“对于输入字符串w 1)在W上运行M1,在w上运行M2 2)若有一个接受则接受,否则拒绝。 时间复杂度:设M1为0(n)M2为0(m)。令c=max{ab} 第一步用时0(n+n),因此总时间为Oma+n)=0(n9 所以L1L2属于P类,即P在并的运算下封闭。 (2)连接 对任意L1,L2属于P类,设有n时间图灵机M1和m时间图灵机M2判定它们,且 c=max{ab}。对L1l2构造判定器M M=“对于输入字符串w=w2灬,Wn 对k=0,1,21…,n重复下列步骤。 在wW2…wk上运行M1,在wk1wk+2…n上运行M 若都接受,则接受。否则继续。 若对所有分法都不接受则拒绝。 时间复杂度:(n+1x0(n+0m-0(m+4)+0(nb+4=0(nc+),F以L1oL2属于P类,即 P在连接的运算下封闭。 对任意L属于P类,设有时间0(n)判定器M判定它,对构造判定器M M=“对于输入字符串 〔1)在w上运行M1 2)若M1接受则拒绝,若M1拒绝则接受。 时间复杂度为:0(m)。所以属于P类,即P在补的运算下封闭。 77证明NP在并和连接运算下封闭。 1)并 对任意L1,L2∈NP,设分别有n时间非确定图灵机M1和n时间非确定图灵机M2判定它 们,且c=max{a,b}。 构造判定LL2的非确定图灵机M: M=“对于输入字符串w 1)在W上运行M1,在w上运行M2。 2)若有一个接受则接受,否则拒绝。 对于每一个非确定计算分支,第一步用时为O(n-)+O(n),因此总时间为On+n)=0(n。所 以LLz∈NP,即NP在并的运算下封闭 2)连接 对任意L,L2∈NP设分别有na时间非确定图灵机M1和m时间非确定图灵机M2判定它 们,且c=max{ab}。 构造判定L1oL2的非确定图灵机M: M=“对于输入字符串w: 1〕非确定地将分成两段xy,使得w=xy。 2)在x上运行M1,在y上运行M2 3)若都接受则接受,否则拒绝。 对于每一个非确定计算分支,第一步用时O(n,第二步用时为0(n)+0(m),因此总时 间为o(n+m)=0(n。所以L1oL2∈NP,即NP在连接运算下封闭。 专题一一图灵机可判定性问题 判定以下问题是否可判定: 声明:思路—想证明B问题不可解, 1.从一个不可解问题A入手(如停机问题) 2.创建B的—个实例,从中推出如果能解决B,A也就可以解决了 3.所以B是不可解的 1.一个图灵机有至少481个状态。<YFS> 我们可以给出这样一个TMN进行cnc(M) a)数M中状态数,直到481 b)如果达到了481,N就接受,否则拒绝 2.给定图灵机在空串上走了481步还没停机。<YES> 构造2带图灵机N, a)2a带:写481个0 b)1s带在空串上模拟M,每走一步,第2带就删掉一个0 c)如果M在所有0都删掉之后停机,则N接受,否则不接受 给定图灵机,判定它是否在一些输入上经过481步还没停机?<YES> a)按字典序找出所有 length<=481的串x b)在每个x上面runM,看是否在481步以内停机 是则接受,否则 reject 4.给定图灵机,判定在所有输入上是否经过481步还没停机?<YES> a)原因同(3)类似 【实例截图】
【核心代码】
标签：
好例子网口号：伸出你的我的手 — 分享！
相关软件
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论