Résumé : Cet exposé concerne la génération aléatoire de familles classiques de chemins (Dyck, Motzkin et Schröder et leurs préfixes). Le point de départ est l'algorithme florentin (Barcucci, Pinzani et Sprugnoli 1994+), qui utilise une méthode de rejet anticipé pour engendrer les préfixes. Je montrerai comment on peut raffiner cet algorithme en utilisant une fonction de « rattrapage » qui permet de fortement réduire, voire d'éliminer, la probabilité de rejet. Les algorithmes obtenus sont asymptotiquement optimaux en termes d'entropie utilisée et significativement plus rapides que les algorithmes florentins.

Dernière modification : Monday 18 March 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr