MCZA035-17 Algoritmos Probabilísticos 2026-3 Professor Jair Donadelli --- email jair.donadelli@ufabc.edu.br --- sala 546 Torre 2 Bloco A
A aleatoriedade consolidou-se como um dos paradigmas centrais no projeto de algoritmos eficientes. Em muitos problemas computacionais, algoritmos aleatorizados são mais simples, mais rápidos e utilizam menos memória do que suas contrapartes determinísticas. Em outros, especialmente em aplicações de larga escala, constituem a única abordagem computacionalmente viável. Atualmente, algoritmos aleatorizados estão presentes em inúmeras tecnologias utilizadas diariamente, desde mecanismos de busca na Web, bancos de dados e sistemas distribuídos até criptografia, inteligência artificial, aprendizado de máquina e processamento de grandes volumes de dados. Ao longo do curso, serão estudados tanto os fundamentos teóricos quanto aplicações em problemas práticos, evidenciando como a aleatoriedade pode ser utilizada para obter soluções eficientes e confiáveis.
| Horários: | Sala: |
|---|---|
| Terça 8-10h | |
| Quinta 10-12h | |
| Recomendação: | T-P-E-I: |
| Análise de Algoritmos e Cálculo de Probabilidade | 4-0-0-4 |
Objetivos
Esta disciplina propõe uma mudança conceitual no raciocínio algorítmico, substituindo garantias determinísticas e absolutas por análises probabilísticas de desempenho e erro. O objetivo pedagógico central do curso não é a mera apresentação de um catálogo de algoritmos, mas o desenvolvimento de uma intuição probabilística: um arcabouço analítico que capacite o estudante a projetar e avaliar soluções sob condições de incerteza, aproximação e escala. A capacidade de identificar quando e como substituir a certeza absoluta por ganhos expressivos em tratabilidade computacional constitui uma das competências mais relevantes para a formação do profissional, preparando-o para enfrentar os desafios computacionais mais complexos da atualidade.
Objetivos específicos
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 deveá 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 aleatorizados, 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 técnicas é um resultado central do curso.
Projetar e implementar algoritmos aleatorizados para problemas em diversas áreas da ciência da computação, utilizando técnicas como amostragem, passeios aleatórios e cadeias de Markov.
Reconhecer e justificar situações em que abordagens probabilísticas são superiores a abordagens determinísticas.
Aplicar técnicas probabilísticas a diversas áreas, como estruturas de dados, algoritmos em grafos, otimização combinatória e processamento de grandes volumes de dados.
Programação da disciplina
Ementa
Fundamentos de probabilidade para algoritmos: Espaços de probabilidade, variáveis aleatórias, esperança e variância, independência, método probabilístico e desigualdades de concentração. Introdução a martingales.
Técnicas fundamentais: amostragem aleatória, hashing, projeções aleatórias e redução de dimensionalidade.
Algoritmos e estruturas probabilísticas: Skip Lists, Hashing universal, Locality Sensitive Hashing, Bloom Filters, 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: processamento online, algoritmos de uma passagem, restrições de memória e garantias probabilísticas. Estimação de momentos de frequência
Passeios Aleatórios e Cadeias de Markov: Passeios aleatórios e aplicações m grafos. Cadeias de Markov, distribuição estacionária e mixing time. Algoritmos de Monte Carlo via Cadeias de Markov (MCMC), Metropolis–Hastings e amostragem de Gibbs.
Tópicos Especiais: Classes de complexidade RP, BPP. Derandomização e pseudoaleatoriedade. 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.
Calendario
Reposição de feriados
Programação das Aulas
| Semana | Módulo Temático | Tópicos Principais | Ferramentas Analíticas Chave | Leitura (Mitzenmacher & Upfal) |
|---|---|---|---|---|
| 1 | Fundamentos Probabilísticos | Revisão de probabilidade discreta, variáveis aleatórias, esperança, linearidade da esperança. Desigualdades de Markov e Chebyshev | Valor esperado, independência | Cap. 1–2 |
| 2 | Análise Probabilística de Algoritmos | Quicksort aleatorizado, Skip list. | Linearidade da esperança, variância | Cap. 2–3 |
| 3 | Concentração e Método Probabilístico | Limites de Chernoff-Hoeffding, método probabilístico, algoritmos Las Vegas e Monte Carlo | Limites de concentração | Cap. 4 e 6 |
| 4 | Hashing e Estruturas Probabilísticas | Hashing universal, Bloom Filters | Funções hash universais, análise de falsos positivos | Cap. 5 e 13 |
| 5 | Sketches e Streaming | Flajolet–Martin, Count-Min Sketch, Heavy Hitters, HyperLogLog (visão geral) | Estimadores probabilísticos, análise de erro | Cap. 14 + notas |
| 6 | Algoritmos em Streams | Modelo de streaming, momentos de frequência (AMS para (F_2)), limites inferiores e trade-offs | Independência limitada, concentração | Cap. 14 |
| 7 | Algoritmos Aleatorizados em Grafos | Algoritmo de Karger, introdução a random walks | Probabilidade condicional, recorrência | Cap. 10 |
| 8 | Cadeias de Markov | Passeios aleatórios, hitting time, cover time, distribuição estacionária, PageRank (visão geral) | Cadeias de Markov | Cap. 7 |
| 9 | Algoritmos de Aproximação | MAX-SAT, Set Cover, arredondamento randomizado | Relaxação linear, randomized rounding | Notas |
| 10 | Redução de Dimensionalidade | Projeções aleatórias, Lema de Johnson–Lindenstrauss, aplicações em aprendizado de máquina | Geometria probabilística | Notas |
| 11 | ||||
| 12 |
Bibliografia
DUBHASHI, Devdatt; PANCONESI, Alessandro. Concentration of measure for the analysis of randomized algorithms. Cambridge: Cambridge University Press, 2009.
MITZENMACHER, Michael; UPFAL, Eli. Probability and computing: randomized algorithms and probabilistic analysis. Cambridge: Cambridge University Press, 2005.
MOTWANI, Rajeev; RAGHAVAN, Prabhakar. Randomized algorithms. Cambridge: Cambridge University Press, 1995.
Bibliografia complementar
ARORA, Sanjeev; BARAK, Boaz. Computational complexity: a modern approach. Cambridge: Cambridge University Press, 2009.
HABIB, Michel et al. Probabilistic methods for algorithmic discrete mathematics. Berlin: Springer, 1998.
HÄGGSTRÖM, Olle. Finite Markov chains and algorithmic applications. Cambridge: Cambridge University Press, 2002.
HROMKOVIČ, Juraj. Design and analysis of randomized algorithms: introduction to design paradigms. Berlin: Springer, 2005.
VERSHYNIN, Roman. High-dimensional probability: an introduction with applications in data science. Cambridge: Cambridge University Press, 2018.
Atendimento
A divulgar
Avaliação
x provas.
As avaliações são individuais, presenciais e sem consulta. Avalia-se a capacidade do aluno de analisar algoritmos probabilísticos de forma rigorosa, com ênfase em demonstrações, garantias probabilísticas e raciocínio matemático estruturado. Critérios e Pesos:
| Critério | Peso |
|---|---|
| Correção matemática | 40% |
| Rigor e completude das provas | 30% |
| Uso adequado de ferramentas probabilísticas | 20% |
| Clareza, organização e notação | 10% |
Expectativas formais : – Escrita matemática clara, precisa e bem organizada. – Uso consistente de notação. – Argumentos probabilísticos explícitos e justificados. – Definição clara de eventos, variáveis aleatórias e espaços de probabilidade.
Observações específicas
Resultados conhecidos podem ser utilizados apenas se explicitamente citados.
Demonstrações parciais corretamente estruturadas podem receber crédito proporcional.
Respostas corretas sem justificativa formal recebem pontuação severamente reduzida ou não recebem pontuação.
Conceito final
Conceito A: média final ≥ 90
Conceito B: 75 ≤ média final < 90
Conceito C: 60 ≤ média final < 75
Conceito D: 50 ≤ média final < 60
Conceito F: média final < 50
Instruções para as provas
Podem usar lápis (legível) ou caneta (não vermelha).
Podem responder às questões em qualquer ordem.
Podem usar parte da folha de resposta como rascunho, identificando-a no topo da página com a palavra Rascunho.
Podem entregar a prova a qualquer momento, desde que assinem a lista de presença.
Devem trazer um documento com foto atual.
Devem deixar as mochilas no chão, com o celular dentro (desligado ou silenciado). É proibido o uso de eletrônicos (celular, calculadoras, smartwatches, etc).
Devem entregar a folha de questões juntamente com a folha de respostas.
Devem deixar sobre a carteira somente lápis, caneta, borracha, documento e garrafa d'água. Qualquer outro objeto deve ser guardado.
Idas ao banheiro apenas mediante a entrega definitiva da prova.
Todo aluno poderá, eventualmente e a critério do professor, ser arguido oralmente sobre as soluções apresentadas na prova e essa arguição será parte da avaliação.
O não cumprimento das instruções implica nota zero. Na ocorrência de fraude, o aluno será reprovado.
Recuperação
Tem direito ao exame recuperação, o qual engloba todo o conteúdo da disciplina, aqueles que foram aprovado com D ou reprovado com F e obtiveram frequência mínima. O resultado do exame é um conceito que compõe com o conceito final M obtido na avaliação regular da disciplina como segue:
O aluno deve manifestar interesse em fazer a recuperação de acordo com as instruções que serão enviadas pelo siga em momento apropriado durante a disciplina.
Substitutiva
Para os casos previstos em resolução mediante comprovação.