Jair Donadelli — email jair.donadelli ‘arroba’ ufabc. bla bla bla
Os algoritmos aleatorizados 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 a criptografia, mecanismos de busca e a teoria da aprendizagem computacional. Esta disciplina apresenta os conceitos básicos de projeto e análise de algoritmos aleatorizados em um nível a alunos avançados no curso de graduação. A disciplina está organizada em três linhas: (1) as ferramentas e técnicas probabilísticas, (2) os fundamentos teóricos-computacionais e (3) as aplicações.
Pré-requisitos: Introdução a Probabilidade e Estatística; Análise de Algoritmos.
Horário:
TPI: 4-0-
Algoritmos Probabilísticos 2024 - 3EmentaObjetivosReferênciasBásicasComplementaresAvaliaçãoProgramação (tentativa)ProvasAtendimentoLinks
Ferramentas e Técnicas: Teoria básica da probabilidade; Markov, Chebyshev e desigualdades de momento; problemas de coleção de cupons e ocupação ; desigualdades de cauda e limites de Chernoff; expectativa condicional e martingais; cadeias de Markov e passeios aleatórios. Fundamentos: 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, incluindo busca por similaridade, vizinhos mais próximos e agrupamento; algoritmos em teoria dos números.
Possibilitar o aluno compreender os modelos probabilísticos de computação, seu poder e suas limitações, capacitar no uso desses modelos em problemas computacionais e no uso das ferramentas mais comuns da probabilidade para a análise de desempenho e limitação da probabilidade de erro.
Probablility and Computing, M. MITZENMACHER, E. UPFAL. [518.1 MITZpr]
Randomized Algorithms, R. MOTWANI e P. RAGHAVAN. [004.015192 MOTWra]
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]
Auto-ajuda
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).
3 Provas com exercícios tirados das notas de aula.
A avaliação final de cada aluno não será o resultado de alguma média feita a partir das avaliações. O resultado de cada avaliação é um conceito (A,..,F) que reflete o desempenho do aluno em todo o curso até aquele instante. Isso significa que a cada conceito atribuído durante o curso leva em conta o resultado das avaliações até o momento. O resultado final é a média aritmética das provas convertida para um conceito
Conceito | Intervalo |
---|---|
A | |
B | |
C | |
D | |
F |
Substitutiva. O aluno que perder uma prova por razão justificada e de acordo com o regimento da UFABC deve apresentar justificativa e manifestar o interesse em realizar uma prova substitutiva.
Recuperação. Engloba todo o conteúdo da disciplina para aqueles alunos com conceito final D ou F e obtiveram frequência mínima. O aluno deve manifestar o interesse em realizar uma prova substitutiva.
O 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.
Semana | Tema | Atividades |
---|---|---|
01 Nessa semana revisamos conceitos fundamentais importantes de probabilidade e vemos exemplos de uso em algoritmos probabilísticos. | ■ Revisão de probabilidade: condicional, independência; continuidade. Exemplos de algoritmos probabilísticos: Gerador de números aleatórios a partir de bits aleatórios. Identidade polinomial (uma variável). ■ Exemplos de algoritmos probabilísticos: identidade entre polinômios (emparelhamento em grafo bipartido); corte mínimo em grafos | ■ Lista 1 ■ Leitura: Notas de aula |
02 Nessa semana revisamos conceitos de análise de algoritmos e de variáveis aleatórias com exemplos de uso desses conceitos em algoritmos probabilísticos. | ■ Exemplos de algoritmos probabilísticos: produto de matrizes e desaleatorização usando matriz de Vandermonde; consequências da desalatorização de identidade entre polinômios. ■ Revisão de probabilidade: variáveis aleatórias. Distribuições Bernoulli, Binomial, Geométrica. | ■ Lista 2 ■ Leitura: seções 2.1 e 2.2 Notas de aula (o conteúdo da seção 2.1 eu considero conhecido pelos estudantes) |
03 Nessa semana estudamos a distribuição de algumas variáveis aleatórias em algoritmos e estruturas de dados. | Análise do quicksort probabilístico. Esperança condicional. | ■ Notas de aula ■ Lista 3 |
04 | ■Análise de Skip Lists. ■ Avaliação | |
05 | 1º momento. max-e3sat. Esperança condicional e desaleatorização. | Lista 4 |
06 | Hash e hashing universal. | |
07 | ■Modelos de computação, maquina turing probabilistica; classes de complexidade, P, NP ■RP, ZPP, BPP. slides. | Notas de aula Lista 5 |
08 | ■Classes de complexidade, P, NP, RP, ZPP, BPP. ■Avaliação | |
09 | ■Tópico de complexidade computacional: Criptografia. slides. | Notas de aula Lista 6 |
10 | Primeiro e segundo momentos e suas desigualdades. Limiar para propriedades monotonas. | |
11 | Martingais; desigualdade de Azuma; parada ótima | Notas de aula |
12 | Avaliação |
P1 4ª semana (aula 2)
P2 8ª semana (aula 2)
P3 11ª semana (aula 2)
Sub 12ª semana (aula 1)
Recuperação 12ª semana (aula 2)
Nas 2ªs 18h-19h e as 21h;
ou em horário agendado por email (presencial ou remoto).
Sala 546-2
How Randomness Improves Algorithms, Quanta Magazine (traduzido no Estadão)
“Avi Wigderson ganha prémio Turing, o ‘Nobel da computação’, muito pelos estudos sobre a aplicação da aleatoridade na criação de algoritmos de computação…“