MAC5711 - Análise de Algoritmos

Objetivos:

A disciplina tem por objetivo: rever algoritmos clássicos, fazer a análise do seu desempenho e desenvolver a capacidade de classificar problemas computacionais e algoritmos de acordo com a sua complexidade.

Justificativa:

O projeto de algoritmos é uma atividade fundamental na computação e a análise é parte indispensável nesse projeto.

Conteúdo:

  1. Notação assintótica.
  2. Recorrências.
  3. Mergesort.
  4. Quicksort.
  5. Filas de prioridade e heapsort.
  6. Ordenação em tempo linear.
  7. Programação dinâmica.
  8. Algoritmos elementares para grafos.
  9. Árvore geradora mínima.
  10. Caminhos mínimos.
  11. Complexidade computacional.

Bibliografia:

  1. T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms, 3nd.ed., MIT Press & McGraw-Hill, 2009.(existe uma boa tradução para português)
  2. J. Kleinberg and E. Tardos, Algorithm Desing, Addison-Wesley, 2006.
  3. A.V. Aho and J.D. Ullman, Foundations of Computer Science, Computer Science Press, 1992.
  4. G. Brassard and P. Bratley, Fundamentals of Algorithmics, Prentice Hall, 1996.
  5. U. Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.
  6. J. Erickson, Algorithms. Etc, (note também os links no topo dessa página)

Outras:

É importante neste curso poder ler e escrever demonstrações matemáticas. Para quem já esqueceu como se faz isso, os livros usados em MAC-105 podem ajudar.
Arnaldo Mandel <am@ime.usp.br>
Última modificação: Wed Aug 15 12:27:31 -03 2018 por am