Dans cet exposé, nous étudions une distribution non-uniforme sur les permutations (de taille fixée quelconque), où la probabilité d’une permutation est proportionnelle à \(\theta^{rec}\), où \(rec\) désigne le nombre de records (ou maxima de gauche à droite).
La définition de ce modèle de permutations aléatoires non-uniformes est motivée par des questions d’analyse d’algorithmes. En effet, lors de l’analyse d’algorithmes fonctionnant sur des tableaux de nombres (modélisés par des permutations), on suppose généralement une distribution uniforme sur l’ensemble des entrées possibles. Cependant, les données réelles sur lesquelles ces algorithmes sont utilisés sont rarement uniformes et présentent souvent un biais vers les tableaux « partiellement triés ». Notre modèle rend compte de ce biais vers les tableaux « partiellement triés », tout en restant maniable du point de vue de l’analyse des algorithmes.
Nous obtenons trois types de résultats. Premièrement, nous présentons plusieurs générateurs aléatoires efficaces de permutations sous cette distribution. Deuxièmement, nous analysons le comportement de certaines statistiques classiques de permutation, dont certaines ont des applications dans l’analyse des algorithmes. Enfin, nous décrivons la « forme typique » des permutations dans notre modèle, à l’aide de leur permuton limite (déterministe).
Il s’agit d’un travail en collaboration avec Nicolas Auger, Cyril Nicaud et Carine Pivoteau.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne