[Livro] Introduction to the Theory of Computation

[bbbnnn]

Introduction to the Theory of Computation





Título: Introduction to the Theory of Computation (2ª edição)
Autor: Michael Sipser
Editora: Thomson Course Technology


Conteúdo:

Clicar aqui para ver conteúdo escondido (Passar cursor para mostrar conteúdo)

Introduction
 - Automata, Computability, and Complexity
 - Mathematical Notions and Terminology
 - Definitions, Theorems, and Proofs
 - Types of Proof
(Part 1: Automata and Languages)
  1. Regular Languages
 - Finite Automata
 - Nondeterminism
 - Regular Expressions
 - Nonregular Languages
  2. Context-Free Languages
 - Context-free Grammars
 - Pushdown Automata
 - Non-context-free Languages
(Part 2: Computability Theory)
  3. The Church-Turing Thesis
 - Turing Machines
 - Variants of Turing Machines
 - The Definition of Algorithm
  4. Decidability
 - Decidable Languages
 - The Halting Problem
  5. Reducibility
 - Undecidable Problems from Language Theory
 - A Simple Undecidable Problem
 - Mapping Reducibility
  6. Advanced Topics in Computability Theory
 - The Recursion Theorem
 - Decidability of logical theories
 - Turing Reducibility
 - A Definition of Information
(Part 3: Complexity Theory)
  7. Time Complexity
 - Measuring Complexity
 - The Class P
 - The Class NP
 - NP-completeness
 - Additional NP-complete Problems
  8. Space Complexity
 - Savitch's Theorem
 - The Class PSPACE
 - PSPACE-completeness
 - The Classes L and NL
 - NL-completeness
 - NL equals coNL
  9. Intractability
 - Hierarchy Theorems
 - Relativization
 - Circuit Complexity
  10. Advanced Topics in Complexity Theory
 - Approximation Algorithms
 - Probabilistic Algorithms
 - Alternation
 - Interactive Proof Systems
 - Parallel Computation
 - Cryptography


Contém exercícios com soluções

 

[outtzider]

Thank you for the book.