Teoria da Computação

Raul H.C. Lopes

Outline

• Fundamentos
  • Indução
  • Conjuntos
  • Sistemas formais
  • Dedução
• Computabilidade
  • Máquinas turing
  • Lógica Booleana
  • Lógica de Primeira Ordem
  • Decidibilidade
  • A tese de Church
• Complexidade
  • Complexidade de Tempo
  • Classes de complexidade
  • Reduções
  • P e NP
  • Complexidade de Espaço
  • Problemas Intratáveis
  • Classe NC
  • Algoritmos do método probabilístico

Referências básicas

• Introduction to Metamathematics
  Stephen C. Kleene
• Foundations of Mathematical Logic
  Haskell B. Curry
• Introduction to Automata Theory, Languages, and Computation
  John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
• Computational Complexity
  Christos H.Papadimitriou
• Algorithmic Information Theory
  Gregory J. Chaitin
• Introduction to the Theory of Computation
  Michael Sipser
• Theory of Recursive Functions and Effective Computability
  Hartley Rogers

Links de interesse

Ferramentas

• Isabelle: Provador de Teoremas
• PVS: Provador de Teoremas
• Implementação do Haskell

Notas de Aula e Exercícios

• Exercícios sobre Lógica Proposicional
• Notas e exercícios sobre indução

Listas de Exercícios

• Prova de Teoremas

Provas