Vidunderlige figurer
Den legendariske Tetris blev skabt i 80'erne af forrige århundrede af Alexey Pajitnov. Matematiker
Pajitnov udgav en af de første versioner af spillet på den sovjetiske mikrocomputer "Electronics-60"
Målet med Tetris er at bevæge sig og rotere faldendegeometriske former for at danne komplette rækker i bunden af spillefeltet og score point. Fra et praktisk synspunkt er dette et spil med reaktionshastighed og koncentration, men matematikere ser på det fra en anden vinkel. Forskere analyserede den beregningsmæssige kompleksitet af Tetris-algoritmen og fastslog, at den tilhører klassen af NP-komplet - ikke-deterministisk polynomium; der er ingen effektive løsningsalgoritmer til sådanne ting.
Det centrale problem er, at mængden affor at finde en løsning på beregningen vokser eksponentielt med en stigning i antallet af variable (problemstørrelse). For eksempel, hvis der er fire parametre, er der brug for 16 iterationer, og hvis 100, så 2 ^ 100, hvilket er mere end atomer i universet (!). En typisk computer kan, når den er korrekt indstillet, udføre flere milliarder af disse iterationer i sekundet. Derfor kan han nemt løse små NP-problemer ved opregning, og når variablerne bliver mærkbart mere end 15, vil han stoppe med at løse.
Hvad angår Tetris.Opgavestørrelsen for det klassiske spil er lille: på et separat trin er der et aktuelt landskab i glasset (spillefeltet) - dette er en parameter, det påvirker ikke mængden af beregninger væsentligt. Der er information om den nuværende og næste figur - disse er to grupper af variable: for hver figur er der maksimalt fire (dog for en firkant - kun én) orienteringer i rummet og maksimalt 10 koordinater for "landingen" af tallene. Hvert træk har 40 stater, to har 1.600, der er ikke flere oplysninger, dette er et lille NP-problem. Selvom Tetris kan være kompliceret: Øg antallet af celler til 100 og sørg for, at spilleren ikke kun ved, hvad den næste figur bliver, men også hundrede af de næste, så ville der være problemer.
Du kender heller ikke andre NP-komplette spilfra rygter: minestryger, sudoku, tag og endda en ikke-kommerciel version af Super Mario. På trods af deres enkle regler, under visse betingelser, deres dimension øges, kan computeren ikke tilbyde en ideel løsning. Hvorfor bekymrer matematikere sig? Fordi valg af den bedste rute, optimering af en proces eller tidsplan også er NP-klasseproblemer.
Klassisk "Mario" så sådan ud
Logik spil er en yderst praktisk testplads fortestalgoritmer og deres softwareimplementering. Gåder er oftest "rene", uden forskellige former for undtagelser fra de regler, der er iboende i praktiske problemer. Tilstandsrummet for sådanne problemer har en justerbar dimension, og egenskaberne ændres ikke ved skalering (for eksempel tags 2x2, 4x4, 3x6). Alle stater er beskrevet på samme måde. Den matematiske beskrivelse af gåder er som regel heller ikke så kompleks som dem af livsproblemer.
Tiden for "kvante" legetøj
Det samme problem med en rygsæk (hvordan man monterer flere tingi et begrænset rum) minder ret meget om et spil Tetris, og det effektive resultat vil være nyttigt for logistikvirksomheder, fordi det giver dem mulighed for ikke at spilde ressourcer. Hvis der findes en "polynomisk hurtig" algoritme for nogen af disse problemer eller spil, så kan ethvert andet problem fra NP-klassen løses lige så "hurtigt". I teorien vil kvantecomputere hjælpe med dette, men indtil videre er der kun prototyper af disse fremtidens computere. I 2018 blev et nyt koncept endda opfundet til at beskrive den nuværende tilstand af kvanteprocessorproduktion - NISQ-æraen (støjende mellemskala kvanteæra), eller tiden for sub-kvanteteknologier.
Mens forskere arbejder på at forbedre kvanteprocesser, leder virksomhedens ledere efter moderne analoger, der hjælper med at optimere produktionsarbejdet. Sådan en "erstatning" er blevet til kvante-inspirerede algoritmer, der finder en 95-99% optimal løsning på konventionelle computere. I Rusland gør QuSolve dette - de opgaver, virksomheden arbejder med, tilhører NP-klassen, og matematikere udvikler og forbedrer algoritmer til løsning af forretningsproblemer. I QuSolve brugte de tags, for at teste deres egen solver (solver), som hjalp med at finde et par fejl i algoritmen og lave tilføjelser til softwarepakkens grænseflade.
Gør moderne videnskabsmænd virkelig ikke andet endTænker du på, hvordan du kan forbedre og optimere alt? Selvfølgelig ikke. I deres fritid fortsætter de med at opfinde spil. Udviklerne har allerede været i stand til at omdanne de fleste spil til NP og tilføjet en lille magi af kvantefysiske fænomener.
Так за последние 10 лет появились квантовые brikker, kvante søslag og kvante tik-tac-toe. Kvanteskak har vundet særlig popularitet, hvor der endda afholdes turneringer, og mesteren tildeles titlen som stormester. De fleste af de nye "kvantespil" er bygget på kvantemekanikkens grundlæggende princip - superposition.
For eksempel kan skakbrikker være iflere pladser på brættet på samme tid, hvilket betyder, at det er sværere at forsvare og angribe - det gør spillet uforudsigeligt og spektakulært. I 2016 filmede de endda en kortfilm, der viste et spil kvanteskak mellem Stephen Hawking og Paul Rudd, en skuespiller kendt for sin rolle som Ant-Man i Marvel Cinematic Universe.
Skærmbillede af spillet. Sådan så onlinebrættet ud i spillet mellem Hawking og Rudd. Så slog skuespilleren den legendariske fysiker
Vi ved ikke, om disse spil vil være sådan i fremtidenlige så almindelige som almindelig tic-tac-toe, tetris og tag, men de vil helt sikkert inspirere matematikere til at skabe unikke algoritmer til at løse praktiske forretningsproblemer og udvikle teknologi. Det er der ingen tvivl om.
Læs mere:
Formen af Mælkevejen er slet ikke, hvad vi har troet hele tiden, har videnskabsmænd fundet
To superjorde fundet på kanten af den beboelige zone: en af dem har en behagelig temperatur
Fandt et sort hul, der ødelægger en stjernerekord tæt på Jorden