Master 1 : STL Année 2017/2018
Algorithmique Avancée Examen Réparti 1
Les seuls documents autorisés sont les polys de cours, ainsi que la copie personnelle. Le barème donné est
indicatif.
Exercice 1 : QCM [4 points]
Dans ce QCM, pour chaque question vous devez donner 1 seule réponse et expliquer votre choix par une
ligne de texte ou une figure. Le barème est le suivant : réponse correcte et correctement argumen-
tée : 1 point. Réponse incorrecte ou correcte mais mal argumentée : 0 point. Il n’y a pas de
points négatifs.
Question 1 Pour un arbre bicolore contenant n Question 3 En utilisant un splay-tree de n
clés, l’algorithme permettant de calculer le plus pe- clés, on peut réaliser un tri des n clés
tit élément a une complexité au pire (en nombre de A. en temps amorti O(n log n).
nœuds traversés) en
A. Θ(1). B. Θ(log n). C. Θ(n). B. en temps moyen O(n log n).
Décrire succinctement cet algorithme. C. en temps pire O(n log n).
Question 2 Laquelle de ces 3 suites d’inégalités Question 4 Le nombre de comparaisons né-
d’ordres de grandeur est correcte, c’est-à dire cor- cessaires pour faire la fusion d’une file binomiale
recte à partir d’un certain rang n ∈ N (expliquer de 1221 éléments avec une file binomiale de 829
pourquoi les autres sont incorrectes) éléments est
A. 3n < n2 2n < n! < n10n . A. 15.
B. n4 log n < n5 < n4 2n . B. 12.
√
C. 2n < n! < ( n)n . C. 10.
Exercice 2 : Exercices [6 points]
Question 1 Donner un algorithme en O(n log n) comparaisons, qui étant donné une suite S de n
nombres entiers et un nombre donné x, détermine s’il existe deux nombres p1 et p2 dans S tels que
p1 + p2 = x.
Question 2 Soit un arbre 2-3-4 qui contient n clés. Supposons que son sous-arbre gauche ne contienne
que des 2-nœuds et son sous-arbre droit que des 4-nœuds. Montrer que le sous-arbre gauche contient
√
Θ( n) nœuds.
Question 3 On veut incrémenter un compteur binaire représenté
P i par un tableau A[0..k − 1] de k bits
(le tableau contenant le bit bi en case i représente l’entier bi 2 ).
1. Écrire l’algorithme pour passer de x à x + 1 dans le tableau ( pour 0 ≤ x ≤ 2k − 2). Quel est le
nombre maximum de flips (passage d’un bit de 1 à 0 ou de 0 à 1) pour une opération d’incrément ?
2. On montre ici que le coût amorti, en nombre de flips, pour incrémenter le compteur de 0 à n = 2k −1
est de O(1) pour une opération d’incrément.
(a) Méthode par agrégat : montrer que le nombre total de flips pour la suite des n incréments est
majoré par 2n.
(b) Méthode de potentiel : on considère la fonction qui à un tableau associe son nombre de
bits à 1. Montrer que c’est une fonction de potentiel. Quel est le coût amorti de l’opération
d’incrément de i vers i + 1 ?
1
Exercice 3 : Concaténation d’arbres 2-3-4 [14 points]
On considère le modèle des arbres 2-3-4 avec éclatements à la descente.
Question 1 Construire l’arbre 2-3-4, noté Ex1 , obtenu en insérant les clés dans l’ordre suivant :
5, 7, 13, 1, 18, 17, 9, 4, 3, 12, 15. On indiquera toutes les étapes intermédiaires.
Question 2 Construire l’arbre 2-3-4, noté Ex2 , obtenu en insérant les clés 25, 20, 22, 28, 21, 30, 26. On
peut directement donner l’arbre final sans les étapes intermédiaires.
Question 3 Donner un algorithme (son pseudo-code ou sa description détaillée) construisant la liste,
dans l’ordre croissant, des clés d’un arbre 2-3-4.
Question 4 Donner le pseudo-code d’un algorithme prenant en entrée un arbre 2-3-4, noté A, et
renvoyant un couple composé de la clé de valeur maximale de A et de l’arbre issu de A en supprimant
cette clé.
La suite de l’exercice consiste à obtenir une méthode efficace pour concaténer deux arbres 2-3-4, notés
par la suite A1 et A2 tels que les clés de A1 sont toutes plus petites (strictement) que les clés de A2 .
Question 5 On propose une première méthode naïve. On insère les clés de A2 successivement dans
A1 . Donner le pseudo-code d’un algorithme opérant selon ce principe. On utilisera la Question 3.
Question 6 Appliquer la méthode précédente aux arbres Ex1 issu de la Question 1 et Ex2 issu de la
Question 2.
Question 7 Dans le cas général, en supposant que les deux arbres A1 et A2 sont de taille similaire n,
quelle est la complexité de cette méthode en nombre de comparaisons ?
Nous allons désormais proposer une méthode plus efficace. On suppose que la hauteur h1 de A1 est
supérieure ou égale à h2 , celle de A2 .
Voilà les idées globales de la méthode
— On descend sur la branche droite de A1 jusqu’au nœud x de profondeur h1 − h2 . Soit Ax l’arbre
enraciné en x.
— On extrait la clé c, de valeur maximale de Ax (et on obtient donc Ãx ).
— On crée un nœud contenant les clés de x, suivies de c, suivies des clés de la racine de A2 . On
donne pour fils à ce nouveau nœud, les fils de la racine de Ãx suivis des fils de la racine de A2 .
— Alors, soit le nouveau nœud vérifie la contrainte de taille des arbres 2-3-4, et alors on a fini après
remplacement de Ax par ce nouvel arbre dans A1 .
— Soit il faut faire des éclatements à la remontée.
Question 8 Décrire avec des schémas les différents cas d’éclatements pouvant se présenter, et comment
chacun d’eux est traité.
Question 9 Donner le pseudo-code de cet algorithme.
Question 10 Quelle est la complexité de cet algorithme, en nombre de comparaisons ?
