| 词条 | 算法设计与分析 |
| 释义 | 书主要取材于算法设计与分析领域的经典内容，并介绍了算法设计的发展趋势。内容主要包括非常经典的算法设计技术，例如递归与分治、动态规划、贪心、回溯、分支限界、图算法，也包括了一些高级的算法设计主题，例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面，介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面，介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。 1.图书信息书 名: 算法设计与分析 作 者：张德富 出版社： 国防工业出版社 出版时间： 2009-8-1 ISBN: 9787118063080 开本： 16开 定价: 36.00元 内容简介本 本书内容基本上涵盖了目前程序设计竞赛所要掌握的算法，并在书后精选了部分ACM国际大学生程序设计竞赛的题目，供大家练习。 本书可作为计算机科学系、数学系、软件学院等专业本科及研究生课程的教材，特别适合于有志于参加程序设计竞赛的学生学习和训练。 目录第1章 入门 第2章 渐近符号 第3章 算法分析方法 第4章 递归 第5章 分治算法 第6章 动态规划 第7章 贪心算法 第8章 图算法 第9章 网络流与匹配 第10章 线性规划 第11章 NP完全理论 第12章 回溯 第13章 分支限界 第14章 启发式搜索 第15章 数论 第16章 计算几何 参考文献 书摘第1章 入门 1.4 算法的效率 对于给定的问题，起初只是考虑只要找到一个算法解决该问题就行，而不管该算法花多长时间或者占用多大的存储空间。随着计算机技术的发展，人们发现，求解同一个问题的不同的算法，所需要的运行时间是不同的。例如对排序问题，除了上面介绍过的插入排序算法，我们还将介绍选择排序、合并排序以及快速排序算法。我们自然会问，哪个排序算法好呢？怎么样评价一个算法的好坏呢？这就涉及到算法的时间和空间资源的分析，即算法效率(Efficiency)的分析。 算法效率的分析，指的是算法求解一个问题所需要的时间和空间。分析一个算法，意味着预测该算法解一个问题时，需要花费多少时间和空间资源。空间资源一般指解决一个问题，需要多大的内存、硬盘空间等来存储输入输出数据等。时间资源一般指的是解决一个问题需要多长的时间。一般地，对一个问题，存在不同的求解算法，我们可以根据算法所需要的时空资源来确定出其中有效的算法。随着计算机硬件技术的发展，现在计算机的内存和硬盘空间基本上能满足问题的需要，即空间资源已经不是问题，因此，我们分析一个算法，主要考虑算法的计算时间，今后，我们也主要从时间资源方面对算法进行分析，即分析算法有多快。 在分析一个算法前，我们需要知道如何实现一个算法，这就涉及到计算模型的概念。如果对一个问题，利用计算模型能够实现一个求解算法，则该问题是可解的，否则是不可解的。排序问题是一个可解的问题，因为我们已经找到了许多排序算法。对于不可解的问题，由于无法找到其求解算法，对其进行算法研究也就没必要，本书探讨可解问题的算法设计与分析。 …… 2.图书信息作者：王晓东 编著 ISBN：10位［7302061866］ 13位［9787302061861］ 出版社：清华大学出版社 出版日期：2003-8-1 定价：29.80 元 内容提要为了适应培养21世纪计算机人才的需要，结合我国高等院校教育工作的现状，立足培养学生能跟上国际计算机科学技术的发展水平，更新教学内容和教学方法，本书以算法设计策略为知识单元，系统地介绍计算机算法的设计方法与分析技巧，以期为计算机科学与技术学科的学生提供广泛而坚实的计算机算法基础知识。 本书内容丰富，观点新颖，理论联系实际。采用Java语言描述算法，简明清晰、结构紧凑，可读性强。本书可以作为高等院校计算机专业本科生和研究生学习计算机算法设计的教材，也可供广大工程技术人员和自学读者学习参考。 编辑推荐本书采用面向对象的JAVA语言作为表述手段，在保持JAVA优点的同时，尽量使算法的描述简明、清晰。为了加深对知识的理解，各章配有难易适当的习题，以适应不同程度读者练习的需要。 目录第1章 算法引论 第2章 递归与分治策略 第3章 动态规划 第4章 贪心算法 第5章 回溯法 第6章 分支限界法 第7章 概率算法 第8章 NP完全性理论 第9章 近似算法 第10章 算法优化策略 参考文献 其他相关设计出高质量的算法，并研究算法所耗费的计算资源与问题规模之间的函数关系。算法设计与算法分析是不可分割的一个整体。算法分析的对象是被设计出的算法，而每一个被设计出的算法只有经过算法分析，才能评价其质量之优劣。 计算效率是一个古老的研究课题。科学技术的发展使得计算日趋复杂，计算量越来越大，许多理论上可计算的问题，常常由于其计算量巨大布变成了现实不可计算的问题，这就产生了理论可计算而现实不可计算的矛盾。20世纪60年代以来，随着各个领域算法研究工作的发展，产生了一个崭新的研究领域，这就是算法的设计与分析。在这一方面已取巨大的进展，它的研究成果对于计算机在各个领域的应用起着重要的作用。 基本内容 按照算法所处理的对象进行分类，算法设计与分析主要有数值算法和非数值算法两大领域。数值算法主要包括多项式计算、矩阵计算、有限域计算、数论计算等有关数值计算的算法问题。非数值算法主要包括整序搜索、几何问题的计算、离散结构的计算、模式匹配等有关非数值计算的算法问题。 按照计算方式进行分类，则可分为串行算法和并行算法，还可以分为确定型算法、非确定型算法、交错型算法、随机型算法等（见计算复杂性理论）。 另外，还有关于近似算法的研究。对于已经证明不存在快速算法，或者至今还未找到快速算法的问题，例如NP完全问题（见NP完全性）, 与其花费大量的时间去寻找精确解，不如花费少量的时间去寻找近似解。 基本概念 设计算法与分析算法的复杂度，都与计算模型有关，大多属于随机存取机器模型，这是一种确定型的串行计算模型。 随机存取机器是一种理想的计算机，由一个累加器、一个存储器和一个程序组成。存储器具有无限多个寄存器，每个寄存器可以存放任意大的一个自然数。程序是由一些最基本的指令所组成的序列，这些指令通常是指包括直接寻址与间接寻址在内的加、减、乘、除、取数、存数、条件转移和停机。所有的运算和逻辑判断都在累加器中进行。 问题的大小，也称问题的规模，通常用一个自然数作为随机存取机器输入数据量多少的度量。 时间复杂度和空间复杂度分别表示对于规模为 n的输入问题、随机存取机器所耗费的时间与空间，它们都是 n的函数。常用的时间和空间的度量方式是均匀耗费标准：执行一条指令算作耗费一个单位的空间，使用一个寄存器算作耗费一个单位的空间；另一种度量方式是对数耗费标准（见随机存取机器模型）。复杂度函数的计算方式又有两种：规模为n的所有问题的复杂度的最大值称为最环情况复杂度；规模为n的所有问题的复杂度的平均值称为平均情况复杂度。当规模n增加时,复杂度的量级即极限属性称为渐近复杂度。由于理论计算机与现实计算机之间的差异，以及不同的现实计算机之是的差异，也由于算法设计与分析主要关心规模 n比较大的情况，通常讨论的是渐近复杂度。 算法设计 算法设计的任务是对各类具体的问题设计高质量的算法，以及研究设计算法的一般规律和方法。常用的算法设计方法主要有分治法、动态规划、贪婪法和回溯法等。 分治法 把一个大规模问题划分成几个子问题，对每一个子问题采用同样的处理方法，求出各子问题的解答，再把这些子问题的解答组合成整个问题的解答。 动态规划 当整个问题的解答无法由少数几个子问题的解答组合得出，而依赖于大量子问题的解答，并且子问题的解答又需要反复利用多次时，系统地列表记录各个子问题的解答，据此求出整个问题的解答。 贪婪法 在算法的每一步骤，都采取当前看来可行的或最优的策略。这是一种最直接的方法，只有在一些特殊情况下，贪婪法才能求出问题的解答。对于录求最优解的问题、贪婪法通常只能求出近似解。 回溯法和分叉截断法 为了寻求问题的解答，有时需要在所有的可能性(称为候选对象)中进行系统的搜索，例如在寻求最优解的问题中，就常碰到这种情况。这时，须把各种候选对象组织成一棵树，每个树叶对应着一个候选对象,于是每个内部顶点就表示若干个候选对象(即在此顶点下面的树叶)。回溯法是从树根开始按深度优先搜索的原则向下搜索,即沿着一个方向尽量向下搜索,直到发现此方向上不可能存在解答时，就退到上一个顶点，沿另一个方向进行同样的工作。分叉截断法也是从树根开始向下搜索，不同的是，分叉截断法常常利用一个适当选取的评估函数，来决定应该从哪一点开始下一步搜索（分叉），以及哪一点下方不可能存在解答，从而这点的下方不必进行搜索（截断）。评估函数选得好，就会很快地找到解答，选得不好，就可能找不到解答或者找到的不是最优解（有时它可以作为最优解的一个近似解）。 算法分析 对于设计出的每一个具体的算法，利用数字作为工具讨论它的各种复杂度，就是算法分析的主要任务。复杂度分析的结果可以作为评价算法质量的标准之一，有时也可以为改进算法的方向提供参考。分析算法的复杂度需要较强的数学技巧,针对不同的算法,采用不同的分析方法。 讨论某些问题类在一定的计算模型中的任意算法的复杂度至少是多大，也是算法分析的一个内容，这就是下界问题。 通常认为，多项式复杂度的算法是现实可行的，而指数复杂度的算法是现实不可行的。 参考书目 A.V.Aho,J.E.Hopcroft,J.D.Ullman,The Design and Analysis of Computer Algorithms,Addison Wesley,Reading,Mass.,1974. D.E.Knuth, The Art of Computer Programming,Vol.1～3,Addison Wesley,Reading,Mass.,1968～1973. |
| 随便看 |
百科全书收录4421916条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。