Salut,
ATTENTION, notez l'horaire inhabituel (15h30).
Cet après-midi, 07 mai 2019 à 15h30 en B107, Axel Bacher nous parlera de :
Algorithmes de rattrapage pour la génération aléatoire de chemins
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.
Thierry
