科罗拉多大学计算理论导引课程考点梳理

科罗拉多大学计算理论导引课程介绍了自动机理论、可计算性理论和复杂性理论的基础，研究了自动机和形式语言之间的关系，阐述了哪些问题可以通过计算手段解决(可判定性与不可判定性)，同时探讨了与问题的计算复杂性相关的概念。以下是这门课的考点梳理。

一、计算理论导引课程考点

1、常规语言：确定性有限状态机；非确定有限状态机；正则表达式；常规语言性质；非常规语言(抽取引理)。

2、上下文无关语言：上下文无关文法；下推自动机；上下文无关语言的属性；CFL抽取引理。

3、可计算性理论：图灵机及其变体；丘奇-图灵论题；可判定语言；不可判定性；使用问题归约证明给定问题的不可判定性；赖斯定理；著名的不可判定问题，如邮政通信问题(PCP)，平铺问题，多栈和双计数器机器的停机问题。

4、复杂性理论：时间和空间复杂性；复杂性类P和NP，以及NP-完全性；著名的NP完全问题；复杂性类PSPACE和PSPACE-完备性；复杂度类L和NL，以及NL-完全性。

5、专题：一元二阶逻辑和自动机；单词和树的正则变换；描述性复杂性；随机计算；量子计算；交互式证明和复杂性类IP；PCP定理和逼近的困难(计算复杂性)；时间和混合自动机；概率自动机。

二、计算理论导引课程目标

计算理论导引课程的目标是介绍计算理论，涵盖以下三个理论计算机科学分支：

1、自动机理论

(1)通过形式语言形式化问题的概念。

(2)使用称为自动机的“抽象计算设备”来形式化计算的概念。

(3)理解问题类别或形式语言的层次结构。

(4)理解自动机类别的层次结构(有限自动机、下推自动机和图灵机)。

2、可计算性理论

(1)理解丘奇-图灵论题。

(2)理解不可判定性的概念，即当一个问题不能用计算机解决时。

(3)如何用问题归约的概念来表示不可判定性。

3、复杂性理论

(1)复杂性分类：如何根据时间和空间需求对可判定的问题进行分类。

(2)复杂性类P和NP，以及难处理性(NP-完全性)。

(3)如何证明NP完全性？

(4)空间复杂性：NL-完全性和PS apce-完全性。

希望我们梳理的科罗拉多大学计算理论导引课程考点以及课程目标对你的学习有帮助。你可以参考上述信息进行学习规划。如果你在学习过程中遇到问题，随时可以联系我们哟。