CI165-A - Análise de Algoritmos

2o semestre de 2014

2a e 4a as 17:30

sala PA 01


Ementa

  1. Conceitos básicos de análise de algoritmos.
  2. Corretude de Algoritmos
  3. Análise de Algoritmos Iterativos e Recursivos
  4. Notação Assintótica
  5. Relações de Recorrência
  6. Algoritmos Aleatorizados e Análise Probabilística.
  7. Reduções
  8. NP-Completude.

Bibliografia

  1. Introduction to Algorithms, Cormen, Leiserson, Rivest e Stein (CLRS)
  2. Bibliografia Complementar

  3. Algorithm Design, Kleinberg e Tardos (KT)
  4. Algorithms, Dasgupta, Papadimitriou e Vazirani (DPV)
  5. Introduction to algorithms : a creative approach, U. Manber (Man)

Avaliação

Sao 2 provas (P1, P2) com mesmo peso e conteúdo cumulativo e uma prova final (PF) sobre toda a matéria.


Nas provas, é permitido UM ÚNICO TIPO DE CONSULTA: uma folha A4, escrita A MÃO, frente e verso.

Calendário

Material das Aulas

# SLIDES DA AULA EXERCÍCIOS REF. BIBLIOGRÁFICA
1 Introdução (exercícios) CLRS - 1
2 Revisão de Somatórios e Logaritmos (exercícios) Wikipedia: (1) e (2)
3 Revisão de Indução e Apêndice (exercícios) Livros de Matemática Discreta, Wikipedia: (1) e essa figura
4 Corretude de Algoritmos Recursivos (exercícios)
5 Corretude de Algoritmos Iterativos (exercícios)

Horário de atendimento