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 UniversityPress, Cambridge, 1995.