Theory of Computation

课程简介

主题 1. 自动机 有限自动机（DFA，NFA）。 2. 正则表达式与语言 正则表达式，DFA与正则表达式之间的转换，正则语言的性质。 3. 上下文无关文法与语言 上下文无关文法，语法树，文法的歧义性，规范形式，丘奇-图灵层次结构。 4. 推down自动机 推down自动机（PDA），泵引引理，PDA的性质。 5. 图灵机 图灵机（TM），图灵机的扩展，与计算机的关系。 6. 计算与可判定性 计算性，丘奇-图灵论题，停机问题，其他不可判定问题，归约技术。 7. 不可解问题 P类与NP类，NP完全性。 8. 高级主题与应用 多项式空间图灵机，随机图灵机，素性测试，密码学，博弈论，量子计算。

学习目标

1. 为学生提供计算理论的概念； 2. 培养学生理解数学证明的能力（计算理论）。

先修要求

先修课程：COMP3011

教学模式

讲授为学生提供主题的主要概念，并通过全面的例子帮助学生理解。 习题课为学生提供实践技巧的机会。 作业帮助学生培养设计和分析技能。