计算理论导引23

5.1 证明EQ CFG 是不可判定的。

解：只须证明ALL CFG ≤m EQ CFG 即可。

构造CFG G 1，使L(G 1)=∑*。

设计从ALL CFG 到EQ CFG 的归约函数如下： F=“对于输入＜G ＞，其中G 是CFG ：1）输出＜G ,G 1＞。

”若＜G ＞ALL CFG ，则<G ,G 1>EQ CFG 。

若＜G ＞ALL CFG ，则<G , G 1>EQ CFG 。

F 将ALL CFG 归约到EQ CFG 即ALL CFG ≤m EQ CFG∵ALL CFG 是不可判定的，∴EQ CFG 是不可判定的。

5.2证明EQ CFG 是补图灵可识别的。

证明：注意到A CFG ={<G,w>|G 是能派生串w 的CFG}是可判定的。

构造如下TM ： F=“输入<G ,H>，其中G ,H 是CFG ，1) 对于字符串S 1, S 2,，重复如下步骤。

2) 检测S i 是否可以由G 和H 派生。

3) 若G 和H 中有一个能派生w ，而另一个不能，则接受。

”F 识别EQ CFG 的补。

5.3 略。

5.4 如果A m B 且B 是正则语言，这是否蕴涵着A 也是正则语言？为什么？ 解：否。

例如：对非正则语言A={0n 1n |n 0}和正则语言B={0}，可以构造一个可计算函数f 使得：f(w)=⎩⎨⎧≠=n n nn 10w 1,10w 0, 于是w A f(w)B,故A m B 。

5.5 证明A TM 不可映射规约到E TM 。

证明：反证法假设A TM m E TM ， 则有TM m TM E A ≤。

而A TM 的补不是图灵可识别的，从而可知E TM 的补也不是图灵可识别的。

下面构造一个识别E TM 的补的图灵机S ：S=“输入<M>，M 是TM,1) 对i=1,2,…重复下一步。

2) 对S 1,S 2,…,S i 模拟M 运行i 步，若有接受，则接受。

计算机技术硕士专业学位培养方案专业代码:0852１1一、培养目标计算机技术工程硕士得培养目标就是面向国民经济信息化建设与发展需要、面向企业事业单位对各类计算机应用人才需求,培养高层次实用型、高素质复合型得计算机技术人才。

二、研究方向(1)软件自动化与形式化方法(２)分布计算与并行处理及新型网络（3)系统软件及其信息安全(４)新型程序设计与软件方法学（5)多媒体技术(6)人工智能与知识工程(７)机器学习与数据挖掘(8)数据库技术(9)语言信息处理四、招生对象三、招生对象１.计算机科学与技术专业及相近专业得本科毕业生;2.从事计算机相关工作或相近专业工作,有实践经验得同等学历人员;四、学习年限ﻩ计算机技术专业硕士实行３年学制。

最长年限为４年。

五、课程设置本专业学分构成为:学位课（Ａ＋B)= 16学分;选修课（D)≧（16)学分；总分≧3２学分。

1.根据中宣部、教育部得相关通知,Ａ类中“自然辩证法等选修课程”就是指“《自然辩证法概论》或《马克思主义与社会科学方法论》或《马克思主义原著选读》”3门,我校要求硕士生须在其中任选1门。

2.非计算机类专业本科及同等学力入学者为36学分，须补修本科专业核心课与指定选修课(具体课程可咨询本科教务员),合计4学分。

六、教学方式ﻩ课堂讲授、课堂讨论、课程论文、课程实习、实习实践(不少于12个月)。

七、考核方式1.笔试、口试、读书报告、实习报告、课程论文。

ﻩ2.中期考核安排在第三学期，考核专业基础理论、对学科动态与前沿得了解、分析问题与解决问题得能力、综合素养、外语水平等。

根据考核成绩向进入硕士毕业设计阶段或中止研究生学习等方向分流。

八、毕业设计ﻩ1．选择具有较强应用价值得设计课题。

2．严格开题报告制度。

3．加强毕业设计得指导与监督。

4．进行毕业设计得规范性教育。

九、答辩与学位授予ﻩ根据学位委员会规定得程序与要求,审阅毕业设计,组织答辩委员会,进行答辩、建议就是否授予学位。

计算机技术硕士专业学位培养方案专业代码：085211一、培养目标计算机技术工程硕士的培养目标是面向国民经济信息化建设和发展需要、面向企业事业单位对各类计算机应用人才需求，培养高层次实用型、高素质复合型的计算机技术人才。

二、研究方向（1）软件自动化与形式化方法（2）分布计算与并行处理及新型网络（3）系统软件及其信息安全（4）新型程序设计与软件方法学（5）多媒体技术（6）人工智能与知识工程（7）机器学习与数据挖掘（8）数据库技术（9）语言信息处理四、招生对象三、招生对象1．计算机科学与技术专业及相近专业的本科毕业生；2．从事计算机相关工作或相近专业工作，有实践经验的同等学历人员；四、学习年限计算机技术专业硕士实行3年学制。

最长年限为4年。

五、课程设置本专业学分构成为：学位课（A+B）= 16学分；选修课（D）≧（16）学分；总分≧32学分。

1.根据中宣部、教育部的相关通知，A类中“自然辩证法等选修课程”是指“《自然辩证法概论》或《马克思主义与社会科学方法论》或《马克思主义原著选读》”3门，我校要求硕士生须在其中任选1门。

2.非计算机类专业本科及同等学力入学者为36学分，须补修本科专业核心课和指定选修课（具体课程可咨询本科教务员），合计4学分。

六、教学方式课堂讲授、课堂讨论、课程论文、课程实习、实习实践（不少于12个月）。

七、考核方式1．笔试、口试、读书报告、实习报告、课程论文。

2．中期考核安排在第三学期，考核专业基础理论、对学科动态和前沿的了解、分析问题和解决问题的能力、综合素养、外语水平等。

根据考核成绩向进入硕士毕业设计阶段或中止研究生学习等方向分流。

八、毕业设计1．选择具有较强应用价值的设计课题。

2．严格开题报告制度。

3．加强毕业设计的指导和监督。

4．进行毕业设计的规范性教育。

九、答辩和学位授予根据学位委员会规定的程序和要求，审阅毕业设计，组织答辩委员会，进行答辩、建议是否授予学位。

计算机科学与技术系二〇一四年六月。

定义概念题目：第三章：1. 图灵机：是一种精确的通用计算机模型，能模拟实际计算机的所有计算行为，它的核心是转移函数δ，它说明了机器如何从一个格局走到下一个格局。

对于图灵机，δ的形式如下：Q×Γ→Q×Γ{L,R},图灵机是一个7元组（Q，∑，Γ，δ，q 0,q accept,q reject）.其中Q，∑，Γ都是有穷集合，并且1）Q是状态集；2）∑是输入字母表，不包括特殊空白符号凵，3）Γ是带字母表，其中凵∈Г，∑∈Г4）δ2. 格局：图灵机的计算过程中，当前状态，当前内容和读写头当前位置组合在一起。

例如：1011q701111：当前状态q7，当前读写头位置在第二个0上。

定义3.2 如果一个语言能被某一个图灵机识别，则称该语言是图灵可识别的（递归可枚举语言）定义3.2 如果一个语言能被某一个图灵机判定，则称该语言是图灵可判定的简称可判定的（递归语言）3.图灵机的变形：多带图灵机、非确定型图灵机、枚举器。

每个4.枚举器：他是图灵机的一种变形，是带有打印机的图灵机，图灵机把打印机当作输出设备，从而可以打印串，每当图灵机想在打印序列中增加一个串时，就把此串送到打印机。

一个语言是图灵可识别的，当且仅当有枚举器枚举它。

5.图灵机的术语：形式化描述，实现描述，高水平描述。

第四章：1.可判定的语言有：（A DFA、A NFA、A REX、E DFA、EQ DFA 是正则语言）、（A CFG、E CFG 是上下无关语言）❶每个上下文无关语言都是可判定的。

2.不可判定的语言有:：EQ CFG、A TM 、停机问题、HALT TM 、E TM、REGULAR TM 、EQ TM 、 E LBA 、ALL CFG 、PCPA TM =｛<M,ω>｜M是TM，ω是串，M接受ω｝是不可判定的。

证明：假设证A TM 是可判定的，下面将由之导出矛盾。

设H是A TM 的判定器。

令M是一个TM，ω是一个串。

8.1 证明对于任意函数f:N N，其中f(n)n，不论用单带TM模型还是用两带只读输入TM模型，所定义的空间复杂性类SPACE(f(n))总是相同的。

证明：为区别，记单带TM模型在f(n)空间内能判定的语言类为SPACE1(f(n)), 而记双带只读输入TM模型在f(n)空间内能判定的语言类为SPACE2(f(n))。

该题要证明的是SPACE1(f(n))＝SPACE2(f(n))。

首先SPACE1(f(n))SPACE2(f(n))。

这是因为设A SPACE1(f(n))，且设M设在f(n)空间内判定A的单带TM，如下构造双带TM只读输入TM N。

N=“对于输入串w：1)将w复制到工作带上。

2)在工作带上模拟M，直到停机。

3)若M接受，则接受；否则，拒绝。

”N在f(n)空间内运行，L(N)=L(M)=A，所以A SPACE2(f(n))。

首先SPACE2(f(n))SPACE1(f(n))。

设A SPACE2(f(n))，且N 为在f(n)空间内判定A的双带只读输入TM。

按照用单带TM模拟多带TM的常规方式构造M：M＝“对于输入串w：1)初始化工作带为＃w1’w2…w n#’.其中以’标记N的两个读写头。

2)模拟N运行直到停机。

每一步模拟，要两次扫描带子。

第一次扫描确定读写头下符号，第二次扫描根据N的转移函数完成改写和移动读写头的工作。

3)若N接受，则接受；否则，拒绝。

”L(M)=L(N)=A。

由于f(n)n，M的运行空间是f(n)+n+2＝O(f(n))。

8.3 考虑广义地理学游戏，其中起始节点就是又无源箭头指入的节点。

选手I有必胜策略吗？选手II呢？给出理由。

1 2 34 5 6I II I II I Winner2 3 6 I4 5 6 II由表上来看选手II有必胜策略I2II4(不能选3)I5II6(不能选2)I。

8.4 证明PSPACE在并、补和星号运算下封闭。

证明：(1) 并：对任意L1, L2PSPACE，设有n a空间图灵机M1和n b空间图灵机M2判定它们，且c=max{a,b}。

5.1 证明EQ CFG 是不可判定的。

解：只须证明ALL CFG ≤m EQ CFG 即可。

构造CFG G 1，使L(G 1)=∑*。

设计从ALL CFG 到EQ CFG 的归约函数如下： F=“对于输入＜G ＞，其中G 是CFG ：1）输出＜G ,G 1＞。

”若＜G ＞∈ALL CFG ，则<G ,G 1>∈EQ CFG 。

若＜G ＞∉ALL CFG ，则<G , G 1>∉EQ CFG 。

F 将ALL CFG 归约到EQ CFG 即ALL CFG ≤m EQ CFG∵ALL CFG 是不可判定的，∴EQ CFG 是不可判定的。

5.2证明EQ CFG 是补图灵可识别的。

证明：注意到A CFG ={<G,w>|G 是能派生串w 的CFG}是可判定的。

构造如下TM ： F=“输入<G ,H>，其中G ,H 是CFG ，1) 对于字符串S 1, S 2,⋯，重复如下步骤。

2) 检测S i 是否可以由G 和H 派生。

3) 若G 和H 中有一个能派生w ，而另一个不能，则接受。

”F 识别EQ CFG 的补。

5.3 略。

5.4 如果A ≤m B 且B 是正则语言，这是否蕴涵着A 也是正则语言？为什么？ 解：否。

例如：对非正则语言A={0n 1n |n ≥0}和正则语言B={0}，可以构造一个可计算函数f 使得：f(w)=⎩⎨⎧≠=n n nn 10w 1,10w 0, 于是w ∈A ⇔f(w)∈B,故A ≤m B 。

5.5 证明A TM 不可映射规约到E TM 。

证明：反证法假设A TM ≤m E TM ， 则有TM m TM E A ≤。

而A TM 的补不是图灵可识别的，从而可知E TM 的补也不是图灵可识别的。

下面构造一个识别E TM 的补的图灵机S ：S=“输入<M>，M 是TM,1) 对i=1,2,…重复下一步。

2) 对S 1,S 2,…,S i 模拟M 运行i 步，若有接受，则接受。

计算机技术硕士专业学位培养方案专业代码：085211一、培养目标计算机技术工程硕士的培养目标是面向国民经济信息化建设和发展需要、面向企业事业单位对各类计算机应用人才需求，培养高层次实用型、高素质复合型的计算机技术人才。

二、研究方向（1）软件自动化与形式化方法（2）分布计算与并行处理及新型网络（3）系统软件及其信息安全（4）新型程序设计与软件方法学（5）多媒体技术（6）人工智能与知识工程（7）机器学习与数据挖掘（8）数据库技术（9）语言信息处理四、招生对象三、招生对象1．计算机科学与技术专业及相近专业的本科毕业生；2．从事计算机相关工作或相近专业工作，有实践经验的同等学历人员；四、学习年限计算机技术专业硕士实行3年学制。

最长年限为4年。

五、课程设置本专业学分构成为：学位课（A+B）= 16学分；选修课（D）≧（16）学分；总分≧32学分。

1.根据中宣部、教育部的相关通知，A类中“自然辩证法等选修课程”是指“《自然辩证法概论》或《马克思主义与社会科学方法论》或《马克思主义原著选读》”3门，我校要求硕士生须在其中任选1门。

2.非计算机类专业本科及同等学力入学者为36学分，须补修本科专业核心课和指定选修课（具体课程可咨询本科教务员），合计4学分。

六、教学方式课堂讲授、课堂讨论、课程论文、课程实习、实习实践（不少于12个月）。

七、考核方式1．笔试、口试、读书报告、实习报告、课程论文。

2．中期考核安排在第三学期，考核专业基础理论、对学科动态和前沿的了解、分析问题和解决问题的能力、综合素养、外语水平等。

根据考核成绩向进入硕士毕业设计阶段或中止研究生学习等方向分流。

八、毕业设计1．选择具有较强应用价值的设计课题。

2．严格开题报告制度。

3．加强毕业设计的指导和监督。

4．进行毕业设计的规范性教育。

九、答辩和学位授予根据学位委员会规定的程序和要求，审阅毕业设计，组织答辩委员会，进行答辩、建议是否授予学位。

计算机科学与技术系二〇一四年六月。

计算理论导引 pdf
计算理论是计算机科学中一个重要的研究领域，与硬件和软件相
互依存、相互作用，研究计算机处理数据和信息的能力，以及多种不
同类型的问题的解决方案。

它研究计算机在运算过程中严重依赖的运
算模型，如图灵机、自动机、标记自动机、堆栈机和算法等，以及设
计和实现它们的技术。

它也与数学密切相关，具有表达性和证明性的
定理，用来分析、评估和开发计算过程的有效性。

计算理论研究计算能力和计算复杂度，研究机器翻译、语言识别
和语音理解等多媒体技术，以及模式识别和机器学习等机器智能技术。

计算理论可以帮助人们更深入地理解有限表示的解决方案，以及用来
解决问题的算法的可计算性和有效性的估计量。

它提供了有效的算法
和数据模型，用于开发现代计算机应用，以及复杂计算问题的解决方案。

计算理论导引pdf
《计算理论导引》是一本经典的计算理论教材，是计算机科学及相关
领域的重要参考书籍。

本书由Michael Sipser撰写，首次出版于1996年，旨在为读者介绍计算理论的基础概念、技术和应用。

本文将对《计算理论
导引》进行综合分析和评价。

《计算理论导引》一共分为七个部分，分别是：有限自动机、正则语言、上下文无关语言、图灵机、不可计算性、随机性计算和复杂性。

每个
部分的章节安排合理，逻辑清晰，内容丰富，深入浅出地介绍了计算理论
的不同方面。

总的来说，《计算理论导引》是一本内容全面、思路清晰的计算理论
教材。

它既适合初学者了解计算理论的基本概念和技术，也适合进阶读者
深入理解计算理论的高级问题和应用。

然而，由于本书内容较为抽象和专业，对于没有计算机科学基础的读者可能会有些困难。

因此，建议读者在
阅读本书之前具备一定的数学和计算机基础知识。

初快23知识点总结在本文中，我将总结23个不同领域的知识点，以便读者对这些知识有一个全面的了解。

这些知识点分别涵盖了科学、技术、文化和其他领域，希望对您有所帮助。

1. 量子力学量子力学是一门研究微观世界的物理学科，它描述了微观粒子的行为。

量子力学的基本原理是不确定性原理，即无法准确确定微观粒子的位置和动量。

量子力学的应用包括原子、分子和固态物质的研究。

2. DNA结构DNA是一种双螺旋结构的分子，它携带了生命的遗传信息。

DNA分子由两条互补的链组成，其中包含了腺嘌呤、鸟嘌呤、胸腺嘧啶和胞嘧啶四种碱基。

DNA的结构和功能对于生物学的研究具有重要意义。

3. 人工智能人工智能是一门研究如何使计算机具有智能的学科，它涉及机器学习、自然语言处理、计算机视觉等多个领域。

人工智能的应用包括智能机器人、智能驾驶、智能医疗等多个方面。

4. 气候变化气候变化是指地球气候系统发生的长期变化，包括全球变暖、冰川消融、海平面上升等现象。

气候变化对于地球生态系统和人类社会都具有重要影响，因此需要采取行动来减缓气候变化的影响。

5. 网络安全网络安全是指保护网络系统和数据免受未经授权的访问、破坏或窃取。

网络安全的技术包括防火墙、加密、身份认证等多种手段，以确保网络系统的安全性。

6. 股票投资股票投资是指通过购买股票来获取投资收益的行为。

股票投资的原则包括分散投资、长期投资、风险控制等多个方面，需要投资者具备一定的经济知识和投资技能。

7. 文艺复兴文艺复兴是指15世纪至16世纪期间在欧洲兴起的一场思想、艺术和科学的复兴运动。

文艺复兴的代表人物包括达·芬奇、米开朗基罗等，他们的作品对后世艺术产生了深远的影响。

8. 生物多样性生物多样性是指地球上不同物种的丰富程度和多样性。

生物多样性对于生态系统的稳定和人类社会的发展都具有重要意义，因此需要采取保护措施来维护生物多样性。

9. 货币政策货币政策是国家央行制定并实施的影响货币供应、利率及货币价值的政策。