estatuetas maravilhosas
O lendário Tetris foi criado na década de 80 do século passado por Alexey Pajitnov. Matemático
Pajitnov lançou uma das primeiras versões do jogo no microcomputador soviético "Electronics-60"
O objetivo do Tetris é mover e girar caindoformas geométricas para formar linhas completas na parte inferior do campo de jogo, marcando pontos. Do ponto de vista prático, este é um jogo de velocidade de reação e concentração, mas os matemáticos olham para isso de um ângulo diferente. Os cientistas analisaram a complexidade computacional do algoritmo Tetris e determinaram que ele pertence à classe NP-completo - polinômio não determinístico; não existem algoritmos de solução eficazes para essas coisas.
O principal problema é que a quantidade depara encontrar uma solução para o cálculo cresce exponencialmente com o aumento do número de variáveis (tamanho do problema). Por exemplo, se houver quatro parâmetros, serão necessárias 16 iterações e, se 100, 2 ^ 100, que é mais do que átomos no Universo (!). Um computador típico, quando devidamente ajustado, pode fazer vários bilhões dessas iterações por segundo. Conseqüentemente, ele pode resolver facilmente pequenos problemas NP por enumeração e, quando as variáveis se tornarem visivelmente maiores que 15, ele interromperá a resolução.
Quanto ao Tetris.O tamanho da tarefa do jogo clássico é pequeno: em uma etapa separada, há uma paisagem atual no vidro (campo de jogo) - este é um parâmetro, não afeta significativamente a quantidade de cálculos. Há informações sobre a figura atual e a próxima - são dois grupos de variáveis: para cada figura há no máximo quatro (embora para um quadrado - apenas uma) orientações no espaço e no máximo 10 coordenadas do "pouso" de as figuras. Cada movimento tem 40 estados, dois tem 1.600, não tem mais informação, isso é um pequeno problema NP. Embora o Tetris possa ser complicado: aumente o número de células para 100 e certifique-se de que o jogador saiba não apenas qual será a próxima figura, mas também uma centena das próximas, então haveria problemas.
Você também não conhece outros jogos NP-completospor boato: caça-minas, sudoku, tag e até uma versão não comercial de Super Mario. Apesar da simplicidade das suas regras, sob certas condições a sua dimensão aumenta, o computador não consegue oferecer uma solução ideal. Por que os matemáticos se importam? Porque escolher a melhor rota, otimizar um processo ou cronograma também são problemas da classe NP.
Clássico "Mario" ficou assim
Os jogos de lógica são um campo de testes extremamente conveniente paratestar algoritmos e sua implementação de software. Os quebra-cabeças são na maioria das vezes “puros”, sem vários tipos de exceções às regras inerentes aos problemas práticos. O espaço de estados de tais problemas tem uma dimensão ajustável e as propriedades não mudam quando dimensionadas (por exemplo, tags 2x2, 4x4, 3x6). Todos os estados são descritos da mesma maneira. A descrição matemática dos quebra-cabeças, via de regra, também não é tão complexa quanto a dos problemas da vida.
O tempo dos brinquedos "quânticos"
O mesmo problema com uma mochila (como colocar mais coisasem um espaço limitado) lembra bastante um jogo de Tetris, e o resultado efetivo será útil para as empresas de logística, pois lhes permitirá não desperdiçar recursos. Se um algoritmo “polinomialmente rápido” for encontrado para qualquer um desses problemas ou jogos, então qualquer outro problema da classe NP poderá ser resolvido com a mesma “rapidez”. Em teoria, os computadores quânticos ajudarão nisso, mas até agora existem apenas protótipos desses computadores do futuro. Em 2018, um novo conceito foi até inventado para descrever o estado atual da produção de processadores quânticos - a era NISQ (era quântica de escala intermediária barulhenta), ou a época das tecnologias subquânticas.
Enquanto os cientistas estão trabalhando para melhorar o quantumprocessos, os executivos da empresa procuram análogos modernos que ajudem a otimizar o trabalho de produção. Tal “substituto” tornou-se algoritmos de inspiração quântica que encontram uma solução ideal de 95-99% em computadores convencionais. Na Rússia, o QuSolve está fazendo isso - as tarefas nas quais a empresa está trabalhando pertencem à classe NP e os matemáticos desenvolvem e aprimoram algoritmos para resolver problemas de negócios. No QuSolve, para testar seu próprio solver (solver), eles usaram tags, que ajudaram a encontrar alguns erros no algoritmo e a fazer adições à interface do pacote de software.
Será que os cientistas modernos não estão realmente fazendo nada além deVocê está pensando em como melhorar e otimizar tudo? Claro que não. Nas horas vagas, eles continuam inventando jogos. Os desenvolvedores já conseguiram transformar a maioria dos jogos em NP, adicionando um pouco da magia dos fenômenos físicos quânticos.
Foi assim que as tecnologias quânticas surgiram nos últimos 10 anos.damas, batalha marítima quântica e jogo da velha quântico. O xadrez quântico ganhou especial popularidade, onde até torneios são realizados, e o campeão recebe o título de grande mestre. A maioria dos novos "jogos quânticos" são construídos com base no princípio fundamental da mecânica quântica - superposição.
Por exemplo, as peças de xadrez podem estar emvários lugares no tabuleiro ao mesmo tempo, o que torna mais difícil defender e atacar - isso torna o jogo imprevisível e espetacular. Em 2016, eles até filmaram um curta-metragem mostrando uma partida de xadrez quântico entre Stephen Hawking e o ator Paul Rudd, mais conhecido por seu papel como Homem-Formiga no Universo Cinematográfico Marvel.
Captura de tela do jogo. Era assim que o tabuleiro online parecia no jogo entre Hawking e Rudd. Então o ator venceu o lendário físico
Não sabemos se esses jogos serão assim no futurotão comuns quanto o jogo da velha, o tetris e o tag, mas certamente inspirarão os matemáticos a criar algoritmos exclusivos para resolver problemas práticos de negócios e desenvolver tecnologia. Não há dúvida sobre isso.
Consulte Mais informação:
A forma da Via Láctea não é nada do que pensávamos o tempo todo, descobriram os cientistas
Duas super-Terras encontradas no limite da zona habitável: uma delas tem temperatura confortável
Encontrado um buraco negro que destrói um registro estelar perto da Terra