"Steinhaus, with his predilection for metaphors, used to quote a Polish proverb, `Forturny kolem sie tocza' [Luck runs in circles], to explain why Pi, so intimately connected with circles, keeps cropping up in probability theory and statistics, the two disciplines which deal with randomness and luck."

Mark Kac, Enigmas of Chance


Tópicos Especiais I

Métodos Probabilísticos em Combinatória e Computação

Para uma idéia sobre o assunto:
  • A Taste of Randomized Computations, O. Goldreich.
  • Randomness and Pseudo-Randomness in Discrete Mathematics, N. Alon.

  • Ementa -- Bibliografia -- Provas -- Listas -- Aulas -- Frequência -- Notas

    Conteúdo:

    Objetivos:

    Apresentar ao aluno os fundamentos das técnicas probabilísticas usadas em combinatória, algoritmos probabilísticos e teoria da computação. Esse curso é baseado em métodos e não em conceitos.

    Carga horária: 60
    Créditos: 4
    Responsável: Jair.

    Bibliografia:

    1. The Probabilistic Method, N. Alon and J.H. Spencer.
    2. Random Graphs, T. Luczak, S. Janson, A. Rucinski.
    3. Ten Lectures on the Probabilistic Method, J. Spencer.
    4. Lecture notes on Probabilistic Methods in Computer Science, S. Naor
    5. On randomization in sequential and distributed algorithms, R. Gupta, S. Smolka, and S. Bhaskar.
    6. Randomized Methods in Computation, O. Goldreich
    7. Some elements of probability theory, B. Reed
    8. Bibliografia Complementar:

    9. Randomized Algorithms, R. Motwani, P. Raghavan.
    10. Concrete Mathematics, R. Graham, D. Knuth e O. Pataschink. (Cap. 8)
    11. Introduction to Algorithms, T. Cormen, C. Leiserson, R. Rivest. (Cap. 6)
    12. An Introduction to Probability Theory and Its Application, W. Feller.
    13. Randomized algorithms and pseudorandom numbers H. Karloff and P. Raghavan.
    14. Graph Theory, R. Diestel. (Cap. 11)
    15. Probabilistic proofs of existence of rare events, N. Alon.
    16. Nine lectures on the probabilistic method, J. Spencer.
    17. Derandomization in computational geometry, J. Matousek.
    18. Pairwise Independence and Derandomization, M. Luby and A. Wigderson.
    19. Probabilistic Algorithms and Pseudorandom Generators, M. Tompa
    20. Optimizing Your Wife
    21. Coloring random graphs - an algorithmic perspective, M. Krivelevich.

    Sistema de avaliação:

    Listas, provas e seminários (veja aqui a lista de tópicos)

    Calendário de provas:

    As provas serão para resolver em casa.

    Não haverá aulas em:

    Listas de exercícios:


    Tópicos das aulas:
    Aula 01  - Espaços de probabilidade, eventos, probabilidade condicional.

    Aula 02 - Números de Ramsey (grafos aleatorios; Teor Erdos; aspectos algoritmicos).

    Aula 03 - Vars. aleatórias e valor esperado. Independencia de eventos.

    Aula 04 - MIN-CUT.

    Aula 05 - 7/8-aproximação para MAX3SAT.

    Aula 06 - Desiguladades de Markov e Chebyshev (Segundo Momento).

    Aula 07 - Função limiar para ocorrencia de subgrafo em G_p.

    Aula 08 - Método da Alteração (Refinamentos): Números de Ramsey (diagonal), uma forma + fraca do Teo. de Turán sobre a cardinalidade max de um conjunto independente.

    Aula 09 - Grafos com cintura e número cromático arbitrariamente grandes.

    Aula 10 - Cota inferior para o número cromático de quase todo grafo.

    Aula 11 - Cota superior para o número cromático de quase todo grafo: análise de caso médio do algoritmo guloso.

    Aula 12 - Distribuições Bernoulli e Binomial. Desigualdades de Chernoff.

    Aula 13 - Uma aplicação de Chernoff: roteamento no hipercubo.

    Aula 14 - Continuação: roteamento no hipercubo. Distribuição Geométrica; Gerar orientações acíclicas.

    Aula 15 - Quicksort probabilístico.

    Aula 16 - o Crivo Local de Lovász: LLL, LLL versão simétrica. Apl. em nos. de ramsey

    Aula 17 - LLL - demonstração.

    Aula 18 - circuitos em grafos dirigidos.

    Aula 19 - Passeios aleatórios; 2-sat.

    Aula 20 - Cadeias de Markov.

    Aula 21 - Convergencia em cadeias de Markov irredutivieis aperiodicas.

    Aula 22 - Passeios aleatórios em grafos. Hitting, commute, cover times - exemplos

    Aula 23 - Passeios aleatórios em grafos x Redes eletricas; ustcon

    Aula 24 -

    Aula 25 -

    Aula 26 -

    Aula 27 - Seminario 1-Murilo: Classes de complexidade probab.

    Aula 28 - Seminario 2-William: Derandomização: método das esperanças condicionais.

    Aula 29 - Seminario 3-Oliver: Grafos pseudo-aleatorios.

    Aula 30 - Seminario 4-Daniel:

    April 2003 May 2003 June 2003 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 5 1 2 3 1 2 3 4 5 6 7 6 7 8 9 10 11 12 4 5 6 7 8 9 10 8 9 10 11 12 13 14 13 14 15 16 17 18 19 11 12 13 14 15 16 17 15 16 17 18 19 20 21 20 21 22 23 24 25 26 18 19 20 21 22 23 24 22 23 24 25 26 27 28 27 28 29 30 25 26 27 28 29 30 31 29 30 July 2003 August 2003 September 2003 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 5 1 2 1 2 3 4 5 6 6 7 8 9 10 11 12 3 4 5 6 7 8 9 7 8 9 10 11 12 13 13 14 15 16 17 18 19 10 11 12 13 14 15 16 14 15 16 17 18 19 20 20 21 22 23 24 25 26 17 18 19 20 21 22 23 21 22 23 24 25 26 27 27 28 29 30 31 24 25 26 27 28 29 30 28 29 30 31


    Tópicos para seminários:

    Sugestões podem ser aceitas.
    "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. ", John von Neumann