Sumários
Apresentações e discussão do 4º projeto
29 maio 2015, 11:00 • Alexandre Francisco
Apresentações e discussão do 4º projeto. FPRAS para problemas NP-hard e RP vs NP.
Apresentações do 4º projeto
29 maio 2015, 09:30 • Alexandre Francisco
Apresentações e discussão do 4º projeto.
Algoritmos online
26 maio 2015, 11:00 • 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. Aplicação do princípio de Yao.
Contagem aproximada
22 maio 2015, 11:00 • Alexandre Francisco
Discussão de exercício de aula anterior relativo a funções de dispersão. Exercício sobre contagem aproximada por amostragem, caso de aplicação de limites de Chernoff. Exemplos de problemas de contagem aproximada por amostragem, análise de complexidade.
Contagem aproximada
22 maio 2015, 09:30 • Alexandre Francisco
Introdução e motivação do problema da contagem. Relação entre problemas e os problemas de contagem associados. Classe de problemas #P. PAS, PRAS e FPRAS. Problema #DNF. Contagem por amostragem. FPRAS para o problema #DNF com recurso à técnica de cobertura de Karp e Luby.