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

Por | Em

OBJETIVOS:  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.

PROGRAMA RESUMIDO:  Técnicas probabilísticas fundamentais e aplicações em combinatória e em teoria da computação.

PROGRAMA:  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.

RESPONSÁVEIS:  Yoshiharu Kohayakawa

PRÉ-REQUISITOS:  MAC0105 MAC0338 MAE0119 MAT0122 MAT0236

CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS:  4 horas, 4 créditos-aula.

CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM:  Média ponderada das notas de provas e listas de exercícios.

BIBLIOGRAFIA BÁSICA: 

  • 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
  • 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.
  • 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.

OBSERVAÇÃO:  Disciplina optativa nos currículos do BCC.

 

[Veja dados da disciplina no JúpiterWeb]