CI165 - Análise de Algoritmos

2o semestre de 2012

2a e 4a as 17:30

sala PA02

Lista de Emails: https://groups.google.com/d/forum/ci165-2012-2


Ementa

  1. Conceitos básicos de análise de algoritmos.
  2. Análise de Algoritmos de Ordenação.
  3. Análise Probabilística.
  4. Programação Dinâmica.
  5. Análise Amortizada.
  6. Reduções
  7. Formulações em Programação Linear.
  8. NP-Completude.

Bibliografia

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

    2. Bibliografia Complementar

  2. Algorithm Design, Kleinberg e Tardos (KT)
  3. Algorithms, Dasgupta, Papadimitriou e Vazirani (DPV) (link para a versão preliminar online)
  4. 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.

Notas

Calendário

Material das Aulas

Alguns dos slides abaixo foram originalmente preparados pelo professor Cid Carvalho de Souza e por Cândida Nunes da Silva (detalhes no 1o slide da introdução). O que disponibilizarei aqui será com algumas modificações feitas por mim.

# SLIDES DA AULA EXERCÍCIOS REF. BIBLIOGRÁFICA
1 Introdução (exercícios) CLRS - 1
2 InsertionSort e Análise de Alg. Iterativos (exercícios) CLRS - 2.1, 2.2
3 MergeSort e Análise de Alg. Recursivos (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 Algoritmos Aleatorizados: Quebra de Simetria (exercícios) KT - 13.1
9 Algoritmos Aleatorizados: Corte Mínimo Global (exercícios) KT - 13.2
PROVA 1
10 Algoritmos Aleatorizados: Variáveis Aleatórias e Esperança (exercícios) KT - 13.3
11 QuickSort: Melhor Caso e Pior Caso (exercícios) CLRS - 7.1, 7.2, 7.4
12 QuickSort: Intuição do Caso Médio e Versão Aleatorizada (exercícios) CLRS - 7.2, 7.3, 7.4
13 Cotas Inferiores para Ordenação e Busca (exercícios) CLRS - 8.1
14 Programação Dinâmica: Corte de Barras (exercícios) CLRS - 15.1
15 Programação Dinâmica: Multiplicação de Cadeia de Matrizes (exercícios) CLRS - 15.2
16 Reduções (exercícios) Man - 10.1, 10.2, 10.4
PROVA 2
17 Problemas de Busca, a.k.a NP - Parte 1 (exercícios) DPV - 8.1
18 Problemas de Busca, a.k.a NP - Parte 2 (exercícios) DPV - 8.1
19 Classes P, NP, NP-Completo (exercícios) DPV - 8.2
20 Reduções de Problemas Difíceis (exercícios) DPV - 8.3
22 Redução de Cook-Levin e Considerações Finais (exercícios) DPV - 8.3
23 PROVA 3

Horário de atendimento