Teoria da Computa\c c\~ao

Raul H.C. Lopes

Outline

• Fundamentos
  • Indu\c c\~ao
  • Conjuntos
  • Sistemas formais
  • Dedu\c c\~ao
• Computabilidade
  • M\'aquinas turing
  • L\'ogica Booleana
  • L\'ogica de Primeira Ordem
  • Decidibilidade
  • A tese de Church
• Complexidade
  • Complexidade de Tempo
  • Classes de complexidade
  • Redu\c c\~oes
  • P e NP
  • Complexidade de Espa\c co
  • Problemas Intrat\'aveis
  • Classe NC
  • Algoritmos do m\'etodo probabil\'istico

Refer\^encias b\'asicas

• 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\c c\~ao do Haskell

Notas de Aula e Exerc\'icios

• Exerc\'icios sobre L\'ogica Proposicional
• Notas e exerc\'icios sobre indu\c c\~ao

Listas de Exerc\'icios

Provas