《计算理论基础》课程教学大纲（本科）

1、计算理论基础(Induction to the Theory of Computation)课程代码：06410052学分：2.0学时：32 （其中：课堂教学学时：32实验学时：0上机学时：0 ）先修课程：离散数学，程序设计基础适用专业：信息安全教材：计算理论导引，Michael Sipser著，段磊，唐长杰等译，机械工业出版社，2016 年10月第1版一、课程性质与课程目标（-）课程性质计算理论基础是专业基础课、必修课。计算理论基础讨论了计算机科学中的纯粹、引人 注目并且普遍存在的基本内容，介绍构成基本计算范例的基本概念、模型、技巧、结果，阐述当 今计算机科学家用于建模、讨论和预测算法与计算

2、的思想概念与数学知识。（二）课程目标1.知识方面课程目标1.1:掌握自动机等基本计算模型及其演绎模型的形式化描述。课程目标1.2：掌握构造能够识别语言的自动装置的基本方法。课程目标1.3：掌握能够证明语言特性的基本证明方法。课程目标1.4： 了解计算模型在应用领域的广泛应用。2.能力与素质方面课程目标2. 1：能够针对信息系统的运行过程演绎其对应的计算模型。课程目标2.2：能够针对简单信息系统设计其对应的计算模型，并理解模型的不足。课程目标2. 3：能够基于计算模型为信息系统的设计与测试提供指导。（三）课程目标与专业毕业要求指标点的对应关系本课程支撑专业培养计划中毕业要求指标点1-4, 2-2

3、, 4-1 o1.毕业要求1-4：能将数学、自然科学、工程基础和专业知识运用到复杂工程问题的表述中。2毕业要求2-2：借助文献辅助，具备对复杂工程问题进行识别、表达、建模、求解的能力, 以及对分析结论进行有效性评价的能力。3.毕业要求4-1：掌握针对复杂工程问题设计实验的科学方法。求指标标点课程目毕业要求1-4毕业要求2-2毕业要求4-1课程目标1.1V课程目标L2V课程目标1.37V课程目标2.1VV课程目标2.2VV课程目标2.3V二、课程内容与教学要求第一章有穷自动机和正则语言本章支持课程目标：L1掌握自动机等基本计算模型及其演绎模型的形式化描述；1.2掌握 构造能够识别语言的自动装置的

4、基本方法；1.3掌握能够证明语言特性的基本证明方法；1. 4 了 解计算模型在应用领域的广泛应用；2.1能够针对信息系统的运行过程演绎其对应的计算模型； 2.2能够针对简单信息系统设计其对应的计算模型，并理解模型的不足；2.3能够基于计算模型 为信息系统的设计与测试提供指导。（一）课程内容（1）有穷自动机。（讲授）（2）正则语言和正则运算。（讲授）（3）非确定性与非确定型有穷自动机。（讲授）（4） NFA、DFA的等价行与正则运算的封闭性。（讲授+课堂练习）（5）正则表达式。（讲授+课堂练习）（6）正则语言的泵引理与非正则语言。（讲授+课堂练习）（一）教学要求.理解有穷自动机的形式化定义与运行

5、过程。.掌握有穷自动机的构造技术。.掌握正则语言的运算及其封闭性。.理解非确定型自动机的运行过程。.理解确定型有穷自动机与非确定型有穷自动机之间的等价性。.掌握构造与非确定型有穷自动机之间等价的自动机的方法。.掌握基于自动机的正则语言运算的封闭性证明技术。.掌握正则语言与有穷自动机之间的等价性。.掌握证明非正则语言的基本技术。（三）重点与难点.重点有穷自动机的构造技术、正则语言的运算及其封闭性、构造与非确定型有穷自动机 之间等价的自动机的方法、基于自动机的正则语言运算的封闭性证明技术、证明非正则 语言的基本技术。.难点有穷自动机的构造技术、构造与非确定型有穷自动机之间等价的自动机的方法、证 明

6、非正则语言的基本技术。第二章上下文无关语言与下推自动机本章支持课程目标：1.1掌握自动机等基本计算模型及其演绎模型的形式化描述；1.3掌握 能够证明语言特性的基本证明方法；1.4 了解计算模型在应用领域的广泛应用；2.1能够针对信 息系统的运行过程演绎其对应的计算模型；2.2能够针对简单信息系统设计其对应的计算模型， 并理解模型的不足。（-）课程内容（1）上下文无关文法。（讲授）（2）设计上下文无关文法与乔姆斯基范式。（讲授+课堂练习）（3）下推自动机。（讲授）（4）与上下文无关文法的等价性。（讲授+课堂练习）（5）非上下文无关语言。（讲授+课堂练习）（二）教学要求（1）掌握上下文无关文法的形

7、式化定义。（2）掌握基于文法的语言派生过程。（3）理解乔姆斯基范式。（4）掌握下推自动机的形式化定义及其运行过程。（5）理解下推自动机与上下文无关文法的等价性。（6）掌握非上下文无关语言的证明方法。（三）重点与难点1.重点基于文法的语言派生过程、下推自动机与上下文无关文法的等价性、非上下文无关 语言的证明方法。2 .难点非上下文无关语言的证明方法。第三章邱奇-图灵论题本章支持课程目标：1.1掌握自动机等基本计算模型及其演绎模型的形式化描述；L2掌握 构造能够识别语言的自动装置的基本方法;2. 1能够针对信息系统的运行过程演绎其对应的计算 模型；2.2能够针对简单信息系统设计其对应的计算模型，并

8、理解模型的不足；2. 3能够基于计 算模型为信息系统的设计与测试提供指导。（-）课程内容（1）图灵机作为一个计算模型的基本定义。（讲授）（2）图灵机运行过程与接受的语言。（讲授）（3）构造图灵机的基本技术。（讲授讲授+课堂练习）（4）图灵机的变形。（讲授+课堂练习）（5）算法的定义。（讲授）（二）教学要求（1）理解图灵机的形式化定义、运行过程。（2）掌握图灵机的基本构造技术。了解计算模型之间的等价性。（4）掌握对计算模型进行演绎的基本思路。（三）重点与难点.重点图灵机的运行过程、图灵机的构造技术、图灵机的演绎。.难点图灵机的构造技术。第四章可判定性本章支持课程目标：L1掌握自动机等基本计算模型

9、及其演绎模型的形式化描述；L 2掌握 构造能够识别语言的自动装置的基本方法；1.3掌握能够证明语言特性的基本证明方法；2.1能 够针对信息系统的运行过程演绎其对应的计算模型。（-）课程内容（1）与正则语言相关的可判定性问题。（讲授）（2）与上下文无关语言相关的可判定性问题。（讲授+课堂练习）（3）对角化方法。（讲授）（4）不可判定语言。（讲授+课堂练习）（-）教学要求（1）理解可判定与不可判定语言的内涵。（2）掌握证明可判定语言的基本方法。（3）掌握对角化方法。（4）理解可判定与图灵可识别之间的关系。（三）重点与难点.重点证明可判定语言的基本方法、对角化方法。.难点对角化方法。三、学时分配及教

10、学方法章（按序填写）教学形式及学时分配主要教学方法支撑的课程目标课堂 教学实 验上 机课程 实践小 计第一章1010讲授、课堂练习1、2、3、4、5、6、7第二章88讲授、课堂练习1、 3、 4、 5、 6第三章88讲授、课堂练习1、 2、 5、 6、 7第四章66讲授、课堂练习1、 2、 3、 5合计3232四、课程考核目考核形式考核要求考核权重备注五平时作业按照作业题目进行评分，总分数平均 计算（5次以上）20%各次作业得分取 平均值、参随堂测试闭卷10%考期末考试闭卷70%书及学习资料1、计算理论导引，Michael Sipser著，段磊，唐长杰等译，机械工业出版社，2016 年10月第1版2、自动机理论、语言和计算导论（原书第3版），John E. Hopcroft等著，机械工业 出版社，2008年7月第1版3、形式语言，自动机理论与计算导论，Kamala Krithivasan Rama R （拉玛）著；孟宇