Ferramentas do usuário

Ferramentas do site


prog2:geracao_de_numeros_aleatorios

Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

Link para esta página de comparações

Ambos lados da revisão anterior Revisão anterior
prog2:geracao_de_numeros_aleatorios [2019/04/04 17:15]
maziero
prog2:geracao_de_numeros_aleatorios [2019/04/09 13:33] (atual)
maziero
Linha 1: Linha 1:
 +====== Geração de números aleatórios ======
 +
 +Números aleatórios são muito importantes em várias áreas da informática,​ como jogos, simulações e na geração de chaves criptográficas. Um gerador de **números pseudoaleatórios** (PRNG - [[https://​en.wikipedia.org/​wiki/​Pseudorandom_number_generator|Pseudo Random Number Generator]]) é um algoritmo que gera uma sequência de valores aparentemente aleatórios. A sequência de números gerada por um PRNG não é realmente aleatória, porque pode ser reproduzida caso seja usado o mesmo valor inicial, usualmente chamado de "​semente"​ (//​seed//​).((A reprodução da sequência pseudoaleatória não é um //bug//, mas uma característica útil, caso se deseje repetir os valores usados em uma simulação,​ ou repetir os passos que levaram o software a um erro, por exemplo.))
 +
 +[[https://​www.random.org/​analysis/​|{{https://​www.random.org/​analysis/​dilbert.jpg}}]]
 +
 +===== Congruência linear =====
 +
 +Uma das abordagens mais simples para a geração de números pseudoaleatórios são os **geradores congruentes lineares** ([[https://​en.wikipedia.org/​wiki/​Linear_congruential_generator|LCG]]),​ que são definidos através da seguinte fórmula:
 +
 +> x<​sub>​i+1</​sub>​ = (A · x<​sub>​i</​sub>​ + C) mod M
 +
 +onde "​x<​sub>​0</​sub>"​ é o valor inicial (semente), A e C são parâmetros inteiros, M é o tamanho do espaço de valores aleatórios possíveis e "​mod"​ é o resto da divisão inteira.
 +
 +Por exemplo, escolhendo-se A=40.692, C=127, M=10.000.000 e x<​sub>​0</​sub>​=0,​ será gerada a seguinte sequência de números pseudoaleatórios:​
 +
 +> x<​sub>​0</​sub>​ = 0
 +> x<​sub>​1</​sub>​ = 127
 +> x<​sub>​2</​sub>​ = 5168011
 +> x<​sub>​3</​sub>​ = 6703739
 +> x<​sub>​4</​sub>​ = 8547515
 +> x<​sub>​5</​sub>​ = 5480507
 +> x<​sub>​6</​sub>​ = 2790971
 +> x<​sub>​7</​sub>​ = 192059
 +> x<​sub>​8</​sub>​ = 5264955
 +> x<​sub>​9</​sub>​ = 1548987
 +> ...
 +
 +<note warning>
 +Os geradores congruentes lineares são considerados fracos, por serem facilmente previsíveis. Por isso, **não devem ser usados** em aplicações críticas, como a criptografia.
 +</​note>​
 +
 +===== Atividade =====
 +
 +==== a) Implementação da biblioteca ====
 +
 +Construa uma biblioteca //​LC-Random//​ para gerar números inteiros pseudoaleatórios usando o algoritmo de congruência linear; a interface dessa biblioteca é definida pelo seguinte arquivo de cabeçalho (que **não deve ser alterado**):​
 +
 +<code c lcrandom.h>​
 +// ATENCAO: ESTE ARQUIVO NAO DEVE SER ALTERADO!
 +
 +#ifndef __LCRANDOM__
 +#define __LCRANDOM__
 +
 +// calcula e devolve um valor pseudoaleatório
 +unsigned long lcrandom () ;
 +
 +// define o valor inicial (semente) da sequência de aleatórios
 +// (inicialmente zero (0) por default
 +void lcrandom_seed (unsigned long s) ;
 +
 +// informa o valor máximo que pode ser gerado (o mínimo é sempre zero)
 +unsigned long lcrandom_max () ;
 +
 +// modifica os parâmetros da equação do gerador; por default
 +// devem ser usados: A=40.692, C=127 e M=10.000.000
 +void lcrandom_parms (unsigned long A, unsigned long C, unsigned long M) ;
 +
 +#endif
 +</​code>​
 +
 +<note important>​Caso a função ''​lcrandom_parms''​ não seja invocada, a implementação deve usar os valores //default// dos parâmetros A, C e M definidos no exemplo acima.
 +</​note>​
 +
 +Dicas para a implementação:​
 +
 +  * Os valores da semente, de x e dos parâmetros A, C e M são parte do **estado interno** da biblioteca, por isso devem ser implementados como variáveis globais dentro do arquivo ''​lcrandom.c''​.
 +  * A biblioteca apenas calcula, atualiza e devolve valores; por isso, **nenhuma função de entrada/​saída** (''​printf'',​ ''​scanf'',​ etc) deve ser chamada dentro da implementação de suas funções (a não ser para produzir eventuais mensagens de erro).
 +
 +==== b) Geração de histograma ====
 +
 +A distribuição dos valores produzidos por um gerador de números aleatórios pode ser avaliada visualmente através de um [[http://​www.portalaction.com.br/​estatistica-basica/​16-histograma|histograma]]((existem diversas outras métricas melhores para avaliar a qualidade de um PRNG, algumas delas são descritas [[https://​www.random.org/​analysis/​|nesta página]])).
 +
 +Escreva um programa C para gerar um histograma dos valores aleatórios produzidos por sua biblioteca.
 +
 +Para isso:
 +
 +  - gere 10<​sup>​6</​sup>​ valores aleatórios no intervalo [0...99] (use ''​lcrandom() % 100''​);​
 +  - conte quantas vezes cada número foi gerado;
 +  - normalize (i.e. ajuste) as contagens para intervalo [0..100], aplicando uma regra de três às contagens obtidas, na qual a maior contagem corresponde a 100;
 +  - plote o histograma resultante em um gráfico em modo texto; no eixo vertical estão os valores possível (0 a 99, neste exemplo); no eixo horizontal estão as frequências de ocorrência normalizadas.
 +
 +Exemplo simplificado de histograma em modo texto (cada ''​*''​ vale 2 unidades):
 +
 +     ​0 ​  ​10 ​  ​20 ​  ​30 ​  ​40 ​  ​50 ​  ​60 ​  ​70 ​  ​80 ​  ​90 ​  100
 +     ​+----+----+----+----+----+----+----+----+----+----+
 +   0 |*****************************
 +   1 |**************************************************
 +   2 |****************************************
 +   3 |******************************************
 +   4 |***********************************
 +   5 |*******************************
 +   6 |****************************
 +   7 |******************************
 +  ...| (linhas omitidas)
 +  98 |**********************************
 +  99 |***********************************************
 +     ​+----+----+----+----+----+----+----+----+----+----+
 +
 +==== c) Cálculo de período ====
 +
 +O **período** de um PRNG corresponde à quantidade de valores gerados por ele antes de começar a repeti-los, para uma dada semente. Por exemplo, para uma semente x<​sub>​0</​sub>​=0,​ um PRNG gera a seguinte sequência, cujo período é 16 (pois são gerados 16 valores distintos antes de repetir o 78):
 +
 +> 0 2233 491 11 7219 **7801** 31 446 9876 831 6159 43259 63 38321 1126 43674 **7801** 31 446 9876 831 ...
 +
 +Escreva um programa C para calcular o período do gerador implementado em sua biblioteca, a partir de x<​sub>​0</​sub>​=0.
 +
 +<note tip>
 +Para os valores default de (A=40.692, C=127 e M=10.000.000),​ o período do gerador vale 62.503.
 +</​note>​
 +
 +==== d) Tudo de novo, com novos parâmetros ====
 +
 +Repita o cálculo do histograma e do período usando valores melhores para os parâmetros A, C e M do gerador: A = 1.103.515.245,​ C = 12.345 e <​del>​M = 2.147.483.648 (2<​sup>​31</​sup>​)</​del>​ M = 1.073.741.824 (2<​sup>​30</​sup>​) - valores inspirados de [[https://​en.wikipedia.org/​wiki/​Linear_congruential_generator|LCG]].
 +
 +<note tip>
 +Para esses valores de A, C e M, o período do gerador deve ser igual a M.
 +</​note>​
 +
 +<note important>​
 +Caso encontre erros do tipo ''​relocation truncated to fit: R_X86_64_PC32 against symbol ...''​ ao compilar seu código, experimente usar as opções ''​-fPIC''​ ou ''​-mcmodel=medium''​ na linha de compilação. Esses erros podem ocorrer no cálculo do período, caso um vetor muito grande.
 +</​note>​
 +
 +==== Entregáveis ====
 +
 +Arquivos a entregar ao professor:
 +
 +  - ''​lcrandom.c''​ : implementação das funções do gerador de aleatórios;​
 +  - ''​histograma-1.c''​ : implementação do histograma do gerador com os valores default de A, C e M;
 +  - ''​histograma-2.c''​ : idem, com os valores melhores de A, C e M;
 +  - ''​periodo-1.c''​ : implementação do cálculo de período do gerador com os valores default de A, C e M;
 +  - ''​periodo-2.c''​ : idem, com os valores melhores de A, C e M.
 +
 +<note important>​
 +**Lembre-se**:​
 +  * Identificar **TODOS** os seus arquivos (comentário com nome completo e GRR na primeira linha de cada arquivo).
 +  * Compilar com a opção ''​-Wall''​ e resolver todos os //​warnings//,​ pois eles penalizam a nota.
 +  * Comentar seu código adequadamente (código sem comentários é penalizado).
 +</​note>​
  
prog2/geracao_de_numeros_aleatorios.txt · Última modificação: 2019/04/09 13:33 por maziero