UFJF - Universidade Federal de Juiz de Fora

Plano de ensino

Disciplina: DCC029 - ASPECTOS FORMAIS DA COMPUTACAO

Créditos: 5

Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE

Ementa Noções de análise de algoritmos e crescimento de funções. Análise de algoritmos de ordenação. Noções de linguagens formais e autômatos. Linguagens livres de contexto. Noções de decidibilidade. Problemas intratáveis.
Conteúdo 1. Noções de análise de algoritmos e crescimento de funções
Notações O, Análise de algoritmos.
2. Análise de algoritmos de ordenação
Algoritmos baseados em comparação. Complexidade de algoritmos de ordenação. Outros algoritmos.
3. Noções de linguagens formais e autômatos
Introdução às linguagens formais, linguagens regulares: autômatos finitos determinísticos e não determinísticos, equivalência entre autômatos finitos determinísticos e não determinísticos, minimização de autômatos finitos, gramáticas e expressões regulares.
4. Linguagens livres de contexto
Autômatos de pilha e gramáticas livres de contexto.
5. Noções de decidibilidade
Máquinas de Turing e a tese de Church-Turing, problemas indecidíveis, redução de problemas.
6. Problemas intratáveis
Classes P e NP. Problemas NP-Completo e NP-Difícil.
Bibliografia DINÉSIO, T.A.;   MENEZES, P. B. Teoria da Computação. Sagra Luzzatto, 1999.
HENNIE, F. Introductions to computability. Addison Wesley, 1977.
HOPCROFT, J. E., MOTIWANI, R.,; ULLMAN, J. D. Introduction to automata theory, languages and computation (3rd ed). Addison-Wesley, 1979 2006.
LEWIS, H. R.; Papadimitrou, C. H. Elementos da Teoria da Computação. Bookman, 2000.
MENEZES, P. B. Linguagens Formais e Autômatos. Sagra Luzzatto, 1997.
SUDKAMP, T. A. Languages and machines: an introduction to the theory of computer science. Addison-Wesley, 1996.
TERADA, R., Desenvolvimento de Algoritmos e Estruturas de Dados. McGraw-Hill, 1991.
TOSCANI, l. V., VELOSO, P. A. S., Complexidade de Algoritmos, Sagra Luzzatto, 2001.
Bibliografia (continuação)
Bibliografia complementar AHO, A.V.; HOPCROFT, J.E.; ULLMAN, J.D. The Design and Analysis of Computer Algorithms. Addison Wesley,1974.
CAMPELLO, R.; MACULAN FILHO, N. Algoritmos e Heurísticas. Editora da UFF, 1994.
GAREY, M. R., JOHNSON D. S., Computer and intractability: a guide to the theory of NP-Completeness, Freeman, 1979.
ZOHAR, M. Mathematical theory of computation. McGraw-Hill, 1974.
Voltar