计算机算法导论：设计、分析与复杂性

计算机算法——设计与分析导论中文翻译 本书是计算机算法领域的一本经典教材，涵盖了算法设计和分析的基础知识。本书由 Sara Baase 和 Allen Van Gelder 编写，并由 sttony.dark 翻译。 **算法的定义和历史** 算法可以定义为一套清楚的简单指令，按照这套指令可以解决某个问题和计算某个函数。多种形式的计算模型是设计和研究出来的。早期这个领域工作的重点叫可计算理论，其主要是描述或总结那些可算法解决问题的特征，以及指出那些问题是不能算法解决的。 **停机问题** 阿兰·图灵建立的一个重要的否定结论是：证明“停机问题”（halting problem）是不可解决的。停机问题是说：能否判断一个任意给出的算法（或计算机程序）在给定输入的情况下是否最终停止（也就是说是否进入死循环）。这个问题不能用计算机程序解决。 **可计算理论** 可计算理论对于计算机科学是明显和基础的本质，但是判断一个问题是否在理论上可以在计算机上解决的知识还不足以告诉在实际中是否也可以。 **算法设计和分析** 算法设计和分析是计算机科学中一个非常重要的分支。一个实际程序明确的时间空间要求是很重要的。因此，他们变成了计算机科学中一个分支的主题，叫计算复杂性。本书涵盖了算法设计和分析的基础知识，包括算法的定义、设计和分析方法、时间和空间复杂性等方面的内容。 **计算复杂性** 计算复杂性是计算机科学中一个非常重要的分支，关心一套正式、有些抽象的关于可计算函数复杂性的理论。度量复杂性的公理已经公式化了；他们是如此的基础和一般以致一个程序执行。 **国际象棋程序** 例如，可以写出一个完美的国际象棋程序。这并不是一件很困难的事情；棋子在棋盘上的摆放方式是有限的，在一定的规则下棋局总会在有限步之后结束。程序可以考虑计算机可能走的每一步，对手对这一步所所有可能的响应，再考虑如何应对对手这一步……一直到每一种可能的走法到达结束。既然知道了每一步的最后结果，计算机就可以选择一个最好的。 本书涵盖了算法设计和分析的基础知识，包括算法的定义、设计和分析方法、时间和空间复杂性等方面的内容。同时，本书还涵盖了计算复杂性和国际象棋程序等相关知识点。