le 16 octobre 2025 à 14:00
Towards a more realistic analysis of algorithms
Les langages de programmation contemporains offrent des implémentations d’algorithmes classiques et de structures de données classiques telles que les listes, les tables de hachage, le tri, etc. Des algorithmes efficaces pour traiter ces questions sont connus depuis plusieurs décennies, depuis les débuts de l’informatique, et plusieurs variantes efficaces ont souvent été proposées dans la littérature.
Cependant, un examen attentif de l’implémentation réelle de ces algorithmes et structures de données révèle que les ingénieurs se sont écartés es sentiers battus et ont développé des heuristiques puissantes, voire de nouveaux algorithmes. L’une des raisons de ces choix, que nous illustrerons en en étudiant l’algorithme Timsort, est la nécessité de disposer d’algorithmes bien adaptés aux types de données que les utilisateurs rencontrent généralement. L’autre raison est la prise en compte des caractéristiques des architectures informatiques modernes, que nous illustrerons en examinant comment les mécanismes de prédiction de branche peuvent être intégrés dans l’analyse théorique des algorithmes.
Ceci est basé sur des travaux menés en collaboration avec Nicolas Auger, Vincent Jugé, Carine Pivoteau et Stéphane Vialette
Biographie :
Cyril Nicaud a obtenu son doctorat à Paris 7, puis est devenu professeur associé, puis professeur titulaire à l’Université de Marne-la-Vallée (UGE). Ancien directeur de son laboratoire (LIGM) et actuel responsable de son équipe, il travaille principalement à la conciliation de l’analyse théorique des algorithmes avec la pratique, en étudiant la manière dont les algorithmes fondamentaux sont mis en œuvre dans les langages de programmation contemporains.
En savoir plus...Amphi Ircica - 50 avenue Halley - Haute Borne - Villeneuve d'Ascq
français
English