算法导论pdf第2版中文文字版 附带答案

算法导论pdf第2版是一款中文高清版的电子书籍，软件包中附带福昕阅读器能够帮助读者方便的打开pdf文件。书中主要介绍了许多常用的数据结构和有效的算法，讨论了线性规划，介绍了动态规划的两个应用，随机化和线性规划技术的近似算法等等，力图让读者能够轻松的掌握。其中第1章是对算法及其在现代计算系统中地位的一个综述。第2章给出了书中的第一批算法，它们解决的是对n个数进行排序的问题。第3章给出了这种表示法的准确定义，称为渐近表示。第4章更深入地讨论了第2章引入的分法方法以及解决递归式的方法。第5章介绍了概率分析和随机化算法。更多的内容请读者下载观看。

注意事项：软件包中附带了算法导论第2版的答案，请须知。

目录列表节选：

第一部分 基础知识

引言

第1章 算法在计算中的作用

1.1 算法

1.2 作为一种技术的算法

第2章 算法入门

2.1 插入排序

2.2 算法分析

2.3 算法设计

2.3.1 分治法

2.3.2 分治法分析

第3章 函数的增长

3.1 渐近记号

3.2 标准记号和常用函数

第4章 传归式

4.1 代换法

4.2 递归树方法

4.3 主方法

4.4 主定理的证明

4.4.1 取正合幂时的证明

4.4.2 上取整函数和下取整函数

第5章 概率分析和随机算法

5.1 雇用问题

5.2 指示器随机变量

5.3 随机算法

5.4 概率分析和指示器随机变量的进一步使用

5.4.1 生日悖论

5.4.2 球与盒子

5.4.3 序列

章节节选

在计算机科学中，排序是一种基本的操作（很多程序都将它用作一种中间步骤），因此，迄今为止，科研人员提出了多种非常好的排序算法。对于一项特定的应用来说，如何选择最佳的排序算法要考虑多方面的因素，其中最主要的是考虑待排序的数据项数、这些数据项已排好序的程度、对数据项取值的可能限制、打算采用的存储设备的类型（内存、盘、带）等如果一个算法对其每一个输入实例，都能输出正确的结果并停止，则称它是正确的，我们说一个正确的算法解决了给定的计算问题。不正确的算法对于某些输入来说，可能根本不会停止，或者停止时给出的不是预期的结果。然而，与人们对不正确算法的看法相反，如果这些算法的错误率可以得到控制的话，它们有时也是有用的。关于这一点，在第 31 中研究用于寻找大质数的算法时介绍了--个例子，但是，一般而言，我们还是仅关注正确的法。算法可以用英语、以计算机程序或甚至是硬件设计等形式来表达。不论采用哪种形式，唯一的要求就是算法的规格说明必须提供关于待执行的计算过程的精确描述。算法可以解决愿些类型的问糖？

研究人员并不仅仅是针对排序这一计算问题设计了大的算法（读者在看到本书的厚度时可能也会这么猜想的）。算法的实际应用面很广，例如。人类基因项目的目标是找出人类 DNA 中的所有 100 000 种基因，确定构成人类 DNA的30 亿种化学基对的各种序列，将这些信息存储在数据库中，并开发出用于进行这方面数据分析的工具，这些步骤中的每一个都需要复杂的算法。该项目所涉及的各个问题的解决方案已超出了本书的范围，但本书中有好几章中的思想在解决这些生物问题时都用到了，这样就使得科学家们可以有效地利用已有资源来完成任务，并且，当利用实验室技术可以提取出更多的信息时，就可以带来人、财、物、时间等方面的节约。因特网使得全世界的人们都能够快速地访问和检索大量的信息。为了能实现这一目的人们采用了巧妙的算法来管理和操纵大量的数据。这方面必须解决的问题包括寻找好的数据传输路径（第 24 章将介绍解决这些间题的技术）用索引警来快地找到包含特定信息的网页等（有关技术将在第 11 章和第32 章中介绍）电子商务使得商品和服务可以以电子的形式进行谈判和交易。然而，电子商务要想得到广泛应用的话，非常重要的一点就是保持信用卡号、密码、银行结单等信息的私密性公共密钥加密技术和数签名术（将在第 31 中绍）是这一领域内所使用的核心技术，它们的基础就是数值算法和数论理论。

在制造业和其他商业应用中，是否能有效地分配稀有资源常常是非常重要的，例如，石油公司可能希望确定该在何处打井，以求最大化预期效益。美国总统候选人可能希望确定该把竞选宣传的资金花在何处，以使赢得竞选胜利的可能性最大，航空公司可能希势以尽可能小的代价来将机组人员分配到不同的航班上，以便做到既到考虑到每一个航班又不会违反政府有关航空人员调度的规定，因特网服务提供商可能希望确定该把额外的资源置于何处，以便能够更有效地服务其客户。所有这些都是可以利用线性规划求解间题的例子，这一技术将在第 29 章中介绍。尽管这些例子中某些细节已经超出了本书的范围，我们仍给出了适用于这些问题和问题领底层支撑技术。此外，在本书中，我们还说明了如何解决许多具体的问题，例如：给定一幅道路交通图，上面标注出了每一对相邻交叉路口之间的距离。我们的目标就是确定-个交叉路口到另一个交又路口之间的最短路线。即使不允许每一条路线自我交叉可能的路线数量也会是巨大的。在所有可能的路线中，该如何来选出最短的路线呢？这里，用一个图来对道路交通图进行建模（前者本身就是对实际道路的一种建模，有关图的内容将在第 10 章和附录 B中介绍），希望在图中找出一个顶点到另一个顶点之间的最短路径。在第 24 章中，将看到如何来有效地解决这一问题。给定由 n个所组成的一个列（A1，A2，”，A确其AAA为矩阵乘法是可以结合的，因而存在着若干合法的乘法顺序。例如，如果 n-4，可以按照以下几种顺序来执行矩阵乘法：（A1（A2（A3A4））），（A1（（AA2AA3）A4）），（（A1A2）（A3A4）），（A1（A2A3））A4），（（A1A2）A3）A4）。如果这些是正方形矩阵（因而其大小都是一样的），乘法的顺序对矩阵乘法将花多少时间是没有影响的。然而，如果这些矩阵的大小不同的话（但其大小对矩阵乘法来说是相容的），那么，乘法的顺序如何就会带来很大的差别了。可能的乘法结合顺序的数量是 n 的指数级的，因此，要尝试所有可能顺序的话，可能会花很长的时间。在第 15 章中，我们将会看到，如何用一种称为动态规划的技术来更为有效地解决这一问题，给定一个方程az=b（mod ），其中an 都是，希出所有（在 时）满足该方程的整数 z。方程的解可能有零个、一个或多个。可以简单地尝试依次用=0,1，”。”，n1来代该方程，但第 31 中给出了种更为有效的方法给定平面上 n个点，希望找出这些点的凸亮，即包含这些点的最小凸多边形，从直观上看，可以将每一个点看成是由一块板上突起的一个钉子表示的。因而，包围这些点的凸亮可以看成是一根包围了所有这些钉子的绷紧的橡皮绳。每一个令橡皮绳发生方向变化