《计算理论基础》 学时分配
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 ）
