信息科学技术学术著作丛书：参数计算导论

图书标准信息

• 作者 王建新、冯启龙 著
• 出版社 科学出版社
• 出版时间 2014-07
• 版次 1
• ISBN 9787030368997
• 定价 80.00元
• 装帧 平装
• 开本 32开
• 纸张 胶版纸
• 页数 248页
• 字数 312千字
• 正文语种 简体中文
• 丛书 智能科学技术著作丛书

【内容简介】

《参数计算导论》较全面地介绍了参数计算理论的提出背景、理论范畴、相关算法设计与分析技术以及参数计算的实际应用。具体阐述了核心化技术、局部贪婪、递归压缩、分支搜索、随机方法、彩色编码、固定参数枚举技术，并从生物信息计算、计算机网络角度探讨了参数计算理论的实际工程应用价值。

【目录】

目录
《信息科学技术学术著作丛书》序
前言
第1章导引1
第2章参数计算简介5
2.1NP完全理论5
2.2固定参数可解7
2.3固定参数不可解8
2.4固定参数枚举10
2.5参数化方法10
2.6本章小结12
第3章核心化13
3.1NT定理15
3.1.1基于最大匹配的NT算法15
3.1.2基于线性规划的NT算法18
3.2皇冠分解19
3.2.1点覆盖与皇冠分解21
3.2.2P2Packing与皇冠分解23
3.3极值归纳技术31
3.3.1极值归纳技术的基本原理31
3.3.2边不相交三角形Packing32
3.3.3最多内部节点生成树34
3.4随机方法36
3.5基于低度点的核心化方法38
3.5.1基于低度点核心化方法的基本思想38
3.5.2连通点覆盖问题的核40
3.5.3边支配集44
3.6核下界技术45
3.6.1对偶性方法46
3.6.2基于复杂性理论假设的方法47
3.6.3基于参数化规约49
3.7本章小结50
第4章分支搜索法51
4.1常规的分支搜索法52
4.2基于隐含参数的分支搜索法55
4.3核心化分支交替搜索法58
4.4基于组合的分支搜索法60
4.5本章小结64
第5章迭代压缩和局部贪婪65
5.1迭代压缩65
5.1.1提出背景与技术要点66
5.1.2典型应用与效率探讨70
5.2局部贪婪73
5.2.1基于极大解和目标解关系的局部贪婪73
5.2.2基于k大小目标解求解k+1大小目标解的局部贪婪77
5.3递归压缩和局部贪婪的运用78
5.4本章小结80
第6章随机参数算法设计技术81
6.1随机方法种类及其应用82
6.1.1基于划分的随机方法83
6.1.2基于分块的随机方法88
6.2确定化方法89
6.2.1(n，k)UniversalSet89
6.2.23SetPacking随机算法的确定化90
6.3本章小结93
第7章彩色编码94
7.1基本概念95
7.2构造方法95
7.2.1随机化构造方法96
7.2.2确定化构造方法98
7.3本章小结114
第8章平面图参数算法设计技术116
8.1平面图上的核心化技术116
8.1.1平面图的基本概念116
8.1.2区域分解技术的基本原理118
8.2基于平面图的参数算法设计122
8.2.1平面支配集问题的亚指数算法123
8.2.2层状分割性质与平面图问题参数算法125
8.3本章小结127

第9章固定参数枚举129
9.1固定参数枚举理论129
9.2基于分支搜索的枚举130
9.3基于彩色编码的枚举136
9.4基于递归压缩的枚举141
9.4.1FVS的固定参数枚举子过程143
9.4.2FVS的固定参数枚举算法153
9.5本章小结155
第10章参数算法与近似算法156
10.1广义参数化近似算法157
10.1.1常数近似率广义参数化近似算法157
10.1.2固定参数可解时间近似方案160
10.1.3以近似性能1/ε作为参数的近似算法162
10.2标准参数化近似算法162
10.2.1常数近似率标准参数化近似算法163
10.2.2函数近似率标准参数化近似算法165
10.2.3固定参数可解问题的近似算法168
10.33DMatching计数问题的一种参数化随机近似算法170
10.3.1算法的基本思想170
10.3.2算法的主要步骤171
10.4不存在参数化近似算法的问题174
10.5本章小结175
第11章树分解及其应用176
11.1树分解基本理论176
11.2基于树分解的参数算法设计178
11.3其他宽度参数180
11.4树分解的应用181
11.5本章小结187
第12章参数计算的实际应用188
12.1单体型计算问题188
12.2生物多叉系统发生树最大一致森林问题195
12.3无线网络中延时受限的最小能量组播路由的参数算法研究213
12.4本章小结226
参考文献227
附录234