计算机数学——计算复杂性理论与NPC、NP难问题的求解

图书标准信息

• 作者 徐宗本 编；陈志平
• 出版社 科学出版社
• 出版时间 2001-08
• 版次 1
• ISBN 9787030091512
• 定价 28.00元
• 装帧 平装
• 开本 其他
• 纸张 胶版纸
• 页数 292页
• 字数 337千字

【内容简介】

本书全面、系统地介绍了计算复杂性理论的基本内容与各种NPC问题、NP难问题等复杂问题的计算机求解方法。前四章分别简要介绍了线性规划、多面体理论、网络规划与动态规划等预备知识。第五至九章具体介绍了计算复杂性理论。包括复杂性的定义与分类，证明一个问题为P类或NPC类的基本方法，NPC记理论在分析、求解问题中的应用与近似算法的性能度量等。第十至十六章则主要以整数规划为框架，详细论述求解NPC及NP难问题各种不同形式的精确算法与近似算法。

  本书可作为信息与计算科学、应用数学、计算机、管理科学等专业的研究生教材或本科生的选修课教材，也可供有关的科研人员参考。

【目录】

第一章  线性规划

  1.1 线性规划的基本概念

  1.2 单纯形算法

  1.3 字典序单纯形算法

  1.4 对偶理论

  1.5 内点算法

第二章  多面体理论

  2.1 多面体的定义及其维数

  2.2 用有效不等式与边界面来描述多面体

  2.3 用极点和极射向表示多面体

第三章  图与网络规划

  3.1 图的基本知识

  3.2 几类重要的图

  3.3 最短路间题

  3.4 最小权支撑树问题

  3.5 最大流问题

第四章  动态规划方法

  4.1 多阶段决策问题与动态规划的基本概念

  4.2 动态规划方法的基本思想与最优性定理

  4.3 最小权问题

  4.4 背包问题

  4.5 旅行商问题

第五章  算法复杂性概论

  5.1 引言

  5.2 基本概念

  5.3 多项式时间算法与指数时间算法

第六章  问题复奈性的分类

  6.1 判定问题与语言

  6.2 算法的严格定义与P类问题。

  6.3 NP类问题

  6.4 多项式变换与MD完全问题

  6.5 强MD完全问题

  6.6 CO-NP类问题

  6.7 NP困难问题

  6.8 空间复杂性简介

第七章  证明问题为NP完全的或P的方法

  7.1 证明问题为NPC的一般步骤

  7.2 限制法(Restr1ct1on)

  7.3 局部置换法(Local Rep1acement)

  7.4 分量设计法(Component Des1gn)

  7.5 证明问题属于P类的方法

第八章  NP完全理论在分析、求解新问题中的应用

  8.1 分析新问题复杂性的双向研究方法

  8.2 子问题分析法

  8.3 求解NPC问题的算法类型

第九章  近似算法的性能度量与NP完全理论的应用

  9.1 近似算法的性能度量

  9.2 NP完全理论在限定问题可近似程度中的应用

第十章  一般整数规划的基本性质

  10.1 一般整数规划问题

  10.2 整数规划与线性规划之间的关系

  10.3 整数规划问题解的有界性

  10.4 整数规划问题的计算复杂性

第十一章  割平面算法

  11.1 分数割平面算法

  11.2 整数割平面算法

  11.3 导出有效不等式的方法

  11.4 混合整数规划问题的求解

  11.5 覆盖问题的割平面算法

第十二章  分解算法

  12.1 拉格朗日松弛法

  12.2 Benders分解

  12.3 一般分解方法

  12.4 选址问题的分解算法

第十三章  分枝定界法

  13.1 一般分枝定界法

  13.2 使用线性规划松弛的分枝定界算法

  13.3 0-1背包问题的分枝定界算法。

第十四章  匹配问题

  14.1 匹配问题简介

  14.2 最大匹配问题

  14.3 加权匹配问题

  14.4 b匹配问题与其他相关论题

第十五章  近似算法的设计与分类

  15.1 近似算法概述

  15.2 贪婪算法(Greedy Algor1thms)

  15.3 局部搜索法(Local Search Heur1st1cs)

  15.4 原始-对偶法

  15.5 近似算法的其他设计方法

  15.6 近似算法的分类

第十六章  对称旅行商问题

  16.1 有效不等式的构造

  16.2 松弛问题的构造

  16.3 近似算法

  16.4 精确算法

参考文献