Simulacao

Simulação
• Emulação de sistemas reais
• Levantamento de estatísticas
– Não envolve pessoas/sistemas reais
– Situações extremas podem ser testadas
– Intervalos de tempo “irreais” podem ser avaliados
Simulação
• Problema de Josephus
– N pessoas (numeradas de 1 a N) sentadas em um círculo
– Começando pela pessoa 1, uma batata quente é passada
para a pessoa do lado.
– Depois de M passes, a pessoa que está com a batata
quente é eliminada do círculo.
– A batata recomeça a ser passada pela pessoa ao lado da
eliminada
1
Simulação
Problema de Josephus
• M=0
– Pessoas eliminadas na ordem a partirda pessoa 1. Ganha a
última pessoa.
• M=1
– A ordem de eliminação de pessoas não é tão intuitiva.
– N=5, M=1:
•
•
•
•
Começa com 1, passa para 2 que é eliminado
3 pega a batata, passa para 4 que é eliminado
5 pega a batata, passa para 1 que é eliminado
3 pega a batata, passa para 5 que é eliiminado. 3 ganha.
Simulação
Problema de Josephus – Solução 1
• Pessoas: elementos em uma lista ligada
• Cada passe da batata é uma operação next em um
iterator da lista ligada.
2
Simulação
Problema de Josephus - Implementação
public static int josephus( int people, int passes) {
Collection theList = new LinkedList();
for (int i=1;i<=people;i++)
theList.add(new Integer(i));
Iterator its = theList.iterator();
O(MN)
while (people -- !=1) {
for (int i=0;i<=passes;i++) {
if (!itr.hasNext())
itr=theList.iterator();
itr.next();
}
itr.remove();
}
itr.theList.iterator();
return ((Integer) itr.next()).intValue();
}
Simulação
Problema de Josephus – Solução 2
• Podemos notar que a pessoa a ser eliminada sempre é dada
por:
(P+M) mod N
Onde N = número de pessoas
P = pessoa com a batata
M = número de passes
• Para o exemplo inicial: N=5, P=1, M=1
–
–
–
–
–
(1+1) mod 5 = 2 (eliminado) (pessoa 2)
(2+1) mod 4 = 3 (eliminado) (pessoa 4)
(3+1) mod 3 = 1 (eliminado) (pessoa 1)
(1+1) mod 2 = 0 (apontamos para N) eliminamos pessoa 5.
Pessoa 3 ganha.
3
Simulação
Problema de Josephus – Solução 2
• Encontramos facilmente o elemento que deve ser removido.
• Podemos utilizar uma árvore para realizar a busca pelo
elemento k do conjunto.
• O (N log N)
Árvores Binárias – k-ésimo maior elemento
• Como obter de forma simples o k-ésimo maior elemento de uma
árvore binária?
• Colocar em cada nó um contador que indica quantos nós existem
sob este nó (inclusive o próprio nó):
R
20
15
4
8
6
3
7
5
SL
1
1
3
6
2
2
1
SR
1
1
3
1
1
4
Árvores Binárias – Complexidade de uma busca
• O custo é proporcional ao número de nós visitados até
atingir o nó procurado.
• No pior caso esse número é igual à altura da árvore.
• A configuração da árvore interfere no custo:
– Situação linear: altura = número de nós (a árvore é uma lista
encadeada de nós)
– Melhor situação: árvore balanceada, cada nó tem o seu número
máximo de filhos. (árvore de altura/profundidade mínima)
k −1
N = ∑ 2i = 2 k − 1
k = O(log N )
i =0
Onde k é a altura da árvore
5