理论计算机初步:算法和计算模型

作者: , 共 1178 字
系列:理论计算机初步

查看该系列所有文章

下面是 wikipedia 上 算法的定义

算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据,经过 计算机程序 的有限次运算,能够得出所要求或期望的终止状态或输出数据。

算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

一个简单而且耳熟能详的算法的例子是求最大公约数的 辗转相除法 :给出两个数,要求出他们俩的最大公约数。在小学的时候,我们就知道这样做就行了:将大数除以小数,用所得余数替换大数,继续用这两个数中大者除以小者,用所得余数替换较大者,继续下去,直到所得余数为 0 ,此时除数即为所求的最大公约数。下面是一个实例:(15, 21) = (15, 6) = (3, 6) = (3, 0) = 3。又如,要判断某个数是否为质数,只需枚举所有比它小的数,检验是否其约数即可。

算法是理论计算机的灵魂。几乎所有问题都围绕它而来。为了讨论算法的性质,在理论计算机中,算法已不限于只是上面定义中的计算机程序。或者说,这里计算机的含义被大大扩广了。

我们平时所说和所使用的计算机,基于图灵提出的 确定型图灵机 模型。它是最好理解的:给出固定的程式,模型按照程式和输入完全 确定性 地运行。

但为了理解算法和这种确定型图灵机的能力,人们又发展了许多其它各式各样的图灵机模型。其中最为有名的是 非确定型图灵机 。这种计算模型,它在进行计算的时候,会自动选择最优路径进行计算。通俗地说,它 有预测能力 。比如说,为了说明某个数是合数,非确定型图灵机会猜测一个数,恰好是其因子,从而证明了它不是质数。

确定型和非确定型图灵机的计算性能所引起的 P vs NP 问题,一直是理论计算机科学的核心问题,这点下面专文论述。

另一个引起广泛关注的计算机模型是 量子计算机模型 。与上面的非确定型图灵机只存在于人们的想象中不同,量子计算机在物理上是可以实现的。关于量子计算理论,以后也有单独的介绍性文章。

虽然上面的各种计算模型的效率可能不同,比如非确定性图灵机判定一个数是合数便要快得多,但是它们的计算能力是完全一样的。也就是在某个计算模型上面运行的算法,可以被其余模型模拟实现。

这些计算模型的计算能力是一样的,那是不是世界上所有问题都有算法呢?看上去这似乎是一个哲学问题,但答案早就有了,有些问题是不可能能通过算法求解的,连下面这个看上去很简单的问题都不行:给出一些分数(指 12/23 , 18/9 这样的),问是否可以从中选出若干个分数数(可以重复选取),使得按一定顺序排起来,其分母连起来和分子连起来恰好一样?

Q. E. D.

系列: 理论计算机初步 »
我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是 Andrew Yao 的研究方向
类似文章:
前面 已经提到了显示中大多数难解问题问题最后都被证明是 NP- 完全问题。这意味着,除非 NP=P ,它们是不可能有多项式时间算法的(而且,在 这篇文章 提到即使 NP=P ,人们也可能找不到一个 NP 完全问题的「有效」算法)。
我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是 Andrew Yao 的研究方向
英文是 communication complexity ,不知道该翻译成通信复杂性,还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域,在过去 30 年衍生了很多东西。它是我的研究的主要内容,这里简略介绍一下。
上篇文章 已经提到, P vs NP 是理论计算机科学的核心问题。从数学的角度来说,它和其他历史上有名的数学问题一样,给与人们一个智力上重大的挑战。而更为重要的是,在无数与计算有关的的学术领域中, NP- 完全问题以各种不同形式层出不穷。因此,这并不是一个纯粹的与世独立的智力游戏,而是对计算机科学有全面影响力的问题。
我所学的专业英文名是 Theoretical Computer Science ,理论计算机科学,在这里我就简化成理论计算机了。具体研究些什么呢,下面是 Andrew Yao 的研究方向