Análise de Algoritmos (2/04)
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 à ela.
- 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étodos 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.*
- S. Baase e A. Van Gelder, Computer
Algorithms: Introduction to Design and Analysis (3rd ed),
Addison-Wesley, 2000.*
- N. Ziviani, Projeto de Algoritmos com
Implementações em PASCAL e C (2nd ed.), Thompson, 2004.*
- 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)
- 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.