Programa

• Conceitos Básicos de Matemática: conceitos básicos de teoria dos conjuntos; relações e funções; definições recursivas; conceitos básicos de grafos; indução matemática.
• Linguagens Formais
  • Linguagens regulares: expressões regulares; gramáticas regulares; autômatos finitos; propriedades.
  • Linguagens livres do contexto: gramáticas livres do contexto; autômatos a pilha; propriedades.
  • Linguagens sensíveis ao contexto: gramáticas sensíveis ao contexto; autômatos lineares limitados; propriedades.
  • Linguagens recursivamente enumeráveis: gramáticas irrestritas; máquinas de Turing; linguagens recursivas; propriedades.
• Decidibilidade e Computabilidade:
  • Decidibilidade: problemas de decisão; tese de Church-Turing; o problema da parada; máquina de Turing universal; redutibilidade; exemplos de problemas indecidíveis.
  • Computação numérica: computação de funções; computação numérica; composição de funções; funções não computáveis.