在好例子网,分享、交流、成长!
您当前所在位置:首页Others 开发实例一般编程问题 → Computers and intractability a guide to the theory of NP-completeness (Garey, Michael R)

Computers and intractability a guide to the theory of NP-completeness (Garey, Michael R)

一般编程问题

下载此实例
  • 开发语言:Others
  • 实例大小:5.82M
  • 下载次数:6
  • 浏览次数:111
  • 发布时间:2022-06-25
  • 实例类别:一般编程问题
  • 发 布 人:22.6.25
  • 文件格式:.pdf
  • 所需积分:0
 相关标签: Computer Complete theory GUIDE GUID

实例介绍

【实例简介】Computers and intractability  a guide to the theory of NP-completeness (Garey, Michael R)

【实例截图】

【核心代码】

Contents
Preface.ix
1 Computers, Complexity, and Intractability.1
1.1 Introduction.1
1.2 Problems, Algorithms, and Complexity.4
1.3 Polynomial Time Algorithms and Intractable Problems.6
1.4 Provably Intractable Problems.11
1.5 NP-Complele Problems.13
1.6 An Outline of the Book.14
2 The Theory of NP-Completeness.17
2.1 Decision Problems, Languages, and Encoding Schemes.18
2.2 Deterministic Turing Machines and the Class P.23
2.3 Nondeterministic Computation and the Class NP.27
2.4 The Relationship Between P and NP.32
2.5 Polynomial Transformations and NP-Completeness.34
2.6 Cook’s Theorem .38
3 Proving NP-Completeness Results .45
3.1 Six Basic NP-Complete Problems.46
3.1.1 3-SATISFIABILITY.48
3.1.2 3-DIMENSIONAL MATCHING.50
3.1.3 VERTEX COVER and CLIQUE.53
3.1.4 HAMILTONIAN CIRCUIT.56
3.1.5 PARTITION.60
3.2 Some Techniques for Proving NP-Completeness .... i .... 63
3.2.1 Restriction.63
3.2.2 Local Replacement.66
3.2.3 Component Design.72
3.3 Some Suggested Exercises.74
CONTENTS
4 Using NP-Completeness to Analyze Problems 77
4.1 Analyzing Subproblems.80
4.2 Number Problems and Strong NP-Completeness.90
4.2.1 Some Additional Definitions.92
4.2.2 Proving Strong NP-Completeness Results .95
4.3 Time Complexity as a Function of Natural Parameters .... 106
5 NP-Hardness.109
5.1 Turing Reducibility and NP-Hard Problems .109
5.2 A Terminological History.118
6 Coping with NP-Complete Problems.121
6.1 Performance Guarantees for Approximation Algorithms . . .123
6.2 Applying NP-Completeness to Approximation Problems . . .137
6.3 Performance Guarantees and Behavior “In Practice”.148
7 Beyond NP-Completeness.153
7.1 The Structure of NP.154
7.2 The Polynomial Hierarchy .161
7.3 The Complexity of Enumeration Problems.167
7.4 Polynomial Space Completeness.170
7.5 Logarithmic Space.177
7.6 Proofs of Intractability and P vs. NP.181
Appendix: A List of NP-Complete Problems .187
A1 Graph Theory.190
Al.l Covering and Partitioning.190
A1.2 Subgraphs and Supergraphs.194
A1.3 Vertex Ordering.199
A 1.4 Iso-and Other Morphisms.202
A1.5 Miscellaneous. 2 0 3
A2 Network Design.206
A2.1 Spanning Trees .206
A2.2 Cuts and Connectivity.209
A2.3 Routing Problems.211
A2.4 Flow Problems.214
A2.5 Miscellaneous.218
A3 Sets and Partitions .221
A3.1 Covering, Hitting, and Splitting.221
A3.2 Weighted Set Problems.223
A4 Storage and Retrieval.226
A4.1 Datastorage.226
A4.2 Compression and Representation.228
A4.3 Database Problems.232
CONTENTS vii
A5 Sequencing and Scheduling.236
A5.1 Sequencing on One Processor.236
A5.2 Multiprocessor Scheduling .238
A5.3 Shop Scheduling.241
A5.4 Miscellaneous.243
A6 Mathematical Programming.245
A7 Algebra and Number Theory.249
A7.1 Divisibility Problems.249
A7.2 Solvability of Equations.250
A7.3 Miscellaneous.252
A8 Games and Puzzles.254
A9 Logic.259
A9.1 Propositional Logic.259
A9.2 Miscellaneous.261
A10 Automata and Language Theory .265
A10.1 Automata Theory.265
A10.2 Lormal Languages.267
All Program Optimization.272
All.l Code Generation.272
A11.2 Programs and Schemes.275
A12 Miscellaneous.279
A13 Open Problems .285
Symbol Index .289
Reference and Author Index.291
Subject Index .327
Update for the Current Printing.339

实例下载地址

Computers and intractability a guide to the theory of NP-completeness (Garey, Michael R)

不能下载?内容有错? 点击这里报错 + 投诉 + 提问

好例子网口号:伸出你的我的手 — 分享

网友评论

发表评论

(您的评论需要经过审核才能显示)

查看所有0条评论>>

小贴士

感谢您为本站写下的评论,您的评论对其它用户来说具有重要的参考价值,所以请认真填写。

  • 类似“顶”、“沙发”之类没有营养的文字,对勤劳贡献的楼主来说是令人沮丧的反馈信息。
  • 相信您也不想看到一排文字/表情墙,所以请不要反馈意义不大的重复字符,也请尽量不要纯表情的回复。
  • 提问之前请再仔细看一遍楼主的说明,或许是您遗漏了。
  • 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦,又没人会搭理,于人于己都无利。

关于好例子网

本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享,对搜索内容的合法性不具有预见性、识别性、控制性,仅供学习研究,请务必在下载后24小时内给予删除,不得用于其他任何用途,否则后果自负。基于互联网的特殊性,平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查;无论平台是否已进行审查,用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场,基于网友分享,根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定,若资源存在侵权或相关问题请联系本站客服人员,点此联系我们。关于更多版权及免责申明参见 版权及免责申明

;
报警