Υπέροχα ειδώλια
Το θρυλικό Tetris δημιουργήθηκε τη δεκαετία του '80 του περασμένου αιώνα από τον Alexey Pajitnov. Μαθηματικός
Ο Pajitnov κυκλοφόρησε μια από τις πρώτες εκδόσεις του παιχνιδιού στον σοβιετικό μικροϋπολογιστή "Electronics-60"
Ο στόχος του Tetris είναι να κινείται και να περιστρέφεται πέφτονταςγεωμετρικά σχήματα για να σχηματίσετε ολόκληρες σειρές στο κάτω μέρος του αγωνιστικού χώρου, κερδίζοντας πόντους. Από πρακτική άποψη, αυτό είναι ένα παιχνίδι ταχύτητας αντίδρασης και συγκέντρωσης, αλλά οι μαθηματικοί το βλέπουν από διαφορετική οπτική γωνία. Οι επιστήμονες ανέλυσαν την υπολογιστική πολυπλοκότητα του αλγόριθμου Tetris και προσδιόρισαν ότι ανήκει στην κατηγορία του NP-πλήρους - μη ντετερμινιστικού πολυωνύμου. δεν υπάρχουν αποτελεσματικοί αλγόριθμοι λύσης για τέτοια πράγματα.
Το βασικό πρόβλημα είναι ότι η ποσότητα τουγια την εύρεση λύσης στον υπολογισμό αυξάνεται εκθετικά με την αύξηση του αριθμού των μεταβλητών (μέγεθος προβλήματος). Για παράδειγμα, εάν υπάρχουν τέσσερις παράμετροι, τότε χρειάζονται 16 επαναλήψεις και αν 100, τότε 2 ^ 100, που είναι περισσότερα από άτομα στο Σύμπαν (!). Ένας τυπικός υπολογιστής, όταν είναι σωστά συντονισμένος, μπορεί να κάνει αρκετά δισεκατομμύρια από αυτές τις επαναλήψεις ανά δευτερόλεπτο. Κατά συνέπεια, μπορεί εύκολα να λύσει μικρά προβλήματα NP με απαρίθμηση και όταν οι μεταβλητές γίνουν αισθητά περισσότερες από 15, θα σταματήσει να λύνει.
Όσο για το Tetris.Το μέγεθος εργασίας του κλασικού παιχνιδιού είναι μικρό: σε ένα ξεχωριστό βήμα, υπάρχει ένα τρέχον τοπίο στο γυαλί (πεδίο παιχνιδιού) - αυτή είναι μια παράμετρος, δεν επηρεάζει σημαντικά τον αριθμό των υπολογισμών. Υπάρχουν πληροφορίες για το τρέχον και το επόμενο σχήμα - πρόκειται για δύο ομάδες μεταβλητών: για κάθε σχήμα υπάρχουν το πολύ τέσσερις (αν και για ένα τετράγωνο - μόνο ένας) προσανατολισμοί στο χώρο και το πολύ 10 συντεταγμένες της "προσγείωσης" του οι φιγούρες. Κάθε κίνηση έχει 40 καταστάσεις, δύο έχουν 1.600, δεν υπάρχουν περισσότερες πληροφορίες, αυτό είναι ένα μικρό πρόβλημα NP. Αν και το Tetris μπορεί να είναι περίπλοκο: αυξήστε τον αριθμό των κελιών σε 100 και βεβαιωθείτε ότι ο παίκτης ξέρει όχι μόνο ποια θα είναι η επόμενη φιγούρα, αλλά και εκατό από τα επόμενα, τότε θα υπάρξουν προβλήματα.
Δεν ξέρεις ούτε άλλα παιχνίδια NP-completeαπό φήμες: ναρκαλιευτής, sudoku, tag και ακόμη και μια μη εμπορική έκδοση του Super Mario. Παρά την απλότητα των κανόνων τους, υπό προϋποθέσεις αυξάνεται η διάστασή τους, ο υπολογιστής δεν μπορεί να προσφέρει ιδανική λύση. Γιατί νοιάζονται οι μαθηματικοί; Επειδή η επιλογή της καλύτερης διαδρομής, η βελτιστοποίηση μιας διαδικασίας ή χρονοδιαγράμματος αποτελούν επίσης προβλήματα κατηγορίας NP.
Το κλασικό "Mario" έμοιαζε έτσι
Τα παιχνίδια λογικής είναι ένα εξαιρετικά βολικό πεδίο δοκιμώναλγόριθμους δοκιμών και την εφαρμογή λογισμικού τους. Τα παζλ είναι συνήθως «καθαρά», χωρίς διάφορα είδη εξαιρέσεων από τους κανόνες που είναι εγγενείς στα πρακτικά προβλήματα. Ο χώρος κατάστασης τέτοιων προβλημάτων έχει ρυθμιζόμενη διάσταση και οι ιδιότητες δεν αλλάζουν κατά την κλιμάκωση (για παράδειγμα, ετικέτες 2x2, 4x4, 3x6). Όλες οι πολιτείες περιγράφονται με τον ίδιο τρόπο. Η μαθηματική περιγραφή των παζλ, κατά κανόνα, επίσης δεν είναι τόσο περίπλοκη όσο αυτή των προβλημάτων ζωής.
Η ώρα των «κβαντικών» παιχνιδιών
Το ίδιο πρόβλημα με ένα σακίδιο (πώς να χωρέσετε περισσότερα πράγματασε περιορισμένο χώρο) θυμίζει αρκετά παιχνίδι Tetris και το αποτελεσματικό αποτέλεσμα θα είναι χρήσιμο για τις εταιρείες logistics, γιατί θα τους επιτρέψει να μην σπαταλούν πόρους. Εάν βρεθεί ένας αλγόριθμος «πολυωνυμικά γρήγορος» για οποιοδήποτε από αυτά τα προβλήματα ή παιχνίδια, τότε οποιοδήποτε άλλο πρόβλημα από την κατηγορία NP μπορεί να λυθεί εξίσου «γρήγορο». Θεωρητικά, οι κβαντικοί υπολογιστές θα βοηθήσουν σε αυτό, αλλά μέχρι στιγμής υπάρχουν μόνο πρωτότυπα αυτών των υπολογιστών του μέλλοντος. Το 2018, εφευρέθηκε μια νέα ιδέα για να περιγράψει την τρέχουσα κατάσταση παραγωγής κβαντικών επεξεργαστών - την εποχή NISQ (θορυβώδης κβαντική εποχή μέσης κλίμακας) ή την εποχή των υποκβαντικών τεχνολογιών.
Ενώ οι επιστήμονες εργάζονται για τη βελτίωση του κβαντικούδιεργασίες, τα στελέχη της εταιρείας αναζητούν σύγχρονα ανάλογα που βοηθούν στη βελτιστοποίηση του έργου της παραγωγής. Ένα τέτοιο «υποκατάστατο» έχει γίνει αλγόριθμοι κβαντικής έμπνευσης που βρίσκουν μια βέλτιστη λύση 95-99% σε συμβατικούς υπολογιστές. Στη Ρωσία, το QuSolve το κάνει αυτό - οι εργασίες στις οποίες εργάζεται η εταιρεία ανήκουν στην κατηγορία NP και οι μαθηματικοί αναπτύσσουν και βελτιώνουν αλγόριθμους για την επίλυση επιχειρηματικών προβλημάτων. Στο QuSolve, για να δοκιμάσουν τον δικό τους λύτη (solver), χρησιμοποίησαν ετικέτες, οι οποίες βοήθησαν να βρουν μερικά λάθη στον αλγόριθμο και να κάνουν προσθήκες στη διεπαφή του πακέτου λογισμικού.
Οι σύγχρονοι επιστήμονες δεν κάνουν τίποτε άλλο παράΣκέφτεστε πώς να βελτιώσετε και να βελτιστοποιήσετε τα πάντα; Φυσικά και όχι. Στον ελεύθερο χρόνο τους συνεχίζουν να επινοούν παιχνίδια. Οι προγραμματιστές έχουν ήδη καταφέρει να μετατρέψουν τα περισσότερα παιχνίδια σε NP, προσθέτοντας λίγη μαγεία σε κβαντικά φυσικά φαινόμενα.
Έτσι εμφανίστηκαν οι κβαντικές τεχνολογίες τα τελευταία 10 χρόνια.πούλια, κβαντική θαλάσσια μάχη και κβαντικό τικ-τακ. Το κβαντικό σκάκι έχει αποκτήσει ιδιαίτερη δημοτικότητα, στα οποία διεξάγονται ακόμη και τουρνουά και ο πρωταθλητής λαμβάνει τον τίτλο του γκρανμάστερ. Τα περισσότερα από τα νέα «κβαντικά παιχνίδια» είναι χτισμένα στη θεμελιώδη αρχή της κβαντικής μηχανικής - υπέρθεση.
Για παράδειγμα, τα πιόνια σκακιού μπορούν να είναι μέσαπολλές θέσεις στο ταμπλό ταυτόχρονα, πράγμα που σημαίνει ότι είναι πιο δύσκολο να αμυνθείς και να επιτεθείς - αυτό κάνει το παιχνίδι απρόβλεπτο και θεαματικό. Το 2016, γύρισαν ακόμη και μια ταινία μικρού μήκους που έδειχνε μια παρτίδα κβαντικού σκακιού μεταξύ του Stephen Hawking και του Paul Rudd, ενός ηθοποιού που είναι γνωστός για τον ρόλο του Ant-Man στο Marvel Cinematic Universe.
Στιγμιότυπο οθόνης παιχνιδιού. Έτσι ήταν ο διαδικτυακός πίνακας στο παιχνίδι μεταξύ Χόκινγκ και Ραντ. Τότε ο ηθοποιός χτύπησε τον θρυλικό φυσικό
Δεν ξέρουμε αν αυτά τα παιχνίδια θα είναι έτσι στο μέλλοντόσο συνηθισμένο όσο το συνηθισμένο tic-tac-toe, tetris και tag, αλλά σίγουρα θα εμπνεύσουν τους μαθηματικούς να δημιουργήσουν μοναδικούς αλγόριθμους για την επίλυση πρακτικών επιχειρηματικών προβλημάτων και την ανάπτυξη τεχνολογίας. Δεν υπάρχει αμφιβολία γι' αυτό.
Διαβάστε περισσότερα:
Το σχήμα του Γαλαξία δεν είναι καθόλου αυτό που νομίζαμε από παλιά, ανακάλυψαν οι επιστήμονες
Δύο υπερ-Γαίες βρέθηκαν στην άκρη της κατοικήσιμης ζώνης: η μία από αυτές έχει μια άνετη θερμοκρασία
Βρέθηκε μια μαύρη τρύπα που καταστρέφει ένα αρχείο αστεριών κοντά στη Γη