当前位置：

算法设计与分析(高级教程)

作者：张德富　编著

出版社：国防工业出版社

出版年：2007-02-01

评分：5分

ISBN：9787118049336

所属分类：网络科技

书刊介绍

算法设计与分析(高级教程) 内容简介

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

算法设计与分析(高级教程) 本书特色

本书深入浅出、通俗易懂地介绍了以下主要内容：第1章简单介绍一些本书中需要用到的数学基础、问题的复杂性以及规划问题的一些预备知识。第2章重点介绍随机算法，其内容包括数值随机算法、Sherwood算法、Las Vegas算法和Monte Carlo算法的设计与分析。*后介绍如何扩大随机优势、随机复杂类的定义等内容。第3章重点介绍近似算法，其内容包括：基本定义，包括差界、相对性能界、多项式时间近似策略以及完全多项式时间近似策略。根据这些定义，可以衡量求解着色问题、调度问题、旅行商问题、覆盖问题、装箱问题、背包问题等的近似算法的性能。然后介绍了随机近似算法以及基于线性规划问题的近似算法及其应用。在NP难解性理论初步的基础上，进一步深入介绍近似的难度，*后介绍了在线算法。第4章重点介绍基于近似与随机思想的启发式算法的设计与分析，特别是现代启发式算法，例如模拟退火、禁忌搜索以及遗传算法等的应用实例。本书可作为计算机科学系、数学系、管理科学等高年级本科以及研究生课程的教材，也适合科研人员学习使用。

算法设计与分析(高级教程) 目录

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