UFC - Departamento de Computação

Algoritmos Probabilísticos (CK0191 - CKP8511)

Semestre: 2023.1
Horário: Terças e Quintas 16h-18h
Local: Bloco 915, Sala 1074
Atendimento: Pelo SIGAA ou pelo email: rudini @ dc . ufc . br

Apresentação

Listas de Exercícios

Ementa:

Ementa Oficial (MDCC-UFC) (CC-UFC)

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

Algoritmo Las Vegas versus Algoritmo Monte Carlo
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

Algoritmos usando 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

Bibliografia

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)