Samuel Fiorini a obtenu un consolidator grant de l’ERC

Imprimer la pageImprimer la page || VERSION PDF: Enregistrer au format PDF

ERC :un nouveau grant en mathématique

Samuel Fiorini décroche un consolidator grant du Conseil européen de la recherche (ERC) pour une recherche mêlant algorithmes et géométrie.

Imaginez que vous deviez vous rendre d’un point A à un point B, quel chemin le plus court ou le plus rapide emprunter ? Rien de plus facile, votre GPS va le calculer, pensez-vous ? Et vous avez raison : n’importe quel GPS pourra vous fournir la réponse rapidement. Mais imaginez maintenant que vous alliez non pas de A à B, mais de A à Z, en passant entre autres par D, G ou encore L, selon un ordre à définir, le tout en évitant les pertes de temps et retours sur ses pas, tout en devant gérer des livraisons périssables et une météo instable... Là, le problème devient complexe, voire trop complexe : dès que le nombre de points dépasse les cent mille, nous sommes incapables d’en trouver une solution optimale aujourd’hui tant la puissance de calcul et le temps nécessaire sont considérables.

Chargé de cours au Département de mathématique en Faculté des Sciences, Samuel Fiorini s’intéresse à la théorie de la complexité, qui se situe à l’interface entre mathématique et informatique. La question phare de cette théorie est la question P versus NP. Le Clay Mathematics Institute offre une prime d’1 million de dollars pour sa résolution ! Les problèmes dans P – par exemple trouver un plus court chemin entre un point A et un point B dans un réseau routier – peuvent être résolus rapidement. Autrement dit, il existe pour chacun de ces problèmes, un algorithme efficace. En revanche, il existe beaucoup de problèmes dans NP pour lesquels on ne connaît pas de tels algorithmes ; ces problèmes semblent nécessiter un temps de calcul croissant très rapidement. Par définition, tous les problèmes dans P sont en particulier dans NP. La question P versus NP est de démontrer mathématiquement que tous les problèmes dans NP sont également dans P, ou au contraire que P et NP sont différents, ce qui signifierait que pour une large part des problèmes, tout algorithme doit d’une manière ou d’une autre recourir à la recherche exhaustive pour trouver une solution optimale, résultant en un temps de calcul prohibitif.

Grace au soutien du Conseil européen de la recherche (ERC), Samuel Fiorini va mettre en place une équipe – 2 doctorants, 3 post-docs seront engagés à partir d’octobre 2014 – au sein du service de Géométrie, Combinatoire et Théorie des groupes pour étudier la théorie de la complexité par un biais géométrique. « J’ai abordé ces problèmes dans un article, co-écrit notamment avec Serge Massar du service OPERA puisqu’il existe des liens étroits avec la physique quantique. L’article a été reconnu meilleur article du Symposium on Theory of Computing (STOC) en 2012 et a suscité beaucoup de discussions sur des blogs scientifiques » explique Samuel Fiorini, « Mon projet ERC vise à mieux comprendre une méthodologie puissante et très utilisée consistant à reformuler un problème complexe de manière géométrique, avec autant de dimensions qu’il y a de variables. On obtient alors un objet mathématique, un polytope (généralisation des polygones et polyèdres que l’on connaît en 2D et 3D). Chaque sommet du polytope correspond à une solution du problème ; nous cherchons un point d’hauteur maximum dans une certaine direction qui donnera la meilleure solution. En étudiant la complexité de ces polytopes, j’espère mieux cerner la complexité des problèmes correspondants et réussir à les catégoriser en problèmes solubles ou insolubles par cette méthodologie géométrique ».

Nathalie Gobbe

Source : Esprit libre Jan. – Fév. – Mars 2014 – n° 31 p. 18

Mis en ligne le 28 février 2014 par Charlotte BOUCKAERT