quarta-feira, 21 de janeiro de 2015

O problema do caixeiro viajante ( P versus NP )


Resolução através de números binários...
Por Prof Paulo Godinho em : 01/01/2015 O problema do caixeiro viajante ( P versus NP ) Resolução através de números binários A complexidade computacional é o ramo da Matemática computacional que estuda a eficiência dos algoritmos. Na prática , de nada servirá para nós um algoritmo perfeito se sua implementação computacional irá demorar algumas dezenas , centenas ,...de anos para ser processado .Tarefas relativamente simples ,como produto de dois números com muitos dígitos ,certamente demorará alguns minutos para serem concluidas nos atuais computadores.Entretanto ,se considerarmos que alguns algoritmos necessitam multiplicar números com milhares ,milhões ,...de dígitos esses alguns minutos se transformarão em um tempo excessivamente longo , inviabilizando assim o algoritmo. Atualmente são considerados uma quantidade enorme de problemas NP-completos , mas o mais famoso de todos é o problema do caixeiro viajante . A solução computacional deste problema , por ser ele NP- completo tem como consequências : a existência de algotitmos úteis para uma série de problemas computacionais práticos nas mais diferentes indústrias; destruição de quase todos os setores de segurança eletrônicos do mundo ,como os que ocorrem nas transações comercial,bancárias,..etc. a quebra no sigilo de trocas de informações diplomáticas,governamental,militar , internet,...etc. Vamos supor que temos um computador , capaz de fazer 1 bilhão de adições por segundo.Isso parece uma velocidade imensa , capaz de tudo. Com efeito , no caso de 20 cidades,o computador precisa apenas de 19 adições para dizer o comprimento de uma rota e então será capaz de calcular 10 ( elevado a 9 potênci) / 19 = 53 milhões de rotas por segundo .Contudo ,essa imensa velocidade é um nada frente à imensidão do número 19! = 19 x 18 x 17 x 16 x 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 121.645.100.408.832.000 ;portanto haverá aproximadamente 2,3 x 10 ( elevado a potência 9 ) segundos para completar sua tarefa , o que equivale cerca de 73 anos .A questão ´e que a quantidade ( n - 1 )! cresce com uma velocidade extraordinária , sendo que rapidamente o computador torna-se incapaz de executar o que solicitamos . E ,se esse resultado ou outro qualquer , mesmo com um número com infinito digitos fosse colocado na linguagem do computador , o que aconteceria ? Esse resultado acima dado como exemplo transformamos em uma sequência binária e ficou assim :110.110.000.001.010.111.001.001.100.000.110.100.010.001.111.111.111.111.100 Esta conversão do número inteiro citado acima como exemplo , executanto manualmente e realizado em meia folha de papel a4 durou cerca de 10 minutos . Por Prof de Matemática Paulo Godinho em 01/01/2015 contacto : paulo_godin59@yahoo.com.br cel (91)98209-0792 A complexidade computacional é o ramo da Matemática computacional que estuda a eficiência dos algoritmos. Na prática , de nada servirá para nós um algoritmo perfeito se sua implementação computacional irá demorar algumas dezenas , centenas ,...de anos para ser processado .Tarefas relativamente simples ,como produto de dois números com muitos dígitos ,certamente demorará alguns minutos para serem concluidas nos atuais computadores.Entretanto ,se considerarmos que alguns algoritmos necessitam multiplicar números com milhares ,milhões ,...de dígitos esses alguns minutos se transformarão em um tempo excessivamente longo , inviabilizando assim o algoritmo.
Atualmente são considerados uma quantidade enorme de problemas NP-completos , mas o mais famoso de todos é o problema do caixeiro viajante . A solução computacional deste problema , por ser ele NP- completo tem como consequências :
a existência de algotitmos úteis para uma série de problemas computacionais práticos nas mais diferentes indústrias;
destruição de quase todos os setores de segurança eletrônicos do mundo ,como os que ocorrem nas transações comercial,bancárias,..etc.
a quebra no sigilo de trocas de informações diplomáticas,governamental,militar , internet,...etc.
Vamos supor que temos um computador , capaz de fazer 1 bilhão de adições por segundo.Isso parece uma velocidade imensa , capaz de tudo. Com efeito , no caso de 20 cidades,o computador precisa apenas de 19 adições para dizer o comprimento de uma rota e então será capaz de
calcular 10 ( elevado a 9 potênci) / 19 = 53 milhões de rotas por segundo .Contudo ,essa imensa velocidade é um nada frente à imensidão do número 19! = 19 x 18 x 17 x 16 x 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 121.645.100.408.832.000 ;portanto haverá aproximadamente 2,3 x 10 ( elevado a potência 9 ) segundos para completar sua tarefa , o que equivale cerca de 73 anos .A questão ´e que a quantidade ( n - 1 )! cresce com uma velocidade extraordinária , sendo que rapidamente o computador torna-se incapaz de executar o que solicitamos . E ,se esse resultado ou outro qualquer , mesmo com um número com infinito digitos fosse colocado na linguagem do computador , o que aconteceria ?
Esse resultado acima dado como exemplo transformamos em uma sequência binária e ficou assim :110.110.000.001.010.111.001.001.100.000.110.100.010.001.111.111.111.111.100
Esta conversão do número inteiro citado acima como exemplo , executanto manualmente e realizado em meia folha de papel a4 durou cerca de 10 minutos .
Por Prof de Matemática Paulo Godinho em 01/01/2015
contacto : paulo_godin59@yahoo.com.br
 
 
Postado por às

Nenhum comentário:

Postar um comentário

Assinar: Postar comentários (Atom)

Mensagem

Mensagem

Lições de vida

Cada dia em nossas vidas nos ensina lições que muitas vezes nem percebemos.
Desde o nosso primeiro piscar de olhos, desde cada momento em que a fome bate, desde cada palavra que falamos.
Passamos por inúmeras situações, na maioria delas somos protegidos, até que um dia a gente cresce e começamos a enfrentar o mundo sozinhos.
Escolher a profissão, ingressar numa faculdade, conseguir um emprego...Essas são tarefas que nem todos suportam com um sorriso no rosto ou nem todos fazem por vontade própria.
Cada um tem suas condições de vida e cada qual será recompensado pelo esforço, que não é em vão.Às vezes acontecem coisas que a gente nem acredita.
Às vezes, dá tudo, tudo errado!Você pensa que escolheu a profissão errada, que você mão consegue sair do lugar, ás vezes você sente que o mundo todo virou as costas...Parece que você caiu e não consegue levantar...Está a ponto de perder o ar...Talvez você descubra que quem dizia ser seu amigo, nunca foi seu amigo de verdade e talvez você passe a vida inteira tentando descobrir quem são seus inimigos e nunca chegue a uma conclusão.
Mas nem tudo pode dar errado ao mesmo tempo, desde que você não queira.E aí... Você pode mudar a sua vida!Se tiver vontade de jogar tudo pro alto, pense bem nas conseqüências, mas pense no bem que isso poderá proporcionar.Não procure a pessoa certa, porque no momento certo aparecerá.Você não pode procurar um amigo de verdade ou um amor como procura roupas de marca no shopping e nem mesmo encontra as qualidades que deseja como encontra nas cores e tecidos ou nas capas dos livros.Olhe menos para as vitrines, mas tente conhecer de perto o que está sendo exibido.
Eu poderia estar falando de moda, de surf, de tecnologia ou cultura, mas hoje, escolhi falar sobre a vida!Encontre um sentido para a sua vida, desde que você saiba guiá-la com sabedoria.Não deixe tudo nas mãos do destino, você nem sabe se o destino realmente existe...Faça acontecer e não espere que alguém resolva os seus problemas, nem fuja deles.Encare-os de frente. Aceite ajuda apenas de quem quer o seu bem, pois embora não possam resolver os seus problemas, quem quer o seu bem te dará toda a força necessária pra que você possa suportar e...Confie!
Entenda que a vida é bela, mas nem tanto...Mas você deve estar bem consigo mesmo pra que possa estar bem com a vida.Costumam dizer por aí que quem espera sempre alcança, mas percebi que quem alcança é quem corre atrás...Não importa a tua idade, nem o tamanho de seu sonho...A sua vida está em suas próprias mãos e só você sabe o que fazer com ela...Autor ( Lilian Roque de Oliveira )


twitter

Mapa