Análise de Algoritmos (2/04, 2/05, 1/06)
Programa da Disciplina
Objetivos:
- Desenvolver a capacidade de avaliar a complexidade e a qualidade dos algoritmos propostos para um determinado
problema.
- Estudar os algoritmos básicos para as classes mais importantes de problemas tratados em computação.
- Compreender a importância da implementação e a sensibilidade do comportamento dos algoritmos.
- Conhecer as potencialidades e as limitações do conhecimento algorítmico atual.
- Apresentar as tendências da pesquisa na área.
Ementa:
1. Projeto, Construção e Análise de Algoritmos, 2. Método da Divisão e Conquista. 3. Método Guloso. 4. Programação Dinâmica. 5. Backtraking. 6. Algoritmos em Grafos. 7. Algoritmos Geométricos. 8. Redução. 9. Problemas NP-Completos.
Programa:
1. Introdução - Algoritmos, Projetos de Algoritmos, Corretude e Eficiência. Notação O grande, Omega e Teta. Somatórias e Indução Finita e Recorrências. Análise Probabilística e Algoritmos Randômicos. 2. Ordenação e Estatísticas de Ordem - Algoritmos de Ordenação. InsertionSort, MergeSort, HeapSort e QuickSort. Limites Inferiores para Ordenação. Counting Sort, Radix Sort e Bucket Sort. Seleção e Mediana. 3. Projeto Avançado e Técnicas de Análise - Programação Dinâmica e Método Guloso. 4. Algoritmos em Grafos - Algoritmos Elementares em Grafos. Árvores Geradoras Mínimas. Caminhos Mais Curtos. Fluxo Máximo. 5. Tópicos Selecionados - String Matching. Geometria Computacional. Reduções e Problemas NP-Completos. Algoritmos de Aproximação.
Bibliografia:
- T. Cormen, C. Leiserson, R. Rivest e C. Stein, Introduction to Algorithms (2nd ed), MIT Press, 2001.*
- M.T. Goodrich e R. Tamassia, Algorithm Design - Foundations, Analysis, and Internet Examples, John Wiley & Sons, 2002.* (Projeto de Algoritmos - Fundamentos, análise e exemplos da Internet, Bookman, 2004 - Versão em Português) (JAVA)
- S. Baase e A. Van Gelder, Computer Algorithms: Introduction to Design and Analysis (3rd ed), Addison-Wesley, 2000.(JAVA)*
- N. Ziviani, Projeto de Algoritmos com Implementações em PASCAL e C (2nd ed.), Thompson, 2004.*(C e Pascal)
- G.J. Pothering e T.L. Naps, Introduction to Data Structures and Algorithm Analysis with C++, West, 1995. (C++)
- U. Manber, Algorithms: A Creative Approach, Addison-Wesley, 1989.
- A.V. Aho, J.E. Hopcroft e J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, 1974.
- R. Sedgewick, Algorithms. Addison-Wesley, 1988
- M. Garey e D. Johnson, Computers and Intractability: a guide to the theory of NP-Completeness, Freeman, 1979.