Em ciência da computação há vários algoritmos cuja eficiência se baseiam em uma análise
probabilística ou que usam como subrotina um gerador de número aleatórios, os chamados
algoritmos probabilísticos. Temos, por exemplo, o quick sort[2] que tem sua eficiência demonstrada
através de uma análise probabilística e os algoritmos usados em placas Ethernet[1] que
possui escolhas aleatórias em seus passos.
O objetivo desse trabalho será produzir um texto introdutório à análise probabilística de algoritmos e à
algoritmos probabilísticos sobre grafos. Neste trabalho estudaremos alguns capítulos dos livros Introduction to Algorithms[4], Introdução aos Algoritmos Randomizados[5] e seguiremos mais a fundo
o livro Probability and Computing[3]. Após a parte introdutória, que será feita junto
com Gilson Dias e o nosso orientador, a idéia é se aprofundar nos capítulos doProbability and Computing
que tenham tópicos relacionados a grafos, em particular:
Caminhos disjuntos (Cap 6 - The Probabilistic Methos)
Árvores geradoras mínimas (Cap 10 - The Monte Carlo Method)
Coloração de grafos (Cap 11 - (Coupling of Markov Chains)
Por enquanto as atividades têm se resumido à leitura do livro que usa alguns conceitos de estatística que estão merecendo
maior atenção, devido a sua complexidade. Estudamos também (não a fundo) todos os tópicos do livro que são
relacionados a grafos, a fim de dividirmos as tarefas entre o Gilson e eu. Definimos que o Gilson estudaria mais os capítulos 5 (Balls, Bins, and Random Graphs) e 7 (Markov Chains and Random Walks) do livro, enquanto eu vou estudar os capítulo 6 (The Probabilistic Methods), 10 (The Monte Carlo Method) e 11 (Coupling of Markov Chains).
Celina de Figueiredo e Guilherme da Fonseca e Manoel L. V. de Sá, Introdução aos Algoritmos Randomizados,
Publicações Matemáticas - Colóquio Brasileiro de Matemática
