Prof. Natalia Castro Fernandes
Mestrado em Telecomunicações – UFF
2º semestre/2012
Introdução
 Análise de um problema
 Resolução analítica

Equações e modelos
 Simulação

Modelo simplificado
•Dificuldade de resolução de grande escala
•Simplificações podem distorcer o resultado,
mas sem usar as simplificações o modelo
pode ficar muito complexo
•Quais partes do modelo podemos abstrair?
Qual a distância entre a realidade e o
resultado da simulação?
 Teste

Implementação real
•Implementar pode ser muito complexo
•Como fazer testes em escala?
A melhor análise tem os três tipos: resolução analítica, simulação e teste
Em geral, basta fazer duas análises, desde que uma valide a outra.
Simulação
 Vantagens
 Pode lidar com modelos mais complexos do que a análise
matemática
 Melhor representação do sistema real que a análise matemática
 Mais simples de implementar do que a solução completa

Abstração de detalhes
 Pode analisar cenários com grande escala, o que pode ser proibitivo
em implementações reais
 Desvantagens
 Dificuldade de interpretar os resultados


O que eu fiz está certo???
O que representa o resultado obtido???
 Longo tempo de execução
Caracterização de um simulador
 Determinístico ou estocástico
 Modelo contém eventos aleatórios?
 Estático ou dinâmico
 Evolução do tempo influi no sistema?
 Contínuo ou discreto
 Estado do sistema evolui continuamente ou em pontos
discretos no tempo?
Simulação discreta de eventos
--Estocástica, dinâmica e discreta --
Simulador estocástico
 Modelo contém eventos aleatórios
 Depende de gerador de números aleatórios
Mas como podemos gerar números aleatórios???
 Gerar números pseudo-aleatórios
 Parecem aleatórios, mas são essencialmente
determinísticos

Uso de função pseudo-aleatória
Gerador de números aleatórios
 Deve gerar números que pareçam uma variável
aleatória uniforme
 Uniformemente distribuídos entre 0 e N-1, onde N é um
número qualquer
 Estatisticamente independentes um do outro
Já vimos que a função random() do módulo
random faz exatamente isso.
E se eu quisesse criar o my_random(), que tivesse
as mesmas características de v.a. uniforme?
Método Congruente
 Método para gerar v.a. uniformes
 Utiliza três parâmetros inteiros
 a e M = parâmetros internos do algoritmo

M determina quantos números poderão ser gerados
 x(0) = 1º valor da sequência pseudo-aleatória, também
chamado de semente
x(i+1) = a*x(i) % M
U(i+1) = x(i+1)/M
V.a. uniforme gerada
Método Congruente
 Exemplos
 a=3, M=11, x(0)=4


x(i+1) = 3*x(i) % 11
Sequência = 4, 1,3,9,5, 4, 1,3,9,5,4,...
Má escolha de parâmetros pode gerar uma baixa
variabilidade de valores e repetição da sequência com
poucos sorteios.
Propriedade de um gerador
pseudo-aleatório
 Todos os números da sequência são gerados?
 Qual o tamanho da sequência?
 Sugestão de valores para método congruente:
 M=(2^31) -1
 A=7^5
Método Congruente Linear
 Mai s usado, pois costuma garantir maior variabilidade
nos valores
 Um parâmetro a mais que o método congruente: c
x(i+1) = (a*x(i)+c) % M
U(i+1) = x(i+1)/M
Exercício
 Gere mil números aleatórios entre 0 e 1 com o método
congruente e faça um histograma com intervalos de 0.1
de largura
 Repita utilizando o método congruente linear
 Repita utilizando a função random()
 Compare os resultados
 O gráfico pode ser feito com qualquer ferramenta
Lei dos Grandes Números
 Frequência relativa do resultado de um experimento
aleatório converge para sua probabilidade
 Resultado fundamental em probabilidade e estatística
Prova de que a probabilidade existe!!!!
Números, quando em grande quantidade, convergem!!!
 Portanto, um bom gerador deveria apresentar uma
frequência de ocorrências para todos os valores do
histograma, no exercício anterior, igual a 1/10
 Outro exemplo é o dado não viciado
 Se jogado muitas vezes, a frequência de cada face vale 1/6
Lei dos Grandes Números
 Uma grande quantidade de medidas leva a média real
do experimento
 Ex: gere um número entre 0 e 1 com o random() várias
vezes
Lei dos Grandes Números
Resposta = [0.8490961500569881, 0.6456630621108963, 0.7011384939674841,
0.7093239739503144, 0.008255047174339558, 0.5118803420415918,
0.9067574331321653, 0.04266981994782948, 0.19040859063960625,
0.30762765616240917, 0.2759092882464159, 0.03340334367397668]
 Média com 1 medida: 0.849096150056988
 Média com 2 medidas: 0.7473796060839422
 Média com 3 medidas: 0.7319659020451228
 Média com 12 medidas: 0.3727341022628085
 Média com 100 medidas: 0.48730569712969135
 Média com 1000 medidas: 0.5049299613079365
 Média com 10000 medidas: 0.49950420528919764
Simulação
 Evolução de um sistema estocástico no tempo
 Evolução do estado do sistema
 Estado depende das medidas de interesse
 Medidas de interesse = dados que você deseja medir com
a sua simulação
Variáveis da simulação
 Tempo
 representa o instante de tempo que o simulador se
encontra
 Variáveis de estado
 Representam o estado do sistema no tempo t
 Variáveis de interesse
 Representam valores que permitem o cálculo de
medidas de interesse
Eventos
 São ações que modificam o estado do sistema
 Quando um evento ocorre, as variáveis são atualizadas

Tempo, estado do sistema e medidas de interesse
 Permitem seguir o modelo no tempo
 Utilização de lista de eventos
Lista de eventos
 Lista contendo todos os eventos que irão ocorrer no
futuro
 Cada evento é identificado por tipo e instante que
deverão acontecer
 A lista deve estar ordenada pelos instantes de ocorrência
dos eventos
 Exemplo
Evento 1
T=1
Evento 2
T=7
Evento 3
T=10
Lista de eventos
 Após executar o evento atual, o simulador consulta a
lista
 Simulador processa próximo evento e o remove da lista
 Quando novos eventos serão adicionados à lista?
 Ao processar um evento!
Exemplo
 Simulador processa Evento 1
 Evento 1 gera 2 novos eventos
 Simulador reordena a lista
 Simulador descarta evento 1
 Simulador processa próximo
Simulador
evento
Evento x
T=12
Evento y
T=8
Evento 1
T=1
Evento 2
T=7
Evento 3
T=10
Simulador genérico
 Inicializar variáveis
 Inserir um ou mais eventos na lista de eventos
 Enquanto não chegar ao fim da simulação
 Remover próximo evento da lista de eventos
 Processar evento
Estimando medidas de interesse
 Exemplo de medida de interesse:
 Tempo até que o sistema falhe

Suponha que essa v.a. tenha distribuição desconhecida
 Como estimar algo sobre essa medida de interesse?
 Tirar média amostral

Simular vários valores de X e tirar a média
Intervalo de Confiança
 Média amostral não é igual ao valor esperado
 Média amostral tende ao valor esperado
 Exemplo:

Média amostral da random() é quase 0.5, mas não é
exatamente o valor esperado 0.5
 Ideia
 Utilizar a média para calcular um intervalo onde o valor
esperado pode estar
Teorema do Limite Central
 Seja uma sequência de variáveis aleatórias
identicamente independentes com valor esperado e
variância (σ2) menores que ∞
 A distribuição dessa sequência de variáveis converge
para distribuição Normal se o tamanho da sequência (n)
tende ao infinito (ou seja, se tivermos infinitas amostras,
n-> ∞)
 É possível fazer essa aproximação para a normal, se
usarmos um n suficientemente grande (ou seja, se
tivermos muitas amostras)
Intervalo de confiança
 Definição
 Com probabilidade
o intervalo gerado contém o valor
esperado μ
 Calcula uma barra de erro que, com
=95% de
chance, contém o valor correto da medida
 Boa chance do intervalo gerado conter o valor esperado,
mas não é garantido!
Intervalo de confiança
 Aproximação pela normal
 A confiança do intervalo
Entendendo a conta
 A confiança do intervalo

é a média amostral, ou seja, a média das suas
medidas

é o desvio padrão amostral, ou seja, o desvio padrão
das suas medidas

é o valor do eixo x em uma normal com média 0, de
tal forma que, se considerarmos o intervalo entre +
e, teremos marcado da área da Normal
 n é o seu número de amostras
Z0.9=1.65 e Z0.95=1.96
Entendo a conta
 Lembrando que o desvio padrão amostral
é calculado
como:
Média amostral
 Onde:
Intervalo de confiança
 Como apresentar seus gráficos?
 SEMPRE coloque a média amostral e o intervalo de
confiança de cada um de seus pontos no gráfico
Resultado da simulação
 Estado estacionário x estado transiente
 Existe um tempo, chamado de transiente, no qual o
resultado da simulação ainda não convergiu

Efeito do estado inicial
 Na maioria das simulações, deseja-se conhecer o estado
estacionário e não o estado transiente


Considerar medidas a partir da estabilização do sistema
Outra possibilidade é partir de um estado inicial mais próximo
do estado estacionário
Número de rodadas
 É preciso realizar uma simulação diversas vezes para
obter diversas medidas e tirar a média e o desvio
padrão amostral
 Como saber qual é um bom número de rodadas?
 Lembrando que o ideal seriam infinitas rodadas
Número de rodadas
 Escolher um valor para a confiança do intervalo a ser
gerado, ou seja,
 Escolher um valor máximo para o tamanho do intervalo,
que chamaremos de L
 O valor de L deve ser escolhido de acordo com o seu intervalo
de medidas, de tal forma que a barra de erros não fique
grande demais
 Escolher um número de amostras mínimo, nmin
 O desvio padrão amostral, S, depende de n

Por isso, existe um valor mínimo para n
 nmin=20 é um bom valor mínimo
 Gerar amostras até que intervalo gerado seja menor do que
L
Algoritmo
 Escolha
e L
 Gerar pelo menos nmin amostras
 Gerar mais amostras,
para cada um dos seus
pontos, até que:
2
<L
 Calcular média amostral
 Montar o gráfico
Exercícios
 Faça um script que calcule a média amostral de um conjunto de
medidas. As medidas devem estar em um arquivo, sendo colocada uma
medida por linha com a seguinte configuração:
Valor_eixo_x Medida
O script deve escrever em um arquivo de saída a média amostral para
cada um dos valores de x com o seguinte formato:
Valor_eixo_x Média
Exemplo:
Arquivo de entrada
1
1
1
2
2
2
10
9
8
3
6
9
Arquivo de saída
1 9
2 6
Exercícios
 Faça um script que calcule o desvio padrão amostral,
supondo que as medidas estão dispostas como
explicado no exercício anterior. O script deve retornar
o desvio padrão amostral de cada ponto da mesma
forma que foi feito no exercício anterior.
 Faça um script que mescle os dois exercícios
anteriores, criando um arquivo de saída do tipo:
eixo_x média desvio
Exercícios
 Crie um script que leia a saída do exercício anterior e
calcule o intervalo de confiança de 95% (Sua saída
deve ser referente a
. ). O arquivo de saída
deve ser do tipo:
eixo_x média intervalo
Referências
 Aulas do Prof. Daniel Figueiredo
 http://www.land.ufrj.br/~classes/model-analise2009/slides/aula_simul_1.pdf
 http://www.land.ufrj.br/~classes/model-analise2009/slides/aula_simul_2.pdf
 http://www.land.ufrj.br/~classes/model-analise2009/slides/aula_simul_3.pdf
 http://www.land.ufrj.br/~classes/model-analise2009/slides/aula_simul_4.pdf