Professores

Celina Miraglia Herrera de Figueiredo

Vinícius Gusmão Pereira de Sá

João Paixão

Ementa

Conceitos Básicos de Probabilidade, Algoritmos Randomizados, Análise Probabilística de Algoritmos, Algoritmos de Dados Massivos, Aprendizado de Máquina supervisionado e não-supervisionado , Cadeias de Markov, e Passeios Aleatórios.

Bibliografia

Luerbio Faria, Fabiano de Souza Oliveira, Paulo Eustáquio Duarte Pinto e Jayme Luiz Szwarcfiter. Ciência de dados: algoritmos e aplicações. 33^o Colóquio Brasileiro de Matemática

Celina Miraglia Herrera de Figueiredo, Guilherme Dias da Fonseca, Manoel José Machado Soares Lemos, Vinícius Gusmão Pereira de Sá. Introdução aos Algoritmos Randomizados. Curso introdutório no 26^o Colóquio Brasileiro de Matemática. Texto Completo

Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of Data Science

Programação

Aulas do Prof. Vinícius

Aula 1 (16/11)

Conversa inicial sobre o curso. Primeira conversa sobre algoritmos randomizados. Exemplo de bom uso de randomização: robôs de paraquedas. Exemplo de péssimo uso de randomização: RandomSort. Fisher-Yates shuffle.

Slides emprestados do 26 Colóquio Brasileiro de Matemática aqui.

Slides sobre os robôs de paraquedas aqui.

Código em Python para o problema dos robôs aqui.

Artigo com a análise dos robôs, caso interesse a alguém. :-)

Aula gravada no Google Meet.

Aula 2 (19/11)

Algoritmos de Monte Carlo. Erro unilateral e erro bilateral. Monte Carlo baseado no sim e baseado no não.

Refinando a probabilidade de erro via repetição (exponencial negativa).

Revisão de probabilidades: probabilidade da união e da interseção, probablidades condicionais, probabilidade total.

Link para a Jam sobre probabilidades.

Aula gravada no Google Meet.

Aula 3 (23/11)

Segundo exemplo de algoritmo de Monte Carlo, dessa vez baseado no sim e sem qualquer parâmetro interno para refinamento da probabilidade de erro.

Exemplo: corte mínimo em grafos. Slides.

Monte Carlo de erro bilateral.

Exemplo: o problema dos atiradores no clube. Código em Python para acompanhar a evolução das probabilidades (modelo de crenças).

Aula gravada no Google Meet.

Aula 4 (26/11)

Variáveis aleatórias. Bernoulli, Binomial, Geométrica. Esperança. Linearidade da Esperança.

Exemplo: o problema dos piratas bêbados. Código em Python para uma simulaçãozinha.

Algoritmos de Las Vegas: acertam sempre, tempo de execução é uma V.A.

Quick Sort Randomizado. Análise. Aula gravada no Google Meet.

Aula 5 (3/12) - "Aula dupla" de 8h-12h excepcionalmente.

Análise de caso médio de algoritmo determinístico versus análise do tempo esperado de uma execução de algoritmo de Las Vegas.

Desigualdades de Markov e Chebyshev.

Transformação Monte Carlo em Las Vegas, e vice-versa.

Paradigmas combinatórios: bolas e latas, colecionador de coupons. Exemplo: identifação de roteadores (reservoir sampling).

O Método Probabilístico (para provas de existência): o método da esperança, o método da probabilidade estritamente positiva.

Código em Python para uma estimativa empírica da média da VA geométrica.

Aula gravada no Google Meet.

Não haverá aula nos dias 7/12 e 10/12 porque os alunos estarão dedicados à P1;

Aulas da Profa. Celina

As aulas a partir de 14 de dezembro serão dadas pela professora Celina na sala virtual https://meet.google.com/iva-bvry-skm

Aula 6 (14/12)

Notas

Vídeo

Aula 7 (17/12)

Notas

Vídeo

Aula 8 (21/12)

Notas

Vídeo

Aula 9 (4/1)

Notas

Vídeo

Aula 10 (7/1)

Aula com o Professor Paulo Eustáquio Duarte Pinto

Slides

Vídeo

Tese de mestrado do Judismar Arpini Junior sobre Cuckoo hashing

Entrega da Lista 2

A Lista 2 deverá ser entregue no dia 11/1. Não teremos aula.

Aula 11 (14/1)

Notas

Vídeo

Aula 12 (18/1)

Notas

Vídeo

Dia 21/1: Não teremos aula devido ao feriado do dia 20/1.

Aulas do Prof. João

Aula 13 (25/1)

Notas

Vídeo

Tente resolver as questões 1, 8, 11c e 11d da Lista 3 até sexta 28/1. Não precisa enviar.

Aula 14 (28/1)

Notas

Vídeo

Código

Aula 15 (1/2)

Notas

Vídeo

Código

Não teremos aula no dia 4/2 para vocês trabalharem na Lista 3.

Aula 16 (8/2)

Notas

Vídeo

Entrega da Lista 3 (12/2)

A Lista 3 deverá ser entregue no dia 12/2.

Aula 17 (11/2)

Notas

Vídeo

Aula 18 (16/2) - Essa aula será excepcionalmente na quarta 16/2 às 10h.

Notas 1

Notas 2

Vídeo

Não haverá aula nos dias 18/2 e 22/2 porque os alunos estarão dedicados à P2;