文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 浙江大学2006计算理论试题
侵权投诉

浙江大学2006计算理论试题

浙江大学2006计算理论试题

THEORYOFCOMPUTATION

FinalExamSolutionGraduateCourseCollegeofComputerScienceZhejiangUniversityFall2004Class:ID:Name:Score:

Timeallowed:2Hours.

1.(20%)Determinewhetherthefollowingstatementsaretrueorfalse.Ifitistruewritea otherwisea×inthebracketbeforethestatement.(a)( )Everycontext-freelanguageisrecursive.

(b)( )Language{ambncl|m,n,l∈N,m+n>3l}iscontextfree.

(c)( )EverylanguageinNPisrecursive.

(d)(×)Alllanguagesonanalphabetarerecursivelyenumerable.

(e)(×)There’salanguageLsuchthatLisundecidable,yetLanditscomplement

arebothsemi-decidedbysomeTuringmachines.

(f)( )There’safunction suchthat canbecomputedbysomeTuringma-

chines,yet isnotaprimitiverecursivefunction.

(g)(×)LetL1,L2 Σ belanguages,recursivefunctionτisareductionfromL1

toL2,ifL1isdecidable,thensoisL2.

(h)(×)AlanguageLisrecursiveifandonlyifitisTuring-enumerable.

(i)(×)SupposeA,Baretwolanguagesandthereisapolynomial-timereductions

fromAtoB.IfAisNP-complete,thenBisNP-complete.

(j)( )EverylanguageinNP-completecanbereducibletothe3-SATproblem

inpolynomialtime.

2.(20%)FAandregularlanguages:

(a)Decidewhetherthefollowinglanguageisregularornotandprovideaformal

proofforyouranswer.

L={ambn|m,n∈N,(m n)mod3=0}

第1页

你可能喜欢

  • 理论试卷
  • 理论复习
  • 理论答案
  • 理论考试
  • 浙江大学考博
  • 计算复杂性

热门文档

相关文档

  • 2006-2007浙江大学《大学化学基础实验(G)》理论课程试卷

    2006-2007浙江大学《大学化学基础实验(G)》理论课程试卷_化学_自然科学_专业资料。浙江大学2006–2007学年第一学期期末考试 《大学化学基础实验(G) 》理论课程试卷 ...

  • 2006浙江大学控制理论研究生入学考试真题

    2006浙江大学控制理论研究生入学考试真题 隐藏>> 分享到: X 分享到: 使用一键分享,轻松赚取财富值, 了解详情 嵌入播放器: 普通尺寸(450*500pix) 较大尺寸(...

  • 浙江大学考研题(2000-2006)+ 部分答案(00-03)

    浙江大学考研题(2000-2006)+ 部分答案(00-03)_研究...要求: 1、计算两次考试 成绩(X、Y)的相关 2、求...3、特瑞斯曼与布罗德班特的理论对过滤装置的不同看法...

  • 浙江大学2006研究生考试 理论力学

    浙江大学2006研究生考试 理论力学 隐藏>> 分享到: X 分享到: 使用一键分享,轻松赚取财富值, 了解详情 嵌入播放器: 普通尺寸(450*500pix) 较大尺寸(630*50...

  • 2006浙大新闻与传播理论+新闻实务研究考研试题

    浙江大学二 00 六年攻读硕士学位研究生入学考试试题 考试科目___新闻与传播理论 新闻与传播理论___编号 编号___ 考试科目 新闻与传播理论 编号注意:答案必须写在...

  • 浙江大学2006年Java程序设计试卷(含部分答案)

    浙江大学2006年Java程序设计试卷(含部分答案)_工学_高等教育_教育专区。浙江大学...(10 分) 首先输入一个整数 n,再输入 n 个整数,计算并输出这 n 个数的和...

  • 98-06浙大管理学试题及答案

    06年浙江大学管理学真题 5页 免费喜欢此文档的还喜欢...9 领导理论是研究领导___的理论. 简答题(每题 8...雇员绩效评价中应强调哪些标准, 个人经算 超支将会...

  • 浙江大学2006年高等代数试题解答

    浙江大学2006年高等代数试题解答_研究生入学考试_高等教育_教育专区。浙江大学2006年高等代数试题解答浙江大学 2006 年攻读硕士研究生入学初试试题考试科目:高等代数 科...

  • 浙江大学(2003)计算理论试卷

    浙江大学2006计算理论试题 3页 免费喜欢此文档的还喜欢 2008级_计算理论_试卷答案...浙江大学(2003)计算理论试卷浙江大学(2003)计算理论试卷隐藏>> 浙江大学 2003 ...

  • 浙江大学经济学综合2006年考研试题及答案

    浙江大学 2006 年硕士研究生入学考试试题 考试科目: 编号: 考试科目:经济学综合 编号:402 本试卷由三部分组成:其一是西方经济学部分,共有 l00 分,所有专业必考...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email