Licence Info
Algorithmique Avancée
TD 11 : décembre 2005
Les algorithmes Fusion-Recherche

  1. Quel est le temps de calcul (à O( ) près dans le pire cas) d'une suite d'opérations fusion suivie d'une suite d'opérations recherche pour les trois algorithmes

    1. liste avec mise à jour du plus petit ensemble
      Réponse O(n logn).
    2. arbre avec le plus grand ensemble comme racine (fusion équilibrée) mais sans mise à jour des pointeurs
      Réponse O(n logn).
    3. (l'algorithme de Tarjan) arbre avec le plus grand ensemble comme racine et avec mise à jour des pointeurs (compression des chemins)?
      Réponse O(n log* n).
  2. Pour l'algorithme de Tarjan, quel est le nombre de mises à jour de pointeurs pour la suite d'opérations (si les deux ensembles sont de la même taille, on prendra le deuxième comme racine):
    on va supposer que l'algorithme de fusion ne fait pas de mises à jour sauf celles qui sont la conséquence des recherches des racines des deux arbres fusionnés
    fusion(1,2)            .
    fusion(3,4) .
    fusion(1,3) .
    chercher(1) 1
    fusion(7,8) .
    fusion(5,6) .
    fusion(6,8) .
    chercher(5) 1
    fusion(1,5) .
    chercher(1) 1
    fusion(9,10) .
    fusion(11,12) .
    fusion(9,11) .
    chercher(9) 1
    fusion(15,16) .
    fusion(13,14) .
    fusion(14,16) .
    chercher(13) 1
    fusion(10,14) .
    chercher(9) 1
    fusion(1,13) .
    chercher(2) 2 (noeuds 2 et 4)

    Réponse 8
  3. Dans l'arbre donné, les chiffres indiquent la taille de chaque sous-arbre;

    [l'exemple n'était pas bien choisi; en effet cet arbre ne peut pas être construit par l'algorithme, mais:]

                12
    / \
    / \
    / \
    5 6
    / \ / \
    / 2 / \
    2 / 3 2
    / 1 / \ \
    / / \ \
    1 1 1 1*

    1. Dessinez l'arbre produit par la compression des chemins si on fait une recherche sur l'élément marqué *,
      Réponse
             -----12-----
      / / \ \
      / / \ \
      / / \ \
      1 5 4 1
      / \ /
      / 2 /
      2 / 3
      / 1 / \
      / / \
      1 1 1

    2. Notez que dans cet arbre, pour le sous-arbre de taille 3 il n'est plus vrai que la taille du père est au moins 2 fois la taille d'un fils,
      Réponse taille du père=4.
    3. Expliquez comment l'analyse du temps de calcul peut prendre en compte ce type de possibilité et préserver la conclusion que le temps amorti des opérations est O(log*n).
      Réponse On raisonne avec une taille théorique de chaque sous-arbre qui est ce qui était sa taille réelle au moment où il a été attaché pour la première fois comme fils d'un autre.




File translated from TEX by TTH, version 3.05.
On 16 Dec 2005, 09:42.

symboles bricolés pour netscape par sed