Fantastiske figurer
Den legendariske Tetris ble skapt på 80-tallet av forrige århundre av Alexey Pajitnov. Matematiker
Pajitnov ga ut en av de første versjonene av spillet på den sovjetiske mikrodatamaskinen "Electronics-60"
Målet med Tetris er å bevege seg og rotere fallendegeometriske former for å danne komplette rader nederst på spillefeltet og score poeng. Fra et praktisk synspunkt er dette et spill med reaksjonshastighet og konsentrasjon, men matematikere ser på det fra en annen vinkel. Forskere analyserte beregningskompleksiteten til Tetris-algoritmen og bestemte at den tilhører klassen av NP-komplett - ikke-deterministisk polynom; det finnes ingen effektive løsningsalgoritmer for slike ting.
Hovedproblemet er at mengden avfor å finne en løsning på beregningen vokser eksponentielt med en økning i antall variabler (problemstørrelse). For eksempel, hvis det er fire parametere, er det nødvendig med 16 iterasjoner, og hvis 100, så 2 ^ 100, som er mer enn atomer i universet (!). En typisk datamaskin, når den er riktig innstilt, kan gjøre flere milliarder av disse iterasjonene per sekund. Følgelig kan han enkelt løse små NP-problemer ved oppregning, og når variablene blir merkbart mer enn 15, vil han slutte å løse.
Når det gjelder Tetris.Oppgavestørrelsen til det klassiske spillet er liten: på et eget trinn er det et gjeldende landskap i glasset (spillefeltet) - dette er en parameter, det påvirker ikke antallet beregninger nevneverdig. Det er informasjon om gjeldende og neste figur - dette er to grupper av variabler: for hver figur er det maksimalt fire (selv om for en firkant - bare én) orienteringer i rommet og maksimalt 10 koordinater for "landingen" av figurene. Hvert trekk har 40 stater, to har 1600, det er ikke mer informasjon, dette er et lite NP-problem. Selv om Tetris kan være komplisert: Øk antallet celler til 100 og sørg for at spilleren ikke bare vet hva neste figur blir, men også hundre av de neste, så ville det være problemer.
Du kjenner ikke til andre NP-komplette spill hellerfra høresier: minesveiper, sudoku, tag og til og med en ikke-kommersiell versjon av Super Mario. Til tross for de enkle reglene deres, under visse forhold øker dimensjonen deres, kan ikke datamaskinen tilby en ideell løsning. Hvorfor bryr matematikere seg? Fordi valg av den beste ruten, optimalisering av en prosess eller tidsplan også er NP-klasseproblemer.
Klassisk "Mario" så slik ut
Logikkspill er et ekstremt praktisk testområde fortesting av algoritmer og deres programvareimplementering. Gåter er oftest "rene", uten ulike typer unntak fra reglene som er iboende i praktiske problemer. Tilstandsrommet til slike problemer har en justerbar dimensjon, og egenskapene endres ikke ved skalering (for eksempel tagger 2x2, 4x4, 3x6). Alle stater er beskrevet på samme måte. Den matematiske beskrivelsen av gåter er som regel heller ikke så kompleks som livsproblemer.
Tiden for "kvante" leker
Det samme problemet med en ryggsekk (hvordan du får plass til flere tingpå et begrenset sted) minner ganske mye om et Tetris-spill, og det effektive resultatet vil være nyttig for logistikkselskaper, fordi det vil tillate dem å ikke kaste bort ressurser. Hvis en "polynomisk rask" algoritme blir funnet for noen av disse problemene eller spillene, kan ethvert annet problem fra NP-klassen løses like "raskt". I teorien vil kvantedatamaskiner hjelpe med dette, men foreløpig finnes det kun prototyper av disse fremtidens datamaskiner. I 2018 ble det til og med oppfunnet et nytt konsept for å beskrive den nåværende produksjonstilstanden for kvanteprosessorer – æraen til NISQ (støyende kvanteæra i mellomskala), eller tiden for sub-kvanteteknologier.
Mens forskere jobber med å forbedre kvanteprosesser, bedriftsledere ser etter moderne analoger som hjelper til med å optimalisere produksjonsarbeidet. En slik "erstatning" har blitt kvanteinspirerte algoritmer som finner en 95-99% optimal løsning på konvensjonelle datamaskiner. I Russland gjør QuSolve dette – oppgavene selskapet jobber med tilhører NP-klassen, og matematikere utvikler og forbedrer algoritmer for å løse forretningsproblemer. I QuSolve, for å teste sin egen løser (solver), brukte de tagger, som hjalp til med å finne et par feil i algoritmen og gjøre tillegg til grensesnittet til programvarepakken.
Gjør moderne vitenskapsmenn egentlig ikke annet ennTenker du på hvordan du kan forbedre og optimalisere alt? Selvfølgelig ikke. På fritiden fortsetter de å finne opp spill. Utviklerne har allerede vært i stand til å gjøre de fleste spill til NP, og tilført litt magi av kvantefysiske fenomener.
Slik har kvanteteknologier dukket opp de siste 10 årene.brikker, kvante sjøslag og kvante tikk-tac-toe. Kvantesjakk har fått spesiell popularitet, der det til og med arrangeres turneringer, og mesteren tildeles tittelen stormester. De fleste av de nye "kvantespillene" er bygget på kvantemekanikkens grunnleggende prinsipp - superposisjon.
For eksempel kan sjakkbrikker være inneflere plasser på brettet samtidig, noe som betyr at det er vanskeligere å forsvare og angripe – dette gjør spillet uforutsigbart og spektakulært. I 2016 filmet de til og med en kortfilm som viste et parti kvantesjakk mellom Stephen Hawking og Paul Rudd, en skuespiller kjent for sin rolle som Ant-Man i Marvel Cinematic Universe.
Skjermbilde av spillet. Slik så nettbrettet ut i spillet mellom Hawking og Rudd. Så slo skuespilleren den legendariske fysikeren
Vi vet ikke om disse spillene vil være slik i fremtidenlike vanlig som vanlige tic-tac-toe, tetris og tag, men de vil definitivt inspirere matematikere til å lage unike algoritmer for å løse praktiske forretningsproblemer og utvikle teknologi. Det er ingen tvil om det.
Les mer:
Formen på Melkeveien er slett ikke det vi trodde hele tiden, har forskere funnet
To superjordar funnet på kanten av den beboelige sonen: en av dem har en behagelig temperatur
Fant et svart hull som ødelegger en stjernerekord nær Jorden