AutomataClass

2019年硕士研究生选修课

教学目标及要求：

1. 熟悉有限自动机的基本结论
2. 熟悉正则表达式的基本结论
3. 能实现有限自动机和正则表达式的基本算法
4. 掌握上下文无关语言的基本结论和实现下文无关语言的基本算法
5. 掌握图灵计算模型
6. 掌握P问题和NP问题的概念
7. 掌握SAT问题求解算法

考核方式：

平时成绩（30%）：

课堂考勤 （10%）基本分10%，采用扣分制：一次缺勤扣 2% 直到扣满10%.

讨论表现 （20%）采用加分制： 提一个问题加2%直到满 10%, 回答一个问题加 2% 直到满 10%.

大作业(70%)

1. UNIX正则匹配程序 （20%）
2. XML语言解析程序 (20%)
3. SAT求解器 (30%)

课程内容及学时分配

1. 有限自动机 3课时讲解，3个课时讨论，3个课时课堂实验（实现基本算法）
2. 正则表达式 3课时讲解， 3个课时讨论，3个课时课堂实验（实现基本算法）
3. 上下文无关语言 3课时讲解， 3个课时讨论，6个课时课堂实验（实现基本算法）
4. 图灵计算模型 3课时讲解， 3个课时讨论
5. 掌握P问题和NP问题 3课时讲解， 3个课时讨论
6. 掌握SAT问题 3课时讲解， 3个课时讨论，6个课时课堂实验（实现基本算法）

主要参考书（刊）目录：

1. JOHN E. HOPCROFT， RAJEEV MOTWANI， JEFFREY D. ULLMAN << INTRODUCTION TO Automata Theory, Languages, and Computation >> Pearson Education, Inc

2. Javier Esparza << Automata theory An algorithmic approach >>

3. Daniel Kroening Ofer Strichman << Decision Procedures An Algorithmic Point of View >> Springer