中文XML论坛--北京大学计算机系“理论计算机科学基础”2006年期末试题 zz

贴子主题：北京大学计算机系“理论计算机科学基础”2006年期末试题 zz

举报打印推荐 IE收藏夹

本主题类别:

（每题10分，共60分）

1.语言L={x|x=xR, x属于{0,1}* } 其中xR是x的倒转
(1)证明：L不是正则语言
(2)证明：L是上下文无关语言

2.A={<M,x>|TM M接受x}
(1)证明A是可识别的
(2)证明A不是可判定的

3.任意举出两个PSPACE完全的语言A，B
  A={   |      }
  B={   |      }
  构造A到B的映射规约证明并分析代价

4.两个问题：
对于一个有向图，求出两点间最长路径
对于一个有向图，求出两点间最短路径

  (1)将两个问题转化为数学语言
  A={   |      }
  B={   |      }

  (2)对于A
     I.属于哪个复杂性类
     II.证明之
     III.证明是这个复杂性类完全的

  (3)对于B
     I.属于哪个复杂性类
     II.证明之
     III.证明是这个复杂性类完全的

5.判断以下十句话是正确的(打对号),错误的(打X),还是未知正确性(打?)

P=NP
P=EXPTIME
coNP=NP
coNL=NL
NL=PSPACE
PSPACE=NPSPACE
P=PSPACE
TIME(2^n)=TIME(3^n)
其他2个忘了，和这些都差不多

6.将以下各种类的关系用哈斯图表示出来
L,NL,coNL,P,NP,coNP,PSPACE,NPSPACE,EXPTIME,SPACE((logn)^2)

*树形目录（最近20个回帖）	顶端
主题：北京大学计算机系“理论计算机科学基础”2006年期末试题 zz(946字) － Logician，2006年6月20日
回复：第一题的解答,以下说明中的 x(n)表示n个x的连接.(1) 证明: 假设语言L是正则语言, 现..(2143字) － yneversky，2007年1月24日
回复：第一题，即证明{0,1}*中的回文字符串(1)不是正则语言，(2)而是上下文无关语言..(80字) － yneversky，2007年1月24日
回复：看不懂题目,说的是什么,谁能给个参考答案(38字) － suiyun0234，2006年8月29日
回复：貌似是很基本的东西。(20字) － galois，2006年8月21日
回复：编译原理啊?(11字) － w84u，2006年7月26日
回复：我一道都不会做(14字) － coolhunter，2006年7月5日

*树形目录（最近20个回帖）

主题：

回复：

回复：

回复：

回复：

貌似是很基本的东西。(20字) － galois，2006年8月21日

回复：

编译原理啊?(11字) － w84u，2006年7月26日

回复：

我一道都不会做(14字) － coolhunter，2006年7月5日


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	398.438ms