Sumários

Revisões

24 maio 2013, 10:00 Alexandre Francisco

Esclarecimento de dúvidas e apoio ao projecto 4.


Not Taught.

24 maio 2013, 08:30 Alexandre Francisco

As aulas teóricas terminaram na segunda-feira, 20 de maio.

 


Algoritmos online

20 maio 2013, 08:30 Alexandre Francisco

Algoritmos online, motivação e conceitos básicos. O paging problem: algoritmos deterministicos online e offline; algoritmos randomizados. Análise competitiva e coeficientes de competitividade. Adversários informados e não informados. Limites superior e inferior para o coeficiente de competitividade.


APSP e contagem aproximada

17 maio 2013, 10:00 Alexandre Francisco

Conclusão dos problemas 10.1 e 10.7 do livro  "Randomized Algorithms". Exercício sobre a extensão do algoritmo APSP para grafos pesados com pesos inteiros. Exercício 11.4 do livro  "Randomized Algorithms".


Algoritmos de aproximação

17 maio 2013, 08:30 Alexandre Francisco

Conclusão da aula anterior: contagem aproximada; problema #DNF. Algoritmos de aproximação: motivação e conceitos básicos. O problema da cobertura de conjuntos, algoritmo de aproximação e limite da razão.