Des chercheurs en informatique de l'Université de Copenhague et de l'Université technique du Danemark (DTU) pensaient qu'il leur restait cinq ans avant de résoudre une énigme mathématique des années 1980. En réalité, et sans le savoir, ils avaient presque résolu le problème et venaient de donner une grande partie de la solution dans un article de recherche. La solution pourrait être utilisée pour améliorer les téléphones et les ordinateurs de demain.

Jacob Holm et Eva Rotenberg

Un véritable casse-tête. C'est ainsi que l'on peut décrire en toute sécurité ce problème mathématique dans la discipline de la théorie des graphes. Deux mathématiciens du département d'informatique de l'Université de Copenhague et du DTU ont maintenant résolu un problème auquel les plus rapides et les plus intelligents du monde se débattent depuis les années 1980.

Les deux informaticiens, Le professeur assistant Jacob Holm de l'UCPH et la professeure agrégée Eva Rotenberg du DTU ont failli donner leur solution à l'été 2019, après avoir soumis un article de recherche qui est devenu le précurseur de l'article dans lequel ils ont finalement résolu l'énigme mathématique.

"Nous avions presque renoncé à obtenir le dernier morceau et à résoudre l'énigme. Nous pensions que nous avions un résultat mineur, un qui était intéressant, mais en aucun cas résolu le problème. Nous avons deviné qu'il y aurait encore cinq ans de travail, au mieux, avant de pouvoir résoudre le puzzle, " explique Jacob Holm, qui fait partie de BARC, la section algorithme du Département d'informatique de l'UCPH.

Le problème des trois utilitaires

En 1913, un précurseur de l'énigme mathématique maintenant résolue a été publié dans Le magazine Strand comme "Le problème des trois services publics". Cela a amené les lecteurs du magazine à se gratter la tête et à réfléchir. Dans le problème, chacun des trois chalets doit avoir de l'eau, gaz et électricité, tandis que les "lignes" entre les maisons et l'eau, l'électricité et le gaz peuvent ne pas se croiser, ce qui n'est pas possible.

Une solution entre les lignes

Tout simplement, le puzzle concerne la façon de connecter un certain nombre de points dans un graphique sans permettre aux lignes qui les relient de se croiser. Et comment, avec un calcul mathématique - un algorithme - vous pouvez apporter des modifications à un "réseau graphique" étendu pour vous assurer qu'aucune ligne ne se coupe sans avoir à tout recommencer. Propriétés qui peuvent être utilisées pour, entre autres, construire d'immenses réseaux routiers ou les minuscules entrailles d'ordinateurs, où les circuits électriques sur les cartes de circuits imprimés ne peuvent pas se croiser.

Jacob Holm s'intéresse à l'énigme mathématique depuis 1998, mais la réponse n'a été révélée que pendant que les deux chercheurs lisaient leur article de recherche déjà soumis. En attendant, les chercheurs ont entendu parler d'une nouvelle technique mathématique dont ils ont réalisé qu'elle pouvait être appliquée au problème.

"En lisant notre article de recherche, nous avons soudain réalisé que la solution était sous nos yeux. Notre réaction suivante a été "oh non, nous nous sommes tirés une balle dans le pied et avons donné la solution, ", déclare la professeure agrégée Eva Rotenberg du DTU.

À propos de la théorie des graphes

Un graphe est une construction très simple utilisée pour modéliser des choses qui peuvent être décrites comme des objets et les connexions entre elles. La théorie des graphes est à la fois un domaine des mathématiques et un outil important en informatique.

Dans ce contexte, un graphe peut être illustré par un schéma constitué d'un certain nombre de points (nœuds, sommets) associés à un certain nombre de lignes (arêtes). Chaque arête est illustrée par une ligne (ou une pièce incurvée) avec des nœuds comme ses deux extrémités.

A propos de la solution

Il existe deux types de mises à jour dans les graphiques dynamiques :l'une peut supprimer une arête et vous pouvez insérer une nouvelle arête. Ces deux opérations doivent être effectuées par l'utilisateur, tandis qu'un algorithme garde une trace du dessin du réseau à tout moment. C'est l'algorithme dont les chercheurs ont trouvé la recette.

Pourrait être utilisé pour l'électronique informatique

C'est à ce moment-là que les deux chercheurs se sont occupés de rédiger le document de recherche et de régler les détails pour résoudre l'énigme sur laquelle Holm travaillait par intermittence depuis 1998.

"Nous avons travaillé sur l'article sans arrêt, pendant cinq à six semaines. Et, il a fini par remplir plus de 80 pages, " dit Eva Rotenberg.

Heureusement, personne ne les a battus à la solution et les deux chercheurs ont pu présenter leurs résultats lors des principales conférences théoriques en informatique, qui devaient se tenir à Chicago, mais a fini par se tenir virtuellement.

Donc, à quoi peut servir la solution de cette énigme mathématique ? Les deux chercheurs ne savent pas avec certitude, mais ils ont quelques suggestions.

« Notre recherche est une recherche fondamentale, nous savons donc rarement à quoi il servira. Même depuis le début, nous trouvons des applications difficiles à imaginer, " dit Jacob Holm, qui ajoute, "La conception de puces électroniques et de circuits imprimés, trouvé dans tous les appareils électroniques, pourrait être un domaine où notre résultat finit par être utilisé. Lorsque vous dessinez des fils sur un circuit imprimé, ils ne doivent jamais se croiser. Autrement, des courts-circuits se produiront. Il en va de même pour les puces électroniques, qui contiennent des millions de transistors et pour lesquels il faut avoir un tracé graphique."