figuritas maravillosas
El legendario Tetris fue creado en los años 80 del siglo pasado por Alexey Pajitnov. Matemático
Pajitnov lanzó una de las primeras versiones del juego en la microcomputadora soviética "Electronics-60".
El objetivo del Tetris es moverse y rotar cayendo.formas geométricas para formar filas completas en la parte inferior del campo de juego, sumando puntos. Desde un punto de vista práctico, se trata de un juego de velocidad de reacción y concentración, pero los matemáticos lo ven desde un ángulo diferente. Los científicos analizaron la complejidad computacional del algoritmo Tetris y determinaron que pertenece a la clase de polinomio NP-completo, no determinista; No existen algoritmos de solución eficaces para este tipo de cosas.
El problema clave es que la cantidad depara encontrar una solución al cálculo crece exponencialmente con un aumento en el número de variables (tamaño del problema). Por ejemplo, si hay cuatro parámetros, entonces se necesitan 16 iteraciones, y si 100, entonces 2 ^ 100, que es más que átomos en el Universo (!). Una computadora típica, cuando se ajusta correctamente, puede hacer varios miles de millones de estas iteraciones por segundo. En consecuencia, puede resolver fácilmente pequeños problemas NP por enumeración, y cuando las variables sean notablemente más de 15, dejará de resolver.
En cuanto a Tetris.El tamaño de la tarea del juego clásico es pequeño: en un paso separado, hay un paisaje actual en el cristal (campo de juego); este es un parámetro, no afecta significativamente la cantidad de cálculos. Hay información sobre la figura actual y la siguiente: estos son dos grupos de variables: para cada figura hay un máximo de cuatro (aunque para un cuadrado, solo una) orientaciones en el espacio y un máximo de 10 coordenadas del "rellano" de las figuras. Cada movimiento tiene 40 estados, dos tienen 1600, no hay más información, este es un pequeño problema de NP. Aunque Tetris puede ser complicado: aumentar el número de celdas a 100 y asegurarse de que el jugador sepa no solo cuál será la próxima figura, sino también cien de las siguientes, entonces habría problemas.
Tampoco conoces otros juegos NP completosde oídas: buscaminas, sudoku, tag e incluso una versión no comercial de Super Mario. A pesar de la simplicidad de sus reglas, bajo ciertas condiciones su dimensión aumenta, la computadora no puede ofrecer una solución ideal. ¿Por qué les importa a los matemáticos? Porque elegir la mejor ruta, optimizar un proceso o un cronograma también son problemas de clase NP.
El clásico "Mario" se veía así
Los juegos de lógica son un campo de pruebas extremadamente conveniente paraAlgoritmos de prueba y su implementación de software. Los acertijos suelen ser "puros", sin diversos tipos de excepciones a las reglas inherentes a los problemas prácticos. El espacio de estado de este tipo de problemas tiene una dimensión ajustable y las propiedades no cambian al escalar (por ejemplo, etiquetas 2x2, 4x4, 3x6). Todos los estados se describen de la misma manera. La descripción matemática de los acertijos tampoco suele ser tan compleja como la de los problemas de la vida.
El tiempo de los juguetes "cuánticos"
El mismo problema con una mochila (cómo meter más cosasen un espacio limitado) recuerda bastante a un juego de Tetris, y el resultado efectivo será útil para las empresas de logística, porque les permitirá no desperdiciar recursos. Si se encuentra un algoritmo “polinomialmente rápido” para cualquiera de estos problemas o juegos, entonces cualquier otro problema de la clase NP se puede resolver igual de “rápido”. En teoría, los ordenadores cuánticos ayudarán en esto, pero hasta el momento sólo existen prototipos de estos ordenadores del futuro. En 2018, incluso se inventó un nuevo concepto para describir el estado actual de la producción de procesadores cuánticos: la era de NISQ (era cuántica ruidosa de escala intermedia), o la época de las tecnologías subcuánticas.
Mientras los científicos trabajan para mejorar la tecnología cuánticaprocesos, los ejecutivos de la empresa buscan análogos modernos que ayuden a optimizar el trabajo de producción. Tal "sustituto" se ha convertido en algoritmos de inspiración cuántica que encuentran una solución óptima del 95-99% en las computadoras convencionales. En Rusia, QuSolve está haciendo esto: las tareas en las que está trabajando la empresa pertenecen a la clase NP, y los matemáticos desarrollan y mejoran algoritmos para resolver problemas comerciales. En QuSolve, para probar su propio solucionador (solucionador), usaron etiquetas, lo que ayudó a encontrar un par de errores en el algoritmo y hacer adiciones a la interfaz del paquete de software.
¿Realmente los científicos modernos no hacen más que¿Estás pensando en cómo mejorar y optimizar todo? Por supuesto que no. En su tiempo libre siguen inventando juegos. Los desarrolladores ya han podido convertir la mayoría de los juegos en NP, añadiendo un poco de magia de fenómenos físicos cuánticos.
Así han aparecido las tecnologías cuánticas en los últimos 10 años.damas, batalla naval cuántica y tres en raya cuántica. Particularmente popular ha sido el ajedrez cuántico, en el que incluso se celebran torneos y el campeón recibe el título de gran maestro. La mayoría de los nuevos "juegos cuánticos" se basan en el principio fundamental de la mecánica cuántica: la superposición.
Por ejemplo, las piezas de ajedrez pueden estar envarios lugares en el tablero al mismo tiempo, lo que significa que es más difícil defender y atacar, lo que hace que el juego sea impredecible y espectacular. En 2016 incluso filmaron un cortometraje que mostraba una partida de ajedrez cuántico entre Stephen Hawking y Paul Rudd, actor conocido por su papel de Ant-Man en el Universo Cinematográfico de Marvel.
Captura de pantalla del juego. Así se veía el tablero en línea en el juego entre Hawking y Rudd. Entonces el actor venció al legendario físico.
No sabemos si estos juegos serán así en el futuro.tan comunes como el tres en raya, el tetris y la etiqueta, pero definitivamente inspirarán a los matemáticos a crear algoritmos únicos para resolver problemas comerciales prácticos y desarrollar tecnología. No hay duda al respecto.
Lee mas:
La forma de la Vía Láctea no es en absoluto lo que pensábamos todo el tiempo, según los científicos
Dos súper-Tierras encontradas al borde de la zona habitable: una de ellas tiene una temperatura agradable
Encontrado un agujero negro que destruye un registro de estrellas cerca de la Tierra