A partir de cette page vous pouvez :
author
| Retourner au premier écran avec les étagères virtuelles... |
Détail de l'auteur
Auteur Carl H. Smith |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Faire une suggestion Affiner la recherche Interroger des sources externesA cursive introduction to the theory computation / Carl H. Smith (1994)
Titre : A cursive introduction to the theory computation Type de document : texte imprime Auteurs : Carl H. Smith Editeur : New York : Springer-Verlag Année de publication : 1994 Collection : Graduate texts in computer science Importance : 148 p. Présentation : ill. Format : 24cm ISBN/ISSN/EAN : 978-3-540-94332-7 Note générale : Bibliogr. Index Langues : Anglais Mots-clés : Theory Algorithms Recursive basic Computation Models Abstract Complexity Problems Note de contenu : Preface v
Introduction . 1
1. Models of Computation .3
1.1 Random Access Machines .4
1.2 Partial Recursive Functions .7
1.3 Pairing and Coding 16
1.4 Simulating an Execution of a RAM Program 20
1.5 Turing Machines 22
1.6 Some Other Models 26
1. 7 A Representation for Programs 28
1.8 Historical Notes 30
2. Basic Recursive Function Theory 31
2.1 Acceptable Programming Systems 31
2.2 Recursion Theorems 36
2.3 Alternative Characterizations 48
2.4 The Isomorphism Theorem 52
2.5 Algorithmically Unsolvable Problems 54
2.6 Recursively Enumerable Sets 58
2.7 Historical Notes 67
3. Abstract Complexity Theory 68
3.1 RAM Pseudospace Measure 69
3.2 Abstract Complexity Measures 70
3.3 Fundamental Results 74
3.4 Complexity Gaps 77
3.5 Complexity Compression 79
3.6 Speed-up 80
3. 7 Measures of Program Size 84
3.8 Restricted Programming Systems 88
3.9 Historical Notes 90
4. Complete Problems 91
4.1 Reducibilities 91
4.2 Polynomial Computability 94
4.3 The Deterministic Time Hierarchy 95
4.4 Nondeterminism . 103
viii Contents
4.5 An NP-Complete Problem . 109
4.6 More NP-Complete Problems . 116
4.7 Historical Notes . 124
Solutions to Selected Exercises . 125
List of Symbols . 142
Index . 144En ligne : https://tinman.cs.gsu.edu/~raj/8910/f18/recfuntheory.pdf Permalink : ./index.php?lvl=notice_display&id=15185 A cursive introduction to the theory computation [texte imprime] / Carl H. Smith . - New York : Springer-Verlag, 1994 . - 148 p. : ill. ; 24cm. - (Graduate texts in computer science) .
ISBN : 978-3-540-94332-7
Bibliogr. Index
Langues : Anglais
Mots-clés : Theory Algorithms Recursive basic Computation Models Abstract Complexity Problems Note de contenu : Preface v
Introduction . 1
1. Models of Computation .3
1.1 Random Access Machines .4
1.2 Partial Recursive Functions .7
1.3 Pairing and Coding 16
1.4 Simulating an Execution of a RAM Program 20
1.5 Turing Machines 22
1.6 Some Other Models 26
1. 7 A Representation for Programs 28
1.8 Historical Notes 30
2. Basic Recursive Function Theory 31
2.1 Acceptable Programming Systems 31
2.2 Recursion Theorems 36
2.3 Alternative Characterizations 48
2.4 The Isomorphism Theorem 52
2.5 Algorithmically Unsolvable Problems 54
2.6 Recursively Enumerable Sets 58
2.7 Historical Notes 67
3. Abstract Complexity Theory 68
3.1 RAM Pseudospace Measure 69
3.2 Abstract Complexity Measures 70
3.3 Fundamental Results 74
3.4 Complexity Gaps 77
3.5 Complexity Compression 79
3.6 Speed-up 80
3. 7 Measures of Program Size 84
3.8 Restricted Programming Systems 88
3.9 Historical Notes 90
4. Complete Problems 91
4.1 Reducibilities 91
4.2 Polynomial Computability 94
4.3 The Deterministic Time Hierarchy 95
4.4 Nondeterminism . 103
viii Contents
4.5 An NP-Complete Problem . 109
4.6 More NP-Complete Problems . 116
4.7 Historical Notes . 124
Solutions to Selected Exercises . 125
List of Symbols . 142
Index . 144En ligne : https://tinman.cs.gsu.edu/~raj/8910/f18/recfuntheory.pdf Permalink : ./index.php?lvl=notice_display&id=15185 Exemplaires
Code-barres Cote Support Localisation Section Disponibilité IA61BI/1 IA61BI Livre Magasin d'Ouvrages / INF Intelligence Artificielle Consultation sur place
Exclu du prêtAucun avis, veuillez vous identifier pour ajouter le vôtre !
