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

《计算机算法-设计与分析导论》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机算法－设计与分析导论SaraBaaseAllenVanGelder译者：sttony.dark前言第一章分析算法和问题：原理与例子1.1概述说一个问题是算法可解的（非正式的），意味着可以编写一个计算机程序，如果我们允许这个程序有足够的运行时间和存储空间，这个程序可以为任何输入处理出一个正确的结果。在20世纪30年代，计算机出现之前，数学家们就已经积极的定型和研究算法的概念。算法被解释成（非正式的）一套清楚的简单指令，按照这套指令可以解决某个问题和计算某个函数。多种形式的计算模型是设计和研究出来的。早期这

2、个领域工作的重点叫可计算理论，其主要是描述或总结那些可算法解决问题的特征，以及指出那些问题是不能算法解决的。由阿兰.图灵建立的一个重要的否定结论是：证明“停机问题”（haltingproblem）是不可解决的。停机问题是说：能否判断一个任意给出的算法（或计算机程序）在给定输入的情况下是否最终停止（也就是说是否进入死循环）。这个问题不能用计算机程序解决。尽管可计算理论对于计算机科学是明显和基础的本质，但是判断一个问题是否在理论上可以在计算机上解决的知识还不足以告诉在实际中是否也可以。例如，可以写出一个完美的国际

3、象棋程序。这并不是一件很困难的事情；棋子在棋盘上的摆放方式是有限的，在一定的规则下棋局总会在有限步之后结束。程序可以考虑计算机可能走的每一步，对手对这一步所有可能的响应，再考虑如何应对对手这一步……一直到每一种可能的走法到达结束。既然知道了每一步的最后结果，计算机就可以选择一个最好的。考虑棋子在棋盘上合理的排列（这比步数要少的多），估计就超过1050。检查所有可能结果的程序需要运行几千年，如此程度的程序不能运行。实际应用中大量的问题都是可解决的——就是说可以为他们写出程序——但是对一个实用的程序来说时间和存储

4、空间的要求是十分重要的。一个实际程序明确的时间空间要求是很重要的。因此，他们变成了计算机科学中一个分支的主题，叫计算复杂性。本书并不包含这一分支，这一分支关心一套正式、有些抽象的关于可计算函数复杂性的理论。（解决一个问题等价于根据一套输入计算出函数的输出。）度量复杂性的公理已经公式化了；他们是如此的基础和一般以致一个程序执行指令的条数和需要存储空间的bit数都可以作为复杂性度量。使用这些公理，我们可以证明任意一个复杂问题的存在，以及问题没有最好的程序。-1-（Usingtheseaxioms,wecanpro

5、vetheexistenceofarbitrarilycomplexproblemsandofproblemsforwhichthereisnobestprogram.）本书中学习的计算复杂性分支只关心分析特殊问题和特殊算法。本书打算帮助读者建立一份解决通用问题的经典算法的清单，分析算法、问题的一些一般性的设计技术、工具和指导方针，以及证明正确性的方法。我们将呈现、学习和分析计算机程序中常用的解决各种问题的算法。我们将分析算法执行所需的时间，我们也分析算法执行所需要的空间。在描述各种问题的算法的时候，我们将看

6、到几种经常被证明很有用的算法技术。因此我们暂停一下谈一谈一些一般性的技术，比如分而治之（divide-and-conquer）、贪婪算法（greedyalgorithms）、深度优先搜索（depth-firstsearch）和动态编程（dynamicprogramming）。我们也将学习问题本生的复杂性，就是不管用什么算法解决问题所需固有的时间和空间。我们将学习分类NP完全问题——目前还没有找到这类问题的有效算法——并试图用一些试探的方法找到有用的结果。我们也将说明用DNA代替电子计算机来向解决这类问题接近。

7、最后，我们将介绍并行计算机算法的主题。在下面的一节中我们将给出算法描述语言的大概，回顾一些本书用到的背景知识和工具，并展示在分析算法中涉及的主要概念。1.2Java作为算法描述语言通过平衡多种条件之后，我们选择Java作为算法描述语言。算法必须易读。我们想将注意力放在一个算法的策略和技术上，而不是编译器关心的申明和语法细节。语言必须支持数据抽象和问题分解，这样才能够简单清楚的表示一个算法的思想。语言必须提供一种实际的实现（即已经了编译器，原文Thelanguageshouldprovideapractical

8、pathwaytoimplementation.）。他必须在大部分平台上可用而且提供程序开发的支持。实际的实现和运行一个算法能增强学生的理解，不能陷入与编译器、调试器失败的战斗中。最后因为本书是教算法的，不是程序设计，能轻易的将算法转换成读者使用的各种语言必须是合理的要求，特殊语言特性必须减到最少。在我们要求的许多方面Java表现的很好，尽管我们没有宣称他是理想的。他支持自然的数据抽象。Java是类