Divne figurice
Legendarni Tetris kreirao je 80-ih godina prošlog stoljeća Alexey Pajitnov. Matematičar
Pajitnov je izdao jednu od prvih verzija igre na sovjetskom mikroračunalu "Electronics-60"
Cilj Tetrisa je kretanje i rotacija padajućigeometrijske oblike za formiranje kompletnih redova na dnu polja za igru, bodovanje. S praktične strane, ovo je igra brzine reakcije i koncentracije, no matematičari je gledaju iz drugog kuta. Znanstvenici su analizirali računsku složenost Tetris algoritma i utvrdili da pripada klasi NP-potpunih - nedeterminističkih polinoma; za takve stvari ne postoje učinkoviti algoritmi rješenja.
Ključni problem je u tome što količinaza pronalaženje rješenja računanje eksponencijalno raste s povećanjem broja varijabli (veličina problema). Na primjer, ako postoje četiri parametra, onda je potrebno 16 ponavljanja, a ako 100, onda 2 ^ 100, što je više od atoma u Svemiru (!). Tipično računalo, kada je pravilno podešeno, može napraviti nekoliko milijardi ovih ponavljanja u sekundi. Sukladno tome, lako rješava male NP-probleme nabrajanjem, a kada varijabli postane osjetno više od 15, prestat će rješavati.
Što se Tetrisa tiče.Veličina zadatka klasične igre je mala: u zasebnom koraku postoji trenutni krajolik u staklu (igralište) - ovo je parametar, ne utječe značajno na količinu izračuna. Postoje informacije o trenutnoj i sljedećoj figuri - to su dvije skupine varijabli: za svaku figuru postoje najviše četiri (iako za kvadrat - samo jedna) orijentacije u prostoru i najviše 10 koordinata "slijetanja" brojke. Svaki potez ima 40 stanja, dva imaju 1600, nema više informacija, to je mali problem NP. Iako Tetris može biti kompliciran: povećajte broj ćelija na 100 i pobrinite se da igrač zna ne samo koja će sljedeća figura biti, već i stotinu sljedećih, tada bi bilo problema.
Ne znate ni druge NP-complete igreiz rekla-kazala: minolovac, sudoku, oznaka pa čak i nekomercijalna verzija Super Mario. Unatoč jednostavnosti njihovih pravila, pod određenim uvjetima njihova dimenzija raste, računalo ne može ponuditi idealno rješenje. Zašto je matematičarima stalo? Budući da su odabir najbolje rute, optimizacija procesa ili rasporeda također problemi klase NP.
Klasični "Mario" izgledao je ovako
Logičke igre izuzetno su zgodan poligon za testiranjetestiranje algoritama i njihova programska implementacija. Zagonetke su najčešće "čiste", bez raznih vrsta iznimaka od pravila koja su svojstvena praktičnim problemima. Prostor stanja takvih problema ima podesivu dimenziju, a svojstva se ne mijenjaju prilikom skaliranja (na primjer, oznake 2x2, 4x4, 3x6). Sva stanja su opisana na isti način. Matematički opis zagonetki, u pravilu, također nije tako složen kao životnih problema.
Vrijeme "kvantnih" igračaka
Isti problem s ruksakom (kako stati više stvariu ograničenom prostoru) prilično podsjeća na igricu Tetris, a učinkovit rezultat bit će koristan logističkim tvrtkama jer će im omogućiti da ne troše resurse. Ako se za bilo koji od ovih problema ili igara pronađe "polinomno brz" algoritam, tada se bilo koji drugi problem iz NP klase može riješiti jednako "brzo". U teoriji će u tome pomoći kvantna računala, ali zasad postoje samo prototipovi ovih računala budućnosti. U 2018. čak je izmišljen novi koncept koji opisuje trenutačno stanje proizvodnje kvantnih procesora - doba NISQ-a (noisy intermediate-scale quantum era), odnosno vrijeme subkvantnih tehnologija.
Dok znanstvenici rade na poboljšanju kvantneprocesa, rukovoditelji poduzeća traže moderne analoge koji pomažu optimizirati rad proizvodnje. Takva “zamjena” postali su kvantno inspirirani algoritmi koji pronalaze 95-99% optimalno rješenje na konvencionalnim računalima. U Rusiji to radi QuSolve - zadaci na kojima tvrtka radi pripadaju klasi NP, a matematičari razvijaju i poboljšavaju algoritme za rješavanje poslovnih problema. U QuSolveu su za testiranje vlastitog rješavača (solvera) koristili oznake koje su pomogle u pronalaženju nekoliko pogrešaka u algoritmu i dodavanju sučelja softverskog paketa.
Ne rade li moderni znanstvenici doista ništa osimRazmišljate kako sve poboljšati i optimizirati? Naravno da ne. U slobodno vrijeme nastavljaju smišljati igre. Programeri su već uspjeli većinu igara pretvoriti u NP, dodajući im malo magije kvantnih fizičkih fenomena.
Tako su se u zadnjih 10 godina pojavile kvantne tehnologije.dame, kvantne morske bitke i kvantne tic-tac-toe. Posebnu popularnost stekao je kvantni šah u kojem se čak održavaju turniri, a prvak dobiva titulu velemajstora. Većina novih "kvantnih igara" izgrađena je na temeljnom principu kvantne mehanike - superpoziciji.
Na primjer, šahovske figure mogu biti unutranekoliko mjesta na ploči u isto vrijeme, što znači da je teže braniti se i napadati - to čini igru nepredvidivom i spektakularnom. Godine 2016. čak su snimili kratki film koji je prikazivao partiju kvantnog šaha između Stephena Hawkinga i Paula Rudda, glumca poznatog po ulozi Čovjeka Ant-Mana u Marvelovom filmskom svemiru.
Snimka zaslona igre. Ovako je izgledala online ploča u igri između Hawkinga i Rudda. Tada je glumac pobijedio legendarnog fizičara
Ne znamo hoće li ove igre biti ovakve u budućnostiuobičajeni kao i obični tic-tac-toe, tetris i tag, ali će svakako inspirirati matematičare da stvore jedinstvene algoritme za rješavanje praktičnih poslovnih problema i razvoj tehnologije. U to nema sumnje.
Čitaj više:
Oblik Mliječne staze uopće nije onakav kakav smo cijelo vrijeme mislili, otkrili su znanstvenici
Dvije super-Zemlje pronađene na rubu nastanjive zone: jedna od njih ima ugodnu temperaturu
Pronađena crna rupa koja uništava zapis zvijezda blizu Zemlje