UFC - Departamento de Computação

Algoritmos Probabilísticos (CK191 - CKP8511)

Semestre: 2018.2
Horário: Sextas 10h-12h e 14h-16h
Local: Sala 01 - Bloco 952
Atendimento: Na minha sala, em qualquer horário, desde que com reserva antecipada. Uma reserva pode ser feita via correio eletrônico ou na sala de aula.

Avisos Importantes:

Notas

Listas de Exercícios

Lista 1 (Probabilidade básica e Desigualdades)
Lista 2 (Distribuições clássicas e Cadeias de Markov)
Lista 3 (Construção e Análise de Algoritmos probabilísticos)
Lista 4 (Complexidade Computacional)

Ementa e Bibliografia:

Ementa Oficial

Um algoritmo probabilístico é um algoritmo que usa probabilidade. O conteúdo deste curso é formado por diversas técnicas de construção e análise de algoritmos probabilísticos. A ementa do curso é a seguinte:

Introdução

Probabilidade básica: definição, condicional, esperança, variância
Desigualdades: Markov, Chebyschev, Jensen, Chernoff
Método das Diferenças Limitadas
Método Probabilístico

Distribuições Clássicas

Distribuições Uniforme, Binomial, Geométrica, Hipergeométrica e Binomial Negativa
Distribuições Normal, Poisson, Beta e Gama

Construção e Análise de Algoritmos Probabilísticos

Cadeias de Markov
MAXSAT aleatório, MAXSAT Desaleatorizado
Quick Sort com pivô aleatório
Mediana com pivô aleatório
Verificação de Multiplicação de Matrizes
Algoritmo para Corte Mínimo
Problema do Colecionador de figurinhas

Complexidade Computacional

Classes RP, BPP, ZPP
Hierarquia de classes

Material disponivel

Hromkovic, Design and Analysis of Randomized Algorithms, Springer, 2005 (link)
Mitzenmacher, Upfal, Probability and Computing, Cambridge, 2006 (link)
Motwani, Raghavan, Randomized Algorithms, Cambridge, 1995 link)
Sheldon Ross, Probability Models for Computer Science, Academic Press, 2002 link)
Dubhashi, Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge, 2009 link)