Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Arbres binaires, permutations et ordres d'insertion
du 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