Langages de programmation, algorithmes et structures : modèles et analyse – PLASMA

Un examen approfondi des algorithmes implantés dans les bibliothèques standard des langages de programmation modernes révèle qu'ils s'écartent souvent significativement des algorithmes traditionnels enseignés dans les manuels. Même pour les structures de données et les algorithmes classiques, comme les tables de hachage ou les méthodes de tri, une analyse du code source montre que les ingénieurs dévient souvent des chemins attendus, créant de nouveaux algorithmes ou combinant des techniques existantes de manière innovante.

Il existe deux principales motivations pour s'écarter des algorithmes classiques. La première est de tirer parti des caractéristiques des architectures informatiques modernes, telles que la mémoire cache, les instructions vectorielles (SIMD) ou la prédiction de branchement. La seconde est d'optimiser les performances de l'algorithme pour les données du monde réel.

Dans le cadre de ce projet, nous avons réuni des théoriciens de l’informatique partageant un intérêt commun : apporter un éclairage mathématique aux implantations concrètes. L'un des principaux défis consiste à élaborer des modèles abstraits d’ordinateurs qui incorporent des éléments d’architecture moderne. Ces modèles doivent être assez précis pour refléter finement les performances réelles des algorithmes, tout en demeurant suffisamment épurés pour rester mathématiquement analysables. Par ailleurs, une analyse théorique approfondie de performances des solutions implantées dans les langages de programmation nous permettra d’identifier les paramètres des données d’entrée, ainsi que les scénarios d'utilisation typiques, que les ingénieurs ont privilégiés pour optimiser leurs algorithmes. Notre démarche consiste donc à déduire des informations pertinentes ou à valider des hypothèses concernant les données réelles en étudiant attentivement les choix d’implantation retenus dans les algorithmes actuellement utilisés en production. En développant tous ces aspects, l’objectif général du projet est donc de constituer une de base solide, contenant à la fois des modèles et les outils mathématiques pour les étudier, pour de futurs travaux de la communauté scientifique en analyse d’algorithmes.