Csodálatos figurák
A legendás Tetrist a múlt század 80-as éveiben készítette Alexey Pajitnov. Matematikus
Pajitnov kiadta a játék egyik első verzióját az "Electronics-60" szovjet mikroszámítógépen.
A Tetris célja az esés mozgatása és forgatásageometriai formák, hogy teljes sorokat alkossanak a játéktér alján, pontozással. Gyakorlati szempontból ez a reakciósebesség és a koncentráció játéka, de a matematikusok más szemszögből nézik. A tudósok elemezték a Tetris algoritmus számítási bonyolultságát, és megállapították, hogy az NP-teljes – nem determinisztikus polinom osztályába tartozik; ilyen dolgokra nincsenek hatékony megoldási algoritmusok.
A fő probléma az, hogy az összega megoldás megtalálása a számításra exponenciálisan növekszik a változók számának növekedésével (probléma mérete). Például, ha négy paraméter van, akkor 16 iterációra van szükség, és ha 100, akkor 2 ^ 100, ami több, mint atomok az Univerzumban (!). Egy tipikus számítógép, ha megfelelően van hangolva, több milliárd ilyen iterációt képes végrehajtani másodpercenként. Ennek megfelelően a kis NP-problémákat könnyen meg tudja oldani felsorolással, és amikor a változók észrevehetően több mint 15, akkor abbahagyja a megoldást.
Ami a Tetrist illeti.A klasszikus játék feladatmérete kicsi: külön lépésben az üvegben (játéktéren) aktuális tájkép található - ez egy paraméter, a számítások mennyiségét nem befolyásolja jelentősen. Információk vannak az aktuális és a következő ábráról - ez két változócsoport: minden ábrához legfeljebb négy (bár egy négyzethez csak egy) térbeli tájolás és legfeljebb 10 "leszállási" koordináta tartozik. a figurák. Minden lépésnek 40 állapota van, kettőnek 1600, nincs több információ, ez egy kis NP probléma. Bár a Tetris bonyolult lehet: növelje a cellák számát 100-ra, és ügyeljen arra, hogy a játékos ne csak azt tudja, mi lesz a következő, hanem százat is, akkor gondok lennének.
Más NP-teljes játékokat sem ismerszhallomásból: aknakereső, sudoku, címke és még a Super Mario nem kereskedelmi verziója is. Szabályaik egyszerűsége ellenére, bizonyos feltételek mellett méretük megnő, a számítógép nem tud ideális megoldást kínálni. Miért érdekli a matematikusokat? Mert a legjobb útvonal kiválasztása, egy folyamat vagy ütemezés optimalizálása is NP-osztálybeli probléma.
A klasszikus "Mario" így nézett ki
A logikai játékok rendkívül kényelmes tesztelési terepet jelentenektesztelési algoritmusok és szoftveres megvalósításuk. A rejtvények leggyakrabban „tiszták”, a gyakorlati problémákban rejlő szabályok alóli különféle kivételek nélkül. Az ilyen problémák állapottere állítható mérettel rendelkezik, és a tulajdonságok nem változnak skálázáskor (például 2x2, 4x4, 3x6 címkék). Minden állapot leírása azonos módon történik. A rejtvények matematikai leírása általában nem olyan összetett, mint az életfeladatoké.
A "kvantum" játékok ideje
Ugyanez a probléma a hátizsákkal (hogyan férjen el több dologkorlátozott helyen) egy Tetris játékra emlékeztet, és a hatékony eredmény hasznos lesz a logisztikai cégek számára, mert lehetővé teszi számukra, hogy ne pazarolják az erőforrásokat. Ha ezeknek a problémáknak vagy játékok bármelyikére találunk „polinomiálisan gyors” algoritmust, akkor az NP osztály bármely más problémája ugyanolyan „gyorsan” megoldható. Elméletileg a kvantumszámítógépek segítenek ebben, de ezeknek a jövő számítógépeinek egyelőre csak prototípusai vannak. 2018-ban még egy új koncepciót is kitaláltak a kvantumprocesszorok jelenlegi gyártási állapotának leírására – a NISQ (noisy intermediate-scale quantum korszak) korszaka, vagy a szubkvantumtechnológiák ideje.
Miközben a tudósok a kvantum javításán dolgoznakA vállalatvezetők modern analógokat keresnek, amelyek segítenek optimalizálni a termelési munkát. Egy ilyen „helyettesítő” kvantum-ihlette algoritmusokká váltak, amelyek 95-99%-ban optimális megoldást találnak a hagyományos számítógépeken. Oroszországban a QuSolve végzi ezt - a vállalat által végzett feladatok az NP osztályba tartoznak, a matematikusok pedig algoritmusokat fejlesztenek és fejlesztenek az üzleti problémák megoldására. A QuSolve-ban saját megoldójuk (solver) tesztelésére címkéket használtak, amelyek segítettek megtalálni egy-két hibát az algoritmusban, és kiegészítették a szoftvercsomag felületét.
A modern tudósok tényleg nem tesznek mást, mintAzon gondolkodik, hogyan lehetne mindent javítani és optimalizálni? Természetesen nem. Szabadidejükben továbbra is játékokat találnak ki. A fejlesztőknek már sikerült a legtöbb játékot NP-vé alakítaniuk, a kvantumfizikai jelenségek egy kis varázslatával hozzáadva.
Így jelentek meg a kvantumtechnológiák az elmúlt 10 évben.dáma, tengeri kvantumcsata és kvantum-tic-tac-toe. Különös népszerűségre tett szert a kvantumsakk, amelyen még versenyeket is rendeznek, és a bajnokot nagymesteri címmel tüntetik ki. Az új „kvantumjátékok” többsége a kvantummechanika alapelvére – a szuperpozícióra – épül.
Például sakkfigurák lehetnek benneegyszerre több helyen a táblán, ami azt jelenti, hogy nehezebb védekezni és támadni – ez kiszámíthatatlanná és látványossá teszi a játékot. 2016-ban még egy rövidfilmet is forgattak, amely egy kvantumsakkjátszmát mutatott be Stephen Hawking és Paul Rudd között, aki a Marvel Filmuniverzum Hangyaember szerepéről ismert.
Játék képernyőképe. Így nézett ki az online tábla Hawking és Rudd játékában. Aztán a színész megverte a legendás fizikust
Nem tudjuk, hogy ezek a játékok ilyenek lesznek-e a jövőbenugyanolyan hétköznapi, mint a közönséges tic-tac-toe, tetris és tag, de határozottan arra ösztönzik majd a matematikusokat, hogy egyedi algoritmusokat hozzanak létre gyakorlati üzleti problémák megoldására és technológiafejlesztésre. Kétség sem fér hozzá.
Olvass tovább:
A tudósok megállapították, hogy a Tejútrendszer alakja egyáltalán nem az, amit mindvégig gondoltunk
Két szuperföldet találtak a lakható zóna szélén: az egyiknek kellemes a hőmérséklete
Találtak egy fekete lyukat, amely egy csillagrekordot semmisít meg a Föld közelében