《计算理论》课程教学大纲一、课程名称：计算理论二、课程性质：选修、专业基础理论课三、学时与学分：32学时，1.5学分四、课程先导课：高等数学、离散数学五、课程简介计算理论是关于计算知识的有系统的整体，本是数学的一个研究领域，诞生于数理逻辑学家对计算本质的探索。这里的计算（Computation）并不是指纯粹的算术（Calculation)，而是指一种以“机械而有效的”方式获取问题答案的过程随看计算理论的发展最终促使了计算机的发明，计算理论的重心也从数学转到了计算机科学，而计算理论关心的核心问题是：计算（机）的基本能力和限制究竟是什么？这个问题中包含了两个内容，分别对应计算理论的两个研究方向：可计算性理论和计算复杂性理论，而形式语言与自动机理论正是这两个重要的研究方向的理论基础。为了能够严谨的研究这种机械而有效的计算过程，我们需要严格定义的概念去描述它，需要严谨的计算模型去分析它。这个概念，其实就是已经被我们大家所熟知的“算法”（Algorithm)；而这些模型就是自动机理论，包括有穷自动机、下推自动机和图灵机等几种自动机装置，还包括一些与自动机形式上不相似但能力上却完全相同的模型，如正则表达式和文法等。该课程主要包括5个部分：有限自动机、下推自动机、图灵机、可计算性理论以及初等计算复杂性理论。六、课程目标计算理论主要包括可计算理论以及计算复杂性理论，而形式语言与自动机理论是它们的基础，也是计算机科学与技术领域基本的思想和方法。这些理论不仅是编译技术的基础，在诸如计算机网络协议、文件搜索、数字电路设计和验证以及程序验证等诸多领域也发挥着重要作用。本课程旨在培养学生形式化描述和抽象思维能力，掌握“问题一形式化描述一一自动化（计算机求解）”的思想和方法，并用于解决实际问题。课程的具体目标包括：
《计算理论》课程教学大纲 一、课程名称：计算理论 二、课程性质：选修、专业基础理论课 三、学时与学分：32 学时，1.5 学分 四、课程先导课：高等数学、离散数学 五、课程简介 计算理论是关于计算知识的有系统的整体，本是数学的一个研究领域，诞生 于数理逻辑学家对计算本质的探索。这里的计算 (Computation) 并不是指纯粹的 算术 (Calculation)，而是指一种以 “机械而有效的” 方式获取问题答案的过程。 随着计算理论的发展最终促使了计算机的发明，计算理论的重心也从数学转到了 计算机科学，而计算理论关心的核心问题是：计算（机）的基本能力和限制究竟 是什么? 这个问题中包含了两个内容，分别对应计算理论的两个研究方向：可计 算性理论和计算复杂性理论, 而形式语言与自动机理论正是这两个重要的研究 方向的理论基础。为了能够严谨的研究这种机械而有效的计算过程，我们需要严 格定义的概念去描述它，需要严谨的计算模型去分析它。这个概念，其实就是已 经被我们大家所熟知的“算法”(Algorithm)；而这些模型就是自动机理论，包括 有穷自动机、下推自动机和图灵机等几种自动机装置，还包括一些与自动机形式 上不相似但能力上却完全相同的模型，如正则表达式和文法等。该课程主要包括 5 个部分：有限自动机、下推自动机、图灵机、可计算性理论以及初等计算复杂 性理论。 六、课程目标 计算理论主要包括可计算理论以及计算复杂性理论，而形式语言与自动机理 论是它们的基础，也是计算机科学与技术领域基本的思想和方法。这些理论不仅 是编译技术的基础，在诸如计算机网络协议、文件搜索、数字电路设计和验证以 及程序验证等诸多领域也发挥着重要作用。本课程旨在培养学生形式化描述和抽 象思维能力,掌握“问题——形式化描述——自动化（计算机求解）”的思想和方 法，并用于解决实际问题。 课程的具体目标包括：
目标1：掌握正则语言与上下文无关语言等语言的形式化描述方法和识别方法，能够设计与之相应的文法和自动机，培养学生的抽象思维能力和逻辑思维能力。目标2：分类研究语言的性质，培养针对不同语言的模型描述能力和模型计算能力（包括模型的等价变换、推理等），能够在更高的抽象层面处理复杂工程问题，进而探讨问题的可计算性及其计算的复杂性。目标3：掌握由问题到形式化描述、再到计算机化的问题求解方法，能够对实际问题进行抽象、形式化，构建计算模型，进而用计算机予以解决。目标4：通过自主学习，了解自动机理论与编译、电路设计与验证以及程序验证等其它领域的内在联系，拓宽用计算机高效解决相关应用问题的能力。七、课程目标对毕业要求的支撑关系支撑的毕业要求二级指标点对应课程目标1.1能将数学、自然科学和信息科学的语言工具用于计算机复目标1杂工程问题的表述。目标21.2能针对计算机复杂工程问题的具体对象进行建模和求解2.2对计算机复杂工程问题的一个系统或者过程，能选择或建目标3立一种模型，对关键影响因素进行分析。12.2具备自主学习能力，能通过多种途径拓展自己的知识和目标4能力，包括理解能力、归纳总结能力和提出问题的能力等八、教学设计及对课程目标的支持第一章正则语言1.教学内容语言、确定性有限自动机DFA及其接收的语言、非确定性有限自动机NFA及其接收的语言、DFA与NFA的等价、正则语言的性质、正则表达式、正则语言的泵引理、正则文法。本章教学支持的课程目标为目标1、目标2、目标4。2.教学重点1）DFA与NFA的等价2）正则语言的判定3）有限自动机的设计
目标 1：掌握正则语言与上下文无关语言等语言的形式化描述方法和识别方 法，能够设计与之相应的文法和自动机，培养学生的抽象思维能力和逻辑思维能 力。 目标 2：分类研究语言的性质，培养针对不同语言的模型描述能力和模型计 算能力（包括模型的等价变换、推理等），能够在更高的抽象层面处理复杂工程 问题，进而探讨问题的可计算性及其计算的复杂性。 目标 3：掌握由问题到形式化描述、再到计算机化的问题求解方法，能够对 实际问题进行抽象、形式化，构建计算模型，进而用计算机予以解决。 目标 4：通过自主学习，了解自动机理论与编译、电路设计与验证以及程序 验证等其它领域的内在联系，拓宽用计算机高效解决相关应用问题的能力。 七、课程目标对毕业要求的支撑关系 支撑的毕业要求二级指标点 对应课程目标 1.1 能将数学、自然科学和信息科学的语言工具用于计算机复 杂工程问题的表述。 目标 1 1.2 能针对计算机复杂工程问题的具体对象进行建模和求解 目标 2 2.2 对计算机复杂工程问题的一个系统或者过程，能选择或建 立一种模型，对关键影响因素进行分析。 目标 3 12.2 具备自主学习能力，能通过多种途径拓展自己的知识和 能力，包括理解能力、归纳总结能力和提出问题的能力等 目标 4 八、教学设计及对课程目标的支持 第一章 正则语言 1.教学内容 语言、确定性有限自动机 DFA 及其接收的语言、非确定性有限自动机 NFA 及其接收的语言、DFA 与 NFA 的等价、正则语言的性质、正则表达式、正则语 言的泵引理、正则文法。 本章教学支持的课程目标为目标 1、目标 2、目标 4。 2.教学重点 1）DFA 与 NFA 的等价 2）正则语言的判定 3）有限自动机的设计
3.教学难点1）正则表达式与正则语言的等价2）正则语言的判定第二章上下文无关语言1.教学内容上下文无关文法及其语言、上下文无关文法的二义性、上下文无关文法的化简及范式、上下文无关语言的性质、下推自动机及其接收的语言、下推自动机与上下文无关文法的等价、确定性下推自动机、下推自动机的泵引理。本章教学支持的课程目标为目标2、目标3和目标4。2.教学重点1）上下文无关文法在程序设计语言的设计与编译上的应用2）下推自动机与有限自动机的区别3）下推自动机的应用3.教学难点1）下推自动机与上下文无关文法的等价2）上下文无关语言的判定本章教学支持的课程目标为目标1、目标2、目标4。第三章图灵可识别语言1.教学内容标准图灵机及其语言、丘奇-图灵论题、标准图灵机的变种（包括多带图灵机以及非确定性图灵机等）、变种图灵机与标准图灵机的等价、通用图灵机、枚举器与图灵机不可识别语言。本章教学支持的课程目标为目标2与目标3。2.教学重点1）图灵机与有限自动机及下推自动机的区别2）各变种图灵机与标准图灵机的等价证明3）如何证明存在图灵机不可识别语言3.教学难点1）怎样用模拟方法（simulation）证明各种图灵机的等价2）对角化方法的应用
3.教学难点 1）正则表达式与正则语言的等价 2）正则语言的判定 第二章 上下文无关语言 1.教学内容 上下文无关文法及其语言、上下文无关文法的二义性、上下文无关文法的化 简及范式、上下文无关语言的性质、下推自动机及其接收的语言、下推自动机与 上下文无关文法的等价、确定性下推自动机、下推自动机的泵引理。 本章教学支持的课程目标为目标 2、目标 3 和目标 4。 2.教学重点 1）上下文无关文法在程序设计语言的设计与编译上的应用 2）下推自动机与有限自动机的区别 3）下推自动机的应用 3.教学难点 1）下推自动机与上下文无关文法的等价 2）上下文无关语言的判定 本章教学支持的课程目标为目标 1、目标 2、目标 4。 第三章 图灵可识别语言 1.教学内容 标准图灵机及其语言、丘奇-图灵论题、标准图灵机的变种（包括多带图灵 机以及非确定性图灵机等）、变种图灵机与标准图灵机的等价、通用图灵机、枚 举器与图灵机不可识别语言。 本章教学支持的课程目标为目标 2 与目标 3。 2.教学重点 1）图灵机与有限自动机及下推自动机的区别 2）各变种图灵机与标准图灵机的等价证明 3）如何证明存在图灵机不可识别语言 3.教学难点 1）怎样用模拟方法（simulation）证明各种图灵机的等价 2）对角化方法的应用
第四章语言的可判定性1.教学内容正则语言的可判定问题、上下文无关语言的可判定问题、图灵可识别语言与枚举器的关系、可判定语言与判定器、不可判定语言与对角化方法。本章教学支持的课程目标为目标2与目标4。2.教学重点1）图灵可识别语言与可判定语言的区别2）枚举器与判定器的区别3）上下文无关语言的可判定性3.教学难点1）如何构造判定器2）不可判定语言的证明第五章语言的归约1.教学内容线性受限自动机、可计算归约方法、不同语言间的可计算归约、可计算归约与可判定以及不可判定语言的关系。本章教学支持的课程目标为目标2与目标4。2.教学重点1）线性受限自动机与图灵机的区别2）图灵可识别语言上的不可判定问题3）几个常用不可判定语言之间的可计算归约3.教学难点1）不同语言间可计算归约的构造方法第六章时间复杂性理论1.教学内容时间复杂度、P语言、NP语言、co-NP语言、NP完全语言、首个NP完全语言的证明、多项式归约方法、交替式图灵机及多项式时间层级。本章教学支持的课程目标为目标2、目标3与目标4。2.教学重点1）多项式归约与可计算归约的区别2）SAT问题的NP完全证明
第四章 语言的可判定性 1.教学内容 正则语言的可判定问题、上下文无关语言的可判定问题、图灵可识别语言与 枚举器的关系、可判定语言与判定器、不可判定语言与对角化方法。 本章教学支持的课程目标为目标 2 与目标 4。 2.教学重点 1）图灵可识别语言与可判定语言的区别 2）枚举器与判定器的区别 3）上下文无关语言的可判定性 3.教学难点 1）如何构造判定器 2）不可判定语言的证明 第五章 语言的归约 1.教学内容 线性受限自动机、可计算归约方法、不同语言间的可计算归约、可计算归约 与可判定以及不可判定语言的关系。 本章教学支持的课程目标为目标 2 与目标 4。 2.教学重点 1）线性受限自动机与图灵机的区别 2）图灵可识别语言上的不可判定问题 3）几个常用不可判定语言之间的可计算归约 3.教学难点 1）不同语言间可计算归约的构造方法 第六章 时间复杂性理论 1.教学内容 时间复杂度、P 语言、NP 语言、co-NP 语言、NP 完全语言、首个 NP 完全 语言的证明、多项式归约方法、交替式图灵机及多项式时间层级。 本章教学支持的课程目标为目标 2、目标 3 与目标 4。 2.教学重点 1）多项式归约与可计算归约的区别 2）SAT 问题的 NP 完全证明
3）几个常用NP难问题的相互多项式归约方法3.教学难点1）针对不同问题如何构造实例上的多项式归约2）交替式图灵机与多项式时间层级九、教与学1.教学方法主要的教学环节包括课堂授课、课堂研讨、课后作业、课后留思考问题等。本课程的教学设计特色主要体现在如下四个方面：1）基于问题探究的教学方法。将围绕课程教学的重、难点，精心设计若干探究性问题，引导同学深入思考，加深所学重、难点知识的理解和应用；2）注意强化培养计算思维，提高逻辑思维和抽象思维能力：3）计算理论很多内容抽象，讲授概念时，多从具体、直观的实例出发，引导学生进入到抽象的自动机概念。教学生如何对具体问题进行抽象。理论联系实际，培养学生运用自动机进行建模的意识和能力，最终解决实际问题；4）辅导答疑：采用课堂内外当面答疑和网上答疑两种方式。尤其是网上在线答疑，开放畅通答疑交流的教与学的渠道。2.学习方法“计算理论”是一门理论性很强的核心专业基础课程，但同时又跟实际应用联系非常紧密。学习过程中，首先要注重对课程基本理论的钻研，要引导学生积极参与课堂讨论、深刻理解概念、原理和计算等的本质。其次，本课程的学习为后续的编译原理、数字电路与逻辑设计、算法、计算机网络、人工智能等课程提供必要的模型基础。第三，独立完成布置的各种作业题，独立思考探究课堂或课后留下的思考问题，加深对课程理论知识的理解，同时，训练学生发现问题、分析问题和解决问题的能力。十、学时分配序号学时分配主要内容16第一章正则语言62第二章上下文无关语言36第三章图灵可识别语言44第四章语言的可判定性45第五章语言的归约
3）几个常用 NP 难问题的相互多项式归约方法 3.教学难点 1）针对不同问题如何构造实例上的多项式归约 2）交替式图灵机与多项式时间层级 九、教与学 1.教学方法 主要的教学环节包括课堂授课、课堂研讨、课后作业、课后留思考问题等。 本课程的教学设计特色主要体现在如下四个方面： 1）基于问题探究的教学方法。将围绕课程教学的重、难点，精心设计若干 探究性问题，引导同学深入思考，加深所学重、难点知识的理解和应用； 2）注意强化培养计算思维，提高逻辑思维和抽象思维能力； 3）计算理论很多内容抽象，讲授概念时，多从具体、直观的实例出发，引 导学生进入到抽象的自动机概念。教学生如何对具体问题进行抽象。理论联系实 际，培养学生运用自动机进行建模的意识和能力，最终解决实际问题； 4）辅导答疑：采用课堂内外当面答疑和网上答疑两种方式。尤其是网上在 线答疑，开放畅通答疑交流的教与学的渠道。 2.学习方法 “计算理论”是一门理论性很强的核心专业基础课程，但同时又跟实际应用联 系非常紧密。学习过程中，首先要注重对课程基本理论的钻研，要引导学生积极 参与课堂讨论、深刻理解概念、原理和计算等的本质。其次，本课程的学习为后 续的编译原理、数字电路与逻辑设计、算法、计算机网络、人工智能等课程提供 必要的模型基础。第三，独立完成布置的各种作业题，独立思考探究课堂或课后 留下的思考问题，加深对课程理论知识的理解，同时，训练学生发现问题、分析 问题和解决问题的能力。 十、学时分配 序号 主要内容 学时分配 1 第一章 正则语言 6 2 第二章 上下文无关语言 6 3 第三章 图灵可识别语言 6 4 第四章 语言的可判定性 4 5 第五章 语言的归约 4
661第六章时间复杂性理论32总计十一、课程考核与成绩评定1.课程成绩构成课程最终成绩由平时成绩、课程期末考试成绩综合而成，各部分成绩的比例如下：1）作业成绩及平时成绩：30%。作业将引导学生复习和巩固讲授的内容（基本理论、基本方法、基本理论分析与计算、课外思考问题解决等），主要考察作业完成率和完成质量；再综合参考上课签到记录。2）期末考试成绩：70%。主要考核计算理论基础知识、基本方法的掌握程度和应用能力，是对学生学习情况的全面检验。考试强调对计算理论的基本概念、基本方法和技术的掌握，并通过综合型试题考核学生运用所学知识进行问题建模进一步用自动机的模型方法表达实际工程问题的能力。考试采用书面闭卷考试形式。题型为判断、填空、计算、证明、综合应用等题型。课程考核成绩评定如表1所示。表1计算理论课程考核与成绩评定考核与评价方式及成绩比例课程目标成绩占比(约）作业期末考试1030131%2104038%352019%451012%2.考核与评价标准1）作业成绩考核与评价标准表2计算理论作业考核与成绩评定评价标准优秀良好及格不及格按时提交作业，概念按时提交作业，概念按时提交作业，概念未按时交作业，概念准确，计算结果正准确，计算结果大多基本准确，计算结果欠准确，计算结果错确，分析充分，论述正确，分析较充分，存在少量错误，分析误较多。清晰，层次分明。论述清晰，层次分不充分，论述基本清明。晰。2）课程考核与成绩评定
6 第六章 时间复杂性理论 6 总计 32 十一、课程考核与成绩评定 1.课程成绩构成 课程最终成绩由平时成绩、课程期末考试成绩综合而成，各部分成绩的比例 如下： 1）作业成绩及平时成绩：30%。作业将引导学生复习和巩固讲授的内容（基 本理论、基本方法、基本理论分析与计算、课外思考问题解决等），主要考察作 业完成率和完成质量；再综合参考上课签到记录。 2）期末考试成绩：70%。主要考核计算理论基础知识、基本方法的掌握程 度和应用能力，是对学生学习情况的全面检验。考试强调对计算理论的基本概念、 基本方法和技术的掌握，并通过综合型试题考核学生运用所学知识进行问题建模， 进一步用自动机的模型方法表达实际工程问题的能力。考试采用书面闭卷考试形 式。题型为判断、填空、计算、证明、综合应用等题型。 课程考核成绩评定如表 1 所示。 表 1 计算理论课程考核与成绩评定 课程目标 考核与评价方式及成绩比例 作业 期末考试 成绩占比（约） 1 10 30 31% 2 10 40 38% 3 5 20 19% 4 5 10 12% 2.考核与评价标准 1）作业成绩考核与评价标准 表 2 计算理论作业考核与成绩评定 评价标准 优秀 良好 及格 不及格 按时提交作业，概念 准确，计算结果正 确，分析充分，论述 清晰，层次分明。 按时提交作业，概念 准确，计算结果大多 正确，分析较充分， 论述清晰，层次分 明。 按时提交作业，概念 基本准确，计算结果 存在少量错误，分析 不充分，论述基本清 晰。 未按时交作业，概念 欠准确，计算结果错 误较多。 2）课程考核与成绩评定
根据期末考试的试卷评分标准进行评定。十二、教材及推荐参考书（一）教材[1] Michael Sipser. Introduction to the Theory of Computation, 3rd edition, CengageLearning,2012（二）推荐参考书[1] John E.Hopcroft, Rajeev Motwani, Jeffrey D.Ullman.Introduction to AutomataTheory,Languages,and Computation (3rd Edition),Addison-Wesley LongmanPublishing,2006[2]张立昂.可计算性与计算复杂性导引（第3版），北京大学出版社，2011.计算理论课程组（华强胜）2021年5月修订
根据期末考试的试卷评分标准进行评定。 十二、教材及推荐参考书 （一）教材 [1] Michael Sipser. Introduction to the Theory of Computation, 3rd edition, Cengage Learning, 2012. （二）推荐参考书 [1] John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley Longman Publishing, 2006. [2] 张立昂. 可计算性与计算复杂性导引（第 3 版），北京大学出版社，2011. 计算理论课程组（华强胜） 2021 年 5 月修订