Projeto e Análise de Algoritmos
Notação assintótica, recorrência. Análise do melhor, pior e caso médio. Algoritmos de busca, ordenação e seleção. Paradigmas de projeto de algoritmos (tentativa e erro, divisão e conquista, programação dinâmica, análise amortizada, algoritmos gulosos, algoritmos randomizados, algoritmos aproximados). Algoritmos para problemas básicos em grafos (busca em profundidade/largura, árvore geradora mínima, caminhos mais curtos, componentes fortemente conectados, ordenação topológica). Problemas intratáveis; classes P, NP-difícil, NP e NP-completo.
Informações Básicas
Carga horária
60h.
Pré-requisito
Estrutura de Dados
Obrigatória:
- CORMEN, T.; LEISERSON, C.; RIVEST, R.; STEIN C. Algoritmos: Teoria e Prática, 3 ed. Elsevier, 2012.
- DASGUPTA, S.; PAPADIMITRIOU C.; VAZIRANI U. Algoritmos. McGraw-Hill, 2009.
- STROUSTRUP, B. C++ Programming Language. 4 Ed. Addison-Wesley Professional, 2013.
Complementar:
- CORMEN, T. Desmistificando Algoritmos. 1. ed. Rio de Janeiro: Elsevier, 2014.
- TOSCANI, L. V.; VELOSO, P. A. S. Complexidade de Algoritmos. 3. ed. Porto Alegre: Bookman, 2012.
- BHARGAVA, A.Y. Entendendo Algoritmos. 1 ed. Novatec Editora, 2017.
- ZIVIANI, N. Projeto de algoritmos: com implementações em Java e C++. - São Paulo: Cengage Learning, 2007.
- PEREIRA, J. M. S. S. Grafos e redes: Teoria e algoritmos básicos: 1 ed. Editora Interciência, 2014