算法设计与分析

章节摘录

　　第1章 入门　　1.4 算法的效率　　对于给定的问题，起初只是考虑只要找到一个算法解决该问题就行，而不管该算法花多长时间或者占用多大的存储空间。随着计算机技术的发展，人们发现，求解同一个问题的不同的算法，所需要的运行时间是不同的。例如对排序问题，除了上面介绍过的插入排序算法，我们还将介绍选择排序、合并排序以及快速排序算法。我们自然会问，哪个排序算法好呢？怎么样评价一个算法的好坏呢？这就涉及到算法的时间和空间资源的分析，即算法效率(Efficiency)的分析。　　算法效率的分析，指的是算法求解一个问题所需要的时间和空间。分析一个算法，意味着预测该算法解一个问题时，需要花费多少时间和空间资源。空间资源一般指解决一个问题，需要多大的内存、硬盘空间等来存储输入输出数据等。时间资源一般指的是解决一个问题需要多长的时间。一般地，对一个问题，存在不同的求解算法，我们可以根据算法所需要的时空资源来确定出其中有效的算法。随着计算机硬件技术的发展，现在计算机的内存和硬盘空间基本上能满足问题的需要，即空间资源已经不是问题，因此，我们分析一个算法，主要考虑算法的计算时间，今后，我们也主要从时间资源方面对算法进行分析，即分析算法有多快。　　在分析一个算法前，我们需要知道如何实现一个算法，这就涉及到计算模型的概念。如果对一个问题，利用计算模型能够实现一个求解算法，则该问题是可解的，否则是不可解的。排序问题是一个可解的问题，因为我们已经找到了许多排序算法。对于不可解的问题，由于无法找到其求解算法，对其进行算法研究也就没必要，本书探讨可解问题的算法设计与分析。

前言

　　民众多好饮酒，中外概莫能外。酒馆和酿酒坊伴随饮酒客而起，人类对酒的喜爱造就了酒文化和一个庞大的产业。好酒能卖好价钱，能使文人诗兴大发，催生佳作，还能解人间百难。于是，酿天下名酒自然成为不少人的毕生追求。　　怎样才能酿出好酒呢？国人的看法不尽相同。崇信洋酒的人主张引进国外的生产工艺，学习洋人的生产和经营理念，而喜欢国酒的人则主张走自己的路，但不排除借鉴国外先进的科学技术和管理经验。这样的争论或许永远不会终结，但外国人重视科学酿酒，这一点是值得我们学习和借鉴的。　　计算机科学教育，如同酿酒工业的生产一样，科学办学迄今还只是部分学者的一种理想。与国内一样，国外的计算机科学教育并没有像他们的科学酿酒业一样，实现科学办学。也许科学办学要远比科学酿酒困难得多。譬如，怎么实现科学办学？甚至怎么推出一套科学的系列教材都是一篇大文章。　　这套教材的创作始于教育部面向21世纪教育与教学改革13-22项目的研究。2000年，在13-22项目研究工作即将完成之际，一些学者开始认识到面对计算机科学与技术的高速发展，我们亟需一套体现科学办学思想、反映内涵发展要求、服务教育与教学改革、参与构建学科人才培养科学体系的系列教材。强调系列教材是因为那时已经意识到计算机科学教育本质上是一项科学活动，但长期以来教师向学生传授科学技术知识的方式方法科学性不强。由于高等教育几百年来一直沿袭经验方式而非科学方式办学，大学教学的方式方法仍然还停留在古代作坊式的阶段，只不过今天使用的教学技术手段先进而已。在经验办学方式下，无论是研究型大学还是教学型大学，由于种种原因，教学活动的全过程存在着太多的漏洞和质量上的隐患。科学办学是对高等教育界传统的一个挑战，尽管在认识上，人们不难理解，科学办学是经验办学的最高形式，而经验办学应该成为科学办学的有益补充。

书籍目录

第1章　预备知识　1.1　数学基础　1.2　问题的复杂性　1.3　规划问题第2章　随机算法　2.1　基本概念　2.2　数值随机算法　2.3　Sherwood算法　2.4　Las Vegas算法　2.5　Monte Carlo算法　2.6　随机复杂性　2.7　总结第3章　近似算法　3.1　基本概念　3.2　调度问题　3.3　旅行商问题　3.4　覆盖问题　3.5　Bin packing问题　3.6　背包问题　3.7　随机近似算法　3.8　基于线性规划的近似算法　3.9　近似的难度　3.10　在线算法　3.11　总结第4章　启发式算法　4.1　概述　4.2　作业车间调度问题　4.3　packing问题　4.4　SAT问题　4.5　总结参考文献

作者简介

本书主要取材于反映当今计算机科学与技术学科中算法设计及分析发展潮流方面的内容。内容除包括国外一些比较成熟的算法技术，例如基本的随机算法以及近似算法，还包括一些最新的研究成果，例如基于近似和随机思想的混合算法：随机近似算法、在线算法、现代启发式算法等。本书包括大量的问题实例并给出了相应的求解方法。而工业应用领域的许多实际问题和疑难问题，都需要有效的求解算法，本书提供了大量的可供选择的解决途径。



本书可作为计算机科学系、数学系、管理科学等高年级本科以及研究生课程的教材，也适合科研人员学习使用。

图书封面

---

 算法设计与分析下载

---