计算理论导引

计算理论导引教学设计一、前言计算理论是计算机科学中的基础科学，是计算机科学各个领域的基础。

因此，对于计算机专业学生来说，掌握计算理论是十分重要的。

针对这个问题，本文提出了一些教学活动和教学意见，旨在提高计算理论的教学质量。

二、教学目标1.掌握计算理论的基本概念和基本方法；2.熟悉计算理论中的各种基础概念；3.理解计算理论的本质和应用；4.发展计算机科学中的基础科学。

三、教学内容计算理论课程应该包含以下内容：1.构造有效的算法；2.分析算法的正确性和效率；3.计算复杂度的理论；4.应用算法分析计算问题。

四、教学方法教学方法应包括课堂教学和实验学习两个主要部分。

1. 课堂教学（1）引导式讲授法通过问题提出、举例说明和引导学生思考等方式，引导学生理解基本概念和基本方法。

（2）演示式讲授法通过算法流程演示、举例说明和实例练习等方式，让学生熟悉算法的构造、分析和应用。

2. 实验学习对于计算理论的课程，实验是不可或缺的一部分。

实验可以帮助学生将课堂学习到的理论知识进行实际应用：（1）构造算法实验；（2）分析算法性质实验；（3）基本算法应用实验；（4）复杂性分析实验。

3. 课外作业在课程结束后，老师可以通过作业的形式向学生反馈他们所学的知识和技能。

（1）计算理论基础知识作业；（2）基本算法应用作业；（3）复杂性分析作业。

五、教学评估为了评估教学的质量，教师应该利用以下方式来评估学生的掌握程度：（1）课堂小测验教师可以在课堂上进行简单的小测验，让学生及时掌握所学的知识，及时调整教学进度。

（2）实验与项目实验评估可以基于学生成绩，目的是评估学生的实际能力。

（3）考试和论文在教学的最后阶段，教师可以进行考试和论文等形式的评估，最终确定学生的成绩。

六、小结教学计划可以用来确保教师和学生之间的理解一致，是教学活动的基础。

为了提高教学质量，教师应该在计划中明确教学目标，内容和方法，同时采用多种评估方法来评估学生的学习效果。

13
递归定理的应用
计算机病毒是一个计算机程序，它被设计成在计算机中传 播它自己。为了实现自我复制的基本任务，可能使用到递 归定理证明中的结构。
例 计算机病毒；（Autoexec.BAT ) 从A: 盘 复制 到B:盘 Echo This is a Virus program IF exist b:\autoexec.bat goto Virus Goto No_Virus : Virus B: Rename autoexec.bat auto.bat //准备冒名顶替 Copy a:\autoexec.bat b: //自我复制部分 Echo I am Virus //诚实的自白 Del *.exe //实施破坏 : No_virus A: \Auto //调用原来 autoexec.bat，给出平安无事的假象
计算理论
朴秀峰 xfpiao@
1
主要内容
6.1 递归定理
6.1.1 自引用
6.1.2 递归定理的术语 6.1.3 应用
6.2 逻辑理论的可判定性
6.2.1 一个可判定的理论 6.2.2 一个不可判定的理论
6.3 图灵可归约性 6.4 信息的定义
6.4.1 极小长度的描述 6.4.2 定义的优化 6.4.3 不可压缩的串和随机性
23
公式
辖域：紧跟在量词化变元后的一对括号中的部分。 前束范式：所有量词都出现在公式的前面。 自由变元：没有被量词的辖域所约束的变元。 句子或命题：没有自由变元的公式。 (1) x (F(x,y)→G(x, z) ) (2) x (F(x)→G(y)) → y (H(x)∧L(x, y, z))
图灵机 SELF
图灵机 SELF 忽略输入，且打印出它自己的描述。 图灵机 SELF 有两个部分，分别叫做 A 和 B，将 A 和 B 想象成两个分离的 过程，它们一起组成 SELF。 我们希望 SELF 打印出 <SELF> = <AB>。 A 部分首先运行，在根据完成情况将控制传给 B。A 的任务是打印出 B 的 描述。 使用机器 P<B> 来定义 A，其中 P<B>用函数 q 在 <B> 处的值q(<B>)描述，这 样，A 部分是一个打印出 <B> 的图灵机。A 的描述依赖于是否已经有了 B 的描述，所以在构造出 B 之前，无法完成 A 的描述。 定义 B，使之能打印 A：B 从 A 产生的输出来计算 A。 如果 B 能得到 <B>，它就能用 q 来得到 <A>。当 A 结束时，它被留在带上。 所以 B 只要看着带子就能得到 <B>。在计算 q(<B>) = <A>之后，B 将 之加到带的前面。 然后将 A 和 B 组合成一个机器并在带上写下它的描述。

6
计算模型—上下文无关文法
上下文无关文法：是一个 4 元组 ( V, , R, S )
(1) V 是一个有穷集合，称为变元集。 (2) 是一个与 V 不相交的有穷集合，称为终结符集。 (3) R 是一个有穷规则集，每条规则由一个变元和一个由变元及终结 符组成的字符串构成。 (4) SV 是起始变元。
L 类 NL 类、 NL 完全性、 NL 等于 coNL
17
复杂性理论—难解性
层次定理的含义：定理中的每一个都能证明时间和空间复杂性类不全 相同，它们形成了一个层次结构，其中时空界限较大的类比时空界限 较小的类包含更多的语言。 相应的概念和结论 在相对化方法中，将修改计算模型，给图灵机一些本质上是“免费” 的信息。依据实际提供给它的信息，图灵机就可能比以前更轻松地解 决某些问题。 电路复杂性 布尔电路、电路族、…… 3SAT 是 NP 完全的
SPACE(f(n)) ={ L | L是被 O(f(n)) 空间的确定型图灵机判定的语言}
NSPACE(f(n)) = { L | L是被 O(f(n)) 空间的非确定型图灵机判定的语言} 萨维奇定理：对于任何函数 f : NR+ ，其中 f(n) n，NSPACE( f(n) ) SPACE( f 2(n) )。 P NP PSPACE=NPSPACE EXPTIME PSPACE完全的、 PSPACE难的 TQBF={< >| 是真的全量词化的布尔公式} PSPACE 完全的
15
复杂性理论—时间复杂性
NP中问题举例。
CLIQUE = { <G, k > | G 是包含 k 团的无向图} SUBSET-SUM
NP完全性： NP 中的某些问题的复杂性与整个类的复杂性 相关联。这些问题中任何一个如果存在多项式时间算法，那 么所有 NP 问题都是多项式时间可解的。 语言 A 称为多项式时间映射可归约到语言 B，记为A≤pB， 若存在多项式时间可计算函数 f : **，对于每一个 w， 有 w∈A f(w)∈B。 如果语言 B 满足下面两个条件，就称为NP完全的：

什么是时间复杂度？请举例说 明。
时间复杂度是评价算法执行时 间快慢的一个指标，通常用大O 表示法来表示。例如，对于一 个简单的顺序查找算法，其时 间复杂度为O(n)，表示随着问 题规模n的增加，算法的执行时 间线性增长。
计算模型习题答案详解
习题1
解释图灵机的基本原理和工作过程。
答案
图灵机是一种理论上的计算模型，由一条无限长的纸带和一个读写头组成。读写头可以读取、写入和移动纸带上 的符号，根据当前状态和读取的符号来决定下一步的动作和状态转移。图灵机的工作过程可以模拟任何计算机程 序的执行过程。
RAM模型的扩展与优化
包括引入并行计算、分布式计算等概念，以 提高RAM模型的计算能力和效率。
其他计算模型
量子计算模型
利用量子力学原理进行计算的模型，具有在某些特定 问题上比传统计算机更高的计算效率。
生物计算模型
模拟生物体内信息处理过程的计算模型，如神经网络、 基因算法等。
光计算模型
利用光学原理进行计算的模型，具有高速并行处理和 低能耗等优点。
形式语言与自动机习题答案详解
习题1
解释什么是形式语言，并给出其定义和性质 。
答案
形式语言是பைடு நூலகம்于描述计算机程序的语法和语 义的一种数学工具。它由一组符号和一组规 则组成，可以表示各种不同类型的数据结构 和算法。形式语言具有确定性、封闭性和可 计算性等性质，这些性质使得我们可以对计
算机程序进行精确的描述和分析。
Python语言基础 掌握Python语言的基本语法、数 据类型、控制结构、函数等，以 及常用的Python库和框架。
其他编程语言 了解其他常见的编程语言，如C#、 JavaScript、Go等，以及它们的 特点和应用场景。