Muutke küpsiste eelistusi

Introduction to the Theory of Computation 3rd edition [Pehme köide]

4.24/5 (2095 hinnangut Goodreads-ist)
(Massachusetts Institute of Technology)
  • Formaat: Paperback / softback, 504 pages, kõrgus x laius x paksus: 22x160x231 mm, kaal: 635 g
  • Ilmumisaeg: 29-Jan-2021
  • Kirjastus: Course Technology Inc
  • ISBN-10: 0357670582
  • ISBN-13: 9780357670583
Teised raamatud teemal:
  • Pehme köide
  • Hind: 85,39 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Tavahind: 106,74 €
  • Säästad 20%
  • Raamatu kohalejõudmiseks kirjastusest kulub orienteeruvalt 2-4 nädalat
  • Kogus:
  • Lisa ostukorvi
  • Tasuta tarne
  • Tellimisaeg 2-4 nädalat
  • Lisa soovinimekirja
Introduction to the Theory of Computation 3rd editionSuurem pilt
  • Formaat: Paperback / softback, 504 pages, kõrgus x laius x paksus: 22x160x231 mm, kaal: 635 g
  • Ilmumisaeg: 29-Jan-2021
  • Kirjastus: Course Technology Inc
  • ISBN-10: 0357670582
  • ISBN-13: 9780357670583
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780357670583.html
Märksõnad:
Gain a clear understanding of even the most complex, highly theoretical computational theory topics in the approachable presentation found only in the market-leading INTRODUCTION TO THE THEORY OF COMPUTATION, 3E. The number one choice for today's computational theory course, this revision continues the book's well-know, approachable style with timely revisions, additional practice, and more memorable examples in key areas. A new first-of-its-kind theoretical treatment of deterministic context-free languages is ideal for a better understanding of parsing and LR(k) grammars. You gain a solid understanding of the fundamental mathematical properties of computer hardware, software, and applications with a blend of practical and philosophical coverage and mathematical treatments, including advanced theorems and proofs. INTRODUCTION TO THE THEORY OF COMPUTATION, 3E's comprehensive coverage makes this a valuable reference for your continued studies in theoretical computing.
Preface to the First Edition xi
To the student xi
To the educator xii
The first edition xiii
Feedback to the author xiii
Acknowledgments xiv
Preface to the Second Edition xvii
Preface to the Third Edition xxi
Introduction 1(28)
0.1 Automata, Computability, and Complexity
1(2)
Complexity theory
2(1)
Computability theory
3(1)
Automata theory
3(1)
0.2 Mathematical Notions and Terminology
3(14)
Sets
3(3)
Sequences and tuples
6(1)
Functions and relations
7(3)
Graphs
10(3)
Strings and languages
13(1)
Boolean logic
14(2)
Summary of mathematical terms
16(1)
0.3 Definitions, Theorems, and Proofs
17(4)
Finding proofs
17(4)
0.4 Types of Proof
21(8)
Proof by construction
21(1)
Proof by contradiction
21(1)
Proof by induction
22(3)
Exercises, Problems, and Solutions
25(4)
Part One Automata and Languages
29(134)
1 Regular Languages
31(70)
1.1 Finite Automata
31(16)
Formal definition of a finite automaton
35(2)
Examples of finite automata
37(3)
Formal definition of computation
40(1)
Designing finite automata
41(3)
The regular operations
44(3)
1.2 Nondeterminism
47(16)
Formal definition of a nondeterministic finite automaton
53(1)
Equivalence of NFAs and DFAs
54(4)
Closure under the regular operations
58(5)
1.3 Regular Expressions
63(14)
Formal definition of a regular expression
64(2)
Equivalence with finite automata
66(11)
1.4 Nonregular Languages
77(24)
The pumping lemma for regular languages
77(5)
Exercises, Problems, and Solutions
82(19)
2 Context-Free Languages
101(62)
2.1 Context-Free Grammars
102(9)
Formal definition of a context-free grammar
104(1)
Examples of context-free grammars
105(1)
Designing context-free grammars
106(1)
Ambiguity
107(1)
Chomsky normal form
108(3)
2.2 Pushdown Automata
111(14)
Formal definition of a pushdown automaton
113(1)
Examples of pushdown automata
114(3)
Equivalence with context-free grammars
117(8)
2.3 Non-Context-Free Languages
125(5)
The pumping lemma for context-free languages
125(5)
2.4 Deterministic Context-Free Languages
130(33)
Properties of DCFLs
133(2)
Deterministic context-free grammars
135(11)
Relationship of DPDAs and DCFGs
146(5)
Parsing and LR(k) Grammars
151(3)
Exercises, Problems, and Solutions
154(9)
Part Two Computability Theory
163(110)
3 The Church-Turing Thesis
165(28)
3.1 Turing Machines
165(11)
Formal definition of a Turing machine
167(3)
Examples of Turing machines
170(6)
3.2 Variants of Turing Machines
176(6)
Multitape Turing machines
176(2)
Nondeterministic Turing machines
178(2)
Enumerators
180(1)
Equivalence with other models
181(1)
3.3 The Definition of Algorithm
182(11)
Hilbert's problems
182(2)
Terminology for describing Turing machines
184(3)
Exercises, Problems, and Solutions
187(6)
4 Decidability
193(22)
4.1 Decidable Languages
194(7)
Decidable problems concerning regular languages
194(4)
Decidable problems concerning context-free languages
198(3)
4.2 Undecidability
201(14)
The diagonalization method
202(5)
An undecidable language
207(2)
A Turing-unrecognizable language
209(1)
Exercises, Problems, and Solutions
210(5)
5 Reducibility
215(30)
5.1 Undecidable Problems from Language Theory
216(11)
Reductions via computation histories
220(7)
5.2 A Simple Undecidable Problem
227(7)
5.3 Mapping Reducibility
234(11)
Computable functions
234(1)
Formal definition of mapping reducibility
235(4)
Exercises, Problems, and Solutions
239(6)
6 Advanced Topics in Computability Theory
245(28)
6.1 The Recursion Theorem
245(7)
Self-reference
246(3)
Terminology for the recursion theorem
249(1)
Applications
250(2)
6.2 Decidability of logical theories
252(8)
A decidable theory
255(2)
An undecidable theory
257(3)
6.3 Turing Reducibility
260(1)
6.4 A Definition of Information
261(12)
Minimal length descriptions
262(4)
Optimality of the definition
266(1)
Incompressible strings and randomness
267(3)
Exercises, Problems, and Solutions
270(3)
Part Three Complexity Theory
273(170)
7 Time Complexity
275(56)
7.1 Measuring Complexity
275(9)
Big-0 and small-o notation
276(3)
Analyzing algorithms
279(3)
Complexity relationships among models
282(2)
7.2 The Class P
284(8)
Polynomial time
284(2)
Examples of problems in P
286(6)
7.3 The Class NP
292(7)
Examples of problems in NP
295(2)
The P versus NP question
297(2)
7.4 NP-completeness
299(12)
Polynomial time reducibility
300(4)
Definition of NP-completeness
304(1)
The Cook-Levin Theorem
304(7)
7.5 Additional NP-complete Problems
311(20)
The vertex cover problem
312(2)
The Hamiltonian path problem
314(5)
The subset sum problem
319(3)
Exercises, Problems, and Solutions
322(9)
8 Space Complexity
331(32)
8.1 Savitch's Theorem
333(3)
8.2 The Class PSPACE
336(1)
8.3 PSPACE-completeness
337(11)
The TQBF problem
338(3)
Winning strategies for games
341(2)
Generalized geography
343(5)
8.4 The Classes L and NL
348(3)
8.5 NL-completeness
351(3)
Searching in graphs
353(1)
8.6 NL equals coNL
354(9)
Exercises, Problems, and Solutions
356(7)
9 Intractability
363(30)
9.1 Hierarchy Theorems
364(12)
Exponential space completeness
371(5)
9.2 Relativization
376(3)
Limits of the diagonalization method
377(2)
9.3 Circuit Complexity
379(14)
Exercises, Problems, and Solutions
388(5)
10 Advanced Topics in Complexity Theory
393(50)
10.1 Approximation Algorithms
393(3)
10.2 Probabilistic Algorithms
396(12)
The class BPP
396(3)
Primality
399(5)
Read-once branching programs
404(4)
10.3 Alternation
408(7)
Alternating time and space
410(4)
The Polynomial time hierarchy
414(1)
10.4 Interactive Proof Systems
415(12)
Graph nonisomorphism
415(1)
Definition of the model
416(2)
IP = PSPACE
418(9)
10.5 Parallel Computation
427(6)
Uniform Boolean circuits
428(2)
The class NC
430(2)
P-completeness
432(1)
10.6 Cryptography
433(10)
Secret keys
433(2)
Public-key cryptosystems
435(1)
One-way functions
435(2)
Trapdoor functions
437(2)
Exercises, Problems, and Solutions
439(4)
Selected Bibliography 443(5)
Index 448
Michael Sipser has taught theoretical computer science and mathematics at the Massachusetts Institute of Technology for the past 32 years. He is a Professor of Applied Mathematics, a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL), and the current head of the mathematics department. He enjoys teaching and pondering the many mysteries of complexity theory.