Algoritmos Probabilísticos 2024 - 3
email jair.donadelli@ufabc.edu.br
Os algoritmos aleatorizados fazem uso de sorteiros para tomar decisões, nasceram como uma ferramenta na teoria computacional dos números e evoluíram rapidamente para um conjunto de ferramentas e técnicas com uma ampla variedade de aplicações como criptografia, simulação de Monte Carlo, otimização, aprendizado de máquina, mineração de dados, processamento de linguagem natural, oferecendo soluções eficientes para problemas onde algoritmos determinísticos seriam muito lentos ou complexos. Nesta disciplina estudamos a aleatoriedade na computação e no projeto de algoritmos. Os tópicos incluem ferramentas probabilísticas, limitantes da esperança, limites de concentração, algoritmos de streaming, algoritmos em grafos, estruturas de dados, hashing e privacidade.
Se está matriculado, atente para seu email institucional, as comunicações são feitas via siga.
Pré-requisitos: Introdução a Probabilidade e Estatística; Algoritmos e Estruturas de Dados II. É esperado noções básicas de lógica, demonstrações, somatórios, representação binária e aritmética modular. Estruturas de dados, ordenações e busca, notação assintótica, árvores e grafos. Análise de algoritmos e notação assintótica. Probabilidade, eventos, esperança, distribuições padrão (binomial, geometrica, normal), independência de eventos.
Atendimento sextas a partir das 21:05 ou em horário combinado previamente.
Turma NA1MCZA035-17SA Horário: terça 21:00 e sexta 19:00. Local: S-214-0 (3ª) e A-113-0 (6ª)
TPI: 4-0-4
Algoritmos Probabilísticos 2024 - 3EmentaObjetivosReferênciasNotas de aulaBásicasOutras notas de aulaAvaliaçãoProvasCódigo de Ética da Universidade Federal do ABC Programação (tentativa)Links
Ementa
Ferramentas e Técnicas: Teoria básica da probabilidade; Markov, Chebyshev e desigualdades de momento; desigualdades de cauda e limites de Chernoff; esperança condicional e martingais. Fundamentos computacionais: classes de complexidade probabilísticas; técnicas de teoria dos jogos; problemas de aproximação e contagem; amplificação de probabilidade e desaleatorização. Aplicações: classificação e busca; estruturas de dados; otimização combinatória e algoritmos de grafos; algoritmos para conjuntos de dados massivos; algoritmos em teoria dos números.
Objetivos
Desenvolver habilidades para usar, analisar e aplicar algoritmos probabilísticos em diversos contextos.
Aprender as técnicas para analisar a performance e a corretude dos algoritmos probabilísticos, reconhecer e usar as leis de concentração e desvio e análise de eventos raros, que são ferramentas essenciais na avaliação desses algoritmos.
Explorar como algoritmos probabilísticos são usados em problemas práticos.
Compreender os modelos probabilísticos de computação, seu poder e suas limitações, as classes de complexidade relacionadas.
Referências
Notas de aula
Básicas
Probablility and Computing, M. MITZENMACHER, E. UPFAL. [518.1 MITZpr]
Randomized Algorithms, R. MOTWANI e P. RAGHAVAN. [004.015192 MOTWra]
Complementares
Computational Complexity: A Modern Approach, S. ARORA, B BARAK. [511.352 AROc]
Design and Analysis of Randomized Algorithms, J. HROMKOVIC. [Livro Digital]
Concentration of measure for the analysis of randomized algorithms DUBHASHI e DEVSATT. [518.1 DUBHco]
The Probabilistic Method. ALON e SPENCER. [511.6 ALONpr]
Outras notas de aula
Notes on Randomized Algorithms, James Aspnes
Class notes for Randomized Algorithms, Sariel Har-Peled
High-Dimensional Probability An Introduction with Applications in Data Science, Roman Vershynin
Lecture Notes: Randomized Algorithm Design, Palash Dey
Lecture notes for CPSC 536N "Randomized Algorithms", Nick Harvey
R. Bianconi, Como ler e estudar matemática?
Fernando Q. Gouvêa e Shai Simonson, How to Read Mathematics (uma tradução “rápida e grosseira”, segundo o tradutor, aqui).
Avaliação
2 Provas, 12/09 e 13/12. Os critérios de avaliação incluem
Apresentação clara, discursiva e objetiva.
Construção correta e em ordem dos argumentos.
Atendimento às normas de correção ortográfica e gramatical.
Observância às orientações específicas da atividade e aos prazos de entrega.
Conceito final das provas: nas avaliações serão atribuídos concentos cujo resultado ao final será de acordo com a seguinte tabela
| P1 | A | B | C | D | F | A | B | C | D | F | A | B | C | D | F | A | B | C | D | F | A | B | C | D | F | |||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| P2 | A | B | C | D | F | |||||||||||||||||||||||||
| Final | A | A | B | C | D | A | B | B | C | D | B | C | C | C | F | C | D | D | F | F | D | D | F | F | F |
Frequência mínima de 75%.
Substitutiva. O aluno que perder uma prova deve apresentar justificativa e manifestar o interesse em realizar uma prova substitutiva.
Recuperação. Engloba todo o conteúdo da disciplina. Só estarão aptos os alunos frequência mínima. O aluno deve manifestar o interesse em realizar o exame após a divulgação da media das provas.
Provas
P1 7ª semana
P2 11ª semana (aula 2)
Sub 12ª semana (aula 1)
Recuperação 12ª semana (aula 2)
Código de Ética da Universidade Federal do ABC
Estabelece em seu Artigo 25 que:
Quanto aos trabalhos acadêmicos, é eticamente inaceitável que os discentes: I fraudem avaliações; II fabriquem ou falsifiquem dados; III plagiem ou não creditem devidamente autoria; IV aceitem autoria de material acadêmico sem participação na produção; V vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.
Qualquer violação às regras implicará: Reprovação automática com conceito O. Possível denúncia à Comissão de Transgressões Disciplinares Discentes da Graduação. Possível denúncia apresentada à Comissão de Ética da UFABC, de acordo com o artigo 25 do Código de Ética da UFABC.
Programação (tentativa)
| Semana | Tema | Atividades |
|---|---|---|
| 01 | Revisão de probabilidade usando exemplos de algoritmos probabilísticos: gerador de números aleatórios a partir de bits aleatórios; Testes de Igualdade de strings e de polinômios. | ■Exercícios (lista 1) ■Leitura (versão revisada das notas de aula) |
| 02 | Revisão de variáveis aleatórias usando exemplos de algoritmos probabilísticos. Distribuições discretas e análise do quicksort probabilístico. | ■ Exercícios: do texto de leitura ■ Leitura: 3.2 das notas de aula (versão revisada) |
| 03 | Esperança condicional. maxe3sat (método 1ºmomento) e desaleatorização. Análise de Skip Lists. | ■ Exercícios: do texto de leitura: ■ Leitura: 3.3 e 3.4 das notas de aula (versão revisada) |
| 04 | Análise de Skip Lists. Hashing. Funções de hash universais; hashing perfeito. | ■ Exercícios (lista 2) ■ Leitura:3.1 das notas de aula (versão revisada) |
| 05 | Desigualdades de Markov e Chebyshev. Métodos de primeiros momentos: limiar para ocorrência de | ■ Leitura |
| 06 | Desigualdades de Chernoff. Algoritmos de big data; heavy hitters, count min, estimativa de elementos distintos | |
| 07 | Avaliação. Conteúdo até semana 5. | ■ Exercícios: (lista 3) ■ Leitura |
| 08 | Redução de dimensionalidade; Teorema de Johnson-Lindenstrauss; Algoritmos de streaming para | ■ Exercícios: ■ Leitura: |
| 09 | Complexidade. Modelos de computação, maquina turing probabilistica; classes de complexidade, P, NP, RP, ZPP, BPP. | ■ Exercícios: ■ Leitura: |
| 10 | Complexidade | ■ Exercícios: ■ Leitura: |
| 11 | Desaleatorização Avaliação (P2, nas sexta dia 13) | ■ Exercícios: ■ Leitura: |
| 12 | Avaliações substitutiva (3ª) e de recuperação (6ª) | ■ Exercícios: ■ Leitura: |
Links
How Randomness Improves Algorithms, Quanta Magazine (traduzido no Estadão)
“Avi Wigderson ganha prémio Turing, o ‘Nobel da computação’”
Os números aleatórios que guiam nossas vidas e a busca para encontrá-los
Essa disciplina por aí: UTexas, MIT (aqui tem exercícios com resolução), Illinois, Carnegie_Mellon, Edindurgh, EPFL, Stanford, Weizmann, British Columbia, IIT, IIS, Yale