Ma thèse :
Ma thèse est intitulée "Analyse réaliste d'algorithmes standards". Cette thèse est dirigée par Cyril Nicaud et est co-dirigée par Carine Pivoteau.
Dans le cadre de cette thèse, nous nous sommes intéressés à l'analyse de l'algorithme TimSort qui fut créé en 2002, puis implémenter dans des langages populaires comme Python et Java.
L'étude de TimSort nous a conduit à nous intéresser aux caractéristiques des architectures de nos machines actuelles. En particulier, nous nous sommes intéressés au cas de la prédiction de branchements. Nous avons ainsi proposé des modifications d'algorithmes élémentaires afin que ces derniers soient capables de guider les prédicteurs de branchements. Lorsque nous implémentons ces variantes sur des machines récentes, nous parvenons à obtenir de meilleurs temps d'exécutions. Nous nous sommes également intéressés à l'analyse d'algorithmes de tri dans le cas moyen. Par défaut, nous considérons que l'entrée de ces algorithmes est une distribution uniforme sur les permutations. Dans les applications réelles des algorithmes de tri, il semble cependant que ce ne soit pas la distribution la plus naturelle à considérer. Nous proposons ainsi d'étudier des distributions non-uniformes sur les permutations, dont en particulier une généralisation de la distribution d'Ewens qui est populaire chez les probabilistes.
Publications :
- Merge Strategies: from Merge Sort to TimSort; Non publié; Nicolas Auger, Cyril Nicaud, Carine Pivoteau.
- Good predictions are worth a few comparisons; STACS 2016; Nicolas Auger, Cyril Nicaud, Carine Pivoteau.
- Analysis of Algorithms for Permutations Biased by Their Number of Records; AofA 2016; Nicolas Auger, Mathilde Bouvel, Cyril Nicaud, Carine Pivoteau.