Área de Concentração: 45134
Concentration area: 45134
Criação: 14/06/2019
Creation: 14/06/2019
Ativação: 14/06/2019
Activation: 14/06/2019
Nr. de Créditos: 8
Credits: 8
Carga Horária:
Workload:
Teórica (por semana) |
Theory (weekly) |
Prática (por semana) |
Practice (weekly) |
Estudos (por semana) |
Study (weekly) |
Duração | Duration | Total | Total |
---|---|---|---|---|---|---|---|---|---|
4 | 0 | 6 | 12 semanas | 12 weeks | 120 horas | 120 hours |
Docente Responsável:
Professor:
Yoshiharu Kohayakawa
Objetivos:
Estudar tópicos matemáticos relevantes para a análise de certos algoritmos modernos da ciência da computação, incluindo tópicos de probabilidade, da álgebra linear, e da geometria de espaços de dimensão alta.
Justificativa:
Trata-se de uma disciplina de natureza teórica, apresentando a matemática necessária para o estudo rigoroso de certas algoritmos modernos.
Conteúdo:
Tópicos de probabilidade, como concentração de medida e elementos de grafos aleatórios; tópicos da álgebra linear, como decomposição em valores singulares; tópicos da geometria de espaços de dimensão alta, como o lema de Johnson e Lindenstrauss. Aplicações nas seguintes linhas de pesquisa serão consideradas: estruturas de dados e algoritmos aleatorizados, redução de dimensão, algoritmos para streaming data, complexidade de amostragem e teoria de aprendizado, decomposição em aglomerados, aproximações de posto baixo, entre outras.
Forma de Avaliação:
Listas de exercícios e um projeto com componente teórico significativo.
Bibliografia:
1. M. Mitzenmacher e E. Upfal, Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis. Second edition. Cambridge University Press, Cambridge, 2017, xx + 467 pp. ISBN: 978-1-107-15488-9 2. A. Blum, J. Hopcroft, e R. Kannan, Foundations of data science, 2018, 479 pp. Disponível em https://www.cs.cornell.edu/jeh/book.pdf 3. Artigos de pesquisa e notas de aulas.
Tipo de oferecimento da disciplina:
Presencial
Class type:
Presencial