Os Reformados da Investigação

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