Le professeur Piotr Sankowski, informaticien à l’Université de Varsovie, est à la recherche d’algorithmes qui fonctionneraient le mieux, quelles que soient les circonstances. Ses travaux peuvent contribuer au développement de l’informatique moderne.
Le Conseil européen de la recherche (ERC) est l’une des institutions les plus importantes et les plus prestigieuses à offrir des subventions aux chercheurs. Piotr Sankowski de la Faculté des mathématiques, d’informatique et de mécanique de l’Université de Varsovie appartient à un petit groupe de chercheurs qui ont bénéficié plusieurs fois d’une bourse ERC.
Son premier projet portait sur la conception et l’analyse d’algorithmes d’approximation pour des problèmes dont la solution précise est impossible, en raison du temps excessif que prendraient les calculs. La deuxième subvention concernait la commercialisation des résultats de ces recherches. La dernière bourse (plus de 1,5 million d’euros) permet de financer le projet intitulé « Vers l’unification des outils algorithmiques ». Son objectif est de développer des algorithmes universels.
– Un algorithme, c’est…?
Piotr Sankowski: – Une liste d’instructions pour l’ordinateur indiquant comment il doit effectuer des tâches simples, en vue de la réalisation d’opérations plus complexes. Différents problèmes requièrent différentes instructions.
Et l’algorithme universel?
C’est un algorithme aussi efficace que possible, quels que soient les détails du problème donné. Supposons que nous ayons une fonction mathématique à résoudre, par exemple la multiplication. Le problème est qu’aujourd’hui, nous pouvons imaginer dix algorithmes différents prescrivant la manière dont l’ordinateur doit faire cette multiplication, mais nous ne pouvons pas décider lequel est le meilleur, car chacun peut bien servir dans un cas différent. Un algorithme peut mieux fonctionner en pratique, tandis qu’un autre est meilleur, mais seulement en théorie. Encore un autre fonctionne mieux pour des nombres spécifiques, et ainsi de suite. C’est pourquoi il est difficile d’utiliser des algorithmes, car il faudrait être un expert pour savoir quel algorithme doit être utilisé dans tel cas donné. En outre, les algorithmes les plus récents et les meilleurs sont difficiles à appliquer. Par conséquent, on ne les utilise pas, car les solutions universelles n’existent pas encore.
Votre équipe tente de développer de tels algorithmes universels. Quels problèmes sont-ils censés résoudre?
Nous nous concentrons sur trois domaines. Premièrement, nous voulons concevoir des algorithmes universels pour les problèmes de graphes statiques. Un graphe peut être comparé à une carte routière avec des routes et des carrefours. L’un des problèmes les plus simples que les algorithmes peuvent résoudre sur les graphes est de rechercher le chemin le plus court du point A au point B.
Le deuxième domaine concerne les problèmes de réseaux en ligne. Ici, la situation est différente, car nous ne disposons pas de toutes les données. Revenons à l’image de notre carte routière : dans ce cas, nous serions par exemple confrontés à la fermeture d’une des routes. Le nouvel algorithme doit faire face à ce genre de problèmes imprévisibles.
Le troisième domaine implique l’utilisation des propriétés de données supplémentaires.
C’est-à-dire?
Revenons à l’exemple de l’itinéraire le plus court. Il peut s’avérer que ce problème doive être traité différemment, selon si nous le recherchons sur une carte de l’Europe ou s’il s’agit d’une carte de l’Afrique. C’est pourquoi tel algorithme fonctionne mieux pour la carte de l’Europe, alors qu’un autre – pour celle de l’Afrique. Notre objectif est de développer un algorithme universel qui pourrait utiliser les propriétés de données spéciales.
Vos recherches peuvent-elles avoir un impact sur le travail des informaticiens?
Même si actuellement on élabore des algorithmes de plus en plus parfaits, ils ne sont pas largement utilisés, car ils sont si complexes que personne ne sait comment le faire. Nous voulons que nos solutions soient simples et universelles. Nous espérons que nos recherches auront une incidence sur l’utilisation pratique des algorithmes.
Les étudiants polonais en informatique remportent régulièrement des médailles aux concours dans ce domaine. L’équipe de l’Université de Varsovie est ici exceptionnelle, elle a participé à chacune des 25 dernières finales du Concours international de programmation compétitive – le plus ancien et le plus prestigieux concours informatique pour les étudiants. Au total, jusqu’en 2019, les informaticiens de l’Université de Varsovie ont remporté deux fois le championnat du monde et ils ont gagné quinze médailles.
D’autres équipes polonaises remportent également des succès. L’université Jagellonne a participé douze fois à la finale et a remporté trois médailles. L’Université de Wrocław a participé onze fois à la finale et a remporté trois médailles. L’École des mines et de la métallurgie de Cracovie (AGH) et l’École polytechnique de Poznań sont aussi arrivées en finale toutes les deux.
Université de Varsovie
