Algoritmos Probabilísticos 2023 - 3

Jair Donadelli — email jair.donadelli ‘arroba’ ufabc. bla bla bla

Dilbert Random Number Generator - Imgur

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 acessível a alunos avançados no curso de graduação. A disciplina está organizada em três linhas principais: (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: segunda das 19:00 às 21:00, sala A-108-0, semanal , quarta das 21:00 às 23:00, sala A108-0, semanal

TPI: 4-0-4

2 últimas ofertas: [2018] , [2022]

Algoritmos Probabilísticos 2023 - 3EmentaObjetivosReferênciasBásicasComplementaresAvaliaçãoProgramação (tentativa)ProvasAtendimento

Ementa

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.

Objetivos

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.

Referências

Notas de aula

Básicas

Probablility and Computing, M. MITZENMACHER, E. UPFAL.

Randomized Algorithms, R. MOTWANI e P. RAGHAVAN.

Complementares

Computational Complexity: A Modern Approach, S. ARORA, B BARAK.
Design and Analysis of Randomized Algorithms, J. HROMKOVIC.
Concentration of measure for the analysis of randomized algorithms DUBHASHI e DEVSATT.

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).

Avaliação

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	$M\geq 85$
B	$70\leq M<85$
C	$50\leq M < 70$
D	$45 < M < 50$
F	$M \leq 45$

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.

Programação (tentativa)

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

Provas

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)

Atendimento

Nas 2ªs 18h-19h e as 21h;
ou em horário agendado por email (presencial ou remoto).
Sala 546-2