Disciplina: DCC146 - ASPECTOS TEÓRICOS DA COMPUTAÇÃO
Horas Aula: 4
Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE
Plano de Ensino
Voltar
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
DIVÉRIO, T.A.; MENEZES, P. B. Teoria da Computação: Máquinas Universais e Computabilidade. 3ª Ed., Porto Alegre: Bookman, 2011. ISBN 9788577808243
HOPCROFT, J. E., MOTIWANI, R.,; ULLMAN, J. D. Introdução à Teoria de Autômatos, Linguagens e Computação. 2ª Ed. Rio de Janeiro: Campus, 2002. ISBN 9788535210729
MENEZES, P. B. Linguagens Formais e Autômatos. 5ª Ed., Porto Alegre: Bookman, 2008. ISBN 9788577802661
TOSCANI, l. V., VELOSO, P. A. S., Complexidade de Algoritmos, 2ª Ed., Porto Alegre: Bookman, 2009. ISBN 9788577803507
Bibliografia(continuação)
Não informado
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.
HENNIE, F. Introduction to computability. Addison Wesley, 1977. ISBN 9780201028485
LEWIS, H. R.; Papadimitrou, C. H. Elementos da Teoria da Computação. 2ª Ed., Porto Alegre: Bookman, 2004. ISBN 9788573075342
SUDKAMP, T. A. Languages and machines: an introduction to the theory of computer science. 2ª Ed., Addison-Wesley, 1998.
TERADA, R., Desenvolvimento de Algoritmos e Estruturas de Dados. São Paulo: McGraw-Hill, Makron, 1991.
ZOHAR, M. Mathematical theory of computation. McGraw-Hill, 1974.
