Journée-séminaire de combinatoire

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

Le 02 juillet 2014 à 14h45 en B107, Nicolas Basset nous parlera de : Génération aléatoire via les langages temporisés

Résumé : A chaque langage régulier, on associe la classe (appelée régulière) de permutations ayant un motif d'ascentes/descentes (a/d) dans ce langage régulier de {a,d}*. Par exemple, on peut définir ainsi les permutations alternantes, les permutations n’ayant pas deux descentes consécutives, les permutations ayant un nombre pair de descentes... J’expliquerai un algorithme qui étant donné un automate renvoie une formule close pour la série génératrice exponentielle de la classe régulière de permutations associée. J’expliquerai ensuite un algorithme qui permet de générer des permutations aléatoirement et de façon uniforme les permutations de même longueur de la classe régulière de permutations considérée. Les deux algorithmes sont basés sur une correspondance entre comptage de permutations et volumes de langages temporisés qui s’explique en terme de polytopes d’ordre et polytopes de chaîne de Stanley. Les deux algorithmes évoqués ci-dessus sont ainsi obtenus à partir d’algorithmes de calcul de fonction génératrice des volumes et de génération aléatoire de mots temporisé associés à un automate temporisé.

 [Slides.pdf]


Dernière modification : jeudi 19 juin 2014 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr