"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:

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