计算机数学——计算复杂性理论与NPC、NP难问题的求解作者:林鹏杨波

零捌图书网

首页 - 计算机 - 计算机理论与方法 - 计算机数学/离散数学 -> 计算机数学——计算复杂性理论与NPC、NP难问题的求解

书名:计算机数学——计算复杂性理论与NPC、NP难问题的求解
作者:林鹏杨波
译者:
出版社:科学出版社
价格:28元

简介

本书全面、系统地介绍了计算复杂性理论的基本内容与各种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. 1. 1 图 3. 1. 2 有向图 3. 1. 3 图的表示 3. 2 几类重要的图 3. 3 最短路间题 3. 4 最小权支撑树问题 3. 5 最大流问题第四章动态规划方法 4. 1 多阶段决策问题与动态规划的基本概念 4. 2 动态规划方法的基本思想与最优性定理 4. 3 最小权问题 4. 4 背包问题 4. 4. 1 O-1背包问题 4. 4. 2 整数背包问题 4. 5 旅行商问题第五章算法复杂性概论 5. 1 引言 5. 2 基本概念 5. 3 多项式时间算法与指数时间算法第六章问题复奈性的分类 6. 1 判定问题与语言 6. 2 算法的严格定义与P类问题 6. 3 NP类问题 6. 4 多项式变换与MD完全问题 6. 5 Co-MD完全问题 6. 6 Co-NP类问题 6. 7 NP困难问题 6. 8 空间复杂性简介第七章证明问题为NP完全的或P的方法 7. 1 证明问题为NPC的一般步骤 7. 2 限制法 Restriction 7. 3 局部置换法 Local Replacement 7. 4 分量设计法 Component Design 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. 3. 1 取整方法 11. 3. 2 同余方法 11. 3. 3 合并方法 11. 3. 4 超加函数法 11. 4 混合整数规划问题的求解 11. 5 覆盖问题的割平面算法 11. 5. 1 覆盖问题的描述 11. 5. 2 覆盖问题的割平面算法第十二章分解算法 12. 1 拉格朗日松弛法 12. 2 Benders分解 12. 3 一般分解方法 12. 4 选址问题的分解算法第十三章分枝定界法 13. 1 一般分枝定界法 13. 2 使用线性规划松弛的分枝定界算法 13. 2. 1 剪枝准则 13. 2. 2 分枝方法 13. 2. 3 结节选取方法 13. 2. 4 分枝变量选择方法 13. 3 0-1背包问题的分枝定界算法. 第十四章匹配问题 14. 1 匹配问题简介 14. 2 最大匹配问题 14. 2. 1 二部图的匹配算法 14. 2. 2 非二部图的匹配算法 14. 3 加权匹配问题 14. 3. 1 指派问题的求解 14. 3. 2 一般加权匹配问题 14. 4 b匹配问题与其他相关论题 14. 4. 1 b匹配问题 14. 4. 2 匹配理论与算法的应用第十五章近似算法的设计与分类 15. 1 近似算法概述 15. 2 贪婪算法 Greedy Algorithms 15. 3 局部搜索法 Local Search Heuristics 15. 4 原始-对偶法 15. 5 近似算法的其他设计方法 15. 6 近似算法的分类 15. 6. 1 定常近似比算法 15. 6. 2 近似策略 15. 6. 3 最好可能近似比算法 15. 6. 4 比最好还要好的近似算法 15. 6. 5 与真正最优值仅一步之遥的近似第十六章对称旅行商问题 16. 1 有效不等式的构造 16. 2 松弛问题的构造 16. 3 近似算法 16. 3. 1 最近邻法 16. 3. 2 最近插人法 16. 3. 3 贪婪可行法 16. 3. 4 k边交换法 16. 3. 5 三角不等式与贪婪型算法的性能 16. 3. 6 支撑树加倍法 16. 3. 7 支撑树加完美匹配法 16. 4 精确算法 16. 4. 1 指派问题加分枝定界算法 16. 4. 2 拉格朗日松弛加分枝定界算法 16. 4. 3 分数割平面加分枝定界算法参考文献

零八图书网地图分类友情链接：中国书网稀缺复印分站