Conteúdo principal
Tempo atual:0:00Duração total:8:42

Transcrição de vídeo

agora eu tenho um relatório de que enviaram um novo governo a marte nós somos responsáveis por fazer uma coisa que está programando algoritmo dentro do rio verde que verifica se os números são primos digamos que nosso rio verde está se comunicando usando rsa ele precisa de um algoritmo dentro que pode fazer um teste de primaridade quando você cria um governo qualquer coisa para ir para o espaço você tem que ser muito eficiente em todos os sentidos os componentes utilizados deve ser muito leves a quantidade de energia que todos sub sistemas usam tem que ser mínimo você tem que economizar energia em massa em todos os pontos do processo de design então nosso trabalho é o seguinte temos que ser capazes de lidar com números desse tamanho e temos que fazer isso muito rápido se nós demos uma pequena entrada digamos que apenas 90 ele deve ser capaz de calcular quase tão rápido como esse número inteiro conforme entrada cresce não queremos que haja uma diminuição perceptível analisadas perguntas dos usuários ou as idéias que usuários têm que foram realmente boas de um ponto de vista matemático estamos verificando se n é primo composto do nome do n pense nesse espaço de todos os cenários possíveis se ele for sem esse espaço de 2 para 100 o que o nosso algoritmo fácil pesquisar esse espaço pensem em algoritmo procurando um espaço em cada ponto ele está perguntando pense nisso como um passo um passo primitivo ele está fazendo uma pergunta e é na verdade um teste para saber se o composto digamos que esse é um número a diríamos no método de teste de visão e não é divisível por a nós apenas tentamos isso deixamos que aí há aqui tentam dividir n poderá rever sua reserva o que significa que a divisor de n e dizemos a sabemos 100% levantamos a bandeira e temos 100% de certeza que é composto caso contrário a cada passo não é completamente certa pode ser primo mas não não temos certeza que continuamos procurando até chegarmos ao fim lembre se da sua parede neste caso está na raiz quadrada dn a pior situação ocorre quando ele é primo nós pesquisamos todos os caminhos para reis quadrados dn então podemos dizer a ele é primo e temos 100% de certeza no caso de n eu mesmo múltiplo de dois primos 767 com 49 se jogarmos 49 nosso algoritmo ocorre pior caso nós percorremos todo o caminho até a raiz quadrada dn então vamos para o primeiro conjunto de perguntas por exemplo a quarta dimensão pergunta uma vez que exclui 2 como não divisível em seguida todos os múltiplos de dois poderiam ser descartados ou mesmo para 345 e etc isso realmente é um ponto importante do nosso antigo algoritmo que calcula a um passo de cada vez nós poderemos estar usando padrões que conhecemos sobre números compostos como que sabemos com certeza se o número é divisível por dois então é composto de dois então 2 o nome do primo então podemos dizer que quatro é composto de cinco aqui sinto muito por isso quatro seis oito dez e em vez disso podemos dar um passo como esse 3 579 uma categoria de perguntas todos tentam reduzir esse espaço eliminamos todos os números pares agora o espaço de busca em vez de ser da terra esquadra da gnr raiz quadrada dn dividido por dois podemos encontrar outros padrões em números compostos para tentar reduzir ainda mais outro tipo de questão diz respeito ao caso onde encontramos uma testemunha composta isto é nós encontramos um aqui nos permite dizer ó sabemos que ele é composto lula disse que não sairia do loop logo que o teste de personalidade desse falso em algum ponto sim isso é totalmente correto e algo que eu quero fazer assim que estivermos fazendo uma busca com passos definidos por qualquer padrão que estejamos usando encontramos uma testemunha composta e significa que ele passou no teste dizemos com 100% de confiança que deve parar antes nós paramos e dizemos nós terminamos não vamos continuar a procurar essa parada precoce é boa exceto que não nos ajuda no pior dos casos que quando n primo nesse caso a interrupção nos ajudar na agora podemos visualizar como essas melhorias permitem reduzido espaço assim impedindo que sejam feitas muitas verificações dentro do computador e dependendo do seu computador vai reduzir a quantidade de tempo que leva agora eu posso mostrar a visualização que eu montei que nos permite comparar dois algoritmos baseados em quantos passos ocorrem durante a sua execução à esquerda está algoritmo acho que a divisão por teste que verifica a partir de 2 para a raiz quadrada dn à direita está algoritmo b que é digamos o nosso coritiba melhorado nesse caso eu tenho aplicado se a seleção divisível por dois para fazermos metade do número de paz eu também teme nenhum no início deste algoritmo b não é perfeito eu estou apenas aplicando algumas modificações do usuário para que possamos ver o que acontece agora vou brincar com isso pra mostrar pra vocês aqui vemos conforme de su temos algoritmo a temos a saída será composta o primo no fundo você verá o número de passos a primeira coisa a notar é no lado direito qualquer outro número leva apenas um passo nós sabemos por que isso acontece se for um número par como esse ele vai sair nosso velho algoritmo levou 314 paz nosso novo algoritmo só deu um passo porque ele verifica se ele é divisível por dois isso parece ser uma boa utilização no entanto à medida que construímos a nossa entrada você perceberá que os passos aumento ea barra cresce e se torna vermelha uma vez que nos aproximamos da região onde estamos indo colidir essa linha vermelha até aqui é o limite dos passos se a barra bate lá nós falhamos o que significa que o nosso rovida quebrar nesse caso o navegador vai realmente quebrar vou tentar chegar perto dele estou perto dele agora está correndo muito lento pode sentir que o computador está prestes a falhar observe que o algoritmo melhorado levou apenas dois passos mas lembre se do pior caso tem alguns números primos grandes alvos aqui por exemplo temos que ser capazes de lidar com esse caso nós não sabemos o que estamos jogando em nosso algoritmo se eu jogar num grande primo veja o que acontece o algoritmo b como se sabe está tomando metade do número de passos no pior caso mas ele ainda está usando muitos passos aqui porque é o pior caso certo estamos chegando perto de quebrar que esse não é um prêmio muito novo ainda temos nesse caminho pelo menos 15 dígitos quando eu coloco esse nome do primo de 12 dígitos em nosso ritmo vamos ver o que vamos ver o que acontece está lento vai falhar olha só o que aconteceu ambos os algoritmos ficam bem em cima do limite não funcionou nossa operação no algoritmo ainda não está boa o suficiente mas agora temos o entendimento do que estamos tentando melhorar que é o número de passos no pior dos casos temos também essa ferramenta legal que nos permite visualizado com rápida está crescendo com rápido o número de passos cresce conforme entrada cresce abaixo eu vou explicar como configurando assim você pode configurar o seu algoritmo e compará lo com cenário de base e ver muito melhor o que você pode fazer