Jeudi 16 octobre 2025 de 14h00 à 15h30
Amphi Ircica – 50 avenue Halley – Haute Borne – Villeneuve d’Ascq
Short Bio: Cyril Nicaud obtained his PhD from Paris 7, then became Associate Professor and later Full Professor at the University of Marne-la-Vallée (UGE). Former head of his lab (LIGM) and current head of his team, he works mainly on reconciling the theoretical analysis of algorithms with practice, studying how fundamental algorithms are implemented in contemporary programming languages.
Abstrat: Contemporary programming languages offer implementations of classical algorithms and classical data structures such as lists, hash tables, sorting, etc. Efficient algorithms for dealing with such issues have been known for several decades, since the beginning of computing, often with several efficient variants proposed in the literature.
However, a close examination of the actual implementation of these algorithms and data structures reveals that engineers went off tracks and developed powerful heuristics or even new algorithms. One reason for these choices, which we will illustrate by studying the Timsort algorithm, is the need for algorithms that are well-suited to the kinds of data users typically encounter. The other reason is the consideration of features of modern computer architectures, which we will illustrate by looking at how branch prediction mechanisms can be incorporated into the theoretical analysis of algorithms.
This is based on joined works with Nicolas Auger, Vincent Jugé, Carine Pivoteau and Stéphane Vialette.