图书介绍
计算复杂性PDF|Epub|txt|kindle电子书版本网盘下载
- 顾小丰，孙世新，卢光辉编著 著
- 出版社： 北京：机械工业出版社
- ISBN：7111153146
- 出版时间：2005
- 标注页数：160页
- 文件大小：11MB
- 文件页数：168页
- 主题词：计算复杂性－高等学校－教材
PDF下载
下载说明
计算复杂性PDF格式电子书版下载
下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！
（文件页数 要大于 标注页数，上中下等多册电子书除外）
注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具
图书目录
目录1
前言1
作者简介1
第一部分 数值计算的复杂性1
第1章 代数方程和数值计算的复杂性理论简介1
1.1 代数方程的不动点迭代算法1
1.2 收敛性和复杂性——算法优劣判别的两个层次9
2.1.1 剖分法15
2.1 剖分法与标号法15
第2章 代数方程的Kuhn算法15
2.1.2 标号法17
2.2 互补轮回算法19
2.2.1 互补轮回算法原理19
2.2.2 进口出口分析21
2.3 Kuhn算法的收敛性（一）23
2.4 Kuhn算法的收敛性（二）27
3.1 误差估计35
第3章 Kuhn算法的效率35
3.2 成本估计37
3.3 单调性问题42
3.4 关于单调性的结果47
第4章 牛顿法及其计算复杂性简介53
第二部分 计算机科学的复杂性理论57
第5章 算法的计算复杂性和计算模型57
5.1 算法及其计算复杂性57
5.2 确定型图灵机59
5.3 随机存取机62
5.4 RAM机的程序的计算复杂性66
5.5 图灵机和RAM机的相关性69
5.6 PIDGIN ALGOL——一种高级语言71
第6章 几个“难”问题的算法设计75
6.1 贪心法和背包问题75
6.2 动态规划和货郎担问题81
6.3 回溯法和图的可着色性问题83
6.4 分枝限界法和带时限的作业调度问题90
第7章 NP完全问题97
7.1 判定问题、语言和编码97
7.2 多项式变换与可满足性问题99
7.3 非确定型图灵机101
7.4 NP类105
7.5 NP完全问题与Cook定理108
7.6 强NP完全问题112
7.7 Co-NP类问题115
7.8 NP困难问题116
7.9 空间复杂性简介118
第8章 NP完全性证明121
8.1 六个基本的NP完全问题121
8.1.1 三元可满足性122
8.1.2 三维匹配124
8.1.3 节点覆盖和团127
8.1.4 哈密顿回路129
8.1.5 划分132
8.2 NP完全性的证明方法134
8.2.1 限制法135
8.2.2 局部替换法137
8.2.3 分量设计法141
8.3 P类问题的证明143
8.3.1 二元可满足性问题144
8.3.2 偶图的独立集问题145
第9章 近似算法147
9.1 近似的接近程度衡量147
9.2 0-1背包问题148
9.3 装箱问题151
9.4 图的着色问题153
9.5 货郎担问题155
9.6 多处理机调度问题157
参考文献160