Exercice 1 1.a Pour l'implémentation sous la forme d'arbre 2-3, il faut un objet en-tête (car il s'agit d'un type abstrait, et on ne peut pas se permettre de renvoyer un arbre modifié, comme c'est le cas d'un type concret comme l'arbre 2-3). Cet objet en-tête contiendra deux champs. Le premier, nommé arbre, contenant l'arbre 2-3, initialement vide (représenté comme d'habitude avec NIL). Le deuxième, appelé inf, sera utilisé pour stocker la fonction inf pour comparer deux objets du domaine. Je ne vous ai pas demandé d'écrire la fonction de création d'une file de priorités, mais la voici quand même : file-de-priorité créer-file-de-priorité(fonction inf) renvoyer allouer-file-de-priorité(NIL, inf) L'opération vide? est particulièrement simple : booléen vide?(file-de-priorité f) renvoyer arbre(f) = NIL La différence entre la file de priorité ici et l'arbre 2-3 traité en cours et que l'arbre 2-3 contient à la fois des clés et des objets associés aux clés. Ici, en fait, un objet est sa propre clé. Avec ça, on peut implémenter la fonction d'insertion comme ceci : insérer(file-de-priorité f, objet obj) arbre(f) <- insérer(arbre(f), obj, obj, inf(f)) Pour trouver le plus petit élément, il suffit de regarder la feuille qui se trouve à gauche. Mais il faut que la file de priorité ne soit pas vide pour que ça marche. objet premier(file-de-priorité f) assert(!vide?(f)) sommet <- arbre(f) tant que !feuille?(sommet) faire sommet <- gauche(sommet) renvoyer données(sommet) Finalement, pour supprimer le plus petit élément, on peut se servir de la fonction précédent et de la fonction existante de suppression dans un arbre 2-3 : supprimer(file-de-priorité f) obj <- premier(f) arbre(f) <- supprimer(arbre(f), obj, inf(f)) 1.b (n est le nombre d'objets stockés dans la file de priorité) opération complexité justification vide? O(1) une seule opération insérer O(log n) on fait appel à la fonction de l'arbre 2-3 ayant cette complexité premier O(log n) on fait une boucle dont le nombre d'itérations est la hauteur de l'arbre 2-3. supprimer O(log n) premier + suppression dans un arbre 2-3. 1.c Ce calcul a déjà été fait en cours. Pour avoir une estimation, on peut supposer que l'arbre ne contient que des sommets 2. Il y a une feuille par objet, et environ autant de sommets 2 que de feuilles. Chaque feuille contient un mot "gaspillé" (la clé) et chaque sommet 2 contient 3 mots (probablement arrondi à 4 par le système), pour un total d'environ 5*8 = 40 octets par objet. On peut compter quelques en-têtes si l'on veut pour arriver à 8 mots, soit 64 octets, mais l'ordre de grandeur est ça. Autrement dit, une estimation inférieur à 32 octets et supérieur à 100 octets n'est pas raisonnable. Exercice 2 2.a Il y a plusieurs variations possibles. Utilisation de sentinelles ou non, intégration des cellules et des tableaux ou tableaux séparés, etc. Vous trouvez une implémentation sans sentinelles et tableaux séparés à cette adresse : http://dept-info.labri.fr/~strandh/structure.pdf Le champ liste de la séquence pointe sur la cellule actuelle de la liste, à savoir la cellule où la dernière opération a été effectuée. Le champ taille de la séquence contient le nombre d'éléments actuellement dans la séquence. Le champ taille-prefixe contient le nombre d'éléments qui précèdent la cellule actuelle. Chaque cellule contient un champ prec et un champ suiv pour le chaînage, un champ taille contenant le nombre d'éléments stockés dans le tableau, et un champ tableau contenant le tableau de taille fixe. La taille d'une tableau est la valeur de la variable TAILLE. 2.b [solution partielle] ajuster-cache(séquence s, entier position) // cette boucle sera exécutée si la position // se trouve dans une cellule qui précède la // cellule actuelle tant que position < taille-prefixe(s) faire liste(s) <- prec(liste(s)) taille-prefixe(s) <- taille-prefixe(s) - taille(liste(s)) // cette boucle sera exécutée si la position // se trouve dans une cellule qui suit la // cellule actuelle tant que position >= taille-prefixe(s) + taille(liste(s)) faire taille-prefixe(s) <- taille-prefixe(s) + taille(liste(s)) liste(s) <- suiv(liste(s)) objet récupérer(séquence s, entier position) assert(position >= 0 & position < taille(s)) ajuster-cache(s, position) // lorsqu'on arrive ici, la position est dans le tableau // de la cellule actuelle renvoyer tableau(liste(s))[position - taille-prefixe(s)] insérer(séquence s, entier position) assert(position >= 0 & position <= taille(s)) si position = 0 alors ajuster-cache(s, 0) sinon ajuster-cache(s, position - 1) si taille(liste(s)) = TAILLE alors t <- allouer-tableau(TAILLE) c <- allouer-cellule(suiv(liste(s)), liste(s), TAILLE / 2, t) prec(suiv(liste(s))) <- c suiv(liste(s)) <- c déplacer-intervalle(tableau(liste(s)), TAILLE / 2, TAILLE, t, 0) taille(liste(l)) <- TAILLE / 2 // tester si la position est dans le nouveau tableau si position > taille-prefixe(s) + TAILLE / 2 alors taille-prefixe(s) <- taille-prefixe(s) + TAILLE / 2 liste(s) <- suiv(liste(s)) // insérer l'objet l <- liste(s) t <- tableau(l) p <- position - taille-prefixe(s) déplacer-intervalle(t, p, taille(l), t, p + 1) remplir-trou(t, p, taille(l)) t[p] <- obj taille(l) <- taille(l) + 1 taille(s) <- taille(s) + 1 2.c Il faut que la taille du tableau soit considérablement plus grande que celle d´une cellule de la liste, afin que la place occupée par les cellules soit négligeable par rapport à la place occupée par le texte. Mais il faut également que la taille du tableau soit raisonnable, afin d'éviter un coût trop élevé pour les opération d'insertion et de suppression. Une cellule occupe (dans mon exemple) 4 mots, soit 32 octets s'il s'agit d'un ordinateur dont un mot fait 64 bits. Il faut donc une taille de tableau considérablement plus grande que 32 octets. Pour les opérations d'insertion et de suppression, en moyenne, il faut déplacer la moité du contenu d'un tableau. Ceci ne se fait pas un octet à la fois, mais un mot (voire plus) à la fois. Déplacer quelques dizaines de mots ne pose certainement pas de problème, car la gestion des curseurs risque de coûter encore plus que ça. On peut donc facilement imaginer une taille de tableau d'environ 100 mots sans que cela influence la performance de ces opérations. 2.d Il n'est pas nécessaire de pointer sur le début et la fin de la liste des cellules comme le montre la figure http://dept-info.labri.fr/~strandh/structure.pdf Les pointeurs "suiv" dans les cellules qui précèdent le cache sont donc inutiles, et pointeurs "prec" dans les cellules qui suivent le cache le sont également. On peut donc utiliser un seul champ pour les deux pointeurs.