1. Caro Visitante, por que não gastar alguns segundos e criar uma Conta no Fórum Valinor? Desta forma, além de não ver este aviso novamente, poderá participar de nossa comunidade, inserir suas opiniões e sugestões, fazendo parte deste que é um maiores Fóruns de Discussão do Brasil! Aproveite e cadastre-se já!

Dismiss Notice
Visitante, junte-se ao Grupo de Discussão da Valinor no Telegram! Basta clicar AQUI. No WhatsApp é AQUI. Estes grupos tem como objetivo principal discutir, conversar e tirar dúvidas sobre as obras de J. R. R. Tolkien (sejam os livros ou obras derivadas como os filmes)

"Número de Deus" é 20, dizem matemáticos

Tópico em 'Ciência & Tecnologia' iniciado por Morfindel Werwulf Rúnarmo, 4 Nov 2010.

  1. Morfindel Werwulf Rúnarmo

    Morfindel Werwulf Rúnarmo Geofísico entende de terremoto

    Após anos de tentativas, pesquisadores conseguiram mostrar que é possível resolver em até 20 movimentos o "Cubo de Rubik" - um quebra-cabeça 3D criado em 1974 pelo húngaro Ernõ Rubik - a partir de qualquer arranjo inicial.

    O feito foi realizado pela combinação do poder dos computadores usados pelo Google com alguns insights matemáticos, o que permitiu checar todas as 43 quintilhões de possíveis posições que o cubo pode assumir.

    Este conteúdo é limitado a Usuários. Por favor, cadastre-se para poder ver o conteúdo e participar (não demora e não possui custos)

    Cubo de Rubik, quebra-cabeça 3D criado pelo húngaro Erdõs Rubik em 1974, pode ser resolvido com até 20 movimentos​

    afirmou Tomas Rokicki, programador de Palo Alto, Califórnia, que passou os últimos 15 anos procurando pelo número mínimo de movimentos necessários para resolver qualquer configuração do Cubo de Rubik.

    Esse número mínimo de movimentos é chamado de "Número de Deus", pois nem o Todo Poderoso conseguiria resolver mais rapidamente o quebra-cabeças.

    EXPLORANDO A SIMETRIA

    Para simplificar o problema, Rokicki e colaboradores usaram técnicas de um ramo da matemática chamado teoria de grupos.

    Primeiro eles dividiram todas as possíveis configurações iniciais em 2,2 bilhões de conjuntos, cada um contendo 19,5 bilhões de configurações (2,2 bilhões x 19,5 bilhões = 42,9 quintilhões). O critério da divisão foi a maneira como essas configurações respondiam a um grupo de 10 movimentos possíveis.

    Esse agrupamento permitiu que a equipe reduzisse o número de conjuntos para 56 milhões ao explorar as simetrias do cubo. Por exemplo, virar o cubo de cima para baixo não torna o problema mais difícil, então essas posições equivalentes podem ser ignoradas.

    Isso ainda deixa um vasto número de configurações iniciais para ser checadas. A equipe então desenvolveu um algoritmo para acelerar esse processo.

    BECOS SEM SAÍDA


    Métodos anteriores resolviam cerca de 4.000 cubos por segundo, tentando um conjunto de posições iniciais e determinando se a posição resultante o aproximava da solução. Se não o fizesse, o algoritmo se desfazia desses movimentos e começava de novo.

    O insight de Rokicki foi notar que esses becos sem saída são, na realidade, soluções para um cubo com uma posição inicial diferente. Isso o levou a um algoritmo que conseguia tentar um bilhão de cubos por segundo.

    Uma maneira de entender seu algoritmo (conjunto de regras para solução de um problema) é a seguinte: suponha que a tarefa seja visitar um amigo em uma cidade desconhecida e que você tenha recebido instruções para virar à esquerda ou à direita, mas que as instruções não tenham incluído a posição inicial. Se você seguir as instruções a partir de uma posição inicial qualquer, é improvável que chegue a seu destino. Mas pareando os movimentos direita-esquerda à posição inicial correta o levará ao destino.

    Da mesma forma, o algoritmo da equipe rapidamente pareia movimentos com a posição inicial correta, permitindo a resolução de cada conjunto de 19,5 bilhões de configurações em 20 segundos.

    IMPÉRIO DA COMPUTAÇÃO


    Mesmo a essa velocidade, levaria 35 anos para completar toda a tarefa em um computador pessoal. A solução da equipe foi pedir ajuda ao Google.

    O engenheiro da empresa John Dethridge, em Mountain View, Califórnia, conseguiu acesso aos supercomputadores da empresa para resolver o problema em semanas.

    Sabia-se que algumas configurações iniciais requerem apenas 20 movimentos para serem resolvidas, e alguns matemáticos suspeitavam que nenhuma configuração exigiria mais do que isso. A busca exaustiva da equipe de Rokicki mostra que a suspeita estava correta.

    diz Mark Kambites, um matemático na Universidade de Manchester que não participou do trabalho.
    O trabalho ainda precisa passar pelo crivo da revisão por pares, mas Rokicki ressalta que a pesquisa é uma extensão de um trabalho anterior publicado no periódico "The Mathematical Intelligencer". Naquele trabalho, o "Número de Deus" havia sido reduzido para 22.
    Este conteúdo é limitado a Usuários. Por favor, cadastre-se para poder ver o conteúdo e participar (não demora e não possui custos)
     
  2. Bel

    Bel Moderador Usuário Premium

    Ta, e quais são os movimentos? :dente:
     
  3. Faerie

    Faerie Usuário

    Sim sim..quais são?
     
  4. ARABAEL

    ARABAEL Ema Infame e

    Eu só consigo montar dois lados...aff
     
  5. Snaga

    Snaga Usuário não-confiável!!!

    Será que essa ganha o prêmio de inutilidde científica?

    Imagina quantos anos esse povo não tá estudando pra descobrir isso!!! Sendo que eu conheço gente que resolve o cubo sem computador algum em menos de um minuto!
     
  6. Parthadan

    Parthadan Pirata Autista Bebado e não um

    tá, demora uns três minutos, mas eu consigo..

    e sem computador nenhum..


    mas vamos ver se esse computador faz isso aqui:


    [nomedia="http://www.youtube.com/watch?v=pUdXhhDDnaY"]YouTube - The Multicolored Multitask (Guitar Hero + Rubik's Cube)[/nomedia]
     
  7. Morfindel Werwulf Rúnarmo

    Morfindel Werwulf Rúnarmo Geofísico entende de terremoto

    Isso depende do arranjo dos lados, não é uma constante.
     
  8. dermeister

    dermeister Ent cara-de-pau

    Jamais! A generalização de problemas como o deste cubo leva a benefícios para áreas que você nem imagina =) É o mesmo caso do Problema do Caixeiro Viajante, que é aplicado em zilhões de áreas -- exceto traçar rotas para caixeiros viajantes!

    Aos programadores: Falando no caixeiro, vocês já tentaram imaginar o problema do cubo em termos da teoria de grafos? O universo de estados possíveis é um grafo olifantescamente grande, cada estado específico do cubo é um nó e cada movimento possível ligando um estado a outro é uma aresta ligando os respectivos nós. O problema de encontrar o menor número de movimentos entre um estado qualquer e o estado "cubo resolvido" equivale a encontrar o caminho mínimo entre estes nós. Não é prático usar essa técnica para resolver o cubo (o tamanho do grafo torna absolutamente inviável), mas é curioso imaginá-lo desta forma :)
     
    • Gostei! Gostei! x 1
  9. Conan

    Conan Cavaleiro Pendragon

    Pois é. pra vc ter um idea de exemplo pratico, é bem aplicavel a grafos, q são utilizados no sistema q controla com eficiencia os sinais de uma malha viaria por exemplo.

    Isto so aplicado ao cubo em si, afora os conceitos criados em cikma do algoritimo, q são uma ganho absurdo na ciencia da computação.

    E eu consegui montar o cubo, mas depoiis de 20 anos, hahahaha

    Pior q durante uns 12 anos, eu fiquei com so dois cubos faltando, hahaha

    sabia o inicio da combinação dos tres ultimos conjutnos de movimento, ai estava explicando só o movimento em si pra uma amiga minha, pra ela tentar sem estragar todo o resto, quando derepente completei o cubo.

    fiquei olhando perplexo, sem saber direito como tinha finalizado.

    ai desfiz tudo e passei mais uma semana ate conseguir direito, hahahahaha
     

Compartilhar