Estatística e Modelos Probabilísticos - COE241classes/est-prob-2012/slides/aula_12.pdf · Tempo para transmitir uma mensagem em um canal de múltiplo acesso Como o número de parcelas

Rosa – 2012

Estatística e Modelos Probabilísticos - COE241

Aula de hoje

Análise de Comandos de Programação

Introdução à simulação

Geração de números aleatórios

Aula passada

Função Distribuição Condicional

Calculando Probabilidades condicionando

Esperança Condicional

Rosa – 2012

Exemplo: X e Y v.a. contínuas

Queremos calcular P[X<Y]

P [X Y ]=∫−∞

∞

P [X Y /Y= y ] f Y y dy

P [X Y ]=∫−∞

∞

P [X y ] f Y y dy

P [X Y ]=∫−∞

∞

F X y f Y y dy

Rosa – 2012


Rosa – 2012


Rosa – 2012

Somas Aleatórias

Seja T=X1+X

2+ … +X

N, onde N é uma

variável aleatória que é independente deX

ke todos os X

k são variáveis aleatórias

independentes e identicamente distribuídas

Rosa – 2012

Somas Aleatórias Estas variáveis aleatórias ocorrem nos

seguintes casos:

Tempo de execução de comandos de programação como whilewhile e repeat

Tempo para transmitir uma mensagem em um canal de múltiplo acesso

Como o número de parcelas (N) na soma é uma variável aleatória, iremos usar o condicionamento para cálculo de medidas de interesse

Rosa – 2012

Somas Aleatórias: Média

Rosa – 2012

Somas Aleatórias: Variância

Rosa – 2012


Suponha que queiramos obter a média e variância de comandos usados em programação

v.a. X representa o tempo de execução do comando

v.a. N representa a probabilidade de um determinado trecho ser executado

Rosa – 2012


Comando if B then S1 else S2

Variável X está condicionada a N onde N

representa a probabilidade de execução de S

i

X é uma v.a. contínua condicionada a uma

v.a. discreta. Podemos definir a função densidade condicional de X como:

f X /N x /i= f i x , função densidadecondicional de X dada a escolha S i

Rosa – 2012


A função densidade marginal de X é:

Temos que E[X] pode ser obtido de:f X x=∑

i=1n pN i f i x

E [X ]=∫−∞

∞

x∑i=1

npN i f i xdx

E [X ]=∑i=1

npN i ∫−∞

∞

x f i xdx

E [X ]=∑i=1

npN i E [X i ]

Rosa – 2012


No caso do comando if then else, N é uma v.a. Bernoulli, logo temos:

E[X] = pE[X1] + (1-p)E[X

2]

Rosa – 2012


A variância é dada por E[X2] – E[X]2, onde

No caso do comando if then else, N é uma v.a. Bernoulli, logo temos:

Temos que Var[T] = pVar[X1 ] + (1-

p)Var[X2 ] +p(1-p)(E[X

1]-E[X

2])2

E [X 2]=∑i=1

npN i E [X i

2]

E [X 2]= pE [X 1

2]1− pE [X 2

2]

Rosa – 2012


Comando case i of

1: S1;2: S2;end

Mesmo caso do comando if then else, só que existem várias opções de escolha

Variável X está condicionada a N onde N

representa a probabilidade de execução de S

i

Rosa – 2012


Média:

Variância:

E [X ]=∑ipN i E [X i ]

Var [X ]=∑i

npN i E [ X i

2]−∑i

npN i E [X i ]

2

probabilidade de escolha de uma das opções

Tempo médio de execução de Si

Rosa – 2012


Threads concorrentes

N é o número de threads

Xi é o tempo de execução de cada thread

Estatística de ordem permite o cálculo da distribuição até que a primeira thread termine e até que a última termine

Rosa – 2012

Simulação de Sistemas Discretos

É uma técnica de modelagem que visa a representação do comportamento do sistema para obtenção de medidas de desempenho e/ou confiabilidade

O sistema é representado através de eventos que ocorrem segundo uma distribuição de probabilidade

Rosa – 2012

O Ciclo de Modelagem

Criação do Modelo

Solução doModelo

Sistema real

aproximação

Influênciano sistema

Rosa – 2012

Modelando um Sistema

Abstração do sistema

Simplificação necessária

Representação matemática do sistema

Aleatoriedade

Servidor

Web

pedidosCPU

Disco 1

Disco 2

pedido finalizado

Taxa de chegadade pedidos

Rosa – 2012

Algumas Medidas de Desempenho

Vazão de um recurso: número de processos servidos por unidade de tempo

Utilização de um recurso: percentual do tempo que o recurso fica ocupado

Número médio de processos na fila do recurso

Tempo médio que cada processo fica na fila do recurso

Rosa – 2012

Fila Genéricarequisições

CPU

Como avaliar o desempenho desta fila? Qual o tamanho médio da fila?

Simulação

Rosa – 2012

Simulando uma Fila Genéricarequisições

CPU

O que é uma simulação?

Programa que imita comportamento do sistema

Como simular este sistema?

Programa deve gerar eventos de chegadas e serviço, manter estado da fila, calcular medidas de interesse

Rosa – 2012

Simulando uma Fila Genéricarequisições

CPU

N(t)

t

Sistema ocioso

Sistema ocupado

Imitar evolução do sistema: N(t)

Obter medidas de interesse: vazão, utilização, E[N], etc.

Rosa – 2012

Simulação

VantagensPode lidar com modelos mais complexos

Melhor representação do sistema real

DesvantagensDifícil verificar a precisão dos resultados

Pode ter longo tempo de execução

Modelos analíticos possuem vantagens e desvantagens com relação a simulação

Rosa – 2012

Caracterizando um Simulador Determinístico ou Estocástico

Modelo contém eventos aleatórios?

Estático ou DinâmicoEvolução do tempo influi no sistema?

Contínuo ou DiscretoEstado do sistema evolui continuamente ou em instantes discretos no tempo?

Simulação Discreta de Eventos

estocástica, dinâmica e discreta

Rosa – 2012

Primeiro Passo para Simulação

Como gerar números aleatórios?

Gerar números pseudo-aleatóriosque pareçam aleatórios

Rosa – 2012

Gerador de Números Pseudo-Aleatórios

Algoritmo que gera uma sequência de números inteiros U

1, U

2, ..., que

pareçam ser:

Uniformemente distribuídos no intervalo [0, M-1] (para algum M fixo)

Estatisticamente independentes

pareçam ser: sequência deve ter propriedades relevantes de uma sequência de v.a. uniforme

Rosa – 2012

Método Congruente

Dois parâmetros a e M (números inteiros) e o valor inicial é x

0 (semente)

x i=a x i−1mod MU i=

x i

M

x0 determina a sequência inteira

M determina quantos diferentes números podem ser gerados

Rosa – 2012

Exemplo

Supor a=3 e M=11

x i=3 xi−1mod 11

x0=4Supor (semente)

Quantos números diferentes podemos gerar?

x 1 =3 x 0 m o d1 11 2m o d1 11

=

=

x 2 =3 x 1 m o d1 13 m o d 1 13

=

=

Rosa – 2012

Exemplo

Supor a=3 e M=11

x i=3 x i−1 m o d1 1

x0=4x1=1x2=3x3=9x4=5x5=4x6=1

.

.

.

Gerador entra em loop depois de 5 amostrasE se x

0 for diferente ?

Rosa – 2012

Propriedades do Gerador

Qual o tamanho de uma sequência?Escolher a e M tal que para qualquer x

0

Sequência pareça aleatóriaLongo ciclo antes de repetiçãoCálculo seja eficiente

Rosa – 2012

Método Congruente LinearTrês parâmetros a, c e M (números inteiros)Dado x

0 (semente)

x i=a x i−1c m o dM

U i=x i

M

x0 determina a sequência inteira

Bastante utilizado

diferença do outro método

Rosa – 2012

ExemploSupor a = 3, M = 11, c = 2Semente x

0 = 4

x i=3 x i−12 m o d1 1

x 0 =4x 1 =3x 2 =0x 3 =2x 4 =8x 5 =4x 6 =3

.

.

.

x 1 =3 x 0 2 m o d1 1

1 4m o d 1 13

=

=

Rosa – 2012

Geradores na PráticaLinguagens de programação oferecem geradores

C ou C++ (gnu)

lrand48() - retorna long [0, 231]

drand48() - retorna float [0, 1)

Método Congruente Linear

Usuário define semente (x0)

Matlab utiliza múltiplos geradores

usuário pode escolher

M=248 a=25214903917 c =1 1

Rosa – 2012

Tarefa de Casa (1)Fazer um programa para gerar números aleatórios usando o método congruente linear

Escolha conjuntos de parâmetros e justifique a escolha de cada conjunto

Gerar gráfico com histograma para cada conjunto de parâmetros comentando como a escolha dos parâmetros influenciou nos resultados

0.1 0.2 0.3 0.4 0.5 0.6 . . .

Número de ocorrências

0 1.0

Rosa – 2012

Tarefa de Casa (2)

Repetir o experimento usando o gerador da linguagem de programaçãoComparar resultados do seu gerador com os obtidos com o gerador da linguagemEntregar relatório contendo os resultados do seu experimento e o código do programa

Documents

Estatística e Modelos Probabilísticos - COE241classes/est-prob-2012/slides/aula_12.pdf · Tempo para transmitir uma mensagem em um canal de múltiplo acesso Como o número de parcelas