一. 本课的性质以及研究的内容
任何一门学科都有它的基础和它的基本问题，如物质的本质是什么？有机体生命的基础和起源是什么？
什么是计算机科学的基础？什么是计算机科学的基本问题？
诸如什么是形式语言？什么是计算？什么是能计算的？什么是不能计算的？什么是算法？如何评价算法？什么样的算法是可行的？这些问题能否判定？这又引出什么是可判定的？什么是不可判定的？
这些问题就是计算理论要讨论的问题。
1.1 形式语言基本概念（ 1 ）
1.2 文法概念（ ）
1.3文法的分类（ ）
2.1确定的有限自动机（ 1 ）
2.2 不确定的有限自动（ ）
2.3 具有ε转移的NFA（ ）
2.4 正规表达式及其与有限自动机之间的等价性（ 1 ）
2.5 有限自动机的简化（1）
2.6 正规集对运算的封闭性（1 ）
2.7 正规文法与有限自动机之间的等价性（ 2 ）
2.8 正规集的判定问题（ 1 ）
3.1 上下文无关文法的派生树(推导树) （ 1 ）
3.2 上下文无关文法的简化（ 2 ）
3.3 上下文无关文法的Chomsky范式（ 1 ）
3.4 CFG 的Greibach范式(GNF) （ 2 ）
3.5 下推自动机(Push Down Automaton，PDA) （ 2 ）
3.6 PDA与CFG之间的等价性（ 1 ）
3.7 CFL的有关判定问题（ 1 ）
4.1 图灵机模型（ 2 ）
4.2 图灵机的变化和组合（ ）
4.3 通用图灵机（ 2 ）
4.4 图灵机可计算性（ 2 ）
5.1 函数的复合算子、递归算子、取极小值算子（ 1 ）
5.2 原始递归函数（ ）
5.3 原始递归谓词和原始递归集合（ ）
5.4 部分递归函数及其与图灵机的等价性（ 2 ）
6.1 半可计算谓词与半可计算集合（ 1 ）
6.2 半可计算的封闭性（ ）
6.3 可计算性和半可计算性（ 1 ）
7.1 图灵机计算复杂性量度（ 1 ）
7.2 线性加速和带压缩（ ）
7.3 谱系定理（ ）
7.4 复杂性量度间的关系及非确定谱系（ ）
7.5 间隙定理、加速定理（ ）
7.6 P类与NP类（ 2 ）
评论0
最新资源