计算机算法-设计与分析导论.pdf

计算机算法 －设计与分析导论 Sara Baase Allen Van Gelder 译者：sttony.dark 前言 第一章 分析算法和问题：原理与例子 1.1 概述 11..11 概概述述 说一个问题是算法可解的（非正式的），意味着可以编写一个计算机程序，如果我们允 许这个程序有足够的运行时间和存储空间，这个程序可以为任何输入处理出一个正确的结 果。在20 世纪30 年代，计算机出现之前，数学家们就已经积极的定型和研究算法的概念。 算法被解释成（非正式的）一套清楚的简单指令，按照这套指令可以解决某个问题和计算某 个函数。多种形式的计算模型是设计和研究出来的。早期这个领域工作的重点叫可计算理论， 其主要是描述或总结那些可算法解决问题的特征，以及指出那些问题是不能算法解决的。由 阿兰. 图灵建立的一个重要的否定结论是：证明“停机问题”（halting problem）是不可解决 的。停机问题是说：能否判断一个任意给出的算法（或计算机程序）在给定输入的情况下是 否最终停止（也就是说是否进入死循环）。这个问题不能用计算机程序解决。 尽管可计算理论对于计算机科学是明显和基础的本质，但是判断一个问题是否在理论上 可以在计算机上解决的知识还不足以告诉在实际中是否也可以。例如，可以写出一个完美的 国际象棋程序。这并不是一件很困难的事情；棋子在棋盘上的摆放方式是有限的，在一定的 规则下棋局总会在有限步之后结束。程序可以考虑计算机可能走的每一步，对手对这一步所 有可能的响应，再考虑如何应对对手这一步…… 一直到每一种可能的走法到达结束。既然 知道了每一步的最后结果，计算机就可以选择一个最好的。考虑棋子在棋盘上合理的排列（这 比步数要少的多），估计就超过1050。检查所有可能结果的程序需要运行几千年，如此程度 的程序不能运行。 实际应用中大量的问题都是可解决的——就是说可以为他们写出程序——但是对一个 实用的程序来说时间和存储空间的要求是十分重要的。一个实际程序明确的时间空间要求是 很重要的。因此，他们变成了计算机科学中一个分支的主题，叫计算复杂性。本书并不包含 这一分支，这一分支关心一套正式、有些抽象的关于可计算函数复杂性的理论。（解决一个 问题等价于根据一套输入计算出函数的输出。）度量复杂性的公理已经公式化了；他们是如 此的基础和一般以致一个程序执行指令的条数和需要存储空间的 bit 数都可以作为 复杂性 度量。使用这些公理，我们可以证明任意一个复杂问题的存在，以及问题没有最好的程序。 - 1 - （Using these axioms, we can prove the existence of arbitrarily complex problems and of problems for which there is no best program.） 本书中学习的计算复杂性分支只关心分析特殊问题和特殊算法。本书打算帮助读者建立 一份解决通用问题的经典算法的清单，分析算法、问题的一些一般性的设计技术、工具和指 导方针，以及证明正确性的方法。我们将呈现、学习和分析计算机程序中常用的解决各种问 题的算法。我们将分析算法执行所需的时间，我们也分析算法执行所需要的空间。在描述各 种问题的算法的时候，我们将看到几种经常被证明很有用的算法技术。因此我们暂停一下谈 一谈一些一般性的技术，比如分而治之（divide-and-conquer）、贪婪算法（greedy algorithms）、 深度优先有哪些信誉好的足球投注网站（depth-first search）和动态编程（dynamic programming）。我们也将学习问题 本生的复杂性，就是不管用什么算法解决问题所需固有的时间和空间。我们将学习分类NP 完全问题——目前还没有找到这类问题的有效算法——并试图用一些试探的方法找到有用 的结果。我们也将说明用DNA 代替电