算法设计技巧与分析

章节摘录

插图：1.1引言最一般的直觉意义上的算法①就是一个由有限的指令集组成的过程。从可能的输人集中给这个过程一个输入，如果系统地执行该指令集，那么对于这个特定的输人，当输出存在时，就能得到输出；当没有输出时，就什么结果也得不到。可能的输入集是指能让该算法给出一个输出的所有输入。如果对于一个特定的输入有一个输出，那么就说该算法能用于这一输入，执行该算法能够得到相应的输出。我们要求算法对于每一个输入能停下来，这意味着每一条指令只需要有限的时间，同时每一个输入的长度是有限的。我们还要求对于一个合法输人所对应的输出是惟一的。也就是说当算法从一个特定的输入开始，多次执行同一指令集时，结果总是相同，从这个意义上讲算法是确定的。第14章研究随机算法时将放宽这一条件。在计算机科学领域，算法设计与分析是十分重要的。正如Donald E.Knuth所说，“计算机科学就是算法的研究”。这没什么可惊讶的，因为计算机科学的每个领域都高度依赖于有效算法的设计。举个简单例子，编译程序和操作系统不外乎就是具有特定目标的算法的直接实现。本章的目的有两个：首先介绍一些简单的算法，特别是与搜索和排序相关的那一类；其次讲述用于算法设计和分析的基本概念。由于算法的“运行时间”这一概念对于设计有效算法是至关重要的，我们将对它进行深入讨论。总之，时间是衡量算法有效性的最好测度。我们也会讨论其他重要资源的测度，比如一个算法所需要的空间等。本章给出的算法虽然简单，但它们是解释一些算法概念的许多例子的基础。从简单有用的、在更复杂的算法中被用做构件模块的算法开始，是非常有益的。1.2 历史背景20世纪早期，尤其在30年代，能否用一种有效的过程（即相当于现在所说的算法）来求解问题受到广泛关注。在那时，人们的注意力是放在问题的可解或不可解的分类上，即是否存在有效过程来求解问题。为此，产生了对计算模型的需要。如果应用这个模型能够建立一个算法来求解这个问题，那么这个问题就被归人可解的问题类。其中的一些模型是哥德尔（del）的递归函数、丘奇（Church）的入演算、波斯特（Post）的波斯特机和图灵（luring）的图灵机。RAM计算模型是作为实际的计算机的理论上的补充被引人的。根据丘奇的论断，所有这些模型是等效的，即意味着如果一个问题在其中的一个模型上是可解的，那么对于所有其他的模型，该问题都是可解的。

前言

算法设计与分析是计算机科学技术中处于核心地位的一门专业基础课，越来越受到重视。本书系统地介绍了一些常用的、经典的算法设计技术，并给出了详细的复杂性分析。全书分七部分19章，内容含有递归技术、分治、动态规划、贪心算法、图的遍历等，同时也包括了近年来发展迅速的近似算法、概率算法和几何算法，对于NP完全问题等复杂性理论的基础内容，也做了基本的、清楚的描述。本书结构合理，选材适度，陈述简明易读，每章附有适量的各种类型练习，没有过难或研讨性题目，适合于教学和自学。出版后已被许多大学选做本科和研究生的教材及参考书。作者M.H.Alsuwaiyel在沙特阿拉伯的King Fahd University of Petroleum & Minerals（KFUPM，皇家法哈德石油矿业大学）完成大学学业，在南加州（USC）大学获得计算机科学硕士和博士学位。作者曾任KFUPM的计算机科学系主任、工程与计算机学院院长。他在沙特阿拉伯有广泛的学术影响，是政府（包括内务部和国防部在内）的高级顾问。本书的翻译工作是在朱洪教授的主持下进行的，全书主要由吴伟昶、方世昌翻译，朱洪审校。对于发现的原书中的错误，在翻译时已做了纠正，主要的错误已给予说明。上海应用技术学院计算机系的教师徐克奇、蔡旖旎、吴晓伟参与了部分翻译工作。复旦大学计算机系研究生李夷磊、葛启、谢之易、李镇坚、王海涛、马俊、田世俊、张涌、张华、李镇坚、李夷磊、谢之易等阅读了本书的大部分译稿，并提出了许多宝贵的意见。对于他们的帮助表示最衷心的感谢。由于译者本身的水平，翻译中难免有错误，恳请读者批评指正。

内容概要

作者：（沙特）阿苏外耶（M.H.Alsuwaiyel） 译者：吴伟昶 方世昌 等 注释 解说词：朱洪

书籍目录

第一部分 基本概念和算法导引第1章 算法分析基本概念  1.1 引言  1.2 历史背景  1.3 二分搜索  1.4 合并两个已排序的表  1.5 选择排序  1.6 插入排序  1.7 自底向上合并排序  1.8 时间复杂性  1.9 空间复杂性  1.10 最优算法  1.11 如何估计算法运行时间  1.12 最坏情况和平均情况的分析  1.13 平摊分析  1.14 输入大小和问题实例  1.15 练习  1.16 参考注释第2章 数学预备知识  2.1 集合、关系和函数  2.2 证明方法  2.3 对数  2.4 底函数和顶函数  2.5 阶乘和二项式系数  2.6 鸽巢原理  2.7 和式  2.8 递推关系  2.9 练习第3章 数据结构  3.1 引言  3.2 链表  3.3 图  3.4 树  3.5 根树  3.6 二叉树  3.7 练习  3.8 参考注释第4章 堆和不相交集数据结构  4.1 引言  4.2 堆  4.3 不相交集数据结构  4.4 练习  4.5 参考注释第二部分 基于递归的技术第5章 归纳法  5.1 引言  5.2 两个简单的例子  5.3 基数排序  5.4 整数幂  5.5 多项式求值（Horner规则）  5.6 生成排列  5.7 寻找多数元素  5.8 练习  5.9 参考注释第6章 分治  6.1 引言  6.2 二分搜索  6.3 合并排序  6.4 分治范式  6.5 寻找中项和第k小元素  6.6 快速排序  6.7 大整数乘法  6.8 矩阵乘法  6.9 最近点对问题  6.10 练习  6.11 参考注释第7章 动态规划  7.1 引言  7.2 最长公共子序列问题  7.3 矩阵链相乘  7.4 动态规划范式  7.5 所有点对的最短路径问题  7.6 背包问题  7.7 练习  7.8 参考注释第三部分 最先割技术第8章 贪心算法  8.1 引言  8.2 最短路径问题  8.3 最小耗费生成树（Kruskal算法）  8.4 最小耗费生成树（Prim算法）  8.5 文件压缩  8.6 练习  8.7 参考注释第9章 图的遍历  9.1 引言  9.2 深度优先搜索  9.3 深度优先搜索的应用  9.4 广度优先搜索  9.5 广度优先搜索的应用  9.6 练习  9.7 参考注释第四部分问题的复杂性第10章 NP完全问题  10.1 引言  10.2 P类  10.3 NP类  10.4 NP完全问题  10.5 co-NP类  10.6 NPI类  10.7 四种类之间的关系  10.8 练习  10.9 参考注释第11章 计算复杂性引论  11.1 引言  11.2 计算模型：图灵机  11.3 k带图灵机和时间复杂性  11.4 离线图灵机和空间复杂性  11.5 带压缩和线性增速  11.6 复杂性类之间的关系  11.7 归约  11.8 完全性  11.9 多项式时间层次  11.10 练习  11.11 参考注释第12章 下界  12.1 引言  12.2 平凡下界  12.3 决策树模型  12.4 代数决策树模型  12.5 线性时间归约  12.6 练习  12.7 参考注释第五部分克服困难性第13章 回溯法  13.1 引言  13.2 3着色问题  13.3 8皇后问题  13.4 一般回溯方法  13.5 分支限界法  13.6 练习  13.7 参考注释第14章 随机算法  14.1 引言  14.2 Las Vegas和Monte Carlo算法  14.3 随机化快速排序  14.4 随机化的选择算法  14.5 测试串的相等性  14.6 模式匹配  14.7 随机取样  14.8 素数性测试  14.9 练习  14.10 参考注释第15章 近似算法  15.1 引言  15.2 基本定义  15.3 差界  15.4 相对性能界  15.5 多项式近似方案  15.6 完全多项式近似方案  15.7 练习  15.8 参考注释第六部分域指定问题的迭代改进第16章 网络流  16.1 引言  16.2 预备知识  16.3 Ford-Fulkerson方法  16.4 最大容量增值  16.5 最短路径增值  16.6 Dinic算法  16.7 MPM算法  16.8 练习  16.9 参考注释第17章 匹配  17.1 引言  17.2 预备知识  17.3 网络流方法  17.4 二分图的匈牙利树方法  17.5 一般图中的最大匹配  17.6 二分图的On2.5算法  17.7 练习  17.8 参考注释第七部分计算几何技术第18 章几何扫描  18.1 引言  18.2 几何预备知识  18.3 计算线段的交点  18.4 凸包问题  18.5 计算点集的直径  18.6 练习  18.7 参考注释第19章 Voronoi图解  19.1 引言  19.2 最近点Voronoi图解  19.3 Voronoi图解的应用  19.4 最远点Voronoi图解  19.5 最远点Voronoi图解的应用  19.6 练习  19.7 参考注释参考文献

编辑推荐

《算法设计技巧与分析》是国外计算机科学教材系列

作者简介

《算法设计技巧与分析》是国际著名算法专家李德财教授主编的系列丛书Lecture Notes Series on Computing中的一本。《算法设计技巧与分析》涵盖了绝大多数算法设计中的一般技术，在表达每一种技术时，阐述它的应用背景，注意用与其他技术比较的方法说明它的特征，并提供大量实际问题的例子。《算法设计技巧与分析》同时也强调了对每一种算法的详细的复杂性分析。全书分七部分19章，从算法设计和算法分析的基本概念和方法入手，先后介绍了递归技术、分治、动态规划、贪心算法、图的遍历等技术，对NP完全问题进行了基本但清楚的讨论。对概率算法、近似算法和计算几何这些近年来发展迅猛的领域也用一定的篇幅讲述了基本内容。书中每章后都附有大量的练习题，有利于读者对书中内容的理解和应用。

《算法设计技巧与分析》结构简明，内容丰富，适合于作为计算机学科及相关学科算法课程的教材和参考书，尤其适宜于学过数据结构和离散数学课程之后的算法课程教材。同时也可作为从事算法研究的一本好的入门书。

图书封面

---

 算法设计技巧与分析下载

---