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é.
| Dernière modification : Thursday 21 November 2024 |
|
Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |