算法设计与分析

章节摘录

插图：第1章 算法分析技术计算机的计算是在程序控制下进行的。程序和数据存放在存储器中，中央处理器执行程序规定的操作步骤，计算出所要解答问题的结果。设计程序首先需要明确程序要解答什么样的问题，这就要形式化地描述问题的输入数据、输出数据和输出数据应满足的条件。好的程序不仅是正确的，还应该是高效的。计算机运行一个程序，输出正确结果或有效结果需要多少时间和多少存储空问，是标志这个程序解答问题优劣的主要量化指标。影响程序运行的计算时间和存储空间的因素很多，仅从程序在具体计算机上运行一次或几次所花费的时间和占用的存储空问难以断定程序的优劣。要客观地评价程序，就要脱离具体的计算机，分析程序解答一定规模的问题实例所使用的基本操作次数和占用的存储单元个数。脱离了具体的计算机、只描述解答问题的基本操作和操作顺序的计算过程就叫做解答问题的算法。实际上算法并不能真正脱离计算机，设想所有算法都在一个通用的计算模型上运行，这个计算模型就是第3章将会讲述到的图灵机模型。分析算法在计算模型上解答问题需要多少基本操作、多少存储单元，有助于客观、精确地评价算法，还有助于我们设计更好的算法。但在实际的算法分析中，通常不会去分析算法在计算模型上运行所需要的操作次数和存储单元个数，只需要脱离具体计算机，分析算法解答问题所使用的基本操作次数和占用的存储单元数，就足够了。1.1 算法及其复杂性所谓问题（problem），就是一个要求给出解答的一般性提问。它由两个要素组成：第一个要素描述问题的所有参量和参量格式，称为实例；第二个要素陈述问题解的格式和应当满足的条件，称为询问。所谓算法（algorithm）是一个过程，这个过程是若干语句的集合，每条语句都由明确指定计算机操作和操作顺序的规则构成。只要按照语句一步步地执行，便可得到问题的解。通常可将程序（program）看成是算法在具体计算机上运行的描述形式。在本书中，常常将程序和算法两个词混用。如果一个算法能应用于问题的任何实例，并保证得到正确的解，那么称这个算法解答了该问题。问题的实例又称为算法的输入，而问题的询问又称为算法的输出。评价算法的好坏，是算法分析（algorithm analysis）的中心内容。

前言

计算机是一种现代化的信息处理工具，它对信息进行处理并提供所需结果，其结果取决于所接受的信息及相应的处理算法。算法是以计算机能够理解的语言描述的解题过程。当算法作用于所求解问题的给定输入集或作用于问题自身的描述上，将产生唯一确定的有限动作序列。此序列或终止于给定问题的解，或终止于对此输入信息无解。对于给定的问题，基于对其的深刻理解，可设计出解答该问题的一个算法。在这个意义上，设计算法是将有关问题的知识，转化为解决问题的智慧。知识诚可贵，智慧价更高。设计算法就是揭示所研究问题的基本特征，以寻求其解答策略的过程，这是一项艰苦的创造性工作。对于给定的问题，有可能设计出多个算法，但不同的算法质量会不一样。衡量算法质量的主要因素是算法执行所耗费的时间和所需存储空间，以及算法适用范围等。对算法质量的分析研究称为算法分析。算法设计和算法分析是计算机科学的核心基础。国内外大学的计算机专业中，都将“算法设计与分析”作为专业基础课。近半个世纪以来，算法研究始终是计算机科学的一个研究热点。以E.W.Dijkstra、S.A.Cook、R.M.Karp、J.H.Hopcroft及R.E.Tariall等为代表的一批计算机科学家，以创造性工作推动着算法研究不断深入发展。在研究过程中，算法理论研究与软件技术研究之间产生了鸿沟，使得算法研究缺乏足够的实验支持，而实验工作又没有充分的理论分析。这种现状弓I起了人们的忧虑。在1996年的ACM计算理论学术年会（STOC’96）上，一些计算机科学家提出“算法工程”的概念，强调研究算法实现技术的重要性，呼吁算法研究者应重视理论与实践的结合，将算法设计、分析、实现、测试及改进等过程一体化、工程化。这种研究思路越来越受到人们的关注，促使算法研究健康发展。本书原稿写于20世纪80年代中期、笔者在山东大学为计算机专业研究生讲授“算法设计与分析”课程期间，先后几经修改，于1992年定稿并由山东大学出版社正式出版。此后一直使用本书作为计算机科学与技术专业的学位课教材，由笔者和朱大铭教授共同为研究生讲授，效果尚好。经过20多年的研究沉淀，算法设计与分析虽然没有太多变迁，但其研究内容更加丰富和成熟。

书籍目录

第1章 算法分析技术§1.1 算法及其复杂性§1.2 渐近估计技术及基本规则§1.3 递归算法分析1.3.1 合并排序算法分析1.3.2 一类递推方程的一般解§1.4 大整数相乘的递归算法§1.5 练习第2章 算法设计技术§2.1 分而治之§2.2 贪心技术§2.3 动态规划§2.4 回溯技术2.4.1 对策树搜索与a／B-删除2.4.2 一般树的回溯搜索与分支定界§2.5 局部搜索技术§2.6 练习第3章 P类、NP类及NPC类§3.1 问题与算法§3.2 确定型图灵机与P类§3.3 非确定型计算与NP类§3.4 多项式变换与NPC类§3.5 库克定理§3.6 练习第4章 证明问题属于NPC类的技术§4.1 基本的NPC问题§4.2 证明NP-完全性的典型技术4.2.1 限制技术4.2.2 局部替换技术4.2.3 分支设计技术§4.3 练习第5章 NPC问题子问题的复杂性§5.1 2SAT问题属于P类§5.2 几个NPC问题在三角化图上的解5.2.1 三角化图的特征5.2.2 用字典编辑广度优先搜索识别三角化图5.2.3 三角化图上着色、团、独立集及团覆盖问题的算法§5.3 子问题中P和NPC的分界§5.4 练习第6章 拟多项式变换和图灵归约§6.1 判定问题、语言和编码方案§6.2 拟多项式时间算法和强NPC类§6.3 用拟多项式变换证明强NP-完全性§6.4 复杂性类之间的关系§6.5 图灵归约和NP-难解问题§6.6 练习第7章 NP-难解问题近似算法§7.1 近似算法及其性能评估§7.2 近似算法设计7.2.1 满足三角不等式的货郎问题及其近似算法7.2.2 满足三角不等式的货郎问题的最小生成树算法7.2.3 多任务排工问题的近似算法7.2.4 独立任务排工问题§7.3 NP-难解问题可近似计算复杂性§7.4 多项式时间近似方案§7.5 练习第8章 近似算法设计技术§8.1 组合技术8.1.1 MaxSAT问题8.1.2 Maxk-SAT问题8.1.3 图顶点覆盖问题8.1.4 整数排列与换位移动排序8.1.5 集合覆盖问题§8.2 线性规划技术8.2.1 顶点覆盖近似算法8.2.2 集合覆盖近似算法§8.3 原始对偶技术8.3.1 集合覆盖8.3.2 击中集问题8.3.3 最短路问题8.3.4 Steiner树问题§8.4 局部搜索技术8.4.1 Max-3SAT问题的局部搜索算法8.4.2 K-median问题的局部搜索算法8.4.3 设施定位问题的局部搜索近似算法§8.5 随机近似算法8.5.1 MaxSAT问题的随机算法8.5.2 欧氏平面上货郎问题的随机算法§8.6 练习参考文献

编辑推荐

《算法设计与分析》特色：面向问题介绍算法与复杂性的有关概念与方法，易于读者理解。从讨论问题的计算复杂性和设计解答问题的算法两个方面，介绍研究计算问题的方法，注重启发读者的解题智慧，鼓励读者寻找解决问题的最佳途径。书中涉及大量的计算问题，虽然不能涵盖算法与复杂性领域的所有问题，但能够使读者在实践中借鉴解决老问题的方法克服新的困难。

作者简介

《算法设计与分析》是普通高等教育“十一五”国家级规划教材。《算法设计与分析》以算法设计策略为知识单元，系统地介绍计算机算法的设计方法与分析技巧，以期为计算机科学与技术专业的学生提供广泛而坚实的计算机基础知识。主要内容包括算法分析技术，算法设计技术，P类、NP类及NPC类，证明问题属于NPC类的技术，NPC问题子问题的复杂性，拟多项式变换和图灵归约，NP-难解问题近似算法，近似算法设计技术，等等。

《算法设计与分析》包括了算法与复杂性领域的主要内容，可以作为高等学校计算机专业高年级本科生和研究生学习计算机算法设计的教材，也可供广大工程技术人员和自学者学习参考。

---

 算法设计与分析下载

---