avr. 2023
Intervenant : | Axel Bacher |
Institution : | LIPN, Institut Galilée, Université Sorbonne Paris Nord |
Heure : | 14h00 - 15h00 |
Lieu : | 3L15 |
Les algorithmes de rejet anticipé sont une classe d'algorithmes de
génération aléatoire dont les plus célèbres sont les algorithmes dits
florentins pour les mots de Motzkin (Barcucci et al., 1992). Je
présenterai plusieurs de ces algorithmes et montrerai des résultats
permettant de les analyser de manière systématique en loi limite. Je
montrerai aussi comment, dans certains cas (mots de Dyck ou arbres
binaires, notamment), on peut obtenir des algorithmes plus efficaces en
s'affranchissant de tout rejet. Enfin, je détaillerai les propriétés des
lois limites de ces algorithmes, dont les densités vérifient une
équation différentielle avec retard, ce qui entraîne une structure un
peu inhabituelle (par exemple, elles ont une singularité en tous les
points entiers).
Certains de ces travaux sont en commun avec Olivier Bodini, Alice
Jacquot, Andrea Sportiello.