Diferenças

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

--- algoritmo:aleatorio [2008/11/27 12:39]
softclean Ajustadas os links de páginas internas da Wiki
+++ 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 ======
+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 a 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 como, 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 de semente de gerador de números aleatórios é fundamental em muitos casos, como 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 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:
-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.
+<m>X(k) = [A * 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 congruencial, usa a 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 a 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 e **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 <nowiki>]]</nowiki>0; 1<nowiki>[[</nowiki>,isto é, U(k) = X(k) = M, onde U(k) é uma sequência uniformemente distribuída em <nowiki>]]</nowiki>0; 1<nowiki>[[</nowiki>. 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)
+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 M é 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>M = 2^b</m>, podemos simplificar para as seguintes duas condições:
-  * A > 0; C > 0
+  * <m>A = 4k + 1</m>, onde **k** é um inteiro positivo
-  * C é 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>
-  * A = 4k + 1, onde k é um inteiro positivo
+<m>Y2 = [ [-2ln(X2)] ] 1/2 cos(2 * pi * X1)</m>
-  * C = ímpar
-Seja agora X1 e X2, duas variáveis aleatórias independentes distribuídas uniformemente no intervalo <nowiki>[[</nowiki>0;|1<nowiki>]]</nowiki>. Então Y1 e Y2 definido por:
-<code>
-Y1 = [[-2ln(X1)]]1/2cos(2 x pi x X2)
-Y2 = [[-2ln(X2)]]1/2cos(2 x pi x X1
-</code>
 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 <nowiki>]]</nowiki> - inf; + inf<nowiki>[[</nowiki>. 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 <nowiki>]]</nowiki> - a; a<nowiki>[[</nowiki>, com a = <nowiki>[[</nowiki>-2 ln(m)<nowiki>]]</nowiki>1/2.
+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>.
 <note normal>//X módulo Y//, é o resto da divisão entre //X// e //Y//!</note>
+<dtopic 2558 Geração de números pseudo-aleatórios (método congruencial e de Box-Muller)>
+{{tag>algoritmo}}

Wiki Portugal-a-Programar

Ferramentas de Site

Diferenças

Ferramentas de Página