Evènement pour le groupe Combinatoire Énumérative et Algébrique


Date 2014-06-13  10:45-11:45
TitreArbres binaires, permutations et ordres d'insertion 
RésuméOn dispose d'une formule très simple pour le nombre d'ordres d'insertion donnant un arbre binaire de forme donnée (ou, de manière équivalente : pour le nombre d'étiquetages des nœuds d'un arbre binaire par les entiers de 1 à sa taille, de manière croissante le long des branches). Mais cette formule ne se traduit pas naturellement en un algorithme de génération aléatoire simple. Je décrirai deux algorithmes de génération aléatoire uniforme de tels ordres : l'un est asymptotiquement optimal en bits aléatoires, mais nécessite de manipuler de grands nombres. Le second, basé sur une bijection, permet de ne travailler qu'avec des entiers allant jusqu'à la taille de l'arbre, mais n'est pas optimal en bits aléatoires. 
Lieu076 
Orateur Philippe Duchon 



Aucun document lié à cet événement.

Retour
Retour à l'index