computer science

theory of computation

  1. 什么是计算理论。

    狭义的理解是我们的数值运算是计算,广义上来说,只要可以通过有限的确定的步骤处理原始数据,得到结果的过程,就是可以称为计算。因此可以理解为计算理论是研究计算的一般性质的数学理论。

  2. 计算机程序

    计算机的多样性就是依赖于程序,一个程序可以说是算法和数据结构的结合,而算法就是逻辑和控制的结合。

  3. 算法

    算法是为解决一个特定问题所采取确定的有限步骤。算法由操作和数据组成。算法是计算机的灵魂,因此不论考研还是工作面试,都离不开算法。

  4. 可计算性

    对于给定的一个输入,可以在有限的确定步骤内给出答案,该问题是可计算的。

    我们可以判断某个问题是否可计算,但是更多问题我们不可判断它是否可计算,经典问题有停机问题。

  5. 停机问题

    对于任意的图灵机和输入,是否存在一个算法,用于判定图灵机在接收初始输入后可达停机状态。若能找到这种算法,停机问题可解;否则不可解。

  6. 计算复杂性

    指用计算机求解问题的难易程度。衡量标准是时间复杂度和空间复杂度。时间复杂度指完成一个算法需要的指令数,空间复杂度指完成一个算法需要的存储空间。

  7. P类问题和NP类问题

    按复杂性将问题分为不同的类。很多问题我们可以在多项式时间内求解,这是P类问题,NP类问题是它的潜在解可以在多项式时间内被证实或证伪(区别是一个求解,一个证明)。显然P类问题属于NP类问题。

  8. 公钥密码学

    我们可以发现,NP类问题很难求解,但是验证却简单多了,这个特性被用在了密码学。例如给定一个大整数要求找到它的素数,这是一个公认的难题,但是如果我告诉你它的素数,你却可以很简单地验证它是否为素数,RSA 加密算法就是基于此特性发明的。