1

我的《计算机算法的设计与分析》今天已经到了。在第一章中，作者介绍了图灵机。我还有另外两本算法教科书，《算法导论》和《算法设计手册》，但它们都没有谈到图灵机，尽管它们在算法和数据结构方面很有名。

我想了解图灵机和算法/数据结构之间的关系是什么。了解图灵机成为算法专家真的很重要吗？

4

2 回答 2

7

图灵机只是分析计算的理论工具，即。我们可以通过创建一个计算它的图灵机来指定一个算法。它们在可计算性的研究中非常有用，也就是说，如果有可能计算一个函数。Hopcroft 和 Ullmann的经典著作中讨论了图灵机和其他几种形式语言结构。例如，在Garey 和 Johnson 所著的这本书中讨论 NP 完备性时，图灵机也出现了。

一般来说，书籍和图灵机都是非常理论化的。如果您以学术方式对算法感兴趣，我会推荐它们。但是，如果您想实际了解在真实计算机上实现的算法并在真实数据上运行，那么我想说，对图灵机有一个粗略的了解很重要。

于 2011-08-20T19:06:31.213 回答
6

图灵机在描述数据结构和算法时很重要的原因是它们提供了一个数学模型，我们可以在其中描述算法是什么。大多数时候，算法是使用高级语言或伪代码来描述的。例如，我可能会描述一种算法来查找数组中的最大值，如下所示：

Set max = -infinity
For each element in the array:
    If that element is greater than max:
        Set max equal to that element.

从这个描述中很容易看出算法是如何工作的，并且很容易将其翻译成源代码。但是，假设我已经写出了这个描述：

Guess the index at which the maximum element occurs.
Output the element at that position.

这是一个有效的算法吗？也就是说，我们能不能说“猜指数”，严格定义它的含义？如果我们允许这样做，需要多长时间才能做到这一点？如果我们不允许，为什么不呢？第一个描述与第二个描述有什么不同？

为了对算法有一个严格的数学定义，我们需要有一些关于计算机如何工作以及它能做什么和不能做什么的正式模型。图灵机是正式定义计算的一种常用方法，但也可以使用其他方法（寄存器机器、字符串重写系统、Church 的lambda 演算等）。一旦我们定义了计算的数学模型，我们就可以开始讨论什么样的算法描述是有效的——即那些可以使用我们的计算模型来实现的描述。

许多现代算法严重依赖于底层计算模型的属性。例如，缓存忽略算法假设计算模型具有一些未知大小的内存缓冲区和两层内存。一些算法要求底层机器是跨二分法的，这意味着机器字的大小必须至少大到足以容纳任何问题的大小。随机算法需要正式定义随机性以及机器如何使用随机值。非确定性算法需要一种指定非确定性计算的方法。基于电路的算法必须知道哪些电路原语是允许的，哪些是不允许的。量子计算机需要正式定义哪些操作是允许的，哪些是不允许的，以及在给定输出是概率的情况下对算法的定义。分布式算法需要一个正式的跨机器通信定义。

简而言之，在描述算法时明确什么是允许的和不允许的是很重要的。然而，要成为一名优秀的程序员或对算法有扎实的掌握，你不需要了解图灵机的内里和外在，也不需要知道如何使用它们对特定问题进行编码的具体细节. 但是，您应该知道的是计算模型可以做什么和不能做什么，以及每次操作的成本是多少。通过这种方式，您可以推断算法的效率如何，它们使用了多少各种资源（时间、空间、内存、通信、随机性、不确定性等）。但话虽如此，如果您不了解底层模型，请不要惊慌。

考虑计算的底层模型还有另一个原因——讨论它的局限性。每个计算模型都有其局限性，在某些情况下，您可以证明某些算法不可能针对某些问题存在，或者任何可以解决某些问题的算法都必须使用一定数量的给定资源。算法设计中最常见的例子是 NP-hardness 的概念。有些问题被推测是极其“难以”解决的，但是这个困难的正式定义依赖于图灵机和非确定性图灵机的知识。在这种情况下，了解模型很有用，因为它可以让您推断某些问题的计算可行性。

希望这可以帮助！

于 2011-08-20T21:00:54.437 回答