Esta é a página do curso de Ciência de Dados - Algoritmos e Aplicações. Nesta página vocês terão todas as informações a respeito do curso, por isso sempre estejam de olho nela. As aulas serão ministradas de forma remota pelo Google Meet.
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.
Início: 16/11/2021
Terças e Sextas de 10h até 12h
Salas: A partir do dia 14/12 - https://meet.google.com/iva-bvry-skm (João Paixão)
Luerbio Faria, Fabiano de Souza Oliveira, Paulo Eustáquio Duarte Pinto e Jayme Luiz Szwarcfiter. Ciência de dados: algoritmos e aplicações. 33o 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 26o Colóquio Brasileiro de Matemática. Texto Completo
Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of Data Science
Lista 1 - Entregar até dia 5/12/21 (Entrega por e-mail para os monitores).
Prova 1 - Entregar até dia 13/12 às 23:59 (tinha um erro na primeira versão, essa versão já está atualizada) para vigusmao@dcc.ufrj.br.
Lista 2 - Entregar até dia 11/1/22 (Entrega por e-mail para os monitores).
Lista 3 - Entregar até dia 12/2/22 (Vamos selecionar algumas questões. Entrega por e-mail para os monitores)
Prova 2 - Entregar até dia 22/2/22 às 23:59 para jpaixao@dcc.ufrj.br e celina@cos.ufrj.br
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)
Aula 7 (17/12)
Aula 8 (21/12)
Aula 9 (4/1)
Aula 10 (7/1)
Aula com o Professor Paulo Eustáquio Duarte Pinto
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)
Aula 12 (18/1)
Dia 21/1: Não teremos aula devido ao feriado do dia 20/1.
Aulas do Prof. João
Aula 13 (25/1)
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)
Aula 15 (1/2)
Não teremos aula no dia 4/2 para vocês trabalharem na Lista 3.
Aula 16 (8/2)
Entrega da Lista 3 (12/2)
A Lista 3 deverá ser entregue no dia 12/2.
Aula 17 (11/2)
Aula 18 (16/2) - Essa aula será excepcionalmente na quarta 16/2 às 10h.
Não haverá aula nos dias 18/2 e 22/2 porque os alunos estarão dedicados à P2;
Aula 1 - Algoritmos Randomizados - Prof. Paulo Eustáquio Duarte Pinto
https://www.youtube.com/watch?v=J0YCaYNwBUI
Aula 2 - Algoritmos para Dados Massivos - Prof. Fabiano de Souza Oliveira
https://www.youtube.com/watch?v=F7sPPEhGfLo
Aula 3 - Aprendizado de Máquina Prof. Jayme Luiz Szwarcfiter
https://www.youtube.com/watch?v=m3yQHyCVTxU
Aula 4 - Cadeias de Markov - Prof. Luerbio Faria
https://www.youtube.com/watch?v=5Ran5oj-FDg
Alua 5 - Passeios Aleatórios - Prof. Luerbio Faria
https://www.youtube.com/watch?v=7wDgsmvdgjs
Explicação do Cuckoo Hashing - Judismar Arpini