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.

E-mails: Toda comunicação ‘aluno → professor’ por email deve ser com o endereço oficial.

Os comunicados gerais ‘professor → aluno’ serão pelo sigaa.

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 aleatorizados, 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 deverá 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 probabilística baseadas em desigualdades de concentração; 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 aleatorização, amostragem 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, testes probabilísticos e problemas computacionais de grande escala.

Programação da disciplina

Ementa

Revisão de probabilidade discreta. Exemplos de algoritmos aleatorizados: Algoritmo para Identidade polinomial; Sigilo perfeito; MAX 3-SAT. Leis de desvios e aplicações em algoritmos e estruturas de dados: hashing universal; treaps. Modelos de computação e classes probabilísticas de complexidade. Aplicações de Cadeias de Markov. Passeios aleatórios em grafos. Algoritmos distribuídos probabilísticos.

Calendário

Reposição de feriados

Programação das Aulas

NOTAS DE AULA (contruída no decorrer da disciplina)

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

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

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

6. BLUM, Avrim; HOPCROFT, John; KANNAN, Ravindran. Foundations of data science. Cambridge: Cambridge University Press, 2020. (online)

7. VERSHYNIN, Roman. High-dimensional probability: an introduction with applications in data science. Cambridge: Cambridge University Press, 2018. (online, soluções)

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

Atendimento

Quartas das 10h às 12h ou em horário previamente combinado, pessoalmente ou por email.

Avaliação

3 provas. 1/10, 1/11, 1/12 (tentativa) - datas e critérios na 3ª semana.

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:

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 não recebem pontuação.

Conceito final

• Conceito A: média final ≥ 90

• Conceito B: 75 ≤ média final < 90

• Conceito C: 52 ≤ média final < 75

• Conceito D: 50 < média final < 52

• Conceito F: média final ≤ 50

Instruções para as provas

1. Podem utilizar lápis, desde que a escrita seja legível, ou caneta, exceto na cor vermelha.

2. Podem responder às questões em qualquer ordem.

3. Podem usar parte da folha de resposta como rascunho, identificando-a no topo da página com a palavra Rascunho.

4. Podem entregar a prova a qualquer momento, desde que assinem a lista de presença.

5. Devem trazer um documento com foto atual.

6. Devem deixar as mochilas no chão, com o celular dentro (desligado ou silenciado). É proibido o uso de eletrônicos (celular, calculadoras, smartwatches, etc), bem como bonés e chapéus.

7. Devem entregar a folha de questões juntamente com a folha de respostas.

8. Devem deixar sobre a carteira somente lápis, caneta, borracha, documento e garrafa d'água. Qualquer outro objeto deve ser guardado.

9. Ida ao banheiro apenas mediante a entrega definitiva da prova.

10. 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 anulação da prova.

​ Na constatação de fraude, o aluno será reprovado.

Recuperação

Tem direito ao exame recuperação, que engloba todo o conteúdo da disciplina, aqueles que foram aprovados com D ou reprovados 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:

A prova será em 9/12. O aluno interessado em realizar a recuperação deverá se manifestar de 04/12 a 07/12 por email ou através de formulário de acordo com as instruções que serão enviadas em um momento apropriado durante a disciplina.

Substitutiva

Nos casos previstos em resolução, mediante a devida comprovação. O aluno que perder prova e tiver interesse em fazer a substitutiva deve entrar em contato com o professor.

Links

Material de ofertas anteriores

• Listas

• Provas

• notas

Notícias relacionadas

• Como a aleatoriedade pode ajudar algoritmos a solucionarem problemas impossíveis

• How Randomness Improves Algorithms (original do item anterior)

• Avi Wigderson ganha prémio Turing, o ‘Nobel da computação’ pelos estudos sobre a aplicação da aleatoridade na criação de algoritmos de computação

• Os números aleatórios que guiam nossas vidas e a busca para encontrá-los

Material online

• Markov Chains and Mixing Times, David A. Levin, Yuval Peres With contributions by Elizabeth L. Wilmer

• Pseudorandomness, Salil Vadhan

• Introduction to Random Graphs, Frieze and Karonski

• Random walks and electric networks, Peter G. Doyle e J. Laurie Snell

• Introduction to Probability for Computing, Harchol-Balter.

• Reversible Markov Chains and Random Walks on Graphs, David Aldous and James Allen Fill

• The Discrepancy Method Randomness and Complexity, Bernard Chazelle

• Useful Inequalities cheat sheet

• Notes on Randomized Algorithms, James Aspnes

• Algorithms for Big Data, Chandra Chekuri

• Hashing, Load Balancing and Multiple Choice, Udi Wieder

A.P. em outras instituições

• CS 574 Randomized Algorithms, Sariel Har-Peled, University of Illinois Urbana-Champaign

• 6.5220/6.856J/18.416J Randomized Algorithms, David Karger, MIT

• CS588 Randomized Algorithms, Kent Quanrud, Purdue University

• CPSC 436R: Introduction to Randomized Algorithms, CPSC 536N: Randomized Algorithms, Nick Harvey, The University of British Columbia

• CS 761: Randomized Algorithms, Lap Chi Lau, University of Waterloo

• CS265/CME309 Randomized Algorithms and Probabilistic Analysis, Mary Wootters, Stanford University

• CSE 525: Randomized Algorithms, Shayan Oveis Gharan, University of Washington

• Randomized Algorithms, Robert Krauthgamer and Moni Naor, Weizmann Institute of Science

• E0 234: Introduction to Randomized Algorithms, Arindam Khan and Anand Louis, Indian Institute of Science (IISc)

Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601. In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering. [ Abelson e Sussman em SICP (o “livro dos magos”)]