Minunate figurine
Legendarul Tetris a fost creat în anii 80 ai secolului trecut de Alexey Pajitnov. Matematician
Pajitnov a lansat una dintre primele versiuni ale jocului pe microcomputerul sovietic „Electronics-60”
Scopul lui Tetris este să se miște și să se rotească în cădereforme geometrice pentru a forma rânduri complete în partea de jos a terenului de joc, punctând puncte. Din punct de vedere practic, acesta este un joc de viteză de reacție și concentrare, dar matematicienii privesc asta dintr-un unghi diferit. Oamenii de știință au analizat complexitatea computațională a algoritmului Tetris și au stabilit că acesta aparține clasei de polinom NP-complet - nedeterminist; nu există algoritmi eficienți de soluție pentru astfel de lucruri.
Problema cheie este că cantitatea depentru găsirea unei soluții la calcul crește exponențial odată cu creșterea numărului de variabile (dimensiunea problemei). De exemplu, dacă există patru parametri, atunci sunt necesare 16 iterații, iar dacă 100, atunci 2 ^ 100, care este mai mult decât atomii din Univers (!). Un computer tipic, atunci când este reglat corespunzător, poate face câteva miliarde de aceste iterații pe secundă. În consecință, el poate rezolva cu ușurință mici probleme NP prin enumerare, iar atunci când variabilele devin semnificativ mai mult de 15, el va opri rezolvarea.
Cât despre Tetris.Dimensiunea sarcinii jocului clasic este mică: la un pas separat, există un peisaj curent în sticlă (teren de joc) - acesta este un parametru, nu afectează semnificativ cantitatea de calcule. Există informații despre figura curentă și următoarea - acestea sunt două grupuri de variabile: pentru fiecare figură există maximum patru (deși pentru un pătrat - doar una) orientări în spațiu și maximum 10 coordonate ale „aterizării” figurile. Fiecare mutare are 40 de stări, două au 1.600, nu mai există informații, aceasta este o mică problemă NP. Deși Tetris poate fi complicat: crește numărul de celule la 100 și asigură-te că jucătorul știe nu numai care va fi următoarea cifră, ci și o sută din următoarele, atunci ar fi probleme.
Nici alte jocuri NP-complete nu cunoștidin auzite: dragă mine, sudoku, etichetă și chiar o versiune necomercială a Super Mario. În ciuda simplității regulilor lor, în anumite condiții dimensiunea lor crește, computerul nu poate oferi o soluție ideală. De ce le pasă matematicienilor? Pentru că alegerea celei mai bune rute, optimizarea unui proces sau a unui program sunt și probleme de clasă NP.
Clasicul „Mario” arăta așa
Jocurile de logică sunt un teren de testare extrem de convenabil pentrualgoritmi de testare și implementarea lor software. Puzzle-urile sunt cel mai adesea „pure”, fără diferite tipuri de excepții de la regulile care sunt inerente problemelor practice. Spațiul de stare al unor astfel de probleme are o dimensiune reglabilă, iar proprietățile nu se modifică la scalare (de exemplu, etichetele 2x2, 4x4, 3x6). Toate stările sunt descrise în același mod. Descrierea matematică a puzzle-urilor, de regulă, nu este, de asemenea, la fel de complexă precum cele ale problemelor vieții.
Epoca jucăriilor „cuantice”.
Aceeași problemă cu un rucsac (cum să încapă mai multe lucruriîntr-un spațiu limitat) amintește destul de mult de un joc de Tetris, iar rezultatul efectiv va fi util companiilor de logistică, deoarece le va permite să nu irosească resursele. Dacă se găsește un algoritm „polinom rapid” pentru oricare dintre aceste probleme sau jocuri, atunci orice altă problemă din clasa NP poate fi rezolvată la fel de „rapid”. În teorie, calculatoarele cuantice vor ajuta în acest sens, dar până acum există doar prototipuri ale acestor computere ale viitorului. În 2018, a fost chiar inventat un nou concept pentru a descrie starea actuală de producție a procesoarelor cuantice - epoca NISQ (era cuantică la scară intermediară zgomotoasă) sau vremea tehnologiilor sub-cuantice.
În timp ce oamenii de știință lucrează pentru a îmbunătăți cuanțiaproceselor, directorii companiei caută analogi moderni care ajută la optimizarea muncii de producție. Un astfel de „înlocuitor” a devenit algoritmi de inspirație cuantică care găsesc o soluție optimă de 95-99% pe computerele convenționale. În Rusia, QuSolve face acest lucru - sarcinile la care lucrează compania aparțin clasei NP, iar matematicienii dezvoltă și îmbunătățesc algoritmi pentru rezolvarea problemelor de afaceri. În QuSolve, pentru a-și testa propriul solutor (solver), au folosit etichete, care au ajutat să găsească câteva erori în algoritm și să facă completări la interfața pachetului software.
Oamenii de știință moderni nu fac nimic altceva decâtVă gândiți cum să îmbunătățiți și să optimizați totul? Desigur că nu. În timpul liber, ei continuă să inventeze jocuri. Dezvoltatorii au reușit deja să transforme majoritatea jocurilor în NP, adăugând puțină magie a fenomenelor fizice cuantice.
Așa au apărut tehnologiile cuantice în ultimii 10 ani.dame, bătălie cuantică pe mare și tic-tac-toe cuantic. Șahul cuantic a câștigat o popularitate deosebită, în care se țin chiar turnee, iar campionului i se acordă titlul de mare maestru. Majoritatea noilor „jocuri cuantice” sunt construite pe principiul fundamental al mecanicii cuantice - suprapunerea.
De exemplu, piesele de șah pot fi înmai multe locuri pe tablă în același timp, ceea ce înseamnă că este mai dificil să te aperi și să ataci - acest lucru face jocul imprevizibil și spectaculos. În 2016, au filmat chiar și un scurtmetraj care a arătat un joc de șah cuantic între Stephen Hawking și Paul Rudd, un actor cunoscut pentru rolul său de Ant-Man în Marvel Cinematic Universe.
Captură de ecran a jocului. Așa arăta tabla online în jocul dintre Hawking și Rudd. Apoi actorul l-a bătut pe legendarul fizician
Nu știm dacă aceste jocuri vor fi așa în viitorla fel de banale ca tic-tac-toe, tetris și tag obișnuite, dar cu siguranță vor inspira matematicienii să creeze algoritmi unici pentru rezolvarea problemelor practice de afaceri și dezvoltarea tehnologiei. Nu există nicio îndoială.
Citeste mai mult:
Forma Căii Lactee nu este deloc ceea ce am crezut noi tot timpul, au descoperit oamenii de știință
Două super-Pământuri găsite la marginea zonei locuibile: unul dintre ele are o temperatură confortabilă
S-a găsit o gaură neagră care distruge un record de stele aproape de Pământ