MO417 - Complexidade de Algoritmos I - 2s2019

• Prof: Rafael C. S. Schouery
  • rafael@ic.unicamp.br
  • Sala 74 - Instituto de Computação
• Aulas: Terças e Quintas às 16h - Sala 351 (IC3.5)
• Atendimento:
  • Sextas às 15h, Sala 28 (IC2) alteração!
  • Quartas às 13h, Sala 28 (IC2) alteração!
• Planilha de Notas e Frequência
• Plano de Desenvolvimento da Disciplina

Testes

• Teste 6: Caminho mínimo, Árvore Geradora Mínima, Reduções e NP-Completude - 28/11 - download
• Teste 5: Grafos e Busca - 14/11
• Teste 4: Programação Dinâmica e Algoritmos Gulosos - 31/10
• Teste 3: Ordenação, Quicksort, Ordenação em tempo linear e Estatísticas de Ordem - 10/10
• Teste 2: Correção de Algoritmos e Projeto de Algoritmos por Indução - 19/09
• Teste 1: Análise de complexidade de algoritmos simples, notação assintótica e recorrências - 29/08

Listas de Exercício (para estudo)

• Lista 1
• Lista 2
• Lista 3
• Lista 4
• Lista 5
• Lista 6
• Lista 7
• Lista 8
• Lista 9
• Lista 10
• Lista 11
• Lista 12

Material de Aula

• 16 - NP-Completude (handout)
• 15 - Redução (handout)
• 14 - Caminho Mínimo (handout)
• 13 - Árvore Geradora Mínima (handout)
• 12 - Busca em Grafos (handout)
• 11 - Grafos (handout)
• 10 - Algoritmos Gulosos (handout)
• 09 - Programação Dinâmica (handout)
• 08 - Estatísticas de Ordem (handout)
• 07 - Ordenação em tempo linear (handout)
• 06 - Quicksort (handout)
• 05 - Ordenação (handout)
• 04 - Projeto de Algoritmos por Indução (handout)
• 03 - Correção de Algoritmos (handout)
• 02 - Complexidade (handout)
• 01 - Introdução (handout)

Calendário

• Início: 01/08
• Não haverá aula em 06/08, 08/08 e 05/09, 07/11

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.