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)
6 Análise de Alg. Iterativos e InsertionSort (exercícios) CLRS - 2.1, 2.2
7 Notação Assintótica - O (exercícios) CLRS - 3.1 e KT - 2.2
8 Notação Assintótica - Ω e Θ (exercícios) CLRS - 3.1 e KT - 2.2
9 Mais sobre Algoritmos Iterativos (exercícios)
10 Análise de Alg. Recursivos e MergeSort (exercícios) CLRS - 2.3
11 Mais sobre Algoritmos Recursivos (exercícios) CLRS - 2.3

Horário de atendimento