Investigadores en ciencias de la computación 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 revelar gran parte de la solución en un artículo de investigación. La solución podría utilizarse para mejorar los teléfonos y las computadoras del mañana.
Jacob Holm y Eva Rotenberg
Un verdadero desafío para la mente. 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 de la Universidad de Copenhague y DTU ahora han resuelto un problema con el que los más rápidos e inteligentes del mundo han estado luchando 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, tras enviar un artículo de investigación que se convirtió en el precursor del artículo en el que finalmente resolvieron el acertijo matemático.
"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 mejor, antes de que podamos resolver el rompecabezas ", explica Jacob Holm, quien 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 enigma matemático ahora resuelto se publicó en The Strand Magazine como "El problema de las tres utilidades". Hizo que los lectores de la revista se rascaran la cabeza y reflexionaran. En el problema, cada una de las tres cabañas debe tener agua, gas y electricidad, mientras que las "líneas" entre las casas y el agua, la electricidad y el gas pueden no cruzarse entre sí, lo que no es posible.
Una solución entre líneas
En pocas palabras, el acertijo trata de cómo conectar varios 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 una extensa "red de gráficos" para asegurarse de que ninguna línea se cruce sin tener que empezar de nuevo. Propiedades que se pueden utilizar, 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 pueden no cruzarse.
Jacob Holm ha estado interesado en el enigma matemático desde 1998, pero la respuesta solo se reveló mientras los dos investigadores leían su artículo de investigación ya enviado. Mientras tanto, los investigadores se enteraron de una técnica matemática novedosa que se dieron cuenta de que podría aplicarse al problema.
“Mientras leíamos 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 de DTU.
Acerca de la teoría de grafos
Un gráfico es una construcción muy simple que se usa para modelar cosas que pueden describirse como objetos y las conexiones entre ellos. La teoría de grafos es un área de las matemáticas y una herramienta importante en la informática.
En este contexto, un gráfico se puede ilustrar mediante un diagrama que consta de varios 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 como sus dos puntos finales.
Sobre la solución
Hay dos tipos de actualizaciones en los gráficos dinámicos: se puede eliminar un borde y se 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. Este es el algoritmo para el que los investigadores han encontrado la receta.
Podría usarse para electrónica informática
Fue entonces cuando los dos investigadores se pusieron ocupados escribiendo el trabajo de investigación y atando 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, encontró en toda la electrónica, podría ser un área donde nuestro resultado termina siendo utilizado. Cuando se dibujan cables en una placa de circuito, nunca deben cruzarse. De lo contrario, se producirán cortocircuitos. Lo mismo se aplica a los microchips, que contienen millones de transistores y para los cuales uno debe tener un dibujo gráfico ".
No hay comentarios:
Publicar un comentario