Journée-séminaire de combinatoire

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

Le 07 mai 2019 à 15h30 en B107, Axel Bacher nous parlera de : Algorithmes de rattrapage pour la génération aléatoire de chemins (attention horaire exceptionnel suite à comité de sélection de ~13h à ~15h)

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 : Wednesday 24 April 2019 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr