Ferramentas de Site


algoritmo:aleatorio

Diferenças

Esta página mostra as diferenças entre as duas revisões da página.

Links para esta vista de comparação

Ambos os lados da revisão anterior Revisão anterior
Próxima revisão
Revisão anterior
algoritmo:aleatorio [2007/10/24 14:05]
127.0.0.1 Edição externa
algoritmo:aleatorio [2021/12/12 12:39]
staff
Linha 1: Linha 1:
-FIXME Passar as expressões matematicas para mathML e escapar alguns caracteres. 
- 
 ====== Geração de Números pseudo-aleatórios ====== ====== Geração de Números pseudo-aleatórios ======
  
 +Imaginem que querem fazer o vosso programa e querem ter uma função que gera números aleatórios ao vosso gosto.
  
-Imaginem que querem fazer o seu programa e querem ter uma função que gera números aleatórios ao seu gosto.+Por exemplo, gerar valores pseudo-aleatórios com distribuição uniforme entre **]0,1]** ou uma distribuição gaussiana de média nula e de variância unitária (ruído branco). Imaginem que não têm qualquer função que gerasse números aleatórios. Então este tópico tem a função de ensinar um algoritmo de um motor de números aleatórios e sua manipulação.
  
-Por exemplo fazer uma geração de valores pseudo-aleatórios com distribuição uniforme entre ]]0,1]] ou uma distribuição gaussiana de média nula e de variância unitária (ruído branco). Imaginem que não têm qualquer função que gera-se números aleatórios. Então este tópico tem função de ensinar um algoritmo dum motor de n.º aleatórios e sua manipulação.+A necessidade da semente de gerador de números aleatórios é fundamental em muitos casos comopor exemplo, para reproduzir eventos de jogo //a posteriori// (sistema de replay). Se garantirmos que o sistema de jogo é determinista (uma acção do jogador conduz sempre ao mesmo resultado), apenas precisamos de reintroduzir a semente do gerador de números aleatórios utilizado para as computações de AI, física, etce obtemos mesma sequência de eventosSem falar, que facilita em muito o processo de debug.
  
-necessidade de semente de gerador de números aleatórios é fundamental em muitos casoscomo por exemplo para reproduzir eventos de jogo a posteriori (sistema de replay)Se garantirmos que o sistema de jogo é determinista (uma acção do jogador conduz sempre ao mesmo resultado)apenas precisamos de reintroduzir a semente do gerador de números aleatórios utilizado para as computações de AI, física, etc. obtemos a mesma sequência de eventos. Sem falar, que facilita em muito o processo de debug.+geração de ruído branco inicia-se com uma fórmula para produzir números aleatórios distribuídos uniformemente no intervalo ]0,1]Aplicando transformações convenientes na sequência distribuída uniformementepodemos obter sequências de números aleatórios com distribuições propriedades arbitrárias.
  
 +Um dos métodos preferidos para a geração de números aleatórios, designado por método congruencial, usa a seguinte fórmula recursiva:
  
-geração de ruído branco inicia-se com uma fórmula para produzir números aleatórios distribuídos uniformemente no intervalo ]]0,1]]Aplicando transformações convenientes na sequência distribuída uniformemente podemos obter sequências de números aleatórios com distribuições e propriedades arbitrárias.+<m>X(k) = [* X(k 1)] modulo M</m> 
 +com k = 1, 2, ...
  
-Um dos métodos preferidos para a geração de números aleatórios, designado por método congruencialusa seguinte fórmula recursiva.+Na fórmula, **A** é um inteiro entre **1** e **M**, em que **M** é um número primo ou uma potência inteira de um número primo, <m>p^m</m>. A geração de números aleatórios começa com a utilização da "semente" inicial X(0). A equação irá produzir inteiros uniformemente distribuídos entre **1** e **M**. Dividindo **X(k)** por **M** podemos gerar valores do intervalo **]0; 1[** isto é<m>U(k) = X(k) = M</m>, onde **U(k)** é uma sequência uniformemente distribuída em **]0; 1[**. Se **M** for muito grande e **A** for convenientemente escolhido, os números na sequência parecerão aleatórios (independentes) e sequência terá um período máximo de **M - 1**.
  
-<code>X(k) = [[A|x X(k - 1)]] modulo M;  k = 1, 2, ...</code> +Para um gerador congruencial multiplicativo, se **M** for <m>2^b</m>, onde **b** é o número de bits de um inteiro sem sinal (//unsigned integer//), o período máximo é <m>M/4 = 2^b-2</m>. Isto pode ser obtido se a semente (X0) for um número ímpar **A** obedeça à seguinte restrição Freeman04:
- +
-onde A é um inteiro entre 1 e M, em que M é um número primo ou uma potência inteira de um número primo, pm. A geração de números aleatórios começa com a utilização da "semente" inicial X(0). A equação produzirá inteiros uniformemente distribuídos entre 1 e M. Dividindo X(k) por M podemos gerar valores do intervalo ]]0; 1[[,isto é, U(k) = X(k) = M, onde U(k) é uma sequência uniformemente distribuída em ]]0; 1[[.|Se M for muito grande e A for convenientemente escolhido os números na sequência parecerão aleatórios (independentes) e a sequência terá um período máximo de M - 1. +
- +
- +
-Para um gerador congruencial multiplicativo, se M for 2^b, onde b é o número de bits de um unsigned integer, o período máximo é M/4 = 2^b-2. Isto pode ser obtido se a semente (X0) for um número impar e A obedeça à seguinte restrição [[Freeman04]]: +
- +
-<code>A = 8k +- 3</code>+
  
 +<m>A = 8k +- 3</m>
 (sendo //k// um número inteiro) (sendo //k// um número inteiro)
  
 +No caso de termos um gerador congruencial normal e a assumindo que o valor do módulo **M** é suficientemente grande - um bom exemplo seria <m>2^b</m> - mas não é obrigatório - os valores de **M**, **A** e de **C** obedecem aos seguintes critérios:
 +  * **A > 0**; **C > 0**.
 +  * **C** é primo relativo de **M**; O maior divisor comum de **C** e **M** é **1**.
 +  * Para todos os factores primos, **p**, de **M**, **p** necessita igualmente de ser factor de **A-1**.
 +  * **4** precisa de ser um factor de **A-1** se **4** for um factor de **M**.
  
-No caso de termos um gerador congruential normal  e a assumindo que o valor do módulo é suficientemente grande - um bom exemplo seria 2^b, mas não é obrigatório - os valores de M, A e de  C obedecem aos seguintes critérios+Se <m>2^b</m>podemos simplificar para as seguintes duas condições
-  * A > 0; C > 0 +  * <m>= 4k + 1</m>, onde **k** é um inteiro positivo 
-  é primo relativo de M; O maior divisor comum de C e M é 1. +  * **C = ímpar**
-  * Para todos os factores primos, p, de M, p necessita igualmente de ser factor de A-1. +
-  4 precisa de ser um factor de A-1 se 4 for um factor de M.+
  
 +Seja agora **X1** e **X2**, duas variáveis aleatórias independentes distribuídas uniformemente no intervalo <nowiki>[0;1]</nowiki>. Então **Y1** e **Y2** definido por:
  
-Se M = 2^b, podemos simplicar para as seguintes duas condições: +<m>Y1 [ [-2ln(X1)] ] 1/2 cos(2 * pi * X2)</m> 
-  4k + 1, onde k é um inteiro positivo +<m>Y2 [ [-2ln(X2)] ] 1/2 cos(2 pi * X1)</m>
-  C = ímpar+
  
 +são variáveis aleatórias gaussianas, independentes, de média nula e variância unitária.
  
 +Este algoritmo, que permite obter um par de v.a. gaussianas a partir de um par de v.a. distribuídas uniformemente é conhecido por método de Box-Muller.
 +Note-se que as equações anteriores produzem números distribuídos no intervalo <m>]-infty; +infty[</m>. Se m for o menor número real positivo que pode ser representado num dado computador, então o algoritmo produzirá números no intervalo <m>]-a; a[</m>, com <m>a = [-2 * ln(m)]^{1/2}</m>.
  
-Seja agora X1 e X2duas variáveis aleatórias independentes distribuídas uniformemente no intervalo [[0;|1]]. Então Y1 Y2 definido por:+<note normal>//X módulo Y//é o resto da divisão entre //X// //Y//!</note>
  
- <code>Y1 = [[-2ln(X1)]]1/2cos(2 x pi x X2) +<dtopic 2558 Geração de números pseudo-aleatórios (método congruencial e de Box-Muller)>
- Y2 = [[-2ln(X2)]]1/2cos(2 x pi x X1)</code> +
- +
-são variáveis aleatórias gaussianas, independentes, de média nula variância unitária. +
- +
-Este algoritmo, que permite obter um par de v.a. gaussianas a partir de um par de v.a. distribuídas uniformemente é conhecido por método de Box-Muller+
-Note-se que as equações anteriores produzem números distribuídos no intervalo ]] - inf; + inf[[.|Se m for o menor número real positivo que pode ser representado num dado computador, então o algoritmo produzirá números no intervalo ]] - a; a[[|com a = [[-2 ln(m)]]1/2.+
  
-**Nota:** //X módulo Y//, é o resto da divisão entre //X// e //Y//!+{{tag>algoritmo}}
algoritmo/aleatorio.txt · Última modificação em: 2021/12/12 12:39 por staff