Sumários
Algoritmos online
30 maio 2014, 12:30 • Alexandre Francisco
Limite inferior para o coeficiente de competitividade de algoritmos online randomizados para o problema de paging, com recurso à aplicação do princípio de Yao e ao cálculo do tempo de cobertura em grafos completos. Exemplos e aplicações reais de alguns dos tópicos estudados ao longo do semestre.
Not Taught.
30 maio 2014, 11:00 • Alexandre Francisco
As aulas teóricas terminaram na segunda-feira, 26 de maio.
Algoritmos online
26 maio 2014, 09: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.
Contagem aproximada
23 maio 2014, 12:30 • Alexandre Francisco
Exercício sobre contagem aproximada por amostragem, caso de aplicação de limites de Chernoff. Exemplos de problemas de contagem, análise de complexidade.
Contagem aproximada II
23 maio 2014, 11:00 • Alexandre Francisco
Problema #DNF. Contagem por amostragem. FPRAS para o problema #DNF com recurso à técnica de cobertura de Karp e Luby.