|
|
|
|||||
 |
|||||||
|
|
|
|||||
|
|
|||||||
Adalberto Ayjara Dornelles Filho Introdução A cena é bastante comum. Ao ter que escolher entre um laço de fita azul ou vermelha para colocar no cabelo, a menina começa a recitar em voz alta: Ma-mãe man-dou eu es-co-lher es-ta da-qui, mas co-mo sou que-ri-da vou es-co-lher es-ta da-qui! Apontando com o dedo alternadamente para o laço azul e para o vermelho ao ritmo cadenciado das sílabas. O laço escolhido é aquele apontado por último. Certamente o leitor conhece esse procedimento ou outro semelhante com cantigas diferentes. Mas o que tem isso a ver com aritmética modular ou números aleatórios? Quando dois inteiros deixam o mesmo resto ao serem divididos por m, dizemos que eles são congruentes (ou côngruos) “módulo m”. Por exemplo, 15 e 23 são côngruos módulo 4, porque ambos deixam resto 3 quando divididos por 4 (ver [1]). Ao recitar a cantiga, a menina aponta alternadamente para as duas fitas. Como a quantidade de sílabas da cantiga é 27, então a menina escolhe a primeira fita, pois 27 é ímpar, isto é, deixa resto 1, quando dividido por 2. De um modo geral, a fita escolhida será sempre a primeira, caso o número de sílabas da cantiga seja ímpar, e será sempre a segunda, caso o número de sílabas da cantiga seja par. O que ocorreria se fossem três fitas? Como 27 é múltiplo de 3 e, portanto, deixa resto zero quando dividido por 3, a terceira fita será escolhida (não existe fita de ordem zero). Pode-se generalizar o procedimento: se a menina tiver que escolher entre m fitas, se sua cantiga tiver n sílabas, e se n deixar resto k quando dividido por m, então a fita escolhida será a k-ésima se k ≠ 0 e a última se k = 0.
Aleatório versus pseudoaleatório Podemos dizer que a menina está efetuando um processo de escolha. Na concepção infantil, essa escolha é ao acaso, aleatória. Mas como se viu nos exemplos acima, usar o “mamãe mandou ...” não tem nada de aleatório, exceto talvez na escolha de qual será a primeira fita; após essa escolha inicial, o resultado está perfeitamente determinado! Uma escolha mais de acordo com nossa noção intuitiva de aleatória ocorreria se a menina lançasse uma moeda para cima e escolhesse a fita conforme o resultado do lançamento (fita azul para cara e vermelha para coroa, por exemplo). Para o caso de ter de escolher entre m fitas, poderíamos girar uma roleta com m números. Não pretendemos entrar aqui na complicada discussão sobre se isso resultaria em uma escolha “verdadeiramente aleatória” em algum sentido preciso. Muitas vezes usamos programas de computador, como MAPLE, MATLAB, Excel, etc., para gerar números “pseudoaleatórios”. Esses comandos podem ser usados para aplicações simples: na simulação do lançamento de uma moeda ou na geração de entradas em testes de algoritmos, ou em usos mais elaborados, como na resolução de problemas de otimização com algoritmos genéticos ou mesmo em sistemas de criptografia. No entanto, é muito importante que nós professores tenhamos consciência de que os números gerados por esses programas não são aleatórios (em nenhum sentido razoável), mas apenas “aparentemente aleatórios” ou, como se costuma dizer, números “pseudoaleatórios”. E, curiosamente, um dos métodos mais usados para gerá-los não difere muito do processo “mamãe mandou ...” da nossa menina, já que se baseia também na noção de congruência entre números inteiros. Para ilustrar essa questão, consideremos as sequências de valores: (si ) = (4, 4, 2, 4, 5, 6, 1, 1, 2, 6, 3, 4, 6, 6 , 2, ...) (1) (ti ) = (5, 5, 6, 6, 2, 2, 3, 6, 4, 3, 3, 1, 1, 2 ,3, ...) (2) Uma delas mostra a sequência dos valores obtidos em sucessivos lançamentos reais de um dado. A outra mostra os valores obtidos por uma fórmula recursiva que vamos explicar mais adiante. O leitor consegue dizer em qual delas isso ocorre? Deixaremos esse mistério em aberto, por enquanto. As sequências (1) e (2) ilustram como pode ser difícil perceber “a olho nu” se uma dada sequência de números provém de um lançamento supostamente aleatório de uma moeda ou de uma fórmula recursiva perfeitamente determinada. De fato, sequências geradas por fórmulas recursivas podem “passar” em muitos testes estatísticos para aleatoriedade, tornando-se aceitável o seu uso em situações que solicitam “entradas aleatórias”, dentro de certos limites de tolerância. Alguns testes analisam as frequências com as quais os valores da sequência ocorrem, outros analisam a frequência de repetições de valores numéricos. Nesse sentido, uma sequência numérica é dita pseudoaleatória se, embora não sendo “verdadeiramente aleatória”, “passa” em um certo número de testes de aleatoriedade.
Algoritmos geradores de números pseudoaleatórios Embora seja bastante simples lançar moedas e girar roletas, tais processos são inadequados no âmbito computacional, que requer velocidade e reprodutibilidade. Assim, os processos mecânicos (roletas, dados, moedas) devem ser substituídos por algoritmos. São diversos os tipos de algoritmos empregados na geração de números pseudoaleatórios (ver [3]). Aqui vamos tratar apenas do mais usual, o gerador de congruência linear, proposto por Lehmer em 1948 (ver [2]), e que foi um dos primeiros a ter uso efetivo na simulação de variáveis pseudoaleatórias. As propriedades desse gerador foram (e continuam sendo) as mais estudadas, tanto teórica quanto empiricamente. A maior parte da teoria sobre geradores de números pseudoaleatórios toma por base esse tipo de gerador. A ideia é formar uma sequência (xi ), obtida por recorrência, de modo que cada xi (i > 1) é o resto da divisão de axi–1 + c por m, onde as “sementes” a, c, m e x1 são escolhidas previamente. Se c = 0, o gerador é dito multiplicativo. Se c ≠ 0, o gerador é dito aditivo.
Exemplo Se forem utilizados os valores a = 12, c = 0, m = 31 e x1= 9 (ver [2]), obtém-se a sequência (verifique): (xi ) = (9, 15, 25, 21, 4, 17, 18, 30, 19, 11, 8, 3, 5, 29, 7, 22, 16, 6, 10, 27, 14, 13, 1, 12, 20, 23, 28, 26, 2, 24, ...). (3)
Após o termo x30 = 24, a sequência se repete, pois x31 = 9, que é o resto da divisão de 12 × 24 por 31. Observe que todos os valores inteiros de 1 a 30 estão presentes na sequência, porém de uma forma “embaralhada”, aparentemente aleatória. A escolha adequada de a, c e m defi ne características teóricas e empíricas do gerador. O período máximo do gerador é m se c ≠ 0; é m – 1 se c = 0.
Conclusão As versões mais modernas do MATLAB e MAPLE utilizam variações mais complexas do gerador de congruência linear. Recentemente, estudos apontam a viabilidade de construção de dispositivos eletrônicos computacionais para geração de números “verdadeiramente aleatórios” tomando por base algumas características da física quântica. Parece-me intrigante que a “ingênua” cantiga infantil e os “engenhosos” algoritmos computacionais compartilhem o mesmo conceito matemático fundamental: o de resto da divisão de números inteiros. O que o leitor acha? A propósito (já ia me esquecendo...): a sequência (2) foi obtida lançando dados; a sequência (1) foi obtida a partir da sequência (3) fazendo si = 1 + (resto da divisão de xi por 6). Qual é o próximo valor?
Referências bibliográficas [1] COUTINHO, S. C. Números inteiros e criptografia RSA. Computação e Matemática. 2
|
edição. Rio de Janeiro: IMPA – SBM, 2000.