算法设计与分析
点此进入淘宝搜索页搜索分類: 图书,计算机/网络,程序设计,其他,
作者： 朱大铭，马绍汉 编著
出 版 社： 高等教育出版社
出版时间： 2009-1-1字数：版次： 1页数： 244印刷时间：开本： 16开印次：纸张：I S B N ： 9787040258714包装： 平装编辑推荐
本书特色：
面向问题介绍算法与复杂性的有关概念与方法，易于读者理解。
从讨论问题的计算复杂性和设计解答问题的算法两个方面，介绍研究计算问题的方法，注重启发读者的解题智慧，鼓励读者寻找解决问题的最佳途径。
书中涉及大量的计算问题，虽然不能涵盖算法与复杂性领域的所有问题，但能够使读者在实践中借鉴解决老问题的方法克服新的困难。
内容简介
本书是普通高等教育“十一五”国家级规划教材。本书以算法设计策略为知识单元，系统地介绍计算机算法的设计方法与分析技巧，以期为计算机科学与技术专业的学生提供广泛而坚实的计算机基础知识。主要内容包括算法分析技术，算法设计技术，P类、NP类及NPC类，证明问题属于NPC类的技术，NPC问题子问题的复杂性，拟多项式变换和图灵归约，NP-难解问题近似算法，近似算法设计技术，等等。
本书包括了算法与复杂性领域的主要内容，可以作为高等学校计算机专业高年级本科生和研究生学习计算机算法设计的教材，也可供广大工程技术人员和自学者学习参考。
目录
第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 练习
参考文献
书摘插图
第1章 算法分析技术
计算机的计算是在程序控制下进行的。程序和数据存放在存储器中，中央处理器执行程序规定的操作步骤，计算出所要解答问题的结果。设计程序首先需要明确程序要解答什么样的问题，这就要形式化地描述问题的输入数据、输出数据和输出数据应满足的条件。好的程序不仅是正确的，还应该是高效的。计算机运行一个程序，输出正确结果或有效结果需要多少时间和多少存储空问，是标志这个程序解答问题优劣的主要量化指标。影响程序运行的计算时间和存储空间的因素很多，仅从程序在具体计算机上运行一次或几次所花费的时间和占用的存储空问难以断定程序的优劣。要客观地评价程序，就要脱离具体的计算机，分析程序解答一定规模的问题实例所使用的基本操作次数和占用的存储单元个数。脱离了具体的计算机、只描述解答问题的基本操作和操作顺序的计算过程就叫做解答问题的算法。实际上算法并不能真正脱离计算机，设想所有算法都在一个通用的计算模型上运行，这个计算模型就是第3章将会讲述到的图灵机模型。分析算法在计算模型上解答问题需要多少基本操作、多少存储单元，有助于客观、精确地评价算法，还有助于我们设计更好的算法。但在实际的算法分析中，通常不会去分析算法在计算模型上运行所需要的操作次数和存储单元个数，只需要脱离具体计算机，分析算法解答问题所使用的基本操作次数和占用的存储单元数，就足够了。
1.1 算法及其复杂性
所谓问题（problem），就是一个要求给出解答的一般性提问。它由两个要素组成：第一个要素描述问题的所有参量和参量格式，称为实例；第二个要素陈述问题解的格式和应当满足的条件，称为询问。所谓算法（algorithm）是一个过程，这个过程是若干语句的集合，每条语句都由明确指定计算机操作和操作顺序的规则构成。只要按照语句一步步地执行，便可得到问题的解。通常可将程序（program）看成是算法在具体计算机上运行的描述形式。在本书中，常常将程序和算法两个词混用。如果一个算法能应用于问题的任何实例，并保证得到正确的解，那么称这个算法解答了该问题。问题的实例又称为算法的输入，而问题的询问又称为算法的输出。评价算法的好坏，是算法分析（algorithm analysis）的中心内容。
……
