Introdução aos Algoritmos Randomizados

Curso introdutório no 26^o Colóquio Brasileiro de Matemática
30/7 a 3/8, 14:00–15:00 (monitoria 13:00–13:30), sala 232

Professores: Celina Miraglia Herrera de Figueiredo (COPPE/UFRJ)
Guilherme Dias da Fonseca (CS/UMD)
Manoel José Machado Soares Lemos (DMAT/UFPE)
Vinícius Gusmão Pereira de Sá (COPPE/UFRJ)
Monitor: Raphael Carlos Santos Machado (COPPE/UFRJ)
Materiais: prefácio · texto completo · soluções dos exercícios · proximos.py
slides: apresentação · aulas 1 e 2 · aula 3 · aulas 4 e 5

O curso tem como objetivo apresentar técnicas fundamentais para o desenvolvimento de algoritmos randomizados (também chamados de probabilísticos, por alguns autores). O curso tem caráter introdutório: não são assumidos conhecimentos avançados de probabilidade ou de algoritmos. Os conceitos teóricos que se fizerem necessários serão apresentados juntamente aos problemas e algoritmos que os demandem. Ao completar este curso introdutório, o aluno terá travado contato com o instrumental básico desta área e com um elenco representativo de algoritmos randomizados — e, em alguns casos, também determinísticos — para diversos problemas combinatórios.

Os principais tópicos do curso são: Introdução aos algoritmos randomizados: modelos de computação randomizada; classes de complexidade; algoritmos de Monte Carlo e Las Vegas; Paradigmas combinatórios: o modelo de bolas-e-latas; o colecionador de cupons; Análise probabilística de algoritmos determinísticos: Quick Sort; Bucket Sort; Algoritmos randomizados em Teoria dos Números: o algoritmo de Rabin para primalidade; Algoritmos randomizados em Geometria Computacional: programação linear, par de pontos mais próximos; O método probabilístico: provas de existência; de-randomização.