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

Por | Em

OBJETIVOS:  Dar continuidade à apresentação de técnicas probabilísticas em combinatória e em teoria da computação, através do estudo aprofundado de tópicos contemporâneos de pesquisa em que há elementos probabilísticos envolvidos, explícita ou implicitamente

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

PROGRAMA:  Tópicos em grafos aleatórios e pseudo-aleatoriedade. O lema de regularidade de Szemerédi e suas variantes; aplicações em combinatória e em complexidade computacional (testabilidade de propriedades). Construções explícitas e desaleatorização em combinatória e em teoria da complexidade. Os seguintes tópicos serão vistos com a profundidade apropriada para cada turma, dependendo dos interesses específicos. Entropia. Discrepância. Jogos posicionais. Técnicas de análise harmônica. Noções de classes de complexidade probabilísticas; relações com as classes de complexidade clássicas e sistemas interativos de provas.

RESPONSÁVEIS:  Yoshiharu Kohayakawa

PRÉ-REQUISITOS:  MAC0775

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
  • J. Beck, Inevitable randomness in discrete mathematics, University Lecture Series, 49. American Mathematical Society, Providence, RI, 2009. xii+250pp. ISBN: 978-0-8218-4756-5.
  • 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.
  • B. Chazelle, The discrepancy method; Randomness and complexity, Cambridge University Press, Cambridge, 2000. xviii+463pp. ISBN: 0-521-77093-9.
  • 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.
  • J. Komlós, e M. Simonovits, Szemerédi's regularity lemma and its applications in graph theory, Combinatorics, Paul Erdos is eighty, Vol. 2 (Keszthely, 1993), 295--352, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996.
  • J. Komlós, A. Shokoufandeh, M. Simonovits, e E. Szemerédi, The regularity lemma and its applications in graph theory, Theoretical aspects of computer science (Tehran, 2000), 84--112, Lecture Notes in Comput. Sci., 2292, Springer, Berlin, 2002.

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

 

[Veja dados da disciplina no JúpiterWeb]