Conteúdo principal
Tempo atual:0:00Duração total:9:23

Transcrição de vídeo

tem uma novidade a nasa disse que haverá um hardware gerador de números aleatórios na ação daqui temos acesso e depois disso eles fizeram mais um comentário e lembraram que precisamos que nosso algoritmo funciona na prática bom para algo funcionar na prática significa que existe sempre uma possibilidade de erro mas talvez a possibilidade seja tão pequena que ignorando na prática exige parece maluquice basta perceber que no mundo físico real nada é 100% certo ele sempre uma chance de erro por exemplo embalagem xix contém pequenas quantidades contaminantes radioativos e quando eles de caen soltam partículas alfa que podem alterar os bits na memória 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 há nada qual exatamente seria uma probabilidade de erro aceitado eles disseram precisamos garantir que a probabilidade de amparar 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 é seis vezes 10 elevado a menos 14 por segurança arredondamos para baixo e dezembro que nossa probabilidade de erro é de dez a menos 15 dessa forma não esperaremos ser um erro e isso pode rodar centenas milhares de vezes agora minha pergunta é acessar números aleatórios nos ajudaria a acelerar um algoritmo de decisão como teste primariedade essa é uma pergunta difícil então vamos voltar um pouco e olhar o panorama geral disso dado algum conjunto de número de um para um limite n vamos pensar nisso como um universo de inteiros nós podemos sempre dividir uma coleção em outras duas partes um programa de decisão pode realmente é pensado como uma partição em 2 partes por exemplo dado o número n onde eliminar que sem isso será verdadeiro para todos os inteiro menos 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 e realmente o que gostaríamos um critério simples de computador que todos os primos satisfação e nenhum dos compostos satisfaço se conhecendo no padrão simples que descreva localizações todos os primos e somente primos então dado um número 1 n nós podemos simplesmente verificar se ele segue 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 de não prêmios 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 ao dividir vez por 2 isso é rápido mas podemos dizer se algo é para apenas olhando o último dígito e mesmo que ele cresça o problema não ficaria mais difícil nós apenas olhamos aquele último dígito também conhecido como vídeo 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 nós algoritmo faz é checar celepar se ele for parar e maior que 2 então nós sabemos com 100% de certeza que é composto por temos uma prova em si em 2 com o vosso testemunho composto no entanto se não for para então não temos certeza se for inter pode ser primo uma vez que todos os prêmios são ímpares ou pode ser um dos vários compostos que são ímpares como óbvio 15 essa região massiva de números ímpares compostos faz este teste ser difícil para ser mais claro vou desenhar isso o número n pode ser primo o composto se ele é primo nosso favoritismo irá dizer primo 100% das vezes uma vez que não há prémios para os maiores que 2 e ele nunca dirá primo quando o número composto fornecido entretanto se ele é composto nosso algoritmo irá dizer composto 50 por cento das vezes e primo 50 por cento das vezes isso significa que esse nosso favoritismo falar que é composto significa que encontrou provas de que o número é composto entretanto se nós favoritismo decerto primo nós sabemos que existe um inaceitável grande chance de erro até agora nova estratégia lidou com esse grande inaceitável erro por interações vamos desenhar o fluxo de nossa máquina da duane nossa máquina faz uma série de testes de divisão iniciando com oa sendo 2 ele pergunta se a dividir m se não dividir n então podemos eliminar toda essa região então ele pergunta a próxima questão é divisível por três se não então eliminamos naquela sessão toda em dividir por cinco sete e assim sucessivamente note que são conjuntos distintos os quais gradualmente preenchem todos os compostos possíveis agora se nunca responderemos sim durante o caminho então temos uma prova que é composto tudo até aqui é nova evidência nós paramos a saída de compostos e neste nosso algoritmo caso contrário continuamos tentando até derrotamos todos os compostos possíveis até chegarmos a raiz quadrada dn pois sabemos que cada número composto n precisa ter um fator menor que ou igual a raiz quadrada dn isso nos leva a questão final de novo algoritmo nenhuma testemunha foi encontrada ea é maior que a raiz quadrada dn então de repente temos uma prova interrompeu uma saída de prêmios perceba que temos dois caminhos de saídas através do nosso favoritismo ambos representam a prova de segurança de que é primo o composto quando o elétrico nos sentamos todos os divisores possíveis basicamente aplicamos a regra todos e essa é a nossa prova de que é prime o problema com essa estratégia é que o nosso valor de teste há no mínimo requer ciclos através de cada primo iniciando em dois até a raiz quadrada dn conforme ele cresce número de prêmios também cresce isso resulta em menor quantidade de interações no pior dos casos tal como quando nós fornecemos um primo para nosso algoritmo olhando panorama geral agora vejo que estamos fornecendo prova de que ele é primo prova que nós sabemos que não precisamos de ninguém diz que precisamos provar isso precisamos a pena ter 99,999 15 9% de certeza então nós precisamos pensar só 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 tentarão usar padrões de tribos com seis carros ou todos os prêmios são da forma 6k mais ou menos um para facilitar o caminho dos trilhos 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 mais ou menos um então podemos dizer que provavelmente é um primo mas existem muitos compostos ainda que seguem esse padrão isso não inclui apenas teremos somente todos os primos de alguns compostos e nós podemos pensar nos compostos extras como um vazamento e esse vazamento é a nossa fonte de erro agora se nós invertemos e verificarmos iene não era o tipo seis khar mais ou menos um então podemos dizer com 100% de certeza que é o número composto assim o vazamento é a nossa fonte de erro no lado dos primos mais 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 eu 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 idéias abaixo em relação aos tipos de testes que desejam realizar e também mais importante seria como gerador de número aleatório pode nos ajudar