Algoritmos aleatórios (introdução)

RKA4JL - Tenho uma novidade: a NASA disse que haverá um hardware gerador de números aleatórios na sonda que temos acesso. E depois disso, eles fizeram mais um comentário e lembraram que precisamos que nosso algoritmo funcione na prática. Bom, para algo funcionar na prática, isso significa que existe sempre uma possibilidade de erro. Mas, talvez, a possibilidade seja tão pequena que a ignoramos na prática. E se isso parece maluquice, basta perceber que no mundo físico real nada é 100% certo, existe sempre uma chance de erro. Por exemplo, embalagens de chips contêm pequenas quantidades de contaminantes radioativos e quando eles decaem, soltam partículas alfa que podem alterar os bits na memória e talvez mudar o número inesperadamente. Ainda mais interessante: raios cósmicos também podem causar erros de software. Ou seja, nunca poderemos resolver a chance de erro completamente. Eu pedi a NASA qual exatamente seria uma probabilidade de erro aceitável. Eles disseram: "Precisamos garantir que a probabilidade de erro para um dado ensaio é menor que a chance de ganhar na loteria duas vezes seguidas. A chance de ganhar na loteria, digamos, 649 duas vezes seguidas, é 6 vezes 10 elevado a menos 14. Por segurança, arredondamos para baixo e dizemos que nossa probabilidade de erro é de 10⁻¹⁵. Dessa forma, não esperaremos ver um erro e isso pode rodar centenas de milhares de vezes. Agora, minha pergunta é: acessar números aleatórios nos ajudaria a acelerar um algoritmo de decisão como teste de primariedade? Essa é uma pergunta difícil. Então, vamos voltar um pouco e olhar o panorama geral disso. Dado algum conjunto de números de 1 para algum limite N, vamos pensar nisso como um universo de inteiros, nós podemos sempre dividir uma coleção em outras duas partes. Um problema de decisão pode realmente ser pensado como uma partição em duas partes. Por exemplo, dado o número "n", onde "n" é menor que 100, isso será verdadeiro para todos os inteiros menores que 100. Isto é uma coleção e não para todos os outros, que seriam outra coleção. OK. Então, vamos agora focar no reconhecimento de primos com a decisão. Idealmente, o que gostaríamos é um critério simples de computador que todos os primos satisfaçam e nenhum dos compostos satisfaça. Se conhecemos um padrão simples que descreve a localização de todos os primos, e somente primos, então, dado um número "n", nós podemos simplesmente verificar se "n" segue o padrão ou não. O problema é que ainda não existe um padrão computacional simples para todos os primos e não-compostos, ou todos os compostos e não-primos. Mas conhecemos testes rápidos para a maior parte dos números compostos. Por exemplo, um simples critério computado poderia ser um teste para números pares e todos os números pares são divisíveis por 2. Isso é rápido, mas podemos dizer se algo é par apenas olhando o último dígito. E mesmo que "n" cresça, o problema não ficaria mais difícil. Nós apenas olhamos aquele último dígito, também conhecido como "bit de menor importância". Feito isso, podemos usar esse teste de nivelamento como um teste composto de baixa qualidade no qual temos um algoritmo que aceite nossos números inteiros N e tudo que nosso algoritmo faz é checar se ele é par. Se ele for par e maior que 2, então nós sabemos com 100% de certeza que é composto, pois temos uma prova. Pense em 2 com o nosso testemunho composto. No entanto, se não for par, então não temos certeza. Se for ímpar pode ser primo, uma vez que todos os primos são ímpares. Ou pode ser um dos vários compostos que são ímpares, como 9 ou 15. Essa região massiva de números ímpares compostos faz este teste ser difícil. Para ser mais claro, vou redesenhar isso. Um número "n" pode ser primo ou composto. Se "n" é primo, nosso algoritmo irá dizer "primo" 100% das vezes, uma vez que não há primos pares maiores que 2. E ele nunca dirá "primo" quando um número composto é fornecido. Entretanto, se "n" é composto, nosso algoritmo irá dizer "composto" 50% das vezes e primo 50% das vezes. Isso significa que se nosso algoritmo falar que "n" é composto, significa que encontrou provas de que o número é composto. Entretanto, se nosso algoritmo disser "primo", nós sabemos que existe uma inaceitável e grande chance de erro. Até agora nossa estratégia lidou com esse grande e inaceitável erro por interações. Vamos desenhar o fluxo de nossa máquina. Dado um "n", nossa máquina faz uma série de testes de divisão iniciando com "a" sendo 2. Ele pergunta se "a" divide "n". Se não divide "n", então podemos eliminar toda essa região. Então, ele pergunta a próxima questão: "n" é divisível por 3? Se não, então eliminamos aquela seção toda. "n" divide por 5? 7? E assim, sucessivamente. Note que são conjuntos distintos, os quais, gradualmente, preenchem todos os compostos possíveis. Agora, se nunca respondemos "sim" durante o caminho, então temos uma prova que "n" é composto. Tudo até aqui é nossa evidência. Nós paramos a saída de compostos "n" de nosso algoritmo. Caso contrário, continuamos tentando até esgotarmos todos os compostos possíveis, até chegarmos a raiz quadrada de "n", pois sabemos que cada número composto "n" precisa ter um fator menor que, ou igual, a raiz quadrada de "n". Isso nos leva a questão final de nosso algoritmo. Se nenhuma testemunha foi encontrada e "a" é maior que a raiz quadrada de "n", então, de repente, temos uma prova e interrompemos uma saída de primos. Perceba que temos dois caminhos de saídas através de nosso algoritmo. Ambos representam a prova de segurança de que "n" é primo ou composto. Quando "n" é primo, nós tentamos todos os divisores possíveis e, basicamente, aplicamos a regra a todos. E essa é a nossa prova de que "n" é primo. O problema com essa estratégia é que o nosso valor de teste "a", no mínimo, requer ciclos através de cada primo iniciando em 2 até a raiz quadrada de "n". Conforme "n" cresce, o número de primos também cresce. Isso resulta em uma enorme quantidade de interações no pior dos casos, tal como quando nós fornecemos um primo para nosso algoritmo. Olhando o panorama geral agora, veja que estamos fornecendo prova de que "n" é primo, prova que nós sabemos que não precisamos. Ninguém disse que precisamos provar isso. Precisamos apenas ter 99,999...% quinze noves % de certeza. Então, nós precisamos pensar sobre o teste composto que está sendo usado em nosso algoritmo. Lembre-se: uma divisão de julgamento rápido nos testes de primariedade, até agora, tentaram usar padrões de primos como 6k, ou todos os primos são da forma 6k mais ou menos 1 para facilitar o caminho dos primos e eliminar muitos dos compostos ao mesmo tempo. Lembre-se: um teste como este pode ser transformado em teste composto, isto é, dado que algum número inteiro "n" é da forma 6k ± 1, então podemos dizer que, provavelmente, é um primo. Mas existem muitos compostos ainda que seguem esse padrão. Isso não inclui apenas primos. Somente todos os primos e alguns compostos. E nós podemos pensar nesses compostos extras como um vazamento, e esse vazamento é a nossa fonte de erro. Agora, se nós invertemos e verificarmos se "n" não é do tipo 6k ±1, então podemos dizer com 100% de certeza que é um número composto. Assim, o vazamento é a nossa fonte de erro no lado dos primos. Mas nesse caso é inaceitável, não é um erro que pode ser ignorado. Existe uma chance muito maior. Nós precisamos definir um novo composto testando um procedimento que é capaz de reduzir esse espaço e fazer a chance de erro ser ignorada. Isso quer dizer que precisamos rever como nós podemos diminuir erros com interações. Acho que agora vocês poderiam colocar suas ideias abaixo em relação aos tipos de testes que desejamos realizar e também, mais importante, seria: "como um gerador de número aleatório pode nos ajudar?"