Wunderbare Figuren
Das legendäre Tetris wurde in den 80er Jahren des letzten Jahrhunderts von Alexey Pajitnov entwickelt. Mathematiker
Pajitnov veröffentlichte eine der ersten Versionen des Spiels auf dem sowjetischen Mikrocomputer "Electronics-60".
Das Ziel von Tetris ist es, sich beim Fallen zu bewegen und zu drehenGeometrische Formen bilden komplette Reihen am unteren Rand des Spielfelds und erzielen Punkte. Aus praktischer Sicht ist dies ein Spiel der Reaktionsgeschwindigkeit und Konzentration, doch Mathematiker betrachten es aus einem anderen Blickwinkel. Wissenschaftler analysierten die Rechenkomplexität des Tetris-Algorithmus und stellten fest, dass er zur Klasse der NP-vollständigen – nichtdeterministischen Polynome – gehört; Für solche Dinge gibt es keine effektiven Lösungsalgorithmen.
Das Hauptproblem ist, dass die Menge anzum Finden einer Lösung für die Berechnung wächst exponentiell mit einer Zunahme der Anzahl von Variablen (Problemgröße). Wenn es beispielsweise vier Parameter gibt, werden 16 Iterationen benötigt, und wenn 100, dann 2 ^ 100, was mehr ist als Atome im Universum (!). Ein typischer Computer kann, wenn er richtig eingestellt ist, mehrere Milliarden dieser Iterationen pro Sekunde ausführen. Dementsprechend kann er kleine NP-Probleme leicht durch Aufzählen lösen, und wenn die Variablen merklich größer als 15 werden, hört er auf zu lösen.
Apropos Tetris.Die Aufgabengröße des klassischen Spiels ist gering: In einem separaten Schritt befindet sich eine aktuelle Landschaft im Glas (Spielfeld) - dies ist ein Parameter, der die Anzahl der Berechnungen nicht wesentlich beeinflusst. Es gibt Informationen über die aktuelle und die nächste Figur - das sind zwei Gruppen von Variablen: Für jede Figur gibt es maximal vier (obwohl für ein Quadrat - nur eine) Orientierungen im Raum und maximal 10 Koordinaten der "Landung". die Figuren. Jeder Zug hat 40 Zustände, zwei haben 1.600, es gibt keine weiteren Informationen, dies ist ein kleines NP-Problem. Obwohl Tetris kompliziert sein kann: Erhöhen Sie die Anzahl der Zellen auf 100 und stellen Sie sicher, dass der Spieler nicht nur weiß, was die nächste Zahl sein wird, sondern auch hundert der nächsten, dann würde es Probleme geben.
Sie kennen auch keine anderen NP-vollständigen Spielevom Hörensagen: Minesweeper, Sudoku, Tag und sogar eine nichtkommerzielle Version von Super Mario. Trotz der Einfachheit ihrer Regeln nimmt unter bestimmten Bedingungen ihre Dimension zu, sodass der Computer keine ideale Lösung bieten kann. Warum kümmern sich Mathematiker darum? Denn auch die Wahl der besten Route, die Optimierung eines Prozesses oder Zeitplans sind Probleme der NP-Klasse.
Der klassische "Mario" sah so aus
Logikspiele sind ein äußerst praktisches Testgelände fürTestalgorithmen und deren Softwareimplementierung. Rätsel sind meist „rein“, ohne verschiedene Ausnahmen von den Regeln, die praktischen Problemen innewohnen. Der Zustandsraum solcher Probleme hat eine einstellbare Dimension und die Eigenschaften ändern sich bei der Skalierung nicht (z. B. Tags 2x2, 4x4, 3x6). Alle Zustände werden auf die gleiche Weise beschrieben. Auch die mathematische Beschreibung von Rätseln ist in der Regel nicht so komplex wie die von Lebensproblemen.
Die Zeit der "Quanten"-Spielzeuge
Das gleiche Problem mit einem Rucksack (wie man mehr Dinge unterbringt).auf begrenztem Raum) erinnert stark an ein Tetris-Spiel, und das effektive Ergebnis wird für Logistikunternehmen nützlich sein, da es ihnen ermöglicht, keine Ressourcen zu verschwenden. Wenn für eines dieser Probleme oder Spiele ein „polynomial schneller“ Algorithmus gefunden wird, kann jedes andere Problem aus der NP-Klasse genauso „schnell“ gelöst werden. Theoretisch werden Quantencomputer dabei helfen, doch bisher gibt es nur Prototypen dieser Computer der Zukunft. Im Jahr 2018 wurde sogar ein neues Konzept erfunden, um den aktuellen Stand der Quantenprozessorproduktion zu beschreiben – die NISQ-Ära (Noisy Intermediate-Scale Quantum Era) oder die Zeit der Subquantentechnologien.
Während Wissenschaftler daran arbeiten, Quanten zu verbessernProzessen suchen Unternehmensleiter nach modernen Entsprechungen, die helfen, die Arbeit der Produktion zu optimieren. Ein solcher „Ersatz“ sind quanteninspirierte Algorithmen geworden, die auf herkömmlichen Computern eine zu 95-99% optimale Lösung finden. In Russland tut dies QuSolve - die Aufgaben, an denen das Unternehmen arbeitet, gehören zur NP-Klasse, und Mathematiker entwickeln und verbessern Algorithmen zur Lösung von Geschäftsproblemen. In QuSolve verwendeten sie zum Testen ihres eigenen Lösers (Solver) Tags, die dabei halfen, ein paar Fehler im Algorithmus zu finden und Ergänzungen an der Schnittstelle des Softwarepakets vorzunehmen.
Tun moderne Wissenschaftler wirklich nichts anderes?Denken Sie darüber nach, wie Sie alles verbessern und optimieren können? Natürlich nicht. In ihrer Freizeit erfinden sie weiterhin Spiele. Den Entwicklern ist es bereits gelungen, die meisten Spiele in NP umzuwandeln und so ein wenig Magie quantenphysikalischer Phänomene hinzuzufügen.
So sind Quantentechnologien in den letzten 10 Jahren entstanden.Dame, Quantenseeschlacht und Quanten-Tic-Tac-Toe. Besonders beliebt ist das Quantenschach, bei dem sogar Turniere ausgetragen werden und dem Meister der Titel Großmeister verliehen wird. Die meisten neuen „Quantenspiele“ basieren auf dem Grundprinzip der Quantenmechanik – der Superposition.
Schachfiguren können zum Beispiel drin seinmehreren Plätzen gleichzeitig auf dem Brett, was das Verteidigen und Angreifen erschwert - das macht das Spiel unvorhersehbar und spektakulär. 2016 drehten sie sogar einen Kurzfilm, der eine Partie Quantenschach zwischen Stephen Hawking und Paul Rudd zeigte, einem Schauspieler, der für seine Rolle als Ant-Man im Marvel Cinematic Universe bekannt ist.
Screenshot des Spiels. So sah das Online-Brett im Spiel zwischen Hawking und Rudd aus. Dann schlug der Schauspieler den legendären Physiker
Wir wissen nicht, ob diese Spiele in Zukunft so sein werdenSo alltäglich wie gewöhnliches Tic-Tac-Toe, Tetris und Tag, aber sie werden Mathematiker auf jeden Fall dazu inspirieren, einzigartige Algorithmen zur Lösung praktischer Geschäftsprobleme und zur Entwicklung von Technologie zu entwickeln. Daran besteht kein Zweifel.
Weiter lesen:
Die Form der Milchstraße ist überhaupt nicht das, was wir die ganze Zeit dachten, haben Wissenschaftler herausgefunden
Zwei Supererden am Rande der bewohnbaren Zone gefunden: Eine davon hat eine angenehme Temperatur
Ein Schwarzes Loch gefunden, das einen Sternenrekord in der Nähe der Erde zerstört