CI165-A - Análise de Algoritmos

2o semestre de 2014

2a e 4a as 17:30

sala PC ??


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) (link para a versão preliminar online)
  5. Introduction to algorithms : a creative approach, U. Manber (Man)

Avaliação

Sao 3 provas (P1, P2 e P3) 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 Análise de Alg. Iterativos e InsertionSort (exercícios) CLRS - 2.1, 2.2
3 Análise de Alg. Recursivos e MergeSort (exercícios) CLRS - 2.3
4 Notação Assintótica - O (exercícios) CLRS - 3.1 e KT - 2.2
5 Notação Assintótica - Ω e Θ (exercícios) CLRS - 3.1 e KT - 2.2
6 Recorrências 1 (exercícios) CLRS - 4.3
7 Recorrências 2 (exercícios) CLRS - 4.4, 4.5
8 PROVA 1
9 Introdução à Algoritmos Aleatorizados (exercícios) KT - 13.1
10 Algoritmos Aleatorizados: Corte Mínimo Global (exercícios) KT - 13.2
11 Algoritmos Aleatorizados: Variáveis Aleatórias e Esperança (exercícios) KT - 13.3
12 QuickSort: Melhor Caso e Pior Caso (exercícios) CLRS - 7.1, 7.2, 7.4
13 QuickSort: Intuição do Caso Médio e Versão Aleatorizada (exercícios) CLRS - 7.2, 7.3, 7.4
14 Cotas Inferiores para Ordenação e Busca (exercícios) CLRS - 8.1
15 Aula de Exercícios
16 PROVA 2
17 Correção da Prova e Breve História do Problema P = NP?
18 Reduções (exercícios) Man - 10.1, 10.2, 10.4
19 Problemas de Busca, a.k.a NP - Parte 1 (exercícios) DPV - 8.1
20 Problemas de Busca, a.k.a NP - Parte 2 (exercícios) DPV - 8.1
21 Classes P, NP, NP-Completo (exercícios) DPV - 8.2
22 Reduções de Problemas Difíceis (exercícios) DPV - 8.3
23 Redução de Cook-Levin e Considerações Finais (exercícios) DPV - 8.3
24 Aula de Exercícios
25 PROVA 3

Horário de atendimento