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:
Listas de Exercícios
Ementa e Bibliografia:
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)