Programa

• Conceitos Básicos de Matemática: representação; prova de teoremas; conjuntos; relações; funções; conjuntos enumeráveis; definições recursivas; indução matemática; grafos; linguagens formais; gramáticas; problemas de decisão.
• 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.