Conteúdo principal
Tempo atual:0:00Duração total:5:06

Transcrição de vídeo

primeiro vamos introduzir alguns conceitos para esse novo tipo de algoritmos randômicos que aceita uma entrada n se ele é primo nosso algoritmo retorna primo com 100% de certeza e nunca rotular a esse número como composto no entanto se ele é composto resistir a uma pequena chance do erro e ser classificado como pelo caso contrário haverá um - essa pequena probabilidade de erro é de que ele seja corretamente identificado como compôs retiraremos de um universo de número inteiro o mundo inteiro n e colocaremos n a nossa máquina antiga que trabalha com o método de teste de visão onde basicamente estamos todos os valores de 1 até a raiz quadrada dn para saber se algum deles de verde n seria ideal estará apenas os treinos para economizar tempo se a dividir n então sabemos iene é o número composto pois acabamos acharam evidência se não dividir então não tenho certeza temos que incrementar a e testar de novo uma vez que varremos todos os valores possíveis poderemos dizer qn é primo se não tivermos encontrado nenhum divisões mas pra que tanto esforço podemos pegar alguns interrogatórios mente e realizar alguns peças de visibilidades que podem ser entendidos como perguntas aleatórias uma vez que sabemos se algum número n é composto ele deve ter alguns divisor espalhados por aí ele tem no mínimo em divisor e pode provavelmente ter vários de qualquer forma nós podemos o inteiro aleatório a entre 1 ea raiz quadrada de ano então apenas checamos se a dividir n como antes se a dividir n então sabemos com certeza que anne é com gosto achamos uma prova se não acharmos então não aprendemos muito além de que ele pode ser crime por segurança poderia gerar mais alguns as aleatórias e continuar testando talvez depois de 100 mil as geradas poderemos dizer que provavelmente é um prémio com uma certeza digamos 99,9 por 100 por exemplo se é semelhante a um evento do jogo de probabilidades condicional na versão mais simples tentamos adivinhar se a moeda era justa com viciada no caso coroa é como achar utilizando uma residência de moeda justa para é o caso onde vamos desejar que a moeda seja julgado novamente depois de cem casas teremos mais de 90% de certeza então parar e dizer que achamos que a moeda iniciado aqui está um programa que preparei que compara o nosso teste antigo de encontrar pilotos com este novo ele se baseia no programa tchau divisa nos pisos livro do criador dino cujo link está no cabeçalho do programa note que a variável não tios é o número de tentativas aleatórias vamos começar com um valor pequeno por exemplo três nós também o pequeno valor de entrada se eles o treino o algoritmo de divisão randômica sempre responder a emprego mas quando a entrada é composta com esse algoritmo pode se enganar identificar incorretamente como primo contudo podemos corrigir isso aumentando o número de tentativas ea probabilidade do erro diminui agora teremos que as respostas casa mais ou menos e à medida que se testam em conta os maiores o erro cresce novamente então temos que aumentar o número de testes de acordo com o tamanho da entrada dessa forma as saídas dos dois algoritmos para idênticas nós para grandes valores de entrada desses anos de muitos testes aleatórios para que a saída seja preciso então não diminuímos a quantidade de passos necessários e o antigo algoritmo ainda parece melhor isso ocorre porque a taxa de erro do teste de divisão é muito alto nós estamos no caminho certo então precisamos de outro teste precisamos de uma equação que seja rápida de calcular e possa aprovar este número é composto deve acertar não só o inteiro n mas também o inteiro aleatório a então basta o valor como teste assim como foi feito com e desigual