计算理论导引4

《计算机导论》教学大纲说明：教师可根据课时和学校特点适当选择、调整教学安排。

一、课程简介实证思维、逻辑思维和计算思维是人类认识世界和改造世界的三大思维。

计算机的出现为人类认识世界和改造世界提供了一种更有效的手段，以计算机技术和计算机科学为基础的计算思维已成为人们必须具备的基础性思维。

如何以计算机思维为切入点，通过重构《大学计算机》的课程体系和知识结构，促进计算思维能力培养，提升大学生综合素质和创新能力是大学计算机课程改革面临的重要课题。

这些不断变化的情况要求对目前《大学计算机》的课程体系进行改革。

所以，如何明确、恰当地将计算思维融入知识体系，培养当代大学生用计算机解决和处理问题的思维和能力，从而提升大学生的综合素质，强化创新实践能力是当前的迫切要求。

1.教学目标（1）基本目标《大学计算机》教学不仅承担着传承知识，更肩负着创新知识的使命。

因此，在传授知识的同时更应培养学生的学习能力、解决问题的能力、交流能力、团队合作能力和创新能力，使他们能更快地适应未来工作的需求。

分层次课程体系体现《大学计算机》课程教学的实效性和针对性，以“全面提高计算机公共课程教学质量，培养学生良好的信息化素养，计算思维品质和计算机应用技能，为学生的后续专业学习提供良好的支持”为核心目标。

（2）高级目标研究性教学在培养学生的综合能力的过程中将发挥越来越重要的作用，它将成为综合性实践课程的主要教学方法。

学习的过程是参与的过程，是创造的过程而非盲目接受的过程。

学生积极的思维习惯和探究问题的意识应该在课程教学中得到培养。

在实现基本目标的基础上，实现高级目标：◆提升学习愿望，学习目标；◆增强学生的自我意识；◆运用已有知识学习新事物；◆教授特定领域和特定课程的学习策略；◆潜移默化，完善学生的人格。

2.实践环节实践性教学内容的设置遵循以下原则：（1）课程实验采用集中实验和自主实验相结合的原则。

其中，集中实验根据课程安排到统一的实验室进行实验；自主实验则由学生利用自己的机器或学校内外公有计算机实验室自主完成实验任务。

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 步，若有接受，则接受。

定义概念题目：第三章：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，ω是一个串。

第5章算法与复杂性习题一、选择题1. B2. D3. C4. A5. B6. B7. D8.B9.C 10.A11.A 12.C 13.A 14.A二、简答题1．什么是算法，算法的特性有哪些？答：“算法(Algorithm)是一组明确的、可以执行的步骤的有序集合，它在有限的时间内终止并产生结果”。

算法的特性有：(1) 有穷性(可终止性)：一个算法必须在有限个操作步骤内以及合理的有限时间内执行完成。

(2) 确定性：算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。

(3) 有效性(可执行性)：算法中描述的操作步骤都是可执行的，并能最终得到确定的结果。

(4) 输入及输出：一个算法应该有零个或多个输入数据、有1个或多个输出数据。

2．什么是算法的时间复杂度和空间复杂度，如何表示？答：时间复杂度是与求解问题规模、算法输入相关的函数，该函数表示算法运行所花费的时间。

记为，T(n)，其中，n代表求解问题的规模。

算法的空间复杂度(Space complexity)度量算法的空间复杂性、即执行算法的程序在计算机中运行所占用空间的大小。

简单讲，空间复杂度也是与求解问题规模、算法输入相关的函数。

记为，S(n)，其中，n代表求解问题的规模。

时间复杂度和空间复杂度同样，引入符号“O”来表示T(n)、S(n)与求解问题规模n之间的数量级关系。

3．用图示法表示语言处理的过程。

答：语言处理的过程如图所示：4．简述算法设计的策略。

答：作为实现计算机程序实现时解决问题的方法，算法研究的内容是解决问题的方法，而不是计算机程序的本身。

一个优秀的算法可以运行在比较慢的计算机上，但一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需要，因此，在计算机程序设计中，算法设计往往处于核心地位。

要想充分理解算法并有效地应用于实际问题，关键是对算法的分析。

通常可以利用实验对比分析、数学方法来分析算法。

实验对比分析很简单，两个算法相互比较，它们都能解决同一问题，在相同环境下，一般就会认为哪个算法的速度快这个算法性能更好。

计算方法引论第四版课程设计概述计算方法是科学计算的基础，广泛应用于科学、工程、金融、医学等各领域。

本课程设计旨在通过实际案例对计算方法的应用进行探究，提高学生对计算方法的理解和应用能力。

课程设计内容设计目标通过本课程设计，使学生:1.掌握计算方法的数学原理和基本算法;2.学会使用计算方法解决实际问题;3.培养自主思考和创新能力。

设计要求1.学生需要使用 Matlab 编写代码并进行模拟实验;2.课程设计分组进行，每组学生自行选题并进行独立研究;3.学生需要提交完整的课程设计报告，包括理论分析、实验过程、结果分析、结论等部分;4.学生需要在汇报时进行课程设计成果的展示，展示形式不限。

选题范围1.数值积分2.常微分方程数值解3.有限差分法4.迭代法5.插值法6.曲线拟合7.数值优化8.矩阵计算9.流体力学数值模拟10.其他相关数值计算方法实验要求1.研究对象必须为实际问题或者现有研究问题，不能是极为简单的数学问题;2.课程设计成果需要展示研究问题的解决方案及其优缺点;3.学生需要在报告中反思课程设计过程，包括遇到的问题及其解决办法。

课程设计流程1.学生分组提交选题申请及初步理论研究报告;2.批准选题后，学生开展实验研究及代码编写;3.学生提交中期报告，包含实验的理论分析、过程及结果展示;4.学生提交最终报告，并进行展示。

成绩评定1.实验报告占总成绩的 50%;2.实验展示占总成绩的 30%;3.课程设计报告占总成绩的 20%。

总结本课程设计采用分组进行，通过学生自选研究题目，增强学生自主学习和动手能力。

同时，在实验过程中学生需要同步进行理论分析，培养学生综合运用知识的能力。

针对不同的实验内容，给出了评分细则，保证了成果的完整性和研究的深度。

此课程设计有利于培养学生的实践能力和学术素养，是一项非常有意义的教学活动。

计算理论导引pdf《计算理论导引》是一本介绍计算理论相关知识的教材，是计算机科学和信息技术领域的基础课程之一、本书通过系统地介绍算法、自动机理论、图灵机模型等内容，旨在帮助读者全面了解计算理论的基础知识和方法，并培养读者的逻辑思维和问题解决能力。

这本教材共分为七章，每一章都涵盖了计算理论中的重要概念和理论。

以下是每章的主要内容：第一章介绍了计算理论的概述和基本概念。

通过介绍计算过程、可计算性和自动性等概念，读者可以了解计算理论的研究范畴以及相关的理论框架。

第二章主要讨论了算法和计算复杂性理论。

其中包括最优算法、计算问题的可解性和复杂性，介绍了P类、NP类、NP完全问题等概念，以及计算问题的近似算法。

第三章介绍了自动机理论和形式语言。

其中包括有限自动机、正则语言、上下文无关语言等内容，以及它们在编译原理和自然语言处理中的应用。

第四章讨论了图灵机模型和可计算函数的理论。

通过介绍图灵机的定义和性质，以及可计算函数的概念和分类，读者可以了解计算机科学中最基本的计算模型和计算能力的限制。

第五章介绍了算术和逻辑的可计算性。

其中包括使用图灵机模型证明加法和乘法的可计算性，以及哥德尔不完备定理等内容，旨在帮助读者了解数学和逻辑在计算理论中的重要作用。

第六章讨论了计算的可验证性和可证明性。

其中包括证明系统、不可判定问题和可证明性形式语言等内容，引导读者理解计算理论中证明和验证的概念以及相关的理论。

第七章介绍了复杂性理论和计算复杂性的研究。

其中包括计算问题的难度分类、NP完全性、多项式时间归约等内容，以及复杂性理论在实际问题中的应用和意义。

《计算理论导引》是一本较为全面的教材，适合计算机科学和信息技术相关专业的本科生和研究生学习。

通过阅读本书，读者可以了解计算理论的基本概念和理论，掌握相关的方法和技术，并进一步深入研究计算理论领域的前沿问题。