|
|
|
|
| LEADER |
03229nam a22003737a 4500 |
| 001 |
44811 |
| 008 |
970109t19791979xxe ||| |||| 00| 0 eng d |
| 009 |
PPN00404066X |
| 020 |
|
|
|a 9780716710455
|
| 020 |
|
|
|a 0716710447 (rel.)
|
| 020 |
|
|
|a 0716710455 (br.)
|
| 024 |
|
|
|a 9780716710455
|
| 041 |
0 |
|
|a eng
|
| 082 |
|
|
|a 518.1
|
| 084 |
|
|
|a F.2
|
| 084 |
|
|
|a 03D15. 1991
|
| 084 |
|
|
|a 68A20. 1991
|
| 084 |
|
|
|a 68C25. 1991
|
| 100 |
1 |
|
|a Garey, Michael R.
|
| 240 |
1 |
0 |
|a NP-completeness
|
| 245 |
1 |
0 |
|a Computers and intractability :
|b A guide to the theory of NP-completeness
|c Michael R. Garey, David S. Johnson,...
|
| 260 |
|
|
|a New York, N.Y :
|b W. H. Freeman.
|
| 260 |
|
|
|c C 1979.
|
| 300 |
|
|
|a 1 volume (X-338 pages) :
|b illustrations, graphiques, couverture illustrée ;
|c 24 cm.
|
| 490 |
1 |
|
|a A series of books in the mathematical sciences / Victor Klee, editor
|
| 500 |
|
|
|a Autres tirages : 1999, 2000, 2002, 2003, 2008
|
| 504 |
|
|
|a Bibliographie p. [291]-325. Index
|
| 505 |
0 |
|
|a 1. Computers, complexity, and intractability -- 1.1 Introduction -- 1.2 Problems, algorithms, and complexity -- 1.4 Provably intractable problems -- 1.5 NP-complete problems -- 1.6 An outline of the book -- 2. The theory of NP-completeness -- 2.1 Decision problems, languages, and encoding schemes -- 2.2 Deterministic Turing machines and the class P -- 2.3 Nondeterministic computation and the class NP -- 2.4 The relationship between P and NP -- 2.5 Polynomial transformations and NP-completeness -- 2.6 Cook's theorem -- 3. Proving NP-completeness results -- 3.1 Six basic NP-complete problems -- 3.2 Some techniques for proving NP-completeness -- 3.3 Some suggested exercises -- 4. Using NP-completeness to analyze problems -- 4.1 Analyzing subproblems -- 4.2 Number problems and strong NP-completeness -- 4.3 Time complexity as a function of natural parameters -- 5. NP-hardness -- 5.1 Turing reducibility and NP-hard problems -- 5.2 A terminological history -- 6. Coping with NP-complete problems -- 6.1 Performance guarantees for approximation algorithms -- 6.2 Applying NP-completeness to approximation problems -- 6.3 Performance guarantees and behavior "in practice" -- 7. Beyond NP-completeness -- 7.1 The structure of NP -- 7.2 The polynomial hierarchy -- 7.3 The complexity of enumeration problems -- 7.4 Polynomial space completeness -- 7.5 Logarithmic space -- 7.6 Proofs of intractability and P vs. NP -- Appendix : a list of NP-complete problems -- A1. Graph theory -- A2. Network design -- A3. Sets and partitions -- A4. Storage and retrieval -- A5. Sequencing and scheduling -- A6. Mathematical programming -- A7. Algebra and number theory -- A8. Games and puzzles -- A9. Logic -- A10. Automata and language theory -- A11. Program optimization -- A12. Miscellaneous -- A13. Open problems
|
| 650 |
|
|
|a Ordinateurs
|
| 650 |
|
|
|a Complexité de calcul (informatique)
|
| 650 |
|
|
|a Analyse combinatoire
|
| 650 |
|
|
|a Théorème de complétude
|
| 700 |
1 |
|
|a Johnson, David S.,
|d 1945-2016.
|4 aut
|
| 997 |
|
|
|0 44811
|1 Livre papier
|a Ressource papier
|b INSA
|c 0/Bourges/
|c 0/Orléans/
|c 1/Bourges/INSA CVL/
|c 1/Orléans/BU Sciences, Technologies, STAPS/
|z Orléans, BU Sciences, Technologies, STAPS, B85-1
|z Bourges, INSA CVL, 005.1 GAR
|
