Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 10 janvier 2017 à 14h00 en B107, Philippe Duchon nous parlera de : Permutations aléatoires et cycles courts (via des arbres de génération)

Résumé : Tirer une permutation aléatoire uniforme de taille n n'est pas bien difficile, et on sait assez bien à quoi c'est censé ressembler. Qu'en est-il si on souhaite imposer des restrictions sur le type cyclique? Il n'est pas bien difficile non plus de tirer une permutation aléatoire ayant un nombre prédéterminé de points fixes - il suffit de savoir tirer un dérangement, et à grande taille, près de 37% des permutations sont des dérangements. On a donc facilement un algorithme qui va nécessiter en moyenne O(n) tirages d'entiers aléatoires d'ordre O(n). Dans ce travail en commun avec Romaric Duvignau (EJC, 2016), nous montrons comment cela peut être fait avec n+O(1) tirages en moyenne, par un rejet anticipé. Cela est possible grâce à la construction d'un arbre de génération pour les permutations, qui a la particularité de "fixer" très rapidement, et aussi vite qu'il est possible, le nombre de points fixes. Comme conséquences faciles, on a alors des algorithmes tout aussi efficaces pour tirer des permutations aléatoires avec un nombre prescrit de points fixes. Le passage de "points fixes" à "cycles d'une longueur k donnée" est possible, mais sensiblement moins élégant.


Dernière modification : mercredi 04 janvier 2017 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr