Sujet 8 : génération d’arbres binaires aléatoires

Question 1 : algo de génération

set.seed(13)
N = 100; #Nous calculerons les 100 premiers nombres de Catalan

C = rep_len(0,N);
C[1] = 1;
C[2] = 1;

for(n in 3:N)
{
  res = 0
  for(q in 1:(n-1))
  {
    res = res + C[q]*C[n-q]
  }
  C[n] = res;
}

Ici, les 100 premiers nombres de Catalan ont étés calculés. Cela nous permet par la suite de faire des arbres aléatoires de 99 noeuds. (C[1] correspond à 0 noeuds)

On créé l’arbre récursivement. Pour ça, on utilise la fonction assembler, qui créé un noeud et y lie les arbres donnés en arguments. (Nous représenterons nos arbres par des listes de listes)

assembler = function(arbre1, arbre2)
{
  return(list(arbre1,arbre2))
}

On utilise la formule vue en TD, permettant de construire un arbre aléatoire prenant en considération le nombre d’arbres possibles pour n noeuds.

creer_arbre = function(n)
{
  if(n == 0) {
    return(NULL);
  } else  {
    n = n + 1;   #Les indices des vecteurs commencent à 1 donc il y a un décalage entre n et C[n]     

    p=0
    x = runif(1)
    i = 0
    repeat {
      p = p + C[i+1] * C[n-i-1] / C[n];
      i = i + 1;
      if(x<=p)
          break
    }
    return(assembler(creer_arbre(i-1),creer_arbre(n-i-1)));
  }
}

Question 2 : hauteur

Intuitivement, je me dis que plus l’arbre est grand, plus il y a de risque pour qu’un nouveau noeud n’augmente pas la taille de cet arbre. Je m’attend donc à une progression logarithmique. Je pense aussi que les arbres ont tendance à s’équilibrer. Hors la hauteur d’un arbre complet dépend de log2(nb_noeuds). On peut donc s’attendre à ce que cela intervienne dans l’évolution de la hauteur.

hauteur = function(l)
{
  if(is.null(l)) {
    return(0);
  }
  else 
  {
    return(1 + max(hauteur(l[[1]]), hauteur(l[[2]]))); 
  }
}

On créé une fonction qui permet de calculer n hauteurs d’arbres aléatoires (pour un nombre de noeuds donné)

distribution = function(n,nodes)
{
  res = rep(n)
  for(i in 1:n)
  {
    res[i] = hauteur(creer_arbre(nodes));
  }
  return(res)
}
nb_echantillons = 10000
#On étudie la distribution pour différents nombres de noeuds (sur 10000 échantillons) 

#-Pour 5 noeuds :
summary(distribution(nb_echantillons, 5))
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##   3.000   4.000   4.000   4.224   5.000   5.000
#-Pour 10 noeuds :
summary(distribution(nb_echantillons, 10))
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##   4.000   6.000   7.000   7.074   8.000  10.000
#-Pour 20 noeuds :
summary(distribution(nb_echantillons, 20))
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##     5.0    10.0    11.0    11.3    13.0    19.0
#-Pour 50 noeuds :
summary(distribution(nb_echantillons, 50))
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##       9      17      20      20      23      38
#-Pour 90 noeuds
summary(distribution(nb_echantillons, 80))
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##   13.00   22.00   26.00   26.34   30.00   53.00

On observe effectivement que la croissance de la hauteur est de plus en plus faible. On voit d’ailleurs que pour 10 noeuds, la hauteur moyenne est de 7.0, tandis que pour 80 noeuds (8 fois plus) la hauteur moyenne est de 26.3 (moins de 4 fois plus). Cependant, log(8)~=2. La croissance ne semble donc pas vraiment logarithmique.

En regardant les Quartiles et les valeurs extrêmes, on constate que la densité de probabilité semble se concentrer de plus en plus sur la médiane. Pour 80 noeuds, max-min = 41 alors que 3rdQu - med = med - 1stQu = 4. Ceci semble s’accorder avec le fait que les arbres aléatoires ont tendance à s’équilibrer (sans le prouver pour autant)

On créé ensuite une fonction qui calcule la moyenne des hauteurs d’arbre pour les arbres ayant 1 à N-1 noeuds. Cette fonction affiche aussi différentes courbes intéressantes :

-L’évolution de la hauteur moyenne en fonction du nombre de noeuds en bleu

-L’évolution de 2*sqrt(pi*n) en rouge

-L’évolution de log(n) en noir

-L’évolution de log2(n) en rose

-La différence entre la courbe rouge et la bleue (apparait en jaune)

-Une courbe représentant 2*sqrt(pi*n) + c*log(n) + c’ (avec des valeurs que j’ai déterminées sans calculs pour c et c’)

nb_echantillons = 1000 #1000 échantillons permettent de lisser de façon acceptable la courbe bleue

show_curves = function(n)
{
  moyennes = seq(1,N-1)
  for (i in 1:N-1)
  {
    moyennes[i] = mean(distribution(n,i))
  }

  racine = 2*sqrt(pi*seq(1,N-1))
  
  logar = log(seq(1,N-1))
  ln = log2(seq(1,N-1))
  
  esperance = racine-logar/2 -3
  
  test = racine - moyennes
  
  plot(moyennes, type="l",lwd=1.5, col="blue")
  lines(racine, type="l",lwd=1.5, col="red")
  lines(logar, type="l",lwd=1.5, col="black")
  lines(esperance, type="l",lwd=1.5, col="green")
  lines(ln,type = "l", lwd = 1.5, col = "pink")
  lines(test, type = "l", lwd = 1.5, col = "yellow")
}


show_curves(nb_echantillons)

Afin de déterminer c, j’ai constaté que E(Hn) s’approchait de la courbe rouge. J’ai donc soustrait à celle-ci la courbe représentant la moyenne. Le résultat apparaît en jaune et semble tendre vers log(n). Le résultat est peu concluant sur des valeurs entre 1 et 100 noeuds mais au delà, les nombres de Catalan sont trop élevés.

J’ai donc commencé par attribuer à c la valeur -1 puis ai ajusté ce coefficient ainsi que c’ pour obtenir un résultat proche de Hn, tout en respectant la forme 2sqrt(pi*n) + c*log(n) + c’ + o(1)

Le résultat que j’ai trouvé est c = -1/2 et c’ = -3. Ce résultat semble beaucoup s’approcher de Hn. Cependant, il serait préférable si possible de le vérifier sur des valeurs plus élevées de Hn