|
Cadeias de Markov
PESC/COPPE/UFRJ |
The Epic 20,000 Roll Dice Randomness Test |
|
Cadeias de Markov
PESC/COPPE/UFRJ |
The Epic 20,000 Roll Dice Randomness Test |
Desde da sua concepção na década de 40 algoritmos de Monte Carlo vem sendo utilizados para resolver diversos tipos de problemas, tais como problemas de amostragem e estimação, encontrando aplicações na Física, Biologia e Engenharia. Dentre suas muitas variações, algoritmos de Monte Carlo acoplados a cadeias de Markov (MCMC) estão entre os mais poderosos, tais como Metropolis-Hastings e simulated annealing. Com a crescente quantidade de dados e demanda por eficiência computacional, tais algoritmos vem sendo usados como base de técnicas emergentes em Ciências dos Dados e Inteligência Artificial. Nesta disciplina iremos explorar algoritmos de Monte Carlo com um enfoque teórico e fundamental, cobrindo probabilidade e teoria de cadeias de Markov, e também algumas aplicações práticas.
Algoritmo de Metropolis para Monte Carlo foi nomeado pela revista IEEE Computing in Science & Engineering como sendo um dos 10 algoritmos que mais influenciaram o desenvolvimento e a prática da ciência e engenharia no século 20!
Revisão de probabilidade, lei dos grandes números, algoritmos de amostragem, integração de Monte Carlo, cadeias de Markov, estado estacionário, tempo de mistura, passeios aleatórios, Metropolis-Hastings, amostragem de Gibbs, simulated annealing.
Pré-requisito: Probabilidade e estatística
Se inscrever no Moodle da discilina, cujo código de acesso para auto-inscrição é codigo767. Iremos utilizar esta plataforma para troca de mensagens e avisos, e entrega de tarefas (listas).
| Encontro | Data | Comentário | Slides | Vídeos | Tarefa |
| 1 | 21/03 | Logística, programação e regras do jogo. Três (tipos de) problemas resolvidos por Monte Carlo, história das origens, Monte Carlo na Computação |
aula_0.pdf aula_1.pdf |
Aula 0 Aula 1 |
Saiu lista 1 |
| - | 23/03 | Não teremos aula: Reunião de Planejamento Estratégico do PESC | Fazer lista 1 | ||
| 2 | 28/03 | Revisão de probabilidade: espaço amostral, probabilidade, eventos, independência, exclusão mútua, probabilidade total, regra de Bayes, variável aleatória, função de distribuição, distribuição de Bernoulli | aula_2.pdf | Aula 2 | Fazer lista 1 |
| 3 | 30/03 | Revisão de probabilidade: distribuição Binomial, Geometrica, Zeta, valor esperado, variância, função de v.a., distribuição conjunta, independência de v.a., valor esperado conditional, espaço amostral contínuo, função densidade | aula_3.pdf | Aula 3 | Fazer lista 1 |
| 4 | 4/04 | Limitantes para probabilidade, desigualdades de Markov, Chebyshev, Chernoff, with high probability (whp), limitante da União | aula_4.pdf | Aula 4 | Entregar lista 1 |
| 5 | 6/04 | Lei dos grandes números (fraca e forte), erro e confiança, margem de erro, falácia do apostador | aula_5.pdf | Aula 5 | Saiu lista 2 |
| 6 | 11/04 | Método de Monte Carlo, estimando somatórios, calculando o erro, estimando pi, integração de Monte Carlo, Monte Carlo Ray Tracing | aula_6.pdf | Aula 6 | Fazer lista 2 |
| 7 | 13/04 | Gerando amostras de v.a. discretas (eficientemente), gerando geométrica, método da transformada inversa, gerando Binomial, gerando permutações | aula_7.pdf | Aula 7 | Fazer lista 2 |
| 8 | 18/04 | Método da rejeição (rejection sampling), exemplos, Importance Sampling, exemplos, generalização | aula_8.pdf | Aula 8 | Fazer lista 2 |
| 9 | 20/04 | Algoritmos randomizados, exemplos, algoritmos de monte carlo, algoritmos de las vegas, comparação | aula_6_1.pdf | Aula 6_1 | Fazer lista 2 |
| 10 | 25/04 | Cadeias de Markov, definição e exemplos, modelo On-Off, sem memória, distribuição no tempo, irredutibilidade, aperiodicidade | aula_9.pdf | Aula 9 | Fazer lista 2 | ...
As listas devem ser submetidas no Moodle da disciplina, até o final do dia de entrega. Listas entregues com atraso serão penalizadas em 10% ao dia.
Livros texto de referência para as notas de aula: