C’est avec enthousiasme et presque soulagement que les chercheurs en informatique théorique évoquent les travaux de Sophie Huiberts et de son directeur de thèse, Daniel Dadush. Au sein du Centrum voor wiskunde en informatica, un centre national de recherche en informatique et en mathématiques aux Pays-Bas, ces deux informaticiens ont percé à jour les mystères de l’algorithme du simplexe. Si ce nom est inconnu du grand public, il fait pourtant partie intégrante de notre quotidien. Car ce programme informatique résout, en pratique, un grand nombre de problèmes très concrets. « Il peut être utilisé partout, de la planification des tournois de base-ball à la gestion des plans de vol pour les avions, en passant par la logistique militaire ou la collecte des ordures ménagères », énumère Sophie Huiberts, maintenant postdoctorante à l’université Columbia, aux Etats-Unis.
Pourtant, jusqu’à récemment, un halo de mystère entourait cet algorithme : impossible de prédire combien de temps il mettrait pour résoudre les problèmes qu’on lui soumettait. Daniel Spielman, professeur d’informatique à l’université Yale, aux Etats-Unis, explique : « On savait qu’il donnerait la réponse, mais serait-ce au bout de quelques minutes ? D’une semaine ? Impossible à dire avec certitude. Mais, en pratique, dans presque toutes les situations, il répondait très rapidement. Or, nous n’arrivions pas à trouver une explication à cela, c’était très frustrant ! »
Un comportement complexe
Comment concevoir que des programmes informatiques adoptent des comportements que les experts ne comprennent pas ? Les algorithmes auraient-ils donc une vie propre, un fonctionnement autonome ? Peut-être, d’après le professeur d’informatique Tim Roughgarden, de l’université Columbia : « Je crois que [les processus algorithmiques] sont découverts et non inventés, qu’ils font partie de l’univers dans lequel nous vivons. Mais même en considérant les algorithmes comme une création humaine, il n’est pas surprenant qu’ils puissent se révéler plus complexes que ce à quoi l’on s’attendait initialement. » Conséquence : il existe tout un domaine de recherche dont l’objectif est de développer des modèles mathématiques capables d’expliquer le comportement réel des algorithmes. Exactement comme des physiciens tentent de modéliser les trous noirs, ou des biologistes les processus génétiques.
C’est donc dans cette optique qu’au cours de sa thèse, soutenue en mai, Sophie Huiberts s’est penchée sur l’algorithme du simplexe, dans la droite ligne de Daniel Spielman, qui avait entrepris des travaux à ce sujet en 2001. Inventé par le mathématicien américain George Dantzig (1914-2005), en 1947, cet algorithme est une méthode de résolution des « problèmes d’optimisation linéaire ». « Imaginez que vous soyez un étudiant désargenté devant aller acheter de la nourriture, illustre Daniel Spielman. Vous pouvez vous demander quels produits acheter et dans quelles quantités afin de satisfaire vos apports journaliers recommandés [AJR] tout en dépensant le moins d’argent possible. Eh bien ça, c’est un problème classique d’optimisation linéaire. »
Il vous reste 48.32% de cet article à lire. La suite est réservée aux abonnés.
