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

Próxima revisão
Revisão anterior
algoritmo:aleatorio [2007/09/27 09:04]
127.0.0.1 external edit
algoritmo:aleatorio [2021/12/12 12:39] (Atual)
staff
Linha 1: Linha 1:
-=====  Geração de n.º pseudo-aleatórios ==+=====Geração de Números pseudo-aleatórios ======
  
-Imaginem que querem fazer o seu programa e querem ter uma função que gera números aleatórios ao seu gosto.+Imaginem que querem fazer o vosso programa e querem ter uma função que gera números aleatórios ao vosso gosto.
  
-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 a função de ensinar um algoritmo dum motor de n.º aleatórios e sua manipulação.+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.
  
-A 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. e obtemos a mesma sequência de eventos. Sem falar, que facilita em muito o processo de debug.+A necessidade da semente de gerador de números aleatórios é fundamental em muitos casos comopor exemplopara 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. e obtemos a mesma sequência de eventos. Sem falar, que facilita em muito o processo de debug.
  
 +A 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.
  
-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.+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:
  
-Um dos métodos preferidos para a geração de números aleatóriosdesignado por método congruencialusa a seguinte fórmula recursiva.+<m>X(k) = [A * X(k - 1)] modulo M</m> 
 +com k = 12...
  
-<code>X(k= [[A|x X(k - 1)]] modulo M k = 1, 2, ...</code>+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)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 a sequência terá um período máximo de **M - 1**.
  
-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 <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:
- +
- +
-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>
  
- 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) +
- +
-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.1190883849.txt.gz · Última modificação em: 2018/05/14 21:37 (edição externa)