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.
Tópicos de probabilidade, tópicos da álgebra linear e tópicos da geometria de espaços de dimensão alta. Aplicações no estudo de algoritmos modernos.
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.
Bibliografia Básica: 1. M. Mitzenmacher e E. Upfal, Probability and computing: an introduction to randomized algorithms and probabilistic analysis. Cambridge University Press, 2005, xvi + 352 pp.2. A. Blum, J. Hopcroft, e R. Kannan, Foundations of data science, Cambridge University Press, 2020, viii + 432 pp. Disponível em https://ttic.uchicago.edu/~avrim/book.pdfBibliografia Complementar:1. N. Alon e J.H. Spencer, The probabilistic method; 3a. edição. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, 2008, xv + 352 pp.2. B. Bollobás, Random graphs; 2a. edição. Cambridge Studies in Advanced Mathematics, 73. Cambridge University Press, 2001. xviii + 498 pp.3. S. Janson, T. Luczak e A. Rucinski, Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization.Wiley, 2000, xii + 333 pp.4. R. Motwani e P. Raghavan, Randomized algorithms. Cambridge University Press, 1995. xiv + 476 pp.
