|
|
|
Intitulé:
Arbres binaires, permutations et ordres d'insertion du groupe Combinatoire Énumérative et Algébrique
|
Date | 2014-06-13 10:45-11:45 |
Titre | Arbres 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. |
Lieu | 076 |
Orateur | Philippe Duchon |
Aucun document lié à cet événement. RetourRetour à l'index
| |