MAC5775 Métodos Probabilísticos em Combinatória e em Teoria da Computação I

[Edição do 1o. Semestre de 2018]

(Página eternamente minimal e em mutação)

Sinopse das aulas

[2018-03-05 Mon] Aula introdutória. Assuntos administrativos. Provas por contagem. Funções booleanas, propriedade B
[2018-03-07 Wed] Espaços de probabilidade finitos. Exemplos. O problema do empregador
[2018-03-12 Mon] Variáveis aleatórias e esperança. Exemplos
[2018-03-14 Wed] Um problema geométrico. Número médio de comparações do quicksort
[2018-03-19 Mon] Mais aplicações do primeiro momento. O teorema de Szemerédi e Trotter via número de cruzamentos
[2018-03-21 Wed] Consequências do teorema de Szemerédi e Trotter. Quicksort (cont.)
[2018-03-26 Mon] Semana Santa
[2018-03-28 Wed] Semana Santa

[2018-04-02 Mon] Método do segundo momento; teorema de Hardy e Ramanujan
[2018-04-04 Wed] Subgrafos pequenos em \(G(n,p)\)
[2018-04-09 Mon] A conjectura de Erdős e Hanani e o teorema de Rödl. O teorema de Frankl, Rödl e Pippenger
[2018-04-11 Wed] Prova do teorema de Frankl, Rödl e Pippenger
[2018-04-16 Mon] Folga (professor fora de São Paulo)
[2018-04-18 Wed] Folga (professor fora de São Paulo)
[2018-04-23 Mon] Prova do teorema de Frankl, Rödl e Pippenger: prova do Nibbling Lemma
[2018-04-25 Wed] Probabilidades exponencialmente pequenas; conjuntos agudos exponenciais
[2018-04-30 Mon] Recesso escolar

[2018-05-02 Wed] Semana de break
[2018-05-07 Mon] Probabilidades exponenciais: algumas provas. A desigualdade FKG–Harris. Desigualdades de Janson
[2018-05-09 Wed] Desigualdade de Janson (cont.). A desigualdade de McDiarmid
[2018-05-14 Mon] Número cromático de \(G(n,p)\): teorema de Bollobás
[2018-05-16 Wed] Teorema de Bollobás via a desigualdade de McDiarmid. Concentração do número de clique e do número cromático
[2018-05-21 Mon] Concentração do número cromático (cont.). Martingais
[2018-05-23 Wed] Martingais e a desigualdade de McDiarmid
[2018-05-28 Mon] Semana de break
[2018-05-30 Wed] Semana de break

[2018-06-04 Mon] O lema local. Circuitos pares em grafos dirigidos
[2018-06-06 Wed] Circuitos \(\equiv0\pmod k\) em grafos dirigidos. Versão algorítmica do lema local (Moser–Tardos)
[2018-06-11 Mon] Moser–Tardos (cont.)
[2018-06-13 Wed] Complexidade de circuitos e o teorema de Razborov
[2018-06-18 Mon] Teorema de Razborov (cont.). Circuitos de profundidade limitada
[2018-06-20 Wed] Circuitos de profundidade limitada (cont.)
[2018-06-25 Wed] Circuitos de profundidade limitada (cont.)
[2018-06-27 Wed] FIFA World Cup

Página principal de MAC5775, 1o. semestre de 2018