Date/heure
12 mai 2022
10:45 - 11:45
Lieu
Salle de conférences Nancy
Oratrice ou orateur
Florent Koechlin (Loria)
Catégorie d'évènement Séminaire Probabilités et Statistique
Résumé
En informatique, les expressions aléatoires sont couramment utilisées pour analyser des algorithmes, que ce soit pour étudier leur complexité en moyenne, ou pour générer des benchmarks pour les tester expérimentalement. Généralement, ces approches considèrent les expressions en entrée comme des arbres purement syntaxiques, et font abstraction de leur sémantique, c’est-à-dire de l’objet mathématique représenté par l’expression.
Pourtant, deux expressions différentes peuvent être équivalentes (par exemple « 0*(x+y) » et « 0 » représentent la même expression, l’expression nulle). Ces phénomènes de redondances remettent-ils en question la pertinence de ces analyses et ces tests qui ne tiennent pas compte de la sémantique des expressions ?
Je présenterai comment la distribution uniforme sur les arbres syntaxiques d’expressions devient complètement dégénérée lorsqu’on commence à prendre en compte leur sémantique, dans le cas très simple mais courant où il existe un élément absorbant. Si le temps le permet, j’expliquerai pourquoi la distribution ABR laisse plus d’espoirs.
Il s’agit d’un travail effectué pendant ma thèse, en commun avec Cyril Nicaud et Pablo Rotondo.