MCZA035-17 Algoritmos Probabilísticos

T P E I 4 0 0 4 Créditos 4 Carga Horária 48

Pré-requisitos: Algoritmos e Estruturas de Dados II, Cálculo de Probabilidade.

A aleatoriedade se consolidou como uma ferramenta central no projeto de algoritmos eficientes. Ao permitir decisões aleatórias esses algoritmos podem ser mais simples, rápidos e econômicos em memória do que alternativas determinísticas, sendo, em muitos problemas, como os de grande escala, a única abordagem computacionalmente viável. Além dos aspectos práticos, a disciplina promove uma mudança conceitual no raciocínio algorítmico, substituindo garantias determinísticas absolutas pela análise probabilística de desempenho e erro. Assim, a disciplina propõe desenvolver a intuição probabilística e a capacidade de projetar soluções sob incerteza, competência fundamental para enfrentar os desafios computacionais contemporâneos.

OBJETIVOS

Esta disciplina tem como objetivo apresentar os fundamentos dos algoritmos probabilísticos, capacitando o aluno a compreender, analisar e projetar algoritmos que utilizam aleatoriedade como ferramenta para obter soluções eficientes para problemas computacionais. Ao final do curso, o aluno será capaz de:

• Compreender o comportamento de processos e algoritmos aleatórios, o poder e as limitações da aleatoriedade no projeto de algoritmos.

• Analisar algoritmos probabilisticamente, dominando técnicas de análise como variáveis aleatórias, esperança e suas principais propriedades e leis de concentração de medida. A maestria dessas ferramentas é um resultado central do curso.

• Projetar e implementar algoritmos aleatorizados para problemas em diversas áreas da ciência da computação usando técnicas avançadas como amostragem, passeios aleatórios e cadeias de Markov.

• Reconhecer problemas onde abordagens probabilísticas são superiores a abordagens determinísticas.

• Aplicar técnicas probabilísticas a diversas áreas, como estruturas de dados, algoritmos de grafos, otimização combinatória e processamento de grandes volumes de dados (big data).

EMENTA

Fundamentos e técnicas básicas de análise: Espaços de probabilidade, variáveis aleatórias discretas e contínuas, esperança e variância, independência e correlação. Linearidade da esperança. Método probabilístico. Desigualdades de concentração: Markov, Chebyshev, Chernoff e Hoeffding. Introdução a martingales e concentração para processos dependentes.

Algoritmos e estruturas de dados: Técnicas de amostragem aleatória. Amostragem por reservatório. Projeções aleatórias e redução de dimensionalidade. Lema de Johnson–Lindenstrauss e aplicações. Sketches probabilísticos para sumarização de dados: Flajolet–Martin para contagem de elementos distintos, Count-Min Sketch para estimação de frequências e identificação de heavy hitters.

Algoritmos em modelo de stream de dados: Modelo de computação em fluxo de dados: processamento online, algoritmos de uma passagem, restrições de memória e garantias probabilísticas. Estimação de momentos de frequência $F_k$$F_k$ em streams, com ênfase no algoritmo de Alon–Matias–Szegedy para $F_2$$F_2$. Limites inferiores e trade-offs entre memória, erro e probabilidade de falha.

Aproximação: Algoritmos de aproximação para problemas NP-difíceis: MAX-3-SAT, MAX-SAT, Set Cover e problemas de scheduling. Análise de razões de aproximação esperadas. Relaxação linear e técnicas de arredondamento randomizado.

Passeios Aleatórios e Cadeias de Markov: Passeios aleatórios e aplicações em algoritmos em grafos. Algoritmos aleatorizados baseados em random walks (e.g., 2-SAT). Cadeias de Markov: estados, transições, irreducibilidade, recorrência e distribuição estacionária. Introdução a algoritmos de Monte Carlo via Cadeias de Markov (MCMC), incluindo Metropolis–Hastings e amostragem de Gibbs.

Tópicos Especiais: Derandomização e pseudorandomness (noções). Algoritmos online. Algoritmos probabilísticos em aprendizado de máquina. Aplicações em grafos, otimização e ciência de dados. Outros tópicos conforme o interesse da turma.

BIBLIOGRAFIA

1. DUBHASHI, Devdatt; PANCONESI, Alessandro. Concentration of measure for the analysis of randomized algorithms. Cambridge: Cambridge University Press, 2009.

2. MITZENMACHER, Michael; UPFAL, Eli. Probability and computing: randomized algorithms and probabilistic analysis. Cambridge: Cambridge University Press, 2005.

3. MOTWANI, Rajeev; RAGHAVAN, Prabhakar. Randomized algorithms. Cambridge: Cambridge University Press, 1995.

BIBLIOGRAFIA COMPLEMENTAR

1. ARORA, Sanjeev; BARAK, Boaz. Computational complexity: a modern approach. Cambridge: Cambridge University Press, 2009.

2. HABIB, Michel et al. Probabilistic methods for algorithmic discrete mathematics. Berlin: Springer, 1998.

3. HÄGGSTRÖM, Olle. Finite Markov chains and algorithmic applications. Cambridge: Cambridge University Press, 2002.

4. HROMKOVIČ, Juraj. Design and analysis of randomized algorithms: introduction to design paradigms. Berlin: Springer, 2005.

5. VERSHYNIN, Roman. High-dimensional probability: an introduction with applications in data science. Cambridge: Cambridge University Press, 2018.