Evènement pour le groupe Combinatoire Énumérative et Algébrique


Date 2013-10-04  10:45-11:45
TitreGénération aléatoire uniforme dans les langages rationnels 
RésuméLes algorithmes de génération de mots aléatoires uniformes (de longueur n fixée) dans un langage rationnel, langage typiquement décrit par un automate, abondent dans la littérature. Les meilleurs ont comme point commun de travailler en temps linéaire ou quasi linéaire après un pré-calcul qui revient, d'une manière ou d'une autre, à compter combien il existe de mots de différentes longueurs ; ce pré-calcul est donc à refaire, ou à affiner, si la longueur des mots qu'on engendre change. La voie que nous explorons, consiste à trouver, dans le graphe orienté défini par l'automate du langage, une marche aléatoire biaisée qui donne « presque » des mots uniformes ; le « presque » étant contrôlé par un rejet. On obtiendrait alors un algorithme de génération aléatoire (exactement) uniforme, dont la complexité moyenne serait linéaire, après un pré-calcul qui aurait la propriété remarquable de ne pas dépendre de la longueur des mots à engendrer. Sans surprise pour les habitués, les suites de comptages sont remplacées par des évaluations de séries génératrices. Dans ce travail en cours avec Adrien Boussicault, on montrera que ce programme peut être mené à bien au moins dans le cas particulier où le graphe orienté défini par l'automate est fortement connexe. Le cas de graphes non fortement connexes reste ouvert, ou en cours, selon qu'on est optimiste ou non.  
Lieu076 
OrateurPhilippe Duchon 



Aucun document lié à cet événement.

Retour
Retour à l'index