计算理论: 绪论
计算理论隶属于理论计算机科学和数学的研究范畴, 其研究对象是计算这一概念本身, 分析和解决什么是可计算的, 而什么不可计算; 有哪些可行的计算模式, 以及对计算的复杂度, 亦即需要耗费多少时间或存储.
本课程的主要介绍内容为正则表达式, 自动机和上下文无关语法:
1. 定义语言和正则表达式
概述语言和正则表达式的相关定义, 性质与其他内容:
- 介绍基本术语和概念
- 使用模式描述语言
- 正则表达式
2. 自动机
介绍不同种类的自动机 (Automata), 并介绍多个实现在自动机和模式 (正则表达式)之间进行转换的算法:
- 有限状态自动机
Finite State Automata - 确定性有穷自动机
Deterministic Finite Automata - 非确定性有穷自动机
Non-deterministic Finite Automata - 非确定性有穷自动机 $\rightarrow$ 确定性有穷自动机的转换算法
- 自动机 $\rightarrow$ 表达式的转换算法
- 表达式 $\rightarrow$ 自动机的转换算法
- 正则语言的一般性质
- 自动机的等价性
3. 表述复杂语言
- 上下文无关语法
- 语法分析和不明确性
Backus-Naur范式- 上下文无关语法的性质
4. While 语法及其状态描述
While程序语法- 描述
While程序执行状态 - 构造简单数据结构
5. 时空复杂度
- 时间复杂度及算法分析
- $O(n)$ 符号的定义及基本性质
6. 计算正确性
- 完全正确性和部分正确性
- 霍尔逻辑: 描述部分正确性
- 霍尔逻辑: 描述完全正确性
- 正确性证明的技巧及方法
