Investigadores de la Universidad de Copenhague y la Universidad Técnica de Dinamarca DTU pensaron que faltaban cinco años para resolver un acertijo matemático de la década de 1980. En realidad, y sin saberlo, casi habían resuelto el problema y acababan de dargran parte de la solución en un artículo de investigación. La solución podría usarse para mejorar los teléfonos y computadoras del mañana.
Jacob Holm y Eva Rotenberg
Los dos informáticos, el profesor asistente Jacob Holm de la UCPH y la profesora asociada Eva Rotenberg de DTU casi regalaron su solución en el verano de 2019, después de enviar un artículo de investigación que se convirtió en el precursor del artículo en el que finalmente resolvieron las matemáticasenigma.
Un verdadero acertijo. Así es como se puede describir con seguridad este problema matemático en la disciplina de la teoría de grafos. Dos matemáticos del Departamento de Ciencias de la Computación y DTU de la Universidad de Copenhague han resuelto un problema que los más rápidos e inteligentes del mundo han sidoluchando desde la década de 1980.
Los dos informáticos, el profesor asistente Jacob Holm de la UCPH y la profesora asociada Eva Rotenberg de DTU casi regalaron su solución en el verano de 2019, después de enviar un artículo de investigación que se convirtió en el precursor del artículo en el que finalmente resolvieron las matemáticasenigma.
"Casi nos habíamos dado por vencidos en conseguir la última pieza y resolver el acertijo. Pensamos que teníamos un resultado menor, uno que era interesante, pero de ninguna manera resolvió el problema. Supusimos que habría otros cinco años de trabajo, en el mejor de los casos, antes de que podamos resolver el rompecabezas ", explica Jacob Holm, que es parte de BARC, la sección de algoritmos del Departamento de Ciencias de la Computación de la UCPH.
El problema de las tres utilidades
En 1913, un precursor del acertijo matemático ahora resuelto se publicó en "The Strand Magazine" como "El problema de las tres utilidades". Esto hizo que los lectores de la revista se rascaran la cabeza y reflexionaran. En el problema, cada una de las tres cabañas debetener agua, gas y electricidad, mientras que las "líneas" entre las casas y el agua, la electricidad y el gas no pueden cruzarse entre sí, lo cual no es posible.
Una solución entre líneas
En pocas palabras, el acertijo trata sobre cómo conectar una cantidad de puntos en un gráfico sin permitir que las líneas que los conectan se crucen. Y cómo, con un cálculo matemático, un algoritmo, puede realizar cambios en un gráfico extensored "para garantizar que ninguna línea se cruce sin tener que empezar de nuevo. Propiedades que pueden utilizarse, entre otras cosas, para construir inmensas redes de carreteras o las diminutas entrañas de las computadoras, donde los circuitos eléctricos de las placas de circuitos no pueden cruzarse.
Jacob Holm ha estado interesado en el acertijo matemático desde 1998, pero la respuesta solo se reveló mientras los dos investigadores estaban leyendo su artículo de investigación ya enviado. Mientras tanto, los investigadores escucharon acerca de una nueva técnica matemática que se dieron cuenta que podría seraplicado al problema.
"Al leer nuestro artículo de investigación, de repente nos dimos cuenta de que la solución estaba ante nuestros ojos. Nuestra siguiente reacción fue 'oh no, nos disparamos en el pie y regalamos la solución', dice la profesora asociada Eva Rotenberg deDTU.
Acerca de la teoría de grafos
UN GRÁFICO es una construcción muy simple que se usa para modelar cosas que se pueden describir como objetos y las conexiones entre ellos. La teoría de gráficos es tanto un área de las matemáticas como una herramienta importante en la informática.
En este contexto, un gráfico se puede ilustrar mediante un diagrama que consta de un número de puntos nodos, vértices asociados con un número de líneas bordes. Cada borde se ilustra como una línea o pieza curva con nodos comosus dos puntos finales.
sobre la solución
Hay dos tipos de actualizaciones en los gráficos dinámicos: uno puede eliminar un borde y puede insertar un nuevo borde. Estas dos operaciones deben ser realizadas por el usuario, mientras que un algoritmo realiza un seguimiento del dibujo de la red en todo momento. Esto esel algoritmo para el que los investigadores han encontrado la receta.
podría usarse para electrónica de computadora
Aquí es cuando los dos investigadores se dedicaron a escribir el artículo de investigación y atar cabos sueltos para resolver el enigma en el que Holm había estado trabajando de forma intermitente desde 1998.
"Trabajamos en el artículo sin parar, durante cinco a seis semanas. Y terminó llenando más de 80 páginas", dice Eva Rotenberg.
Afortunadamente, nadie se les adelantó en la solución y los dos investigadores pudieron presentar sus resultados en las principales conferencias teóricas de ciencias de la computación, que debían celebrarse en Chicago, pero terminaron de forma virtual.
Entonces, ¿para qué se puede usar la solución a este enigma matemático? Los dos investigadores no lo saben con certeza, pero tienen algunas sugerencias.
"Nuestra investigación es básica, por lo que rara vez sabemos para qué terminará siendo utilizada. Incluso desde el principio, encontramos aplicaciones difíciles de imaginar", dice Jacob Holm, quien agrega :
"el diseño de microchips y placas de circuito, que se encuentran en todos los componentes electrónicos, podría ser un área en la que nuestro resultado termine siendo utilizado. Al dibujar cables en una placa de circuito, nunca deben cruzarse. De lo contrario, se producirán cortocircuitos. Lo mismose aplica a los microchips, que contienen millones de transistores y para los cuales se debe tener un dibujo gráfico ".
Fuente de la historia :
Materiales proporcionado por Universidad de Copenhague . Nota: el contenido se puede editar por estilo y longitud.
Referencia de la revista :
cite esta página :