Next: Livro Texto
Up: No Title
Previous: Ementa
- 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.
Newton Jose Vieira
Fri Mar 20 10:12:01 EST 1998