Disciplina: MAC0775 - Métodos Probabilísticos em Combinatória e em Teoria da Computação I (
Probabilistic Methods in Combinatorics and Theory of Computing I
A disciplina tem como objetivo introduzir o aluno às técnicas probabilísticas fundamentais usadas em combinatória e em teoria da computação. Espera-se que o aluno, ao completar esta disciplina, terá visto os instrumentos básicos desta área, e que ele terá também desenvolvido sua sensibilidade para problemas combinatórios tanto determinísticos como probabilísticos.
88134 - Yoshiharu Kohayakawa
Técnicas probabilísticas fundamentais e aplicações em combinatória e em teoria da computação.
Fundamentos da teoria elementar de probabilidades. Aplicações clássicas do primeiro e segundo momentos; linearidade da esperança e o método da alteração. O lema local. Breve discussão sobre desigualdades de correlação. Desigualdades para grandes desvios e o fenômeno da concentração da medida: desigualdades elementares, o método das diferenças limitadas, as desigualdades de Janson; discussão sobre as desigualdades de Talagrand e Kim e Vu. Elementos de grafos aleatórios e pseudo-aleatoriedade. Aplicações em várias áreas, incluindo, entre outros, teoria dos grafos e hipergrafos, geometria, teoria dos números, teoria da complexidade e algoritmos.
Média ponderada das notas de provas e listas de exercícios.
Não há. A avaliação será baseada em um volume substancial de exercícios ao longo do semestre, que terão o papel de levar ao amadurecimento do aluno na área da disciplina. Não é possível reproduzir algo parecido no processo de recuperação, que tem de ter lugar em um período muito curto.
1. N. Alon e J.H. Spencer, The probabilistic method; 4a. edição. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley. 2016. ISBN: 978-1-119-06195-3 2. B. Bollobás, Random graphs; 2a. edição. Cambridge Studies in Advanced Mathematics, 73. Cambridge University Press, Cambridge, 2001. xviii+498pp. ISBN: 0-521-80920-7; 0-521-79722-5. 3. S. Janson, T. Luczak e A. Rucinski, Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000. xii+333pp. ISBN: 0-471-17541-2.