Programação das aulas de MAC6711
Primeiro semestre de 2015
Março
Abril
- 1 e 3 de abril: Semana Santa (não há aula)
- 8 de abril (Aula 6):
- Algoritmos probabilísticos
- Teste de igualdade de polinômios
- Problema da contenção
- Comentários sobre o algoritmo do exponential backoff time
Leitura recomendada: Sec 1.1 do livro
Probability and Computing: Randomized Algorithms and
Probabilistic Analysis, de Computing and Probability
(QA274.M574 2005), e começo do Cap 13 e Sec 13.1 e 13.2 do KT.
Leia também a explicação sobre o algoritmo de
exponential backoff
time, que é utilizado na Ethernet.
Transparências [pdf].
- 10 de abril:
Matéria da prova: notação assintótica,
resolução de recorrência, divisão e conquista.
- 15 de abril (Aula 7):
- Quicksort e Select aleatorizados
- Par mais próximo de pontos: um algoritmo aleatorizado
- Lista 3
Leitura recomendada: Secs 7.3, 7.4 e 9.2 do CLRS. Sec 13.7 do KT.
Transparências [pdf].
- 17 de abril (Aula 8):
- Corte mínimo em um grafo
- Hashing
Leitura recomendada: Secs 13.2 e 13.6 do KT.
Transparências [pdf].
- 22 de abril (Aula 9):
- Método guloso
- Escalonamento de tarefas
(coleção máxima de intervalos disjuntos)
- Alocação de salas de aula
Leitura recomendada: Sec 4.1 do KT e 16.1 do CLRS.
Transparências [pdf].
- 24 de abril (Aula 10):
- Escalonamento com atraso máximo mínimo
- Um pouco sobre matroides
- Lista 4
Leitura recomendada: Sec 4.2 do KT e Sec 16.4 do CLRS.
E Sec 16.5?
Transparências [pdf].
- 29 de abril (Aula 11):
- Caching ótimo e LRU
- Política aleatorizada de caching
Leitura recomendada: Secs 4.3 e 13.8 do KT.
Transparências [pdf].
Maio