Informações da Disciplina

 Preparar para impressão 

Júpiter - Sistema de Gestão Acadêmica da Pró-Reitoria de Graduação


Instituto de Matemática e Estatística
 
Ciência da Computação
 
Disciplina: MAC0776 - Métodos Probabilísticos em Combinatória e em Teoria da Computação II
Probabilistic Methods in Combinatorics and Theory of Computing II

Créditos Aula: 4
Créditos Trabalho: 0
Carga Horária Total: 60 h
Tipo: Semestral
Ativação: 01/01/2019 Desativação:

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
 
 
 
Docente(s) Responsável(eis)
88134 - Yoshiharu Kohayakawa
 
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.
 
 
 
Avaliação
     
Método
Provas e listas de exercícios.
Critério
Média ponderada das notas de provas e listas de exercícios.
Norma de Recuperação
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.
 
Bibliografia
     
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. 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. 

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. 

4. B. Chazelle, The discrepancy method; Randomness and complexity. Cambridge University Press,  Cambridge, 2000. xviii+463pp. ISBN: 0-521-77093-9. 

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. 

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

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

Clique para consultar os requisitos para MAC0776

Clique para consultar o oferecimento para MAC0776

Créditos | Fale conosco
© 1999 - 2024 - Superintendência de Tecnologia da Informação/USP