Pre-requisito: MC448 / MC458 

Ementa:

Conceitos básicos de probabilidade. Técnicas em teoria dos jogos. Desvios e momentos. Desigualdades de cauda. Método probabilístico. Cadeias de markov e passeios aleatórios. Algoritmos de aproximação probabilísticos.  Técnicas algébricas. Aplicações.

Programa:

 1. Eventos e probabilidade.

     Sugestão de exemplos: Verificação de polinômios, multiplicação de matrizes e

     corte mínimo.

 2. Variáveis aleatórias discretas e esperança

    Variáveis de Bernoulli e variáveis binomiais, esperança condicional, distribuição 

    geométrica.

    Sugestão de exemplos: Colecionador de cupons e análise do Quick Sort.

 3. Momentos e desvios

    Desigualdade de Markov, variância e momentos de uma variável aleatória,

   desigualdade de Chebyshev.

    Sugestão de exemplos: Colecionador de cupons, problema da mediana.

 4. Limitantes de Chernoff

    Funções geradoras de momento, derivação e aplicação de limitantes de

    Chernoff.

    Sugestão de exemplos: Balanceamento de conjuntos, roteamento em redes

    esparsas.

 5. Bolas, cestos e grafos aleatórios

    Distribuição de Poisson, aproximação de Poisson, Grafos aleatórios.

    Sugestão de exemplos: paradoxo do aniversário, ordenação pelo Bucket Sort,

    Hasing, circuitos hamiltonianos em grafos aleatórios.

 6. Método probabilístico

    Argumentos de contagem, desaleatorização pelo método de esperanças

    condicionais, métodos por sorteio e modificação, método do segundo momento,

    desigualdades da esperança condicional, lema local de Lovasz.

    Sugestão de exemplos: problemas do corte máximo, satisfatibilidade máxima,

    conjuntos independentes, grafos com cintura grande.

 7. Cadeias de Markov e passeios aleatórios

    Definição e representações, classificação de estados, distribuições

    estacionárias, caminhos  aleatórios em grafos não orientados, paradoxo de

    Parrondo.

    Sugestão de exemplos: problemas da satisfatibilidade, s-t conectividade.

 8. Aplicações em teoria dos jogos, algoritmos de aproximação, etc.

 9. Outros tópicos.

 

Bibliografia:

 

1. M. Mitzenmacher e E. Upfal.  Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press (2005).

2. R. Motwani e P. Raghavan. Randomized Algorithms, Cambridge (1995).
3. J.  Michael Steele. Probability Theory and Combinatorial Optimization, SIAM (1997).
4. V. Vazirani. Approximation Algorithms, Springer-Verlag (2001).