Algoritmos Probabilísticos 2024 - 3

Dilbert Random Number Generator - Imgur

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.

Resultado = max {Conceito final das provas, Conceito do exame}

Provas

P1 7ª semana

P2 11ª semana (aula 2)

Sub 12ª semana (aula 1)

Recuperação 12ª semana (aula 2)

Provas anteriores

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	$K_3$ $\mathbb{G}_{n,p}$ . Balls in Bins, limiar caixas vazias e carga máxima.	■ 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	~~$\ell_2$ $L_p$~~ Modelos de computação.	■ ■ Leitura:
09	Complexidade. Maquina turing probabilistica; classes de complexidade, P, NP, RP, ZPP, BPP.	■ Exercícios:(lista 4) ■ Leitura:
10	Sistemas de prova e prova com conhecimento zero.	■ Exercícios: ■ Leitura:
11	Avaliação (P2, nas sexta dia 13)	■ Exercícios: ■ Leitura:
12	Avaliações substitutiva (3ª) e de recuperação (6ª)	■ Exercícios: ■ Leitura: