巴斯大学课程讲解之计算理论的三个分支

计算理论(TOC)是计算机科学的一个分支，研究如何使用算法解决问题以及解决问题的效率。现实世界中的计算机所执行的计算本身就具有数学模型的功能，并以系统的方式解决问题。计算理论的精髓在于帮助创建高效、切中要害的数学和逻辑模型。由于所有实现逻辑的机器都使用 TOC，因此学习 TOC 可以让学生深入了解计算机硬件和软件的局限性。

一、计算问题的关键考虑因素

a.什么可以计算，什么不可以计算。

b.此类计算的速度。

c.此类计算期间使用的内存量。

二、计算理论的重要性

计算理论构成了以下基础：

a.编写在计算设备中运行的高效算法。

b.编程语言的研究及其发展。

c.高效的编译器设计和构建。

三、计算理论的三个分支

计算理论有三个分支组成，他们是自动机原理、可计算性理论以及复杂性理论。

1.自动机理论

数学家和计算机科学家发展了计算机科学的这一理论分支，通过使用定义明确的抽象计算装置(模型)来简化计算逻辑。自动机理论是对抽象计算设备的研究。它为生物计算机和量子计算机等计算设备的设计和分析提供了一个形式框架。这些模型在计算机科学的多个领域(包括应用和理论)都至关重要。

自动机是一种机器，它根据输入进行单一操作，并按照确定的模式或配置产生所需的输出。通过自动机，我们可以了解如何使用自动机解决计算机问题和功能。

自动机理论的分支有：

a.有限自动机(FA)：这是一种计算能力较低的计算机模型。这种模型适用于内存有限的设备。它是一种简单的抽象机器，由五个元素定义其工作方式和处理问题的方式。有限自动机(FA)是一个有限的状态集合，带有根据输入符号遍历状态的规则(转换函数)。有限自动机通过从左到右读取输入字符串来接受或拒绝它们。

b.上下文语法(CFG)：这是比 FA 更强大的抽象模型，主要用于编程语言和自然语言研究。

c.图灵机：这是具有无限内存(磁带形式)和读取头的真实计算机的抽象模型。它们是比 FA、CFG 和正则表达式更强大的计算模型。

2.可计算性理论

可计算性理论决定了一个问题是否能被抽象机器 "解决"。有些问题是可计算的，而有些问题则不可计算。根据问题的性质，会使用不同的计算模型，如图灵机和有限状态机。

3.复杂性理论

复杂性理论是理论计算机科学的一个分支，它以解决问题所需的资源(时间和空间)作为衡量标准，研究解决问题的成本。算法的运行时间取决于其输入，通常随输入的大小而增加。

要衡量复杂性，需要对算法进行分析，以了解解决问题所需的时间(时间复杂性)。在评估算法时，重点关注输入量增加时的相对增加率。由于算法的精确运行时间通常是一个复杂的表达式，我们通常只使用一个估计值。在确定算法的时间复杂度时，需要测量算法所需的时间与输入大小(n)的函数关系。

T(n) 的时间复杂度使用Big O表示法表示，其中仅考虑代数表达式中的最高阶项，只考虑常量项。

分析算法时常见的运行时间是：

O(1) - 恒定时间或恒定空间，无论输入大小如何。

O(n) - 线性时间或线性空间，其中要求随着输入的大小均匀增加。

O(log n) - 对数时间，其中要求以对数性质增加。

O(n^2) - 二次时间，其中要求以二次性质增加。

该分析基于可用于定义每种算法成本的 2 个界限。

复杂性的主要分类包括：

P 类： P 类由可在多项式时间内解决的问题组成。对于某个常数 k，这些问题可以在 O(n^k) 时间内解决，其中 n 是问题的输入大小。它旨在捕捉高效计算的概念。

NP类：它构成了所有问题的类，其解决方案可以通过非确定性图灵机在多项式时间内实现。NP 是用于对决策问题进行分类的复杂性类别。

复杂性理论的一个主要贡献者是用于解决问题的算法的复杂性。在用于解决计算问题的多种算法中，有些算法的复杂性范围从相当复杂到非常复杂。

算法越复杂，给定问题的计算复杂度就越高。

海马课堂专业课程辅导，2300+严选硕博学霸师资，针对学生的薄弱科目和学校教学进度，匹配背景相符的导师，根据学生情况进行1V1专属备课，上课时间灵活安排，中英双语详细讲解课程中的考点、难点问题，并提供多方位的课后辅导，辅助学生掌握全部课程知识，补足短板。