Informações da Disciplina

 Preparar para impressão 
Júpiter - Sistema de Graduação

Instituto de Matemática e Estatística
 
Ciência da Computação
 
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

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

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

Clique para consultar os requisitos para MAC0775

Clique para consultar o oferecimento para MAC0775

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