Descreva dois métodos que você pode usar para gerar números aleatórios.

Passo 1

O que o enunciado pede: descrever dois métodos que podem ser usados para gerar números aleatórios.
Informações relevantes entregues pelo enunciado: não há restrição sobre tipo de número (inteiro, real, bits) nem sobre aplicação (simulação, criptografia etc.). Portanto devo escolher dois métodos distintos e explicá‑los de forma didática, mostrando como funcionam na prática e quais cuidados tomar.

Passo 2

Rápida orientação conceitual (para não perder o fio): existem, em linhas gerais, dois tipos de geração de aleatoriedade que vamos comparar e explicar:
  • geradores pseudoaleatórios (determinísticos, baratos e rápidos), e
  • geradores verdadeiramente aleatórios por hardware (baseados em processos físicos imprevisíveis).
    Vou apresentar um representante prático de cada tipo, com fórmulas, exemplos e dicas de uso.

Passo 3

Método 1 — Gerador congruencial linear (um gerador pseudoaleatório clássico). Apresentação da fórmula e das variáveis:
X_{n+1} = (a\,X_n + c)\bmod m.
Aqui:
  • X_n é o estado (inteiro) do gerador no passo n (o primeiro X_0 é a semente, o seed);
  • a é o multiplicador (inteiro);
  • c é o incremento (inteiro; pode ser 0 em versões multiplicativas);
  • m é o módulo (inteiro positivo).
    O gerador produz inteiros X_n no intervalo 0,1,\dots,m-1. Para obter um número real uniforme em [0,1) usa‑se
U_n=\frac{X_n}{m}.

Passo 4

Exemplo concreto e passo a passo (escolher parâmetros pequenos para conseguir fazer manualmente): tome m=9, a=2, c=1 e semente X_0=1. Calculemos alguns termos:
X_1=(2\cdot 1 + 1)\bmod 9 = 3,
X_2=(2\cdot 3 + 1)\bmod 9 = 7,
X_3=(2\cdot 7 + 1)\bmod 9 = 15\bmod 9 = 6,
X_4=(2\cdot 6 + 1)\bmod 9 = 13\bmod 9 = 4,
e assim por diante. Convertendo para uniformes em [0,1):
U_1=\frac{3}{9}=\frac{1}{3}\approx 0,333\ldots,\qquad U_2=\frac{7}{9}\approx 0,777\ldots
Este pequeno exemplo ilustra o mecanismo: iterar a fórmula e normalizar por m.

Passo 5

Propriedades, dicas e cuidados do LCG (aula rápida):
  • Periodicidade: o gerador é determinístico e eventualmentes repete a sequência; o período máximo é m. O teorema de Hull–Dobell dá condições para período completo: (i) \gcd(c,m)=1; (ii) a-1 é múltiplo de todos os fatores primos de m; (iii) se m é múltiplo de 4 então a-1 é múltiplo de 4.
  • Sensibilidade à escolha de parâmetros: escolhas ruins geram sequências com padrões e correlações (por ex., projeções em dimensões maiores mostram grades).
  • Uso prático: LCGs são simples, rápidos e suficientes para simulações simples ou para ensino; NÃO são seguros para criptografia. Para aplicações sensíveis use CSPRNGs (por exemplo, basados em AES ou SHA) ou um LCG como componente de um gerador mais robusto.
  • Como testar a aleatoriedade: baterias de testes (por exemplo, testes NIST SP 800-22, Dieharder) verificam uniformidade, autocorrelação, etc.

Passo 6

Método 2 — Gerador verdadeiramente aleatório por hardware (TRNG). Ideia básica: medir um fenômeno físico intrinsecamente imprevisível e transformar a leitura em bits aleatórios. Exemplos de fontes físicas:
  • ruído térmico (Johnson–Nyquist) de um resistor;
  • jitter de relógio ou pequenas variações de tempo em sinais digitais;
  • colisões de partículas ou decaimento radioativo;
  • ruído óptico em fotodetectores.
    Fluxo geral de um TRNG: sensor → amplificador → conversor analógico‑digital → etapa de “whitening”/correção → saída de bits.

Passo 7

Como se faz o “whitening” (remoção de viés) — exemplo prático: método de von Neumann. Considere pares de bits extraídos da fonte. Regras:
  • se o par for 00 ou 11, descartam‑se ambos;
  • se o par for 01, produza bit 0;
  • se o par for 10, produza bit 1.
    Exemplo: sequência raw 0\,1\,0\,0\,1\,1\,1\,0 agrupada em pares (01),(00),(11),(10). Aplicando von Neumann: (01)\to 0, (00)\to descarta, (11)\to descarta, (10)\to 1. Resultado whitened: 0,1. Este procedimento elimina viés simples, embora reduza a taxa de bits; existem outros métodos mais sofisticados (hashing, XOR com chaves, extractores de entropia).

Passo 8

Converter bits de TRNG em números com distribuições úteis:
  • para uniforme em [0,1): junte k bits gerados para formar inteiro Y\in\{0,\dots,2^k-1\} e use \displaystyle U=\frac{Y}{2^k}. Exemplo: bits 0110 formam Y=6 e U=6/16=0,375.
  • para outras distribuições: aplique transformações como inversa da função de distribuição (método do inverso) ou Box–Muller para normal. Box–Muller (duas uniforms U_1,U_2):
Z_1=\sqrt{-2\ln U_1}\cos(2\pi U_2),\qquad Z_2=\sqrt{-2\ln U_1}\sin(2\pi U_2),
que produzem duas amostras \mathcal{N}(0,1).

Passo 9

Comparação prática e recomendações (como escolher):
  • se precisar de velocidade e repetibilidade (simulações, Monte Carlo com seed reproduzível): use PRNGs como LCGs, Mersenne Twister, ou CSPRNGs dependendo do rigor; sempre documente a semente X_0.
  • se precisar de imprevisibilidade (criptografia, geração de chaves): use TRNGs ou CSPRNGs bem testados, preferencialmente TRNG para entropia inicial e CSPRNG para expansão segura.
  • boa prática híbrida: usar TRNG para gerar a semente/entropia inicial e depois usar um CSPRNG para gerar muitos bits com segurança e desempenho.

Passo 10

Dicas finais, mãos na massa e incentivo:
  • sempre teste suas sequências com ferramentas de teste aleatório; simples histogramas e testes de autocorrelação já detectam problemas básicos;
  • pratique implementando o LCG pequeno à mão (como no Passo 4) para entender o ciclo; depois experimente parâmetros reais (por ex., Park–Miller com a=16807 e m=2^{31}-1);
  • se a prova pedir um procedimento rápido para gerar n números uniformes, descreva a fórmula do LCG e como normalizar por m, ou descreva um TRNG em alto nível (sensor → ADC → whitening). Você consegue — respira fundo e resolve passo a passo.

Resposta

Gerador congruencial linear (LCG) — gerador pseudoaleatório determinístico, definido por X_{n+1}=(aX_n+c)\bmod m.
Gerador verdadeiramente aleatório por hardware (TRNG) — obtém bits de uma fonte física imprevisível (ex.: ruído térmico) e aplica whitening/postprocessamento.

Exercícios relacionados