`: `; `! `?  

Figure

    Année 2006-2007 Session de Janvier 2007
   GU : Licence Sciences Technologies (semestre 5) UE : INF209
   Épreuve de : Algorithmique Avancée
   Date :

Durée : 3h
   Documents autorisés
   Épreuve de Monsieur Robson





1
[6 points]
Des arbres binaires peuvent être representés par des structures de noeuds, chaque noeud possédant un champ valeur:entier et deux champs gauche et droit qui seront des pointeurs vers les sous-arbres gauche et droit (ou nul).
On peut définir un ordre sur les arbres binaires tel que l'arbre vide précède tout autre arbre et, entre deux arbres non vides, l'un précède l'autre si sa valeur est inférieur, ou (dans le cas de deux valeurs égales) son sous-arbre gauche précède celui de l'autre, ou (dans les cas de deux sous-arbres gauches égaux) son sous-arbre droit précède celui de l'autre.
Ecrire en exalgo

  1. une fonction entière avec deux paramètres qui seront des pointeurs vers les racines de deux arbres (éventuellement vides) et qui retourne -1 si le premier arbre précède l'autre dans cet ordre, 0 si les deux sont identiques et +1 dans le dernier cas où le deuxième précède le premier.

  2. une procédure avec un paramètre, un tableaux de pointeurs vers la racine d'un arbre, et qui trie les pointeurs selon l'ordre de leur arbre, en utilisant la fonction de la partie précédente. (On n'exige pas que l'algorithme de tri soit efficace.)

2
[5 points]
On veut calculer la probabilité qu'un arbre binaire de recherche aléatoire de 1000 noeuds ait son hauteur strictement inférieure à 50.

  1. Donner une récurrence pour cette probabilité dans le cas général d'un arbre de n noeuds et hauteur inférieure à h.
    Vous devrez utiliser le fait que le sous-arbre gauche de cet arbre a un nombre g de noeuds avec probabilité 1/n pour tout g entre 0 et n-1.

  2. Donner une procédure pour calculer la probabilité demandée en utilisant la programmation dynamique.

3
[4 points]

  1. Donner des affectations d'initialisation et une boucle tant que qui calculent le plus grand entier i tel que i!+(2i)! soit inférieure à un entier positif donné m.

  2. Donner un invariant pour votre boucle et expliquer (sans démonstration) comment cet invariant peut être utilisé pour prouver que la boucle soit correcte.

4
5 [points]
Déterminer (en fonction de n à O( ) près) le temps de calcul des boucles (i), (ii), (iii), (iv) et (v)
(P() est une procédure dont le temps de calcul est constant.) 

  1. pour i allant de 1 a n*n par pas de 1 faire P(); finpour;



  2. pour i allant de 1 a n par pas de 1 faire 
   pour j allant de 1 a i par pas de 1 faire
      pour k allant de j a i par pas de 1 faire P()
      finpour
   finpour; 
finpour;



  3. i:=n;
tant que i>1 faire 
   si i mod 2 = 0 alors
      i:=i/2
   sinon
      i:=i-1 
   finsi
fintantque;



  4. pour i allant de 1 a n par pas de 1 faire 
   j:=1;
   tant que i+j<n faire j:=j*2;
   fintantque; 
finpour;



  5. i:=1;
tant que i<n*n faire
   i:=i+1+i/n /* arrondi vers le bas */
fintantque



File translated from TEX by TTH, version 3.05.
On 18 Jan 2007, 14:07.