MO417 - Complexidade de Algoritmos I

Baixe o Plano de Desenvolvimento da Disciplina (PDD) aqui.

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)

Listas de Exercícios

Listas de exercícios para estudo:

1. Introdução
2. Demonstração
3. Funções
4. Correção
5. Projeto Recursivo
6. Fila de Prioridade
7. Aleatorizado
8. Ordenação Linear
9. Estatísticas de Ordem
10. Programação Dinâmica
11. Gulosos

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.