Complexidade de Algoritmos II - MAB705

Ementa: 

 

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. 

Bibliografia: 
  • R. Motwani e P. Raghavan. Randomized Algorithms. Cambridge University Press, Cambridge, 1995.