MARC details
| 000 -CABECERA |
|---|
| campo de control de longitud fija |
05726 a2200277 4500 |
| 008 - DATOS DE LONGITUD FIJA--INFORMACIÓN GENERAL |
|---|
| campo de control de longitud fija |
250318s########|||||||||||||||||||||||#d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER |
|---|
| International Standard Book Number |
0-13-273417-6 |
| 040 ## - FUENTE DE CATALOGACIÓN |
|---|
| Centro catalogador/agencia de origen |
GAMADERO2 |
| Lengua de catalogación |
spa |
| Centro/agencia transcriptor |
GAMADERO2 |
| 041 ## - CÓDIGO DE IDIOMA |
|---|
| Código de lengua del texto/banda sonora o título independiente |
Español |
| 050 00 - SIGNATURA TOPOGRÁFICA DE LA BIBLIOTECA DEL CONGRESO |
|---|
| Número de clasificación |
LCC |
| 100 ## - ENTRADA PRINCIPAL--NOMBRE DE PERSONA |
|---|
| Nombre de persona |
Harry R. Lewis |
| 245 ## - MENCIÓN DEL TÍTULO |
|---|
| Título |
Elements of theory of computation / |
| 250 ## - MENCION DE EDICION |
|---|
| Mención de edición |
1 |
| 260 ## - PUBLICACIÓN, DISTRIBUCIÓN, ETC. |
|---|
| Nombre del editor, distribuidor, etc. |
Prentice hall |
| Lugar de publicación, distribución, etc. |
Estados Unidos |
| Fecha de publicación, distribución, etc. |
1981 |
| 300 ## - DESCRIPCIÓN FÍSICA |
|---|
| Extensión |
459 |
| Dimensiones |
15cm de ancho X 23cm de largo |
| 490 0# - MENCIÓN DE SERIE |
|---|
| Mención de serie |
Serie |
| 505 ## - NOTA DE CONTENIDO CON FORMATO |
|---|
| Nota de contenido con formato |
PREFACE<br/><br/>Chapter 1 SETS, RELATIONS, AND LANGUAGES<br/><br/>1.1 "If-Then" and its Relatives 1<br/><br/>1.2 Sets 5<br/><br/>1.3 Relations and Functions 8<br/><br/>1.4 Special Types of Binary Relations<br/><br/>12<br/><br/>1.5 Closures 18<br/><br/>1.6 Finite and Infinite Sets 21<br/><br/>1.7 Three Fundamental Proof Techniques<br/><br/>23<br/><br/>1.8 Alphabets and Languages 29<br/><br/>1.9 Finite Representation of Languages<br/><br/>33<br/><br/>Problems 39<br/><br/>References 47<br/>CONTENTS<br/><br/>Chapter 2 FINITE AUTOMATA<br/><br/>2.1 Deterministic Finite Automata 49<br/><br/>2.2 Nondeterministic Finite Automate 54<br/><br/>2.3 Equivalence of Deterministic and Nondatsministic Finite Automata 59<br/><br/>2.4 Properties of the Languages Accepted by Finito Automata 64<br/><br/>2.5 Finite Automata and Regular Expressions 69<br/><br/>2.6 Proofs that Languages Are and Are Not Regular 73<br/><br/>Problems 76<br/><br/>References 53<br/><br/>Chapter 3 CONTEXT-FREE LANGUAGES<br/><br/>31 Context-Free Grammars 95<br/><br/>3.2 Regular Languages and Context-Fres Languages 102<br/><br/>3.3 Pushdown Automata 105<br/><br/>3.4 Pushdown Automata and Context-Free Grammars 110<br/><br/>3.5 Properties of Context-Free Languages 119<br/><br/>3.5.1 Closure Properties 120<br/><br/>3.5.2 Periodicity Properties 122<br/><br/>3.5.3 Algorithmic Properties 131<br/><br/>3.6 Determinism and Parsing 134<br/><br/>3.6.1 Deterministic Pushdown Automata and Context-Free<br/><br/>Languages 135<br/><br/>3.6.2 Top-Down Parsing 138<br/><br/>3.6.3 Bottom-Up Parsing 146<br/><br/>Problems 153<br/><br/>References 164<br/><br/>CONTENTS<br/><br/>Chapter 4 TURING MACHINES<br/><br/>4.1 The Dafinition of a Turing Machine 168<br/><br/>4.2 Computing with Turing Machines 175<br/><br/>4.3 Combining Turing Machines 180<br/><br/>Some Examples of More Powerful Turing Machines 187<br/><br/>4.5 Extensions of the Turing Mechine 192<br/><br/>46 Nondstorministic Turing Machines 204<br/><br/>Problems 211<br/><br/>References 221<br/><br/>Chapter 5 CHURCH'S THESIS<br/><br/>5.1 Church's Thesis 222<br/><br/>5.2 Grammars 224<br/><br/>5.3 The Primitive Recursive Functions 232<br/><br/>54 Gödelization 242<br/><br/>5.5 The -Recursive Functions 248<br/><br/>5.6 Turing-Computability of the -Recursive Functions 252<br/><br/>5.7 Universal Turing Machines 258<br/><br/>Problems 262<br/><br/>References 271<br/><br/>Chapter 6 UNCOMPUTABILITY<br/><br/>6.1 The Halting Problem 272<br/><br/>6.2 Turing-Enumorability, Turing-Acceptability. and Turing-Decidability<br/> |
| 520 ## - RESUMEN, ETC. |
|---|
| Resumen, etc. |
PREFACE<br/><br/>This book is an introduction, on the undergraduate level, to the classi-cal and contemporary theory of computation. The topics covered are, in a few words, the theory of automata and formal languages, computability by Turing machines and recursive functions, uncomputability, computational complexity, and mathematical logic. The treatment is mathematical but the viewpoint is that of computer science; thus the chapter on context-free languages includes a discussion of parsing, and the chapters on logic establish the soundness and completeness of resolution theorem-proving.<br/><br/>In the undergraduate curriculum, exposure to this subject tends to come late, if at all, and collaterally with courses on the design and analysis of algorithms. It is our view that computer science students should be exposed to this material earlier as sophomores or juniors-both because of the deeper insights it yields on specific topics in computer science, and because it serves to establish essential mathematical paradigms. But we have found teaching a rigorous undergraduate course on the subject a difficult under-taking because of the mathematical maturity assumed by the more advanced textbooks. Our goal in writing this book has been to make the essentials of the subject accessible to a broad undergraduate audience in a way that is mathematically sound but presupposes no special mathematical experience.<br/><br/>The whole book represents about a year's worth of coursework. We have each taught a one-term course covering much of the material in Chap-ters I through 6, omitting on various occasions and in various combinations the sections on parsing, on recursive functions, and on particular unsolvable decision problems. Other selections are also possible; for example, a course xiv<br/><br/>PREFACE<br/><br/>emphasizing computability and the foundations of mechanical logic might skip quickly over Chapters 1 through 3 and concentrate on Chapters 4, 6, 8, and 9. However it is used, our fervent hope is that the book will contribute to the intellectual development of the next generation of computer scientists by introducing them at an early stage of their education to crisp and method-ical thinking about computational problems.<br/><br/>We take this opportunity to thank all from whom we have learned, both teachers and students. Specific thanks go to Larry Denenberg and Aaron Temin for their proofreading of early drafts, and to Michael Kahl and Oded Shmueli for their assistance and advice as teaching assistants. In the spring of 1980 Albert Meyer taught a course at M.I.T. from a draft of this book, and we thank him warmly for his criticisms and corrections. Of course, the blame for any remaining errors rests with us alone. Renate D'Arcangelo typed and illustrated the manuscript with her characteristic but extraordinary perfec-tionism and rapidity. |
| 526 ## - NOTA DE INFORMACIÓN SOBRE EL PROGRAMA DE ESTUDIO |
|---|
| Program name |
Ingeniería en Tecnologías de la Información y Comunicación |
| 700 ## - ENTRADA AGREGADA--NOMBRE PERSONAL |
|---|
| Nombre de persona |
Christos H. Papadimitriou |
| 942 ## - ELEMENTOS DE ENTRADA SECUNDARIOS (KOHA) |
|---|
| Tipo de ítem Koha |
Libro |
| Fuente del sistema de clasificación o colocación |
Clasificación Decimal Dewey |
| Edición |
1 |
| 945 ## - CATALOGADORES |
|---|
| Número del Creador del Registro |
1 |
| Nombre del Creador del Registro |
admin |
| Número de último modificador del registro |
1261 |
| Nombre del último modificador del registro |
Jenny Viridiana Quiroz Linares |
