MAC0338 Análise de Algoritmos
OBJETIVOS: Análise do desempenho de alguns algoritmos clássicos. Estudo de ferramentas de matemática discreta úteis para a análise de algoritmos.
PROGRAMA: Matemática discreta: solução de recorrências; problemas elementares de enumeração; coeficientes binomiais; funções geradoras; probabilidade discreta; elementos de análise assintótica. Análise de desempenho de alguns algoritmos clássicos de busca, ordenação, manipulação de árvores binárias, hashing, etc. Análise de pior caso e de caso médio. Análise de desempenho de alguns algoritmos clássicos sobre grafos.
PRÉ-REQUISITOS NO CURRÍCULO DO BCC: MAC0122.
PRÉ-REQUISITO NÃO-OFICIAL: MAC0323.
CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS: 4 horas, 4 créditos-aula.
CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM: Média ponderada de provas e exercícios.
BIBLIOGRAFIA BÁSICA:
- R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, 1989.
- R.L. Graham, D.E. Knuth, O. Patashnik, Matemática Concreta, Livros Técnicos e Científicos, Rio de Janeiro, 1995.
- H. Wilf, Generatingfunctionology, Academic Press, Boston, 1990.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 1990.
BIBLIOGRAFIA ADICIONAL (ainda não consta no Júpiter):
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 2nd ed., McGraw-Hill, 2001.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Algoritmos: Teoria e Prática, Campus, 2002.
- A.V. Aho, J.D. Ullman, Foundations of Computer Science, Computer Science Press, 1992.
OBSERVAÇÃO: Disciplina obrigatória no currículo do BCC.
[Veja dados da disciplina no JúpiterWeb]