MO417 - Complexidade de Algoritmos I

Material de Aula

1. Introdução (Handout)
2. Demonstração (Handout)
3. Funções (Handout)
4. Correção (Handout)
5. Projeto Recursivo (Handout)
6. Fila de Prioridade (Handout)
7. Aleatorizado (Handout)
8. Cota Inferior (Handout)
9. Ordenação Linear (Handout)
10. Estatísticas de Ordem (Handout)
11. Programação Dinâmica (Handout)
12. Gulosos (Handout)
13. Grafo (Handout)
14. Busca (Handout)
15. AGM (Handout)
16. Caminho (Handout)
17. Redução (Handout)
18. NPC (Handout)

Ementa

• Modelos de computação e ferramentas/notação para análise de algoritmos.
• Indução matemática e projeto de algoritmos.
• Algoritmos gulosos.
• Programação dinâmica.
• Divisão e conquista.
• Algoritmos para ordenação e seleção.
• Algoritmos para problemas básicos em grafos.
• Reduções e NP-completude.

Bibliografia

Bibliografia recomendada:

• Cormen, Leiserson, Rivest e Stein. Introduction to Algorithms, second edition, MIT Press, 2001.
  • É possível acompanhar o curso com a terceira edição também
  • Evite, se possível, as versões traduzidas da segunda edição

Bibliografia oficial:

• Cormen, Leiserson e Rivest. Introduction to Algorithms, MIT Press, 1990.
• U. Manber. Introduction to Algorithms. Addison Wesley, 1989.
• Brassard and Bratley. Algorithms. Prentice-Hall, 1996.
• Garey and Johnson. Computers and Intractability. Freeman, 1982.