Os Reformados da Investigação

LITERATURA => Livros técnicos => Tópico iniciado por: bbbnnn em 29 de Abril de 2013, 10:55

Título: [Livro] Introduction to the Theory of Computation
Enviado por: bbbnnn em 29 de Abril de 2013, 10:55

Introduction to the Theory of Computation

(http://ecx.images-amazon.com/images/I/41SKTE8S1YL._SS500_.jpg)


:info:
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

:download:

:multihost:
 

Título: Re: [Livro] Introduction to the Theory of Computation
Enviado por: outtzider em 30 de Abril de 2013, 05:49

Thank you for the book.  :s;