国外计算机科学教材系列 算法设计技巧与分析[Algorithms Design Techniques and Analysis]pdf

图书网 2018年7月19日11:59:28
评论
3.3K

国外计算机科学教材系列 算法设计技巧与分析[Algorithms Design Techniques and Analysis] 内容简介

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

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

国外计算机科学教材系列 算法设计技巧与分析[Algorithms Design Techniques and Analysis] 目录

第一部分 基本概念和算法导引

第1章 算法分析基本概念

第2章 数学预备知识

第3章 数据结构

第4章 堆和不相交集数据结构

第二部分 基于递归的技术

第5章 归纳法

第6章 分治

第7章 动态规划

第三部分 最先割技术

第8章 念心算法

第9章 图的遍历

第四部 问题复杂性

第10章 NP完全问题

第11章 计算机杂性引论

第12章 下界

第五部分 克服困难性

第13章 回溯法

第14章 随机算法

第15章 近似算法

第六部分 域指定问题的迭代改进

第16章 网络流

第17章 匹配

第七部分 计算几何技术

第18章 几何扫描

第19章 Voronoi图解

参考文献

国外计算机科学教材系列 算法设计技巧与分析[Algorithms Design Techniques and Analysis] 精彩文摘

1.1 引言第1章 算法分析基本概念

最一般的直觉意义上的算法山就是一个由有限的指令集组成的过程。从可能的输人集中给这个过程一个输入,如果系统地执行该指令集,那么对于这个特定的输入,当输出存在时,就能得到输出;当没有输出时,就什么结果也得不到。可能的输人集是指能让该算法给出一个输出的所有输入。如果对于一个特定的输入有一个输出,那么就说该算法能用于这一输入,执行该算法能够得到相应的输出。我们要求算法对于每一个输入能停下来,这意味着每一条指令只需要有限的时间,同时每一个输入的长度是有限的。我们还要求对于一个合法输入所对应的输出是惟一的。也就是说当算法从一个特定的输入开始,多次执行同一指令集时,结果总是相同,从这个意义上讲算法是确定的。第14章研究随机算法时将放宽这一条件。

在计算机科学领域,算法设计与分析是十分重要的。正如DonaldE.Knuth所说,“计算机科学就是算法的研究”。这没什么可惊讶的,因为计算机科学的每个领域都高度依赖于有效算法的设计。举个简单例子,编译程序和操作系统不外乎就是具有特定目标的算法的直接实现。

本章的目的有两个:首先介绍一些简单的算法,特别是与搜索和排序相关的那一类;其次讲述用于算法设计和分析的基本概念。由于算法的“运行时间”这一概念对于设计有效算法是至关重要的,我们将对它进行深入讨论。总之,时间是衡量算法有效性的最好测度。我们也会讨论其他重要资源的测度,比如一个算法所需要的空间等。

本章给出的算法虽然简单,但它们是解释一些算法概念的许多例子的基础。从简单有用的、在更复杂的算法中被用做构件模块的算法开始,是非常有益的。

图书网:国外计算机科学教材系列 算法设计技巧与分析[Algorithms Design Techniques and Analysis]pdf

继续阅读

→→→→→→→→→→→→→→→→→→→→查找获取

程序设计

重构 改善既有代码的设计(中文版)pdf

《重构:改善既有代码的设计》(中文版)所提的这些重构准则将帮助你一次一小步地修改你的代码,这就减少了过程中的风险。很快你就会把这些重构准则和其名称加入自己的开发词典中,并且朗朗上口...
程序设计

数据结构 C语言版 第2版pdf

适读人群 :普通高校电子信息大类本科生学习、考研,同时也适合零售和培训。 采用“案例驱动”的编写模式。书中结合实际应用,将各章按照“案例引入——数据结构及其操作——案例分析与实现”...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: