Structure de données de corde (rope) pour la représentation efficace de grandes chaînes de caractères : opérations de base et algorithmes d'équilibrage (dont Garsia-Wachs)
Afficher ou masquer la section
Le sujet d'informatique de l'École polytechnique MP 2008 étudie la structure de corde, une alternative aux chaînes de caractères usuelles fondée sur un arbre binaire dont les feuilles sont des mots. Après des fonctions préliminaires sur les mots puis les opérations essentielles sur les cordes (longueur, concaténation, extraction de caractère et de sous-corde), le sujet aborde le problème de l'équilibrage d'une corde à travers un premier algorithme fondé sur les nombres de Fibonacci garantissant un coût moyen logarithmique, puis l'algorithme optimal de Garsia-Wachs.
1Partie I : préliminaires sur les motsÉcriture de fonctions élémentaires sur des mots représentés par des listes d'entiers : longueur, i-ème caractère, préfixe et suffixe.
2Partie II : opérations sur les cordesDéfinition du type corde, arbre binaire dont les feuilles sont des mots, et programmation de ses opérations essentielles : longueur, création, concaténation, accès à un caractère et extraction d'une sous-corde.
3Partie III : équilibrageÉtude et programmation d'un algorithme d'équilibrage fondé sur les nombres de Fibonacci, garantissant un coût moyen d'accès aux caractères logarithmique en la longueur de la corde.
4Partie IV : équilibrage optimalÉtude de l'algorithme optimal de Garsia-Wachs, procédant en deux étapes : construction d'une corde de coût minimal puis remise en ordre des feuilles à profondeur inchangée.
Difficulté moyenne. Sur 739 copies, la note moyenne est de 10,97/20 avec un écart-type de 3,85 ; les premières questions ont un taux de réussite très élevé mais certaines questions des parties III et IV, notamment la question 18, ont un taux de réussite très faible (12 %), traduisant une difficulté croissante au fil du sujet.
Deux tiers des copies environ (moyenne ± écart-type)
Votre note sur 20 à ce sujet, en conditions de concours.
Source : rapport du jury. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.
Ce qu'a observé le jury
6 erreurs relevées
Conditions d'arrêt mal traitées et solutions quadratiques · Cas du mot vide et complexité non optimale · Trois cas de figure de la sous-corde mal distingués
Afficher ou masquer la section
Le sujet étudiait la structure de corde, alternative efficace aux chaînes de caractères usuelles. Sur 739 copies, la moyenne est de 10,97/20 avec un écart-type de 3,85. Les questions de la partie I étaient faciles mais demandaient de traiter avec soin les conditions d'arrêt ; presque toutes les fonctions demandées pouvaient s'écrire en moins de dix lignes. Le jury rappelle qu'une réponse longue doit être expliquée en détail et qu'un programme très long contient souvent un grand nombre d'erreurs ; il fallait traiter le problème en entier pour obtenir la note maximale.
Les erreurs les plus sanctionnées
1
Conditions d'arrêt mal traitées et solutions quadratiquesQuestions 3 et 4
Un nombre significatif de copies a été pénalisé pour ne pas avoir correctement traité la condition d'arrêt, ce phénomène étant amplifié lorsqu'une solution plus compliquée que nécessaire est choisie ; les solutions quadratiques plutôt que linéaires ont également été sanctionnées.
« les sol utions quadratiques plutôt que linéaires ont été sanctionnées »
2
Cas du mot vide et complexité non optimaleQuestion 6
Cette fonction nécessitait de considérer avec soin le cas du mot vide pour respecter l'invariant sur les cordes ; des solutions linéaires, consistant par exemple à construire un arbre en forme de peigne, ont été sanctionnées alors qu'une complexité constante était attendue.
« des solutions linéaires, consistant par exemple à construire un arbre binaire en form e de peigne avec les lettres du mot, ont été sanctionnées »
3
Trois cas de figure de la sous-corde mal distinguésQuestion 9
Cette question, apparue plus difficile que les précédentes, demandait de bien considérer les trois cas de figure (sous-corde entièrement dans le sous-arbre gauche, dans le droit, ou chevauchant les deux) et de traiter avec soin les nombreux paramètres des appels récursifs.
« la première diffculté étant de bien considérer les trois cas d e figure »
4
Propriété de Fibonacci sur la position du résultat mal compriseQuestion 13
Cette question, l'une des plus difficiles, demandait de comprendre que lorsqu'il y a concaténation de deux cordes non vides, le résultat est nécessairement placé plus loin dans la file, en vertu des propriétés des nombres de Fibonacci.
« La difficulté principale de la question était de comprendre que, lorsqu'il y a effectivement concaténation de deux cordes non vides, alors le résultat se ra »
5
Incompréhension en chaîne de l'algorithme d'équilibrageQuestion 15
De très nombreux candidats ont incorrectement répondu à cette question en raison d'une incompréhension de l'algorithme de la question précédente, la rédaction rigoureuse de la récurrence demandée posant également des difficultés.
« De très nombreux candidats ont incorrectement répondu à cette question en raison d'une incompréhension de l'algori thme à la question 14 »
6
Reconstruction d'une corde à partir des profondeurs, question la plus difficileQuestion 18
C'était peut-être la question la plus difficile du sujet, avec seulement 12 % des candidats obtenant au moins la moitié des points et 84 % obtenant zéro, bien que plusieurs solutions élégantes existent.
« C'était peut-être la question la plus difficile du sujet »
Ce qui a été bien réussi
La question 1 a été correctement traitée dans l'immense majorité des cas (99 % de réussite au moins partielle).
La question 2 a rencontré peu de problèmes (95 % de réussite au moins partielle).
La question 8 sur l'accès à un caractère d'une corde a été bien traitée dans l'ensemble (91 %).
La question 11 sur le calcul des nombres de Fibonacci a été bien traitée dans l'ensemble (95 %).
Conseils du jury
Traiter avec soin les conditions d'arrêt de chaque fonction récursive ou itérative.
Privilégier systématiquement la complexité optimale demandée (constante ou linéaire) plutôt qu'une solution plus lourde mais fonctionnelle.
Respecter scrupuleusement l'invariant donné sur la structure de données étudiée.
Rédiger des réponses concises : une réponse longue doit être expliquée en détail, et un programme très long contient souvent de nombreuses erreurs.
Essayer de traiter le problème dans son ensemble, la note maximale nécessitant de l'aborder en entier.
Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête de la copie.
Structure de corde
La majorité des langages de programmation fournissent une notion primitive de chaînes de caractères. Si ces chaînes s'avèrent adaptées à la manipulation de mots ou de textes relativement courts, elles deviennent généralement inutilisables sur de très grands textes. L'une des raisons de cette inefficacité est la duplication d'un trop grand nombre de caractères lors des opérations de concaténation ou d'extraction d'une sous-chaîne. Or il existe des domaines où la manipulation efficace de grandes chaînes de caractères est essentielle (représentation du génôme en bio-informatique, éditeurs de texte, etc.). Ce problème aborde une alternative à la notion usuelle de chaîne de caractères connue sous le nom de corde. Une corde est tout simplement un arbre binaire, dont les feuilles sont des chaînes de caractères usuelles et dont les nœuds internes représentent des concaténations. Ainsi la corde
représente le mot GATTACCATAGATTAC, obtenu par concaténation des cinq mots GATTAC, CAT, AG, ATT et AC. L'intérêt des cordes est d'offrir une concaténation immédiate et un partage possible de caractères entre plusieurs chaînes, au prix d'un accès aux caractères un peu plus coûteux.
La partie I traite de fonctions préliminaires sur les mots. La partie II définit les principales opérations sur les cordes. Enfin, les parties III et IV étudient le problème de l'équilibrage des cordes, selon deux algorithmes différents dont le second, l'algorithme de Garsia-Wachs, est optimal.
Les parties peuvent être traitées indépendamment. La partie IV utilise les notations de la partie III.
Partie I. Préliminaires sur les mots
On considère les mots dans Σ^∗ construits sur un alphabet Σ. Le mot x = a_0 a_1⋯a_(n − 1) de longueur n est représenté dans ce problème par la liste des entiers codant ses caractères a_0, a_1, …a_(n − 1). Ainsi le mot ATT est représenté par une liste ⟨65, 84, 84⟩. Pour ne pas dépendre du codage des caractères, on identifie les caractères et leurs codes. Le type des mots est défini par :
(* Caml *)
type mot == int list;;
{ Pascal }
type mot = `cellule; cellule = record
lettre : integer; suite : mot; end;
En Pascal la liste vide est nil et on pourra utiliser la fonction suivante pour construire des mots :
function nouveauMot(a:integer; x:mot) : mot;
var r : mot;
begin new(r); r^.lettre := a; r^.suite := x; nouveauMot := r; end;
Question 1 Écrire la fonction longueurMot qui calcule la longueur d'un mot.
(* Caml *) longueurMot : mot -> int
{ Pascal } function longueurMot(x : mot) : integer
Question 2 Écrire la fonction iemeCar qui prend en arguments un entier i et un mot x = a_0 a_1…a_(n − 1), et qui renvoie le caractère a_i. On supposera 0 ≤ i < n.
(* Caml *) iemeCar : int -> mot -> int
{ Pascal } function iemeCar(i : integer ; x : mot) : integer
Question 3 Écrire la fonction prefixe qui prend en arguments un entier k et un mot x = a_0 a_1…a_(n − 1), et qui renvoie le mot a_0 a_1…a_(k − 1) c'est-à-dire le mot constitué des k premiers caractères de x. On supposera 0 ≤ k ≤ n.
(* Caml *) prefixe : int -> mot -> mot
{ Pascal } function prefixe(k : integer ; x : mot) : mot
Question 4 Écrire la fonction suffixe qui prend en arguments un entier k et un mot x = a_0 a_1…a_(n − 1), et qui renvoie le mot a_k a_(k + 1)…a_(n − 1) c'est-à-dire le mot obtenu en supprimant les k premiers caractères de x. On supposera 0 ≤ k ≤ n.
(* Caml *) suffixe : int -> mot -> mot
{ Pascal } function suffixe(k : integer ; x : mot) : mot
Partie II. Opérations sur les cordes
Comme expliqué dans l'introduction, une corde est un arbre binaire dont les feuilles sont des mots. Plus précisément, une corde est soit vide, soit constituée d'un unique mot (une feuille), soit un nœud constitué de deux cordes et représentant leur concaténation. Pour des raisons d'efficacité, on conserve dans les feuilles aussi bien que dans les nœuds la longueur de la corde correspondante. On définit donc le type corde suivant :
(* Caml *)
type corde =
| Vide
| Feuille of int*mot
| Noeud of int*corde*corde;;
{ Pascal }
type corde = `arbre; nature = (Feuille, Noeud);
arbre = record case indicateur : nature of
Feuille : (n :integer; x :mot);
Noeud : (n :integer ; g, d :corde) ; end;
En Pascal la corde vide est représentée par nil.
Dans la suite, on garantira l'invariant suivant sur les cordes :
dans une corde de la forme Feuille(n, x), on a n = longueurMot(x) et n > 0;
dans une corde de la forme Noeud(n, c_1, c_2), on a c_1 ≠ Vide, c_2 ≠ Vide et n est la longueur totale de la corde, c'est-à-dire la somme des longueurs de c_1 et c_2.
On notera en particulier que la corde de longueur 0 est nécessairement représentée par Vide.
Question 5 Écrire la fonction longueur qui renvoie la longueur d'une corde.
(* Caml *) longueur : corde -> int
{ Pascal } function longueur(c : corde) : integer
Question 6 Écrire la fonction nouvelleCorde qui construit une corde à partir d'un mot.
(* Caml *) nouvelleCorde : mot -> corde
{ Pascal } function nouvelleCorde(m : mot) : corde
Question 7 Écrire la fonction concat qui construit la concaténation de deux cordes.
Question 8 Écrire la fonction caractere qui prend en arguments un entier i et une corde c représentant le mot a_0 a_1⋯a_(n − 1), et qui renvoie le caractère a_i. On supposera 0 ≤ i < n.
(* Caml *) caractere : int -> corde -> int
{ Pascal } function caractere(i : integer ; c : corde) : integer
Question 9 Écrire la fonction sousCorde qui prend en arguments un entier i, un entier m et une corde c représentant le mot a_0 a_1⋯a_(n − 1), et qui renvoie une corde représentant le mot a_i a_(i + 1)⋯a_(i + m − 1) c'est-à-dire la sous-corde de c débutant au caractère i et de longueur m. On supposera 0 ≤ i < i + m ≤ n.
(* Caml *) sousCorde : int -> int -> corde -> corde
{ Pascal } function sousCorde(i : integer ; m : integer ; c : corde) : corde
On s'attachera à réutiliser dans la corde résultat autant de sous-arbres de la corde c que possible.
Partie III. Équilibrage
Le hasard des concaténations peut amener une corde à se retrouver déséquilibrée, c'est-à-dire à avoir certaines de ses feuilles très éloignées de la racine et donc d'accès plus coûteux. Le but de cette partie est d'étudier une stratégie de rééquilibrage a posteriori.
Considérons une corde c composée de k + 1 feuilles, et donc de k nœuds internes. Notons ces k + 1 feuilles x_0, x_1, …x_k lorsqu'on les considère de la gauche vers la droite, si bien que c représente
le mot x_0 x_1…x_k. La profondeur de la feuille x_i dans c est notée prof (x_i) et est définie comme la distance de x_i à la racine de c. Voici un exemple de corde pour k = 5 où la profondeur de chaque feuille est indiquée entre parenthèses :
Le coût de l'accès à un caractère de la feuille x_i est défini comme la profondeur de cette feuille dans c, soit prof (x_i) (on ne considère donc pas le coût de l'accès dans le mot x_i lui-même). Le coût total d'une corde est alors défini comme la somme des coûts d'accès à tous ses caractères, et vaut donc
Un rééquilibrage consiste à construire une corde différente, dont les feuilles sont x_0, x_1…x_k dans le même ordre (le mot représenté ne doit pas changer) et dont le coût est, éventuellement, meilleur. L'algorithme proposé est le suivant.
On considère un tableau file de cordes dans lequel les feuilles de c vont être successivement insérées dans le sens des indices croissants. Les cases d'indices 0 et 1 ne sont pas utilisées. La case d'indice i contient soit la corde vide (Vide), soit une corde de hauteur inférieure ou égale à i − 2 et dont la longueur est comprise dans l'intervalle [F_i, F_(i + 1)[ où F_i désigne le i-ème terme de la suite de Fibonacci. La hauteur d'une corde c, notée hauteur(c), est la profondeur maximale de ses feuilles, c'est-à-dire :
Pour équilibrer la corde c dont les feuilles sont les mots x_0, x_1, …x_k, dans cet ordre, on procède ainsi :
On insère successivement chaque feuille x_j dans le tableau file à partir de la case 2. L'insertion d'une feuille, et plus généralement d'une corde, à partir de la case d'indice i se fait ainsi :
(a) La corde à insérer est concaténée à droite de la corde se trouvant dans la case i; soit c^′ le résultat. Si la longueur de c^′ est comprise dans l'intervalle [F_i, F_(i + 1)[, on affecte c^′ à la case i et on a terminé l'insertion de cette corde.
(b) Sinon, on affecte Vide à la case i et on retourne à l'étape (a) pour effectuer l'insertion de c^′ à partir de la case d'indice i + 1.
On garantit l'invariant suivant : après l'insertion de la feuille x_j, la concaténation successive de toutes les cordes contenues dans les cases de file, considérées dans le sens des indices décroissants, est égale à une corde représentant le mot x_0 x_1…x_j.
Le résultat est alors la corde résultant de la concaténation successive de toutes les cordes de file, considérées dans le sens des indices décroissants.
Question 10 Calculer le résultat de cet algorithme sur la corde de l'exemple précédent.
Question 11 On rappelle que la suite de Fibonacci (F_n) est définie par
{F_0, = 0,; F_1, = 1,; F_(n + 2), = F_(n + 1) + F_n pour n ≥ 0.
Afin d'éviter tout débordement arithmétique en calculant F_n, on limite la taille de file à 44 cases indexées de 0 à 43 (les cases 0 et 1 n'étant pas utilisées). On introduit la constante tailleMax = 44 et on calcule les valeurs de F_n pour 0 ≤ n ≤ tailleMax une fois pour toutes dans un tableau fib ainsi déclaré :
(* Caml *)
let tailleMax = 44;; const tailleMax = 44;
let fib = make_vect (tailleMax+1) 0 ; ; var fib :array[0..tailleMax] of integer;
Écrire la fonction initialiserFib qui initialise le tableau fib.
Question 12 Le tableau file utilisé par l'algorithme est déclaré comme un tableau global contenant des cordes :
(* Caml *) { Pascal }
let file = make_vect tailleMax Vide; ; var file :array[0..tailleMax-1] of corde;
Écrire la fonction inserer qui prend en arguments une corde c et un entier i, tels que 2 ≤ i < tailleMax, hauteur (c) ≤ i − 2 et longueur (c) ≥ F_i, et réalise l'insertion de c dans le tableau file à partir de la case d'indice i.
(* Caml *) inserer : corde -> int -> unit
{ Pascal } procedure inserer(c : corde ; i : integer)
Question 13 Montrer que l'invariant hauteur (c_i) ≤ i − 2 et longueur (c_i) ≥ F_i est préservé par cette fonction pour toutes les valeurs c_i non vides des cases du tableau file ( 2 ≤ i < tailleMax).
Question 14 Écrire la fonction equilibrer qui réalise l'équilibrage d'une corde par l'algorithme ci-dessus.
Question 15 Soit c une corde non vide renvoyée par la fonction equilibrer ci-dessus. Soit n sa longueur et h sa hauteur. Montrer que l'on a
n ≥ F_(h + 1)
En déduire qu'il existe une constante K (indépendante de n ) telle que
Coût(c) ≤ n(log_φ(n) + K)
où φ est le nombre d'or (1 + √5)/2 et log_φ désigne le logarithme à base φ. On admettra que l'on a F_(i + 1) ≥ φ^i/√5 pour tout i ≥ 0.
Partie IV. Équilibrage optimal
Bien que satisfaisant en pratique, l'équilibrage étudié dans la partie précédente n'est pas optimal. Le but de cette partie est d'étudier une stratégie optimale de rééquilibrage (algorithme de GarsiaWachs). Les notations sont celles de la partie III. L'algorithme proposé procède en deux temps : il commence par construire une corde de coût minimal, ayant les mêmes feuilles que c mais pas nécessairement dans le même ordre; puis, dans un deuxième temps, il transforme cette corde en une autre de même coût où les feuilles sont maintenant dans le même ordre que dans c.
La première partie de l'algorithme opère sur une liste de cordes q = ⟨q_0, q_1, …q_m⟩ et procède de la manière suivante :
Initialement, la liste q est la liste ⟨x_0, x_1, …x_k⟩ des k + 1 feuilles de c.
Tant que la liste q contient au moins deux éléments, on effectue l'opération suivante:
(a) Déterminer le plus petit indice i tel que
longueur (q_(i − 1)) ≤ longueur (q_(i + 1))
le cas échéant, et poser i = m sinon.
(b) Ôter q_(i − 1) et q_i de la liste q et former leur concaténation; soit c^′ la corde obtenue.
(c) Déterminer le plus grand indice j < i tel que
longueur (q_(j − 1)) ≥ longueur (c^′)
le cas échéant, et poser j = 0 sinon.
(d) Insérer c^′ dans la liste q juste après q_(j − 1) (et donc au début de la liste q si j = 0 ).
3. Le résultat est l'unique élément restant dans la liste q.
Il est clair que le résultat de cet algorithme est une corde ayant les mêmes feuilles que c mais que ces feuilles ne sont pas nécessairement dans le bon ordre. On admettra le résultat suivant : l'arbre obtenu est de coût minimal.
Question 16 Pour simplifier le codage, on suppose que le nombre k de feuilles est inférieur à une certaine valeur (ici maxf = 1000 ) et que la liste q est représentée dans un tableau global q :
(* Caml *) { Pascal }
let maxf = 1000; ; const maxf :integer = 1000;
let q = make_vect maxf Vide; ; var q :array[0..maxf-1] of corde;
Écrire la fonction initialiserQ qui prend en argument une corde c, remplit les k + 1 premiers éléments de q avec les feuilles x_0, …, x_k de c (c'est-à-dire des cordes de la forme Feuille), et renvoie la valeur de k. On supposera c ≠ Vide.
(* Caml *) initialiserQ : corde -> int
{ Pascal } function initialiserQ(c : corde) : integer
On admettra avoir effectué le reste de l'algorithme ci-dessus et avoir donc écrit une fonction phase1 qui prend en argument une corde c et renvoie la corde obtenue par l'algorithme ci-dessus.
La deuxième étape de l'algorithme procède ainsi. Soit c_1 la corde obtenue à l'issue de la première étape de l'algorithme. Chaque feuille x_i de c se trouve dans c_1 à une certaine profondeur; notons p_i cette profondeur. On admet la propriété suivante : il existe une corde c_2 dont les feuilles sont exactement x_0, x_1, …x_k dans cet ordre et où la profondeur de chaque x_i est exactement p_i. On peut alors construire c_2 en ne connaissant que les p_i, et c_2 est dès lors un rééquilibrage optimal de c.
Question 17 Les profondeurs p_i seront stockées dans un tableau global prof :
(* Caml *) { Pascal }
let prof = make_vect maxf 0; ; | var prof :array [0..maxf-1] of
Écrire la fonction initialiserProf qui prend en argument les cordes c et c_1 et range dans le tableau prof, à l'indice i, la profondeur de la feuille x_i (de c ) dans c_1 pour 0 ≤ i ≤ k. On pourra avantageusement réutiliser le tableau q et la fonction initialiserQ.
Indication : on admettra que, pour comparer les feuilles de c et c_1, on peut utiliser l'égalité fournie par le langage, i.e. le symbole =.
Question 18 Écrire la fonction reconstruire qui construit c_2 à partir de la seule donnée des tableaux q et prof. Attention : pour des profondeurs p_i quelconques, il n'existe pas nécessairement de corde où chaque x_i a la profondeur p_i. On demande ici un algorithme qui fonctionne uniquement sous l'hypothèse qu'une telle corde existe (ce qui est le cas ici).
(* Caml *) reconstruire : unit -> corde
{ Pascal } function reconstruire : corde
Question 19 Combiner les fonctions ci-dessus pour obtenir une fonction de rééquilibrage optimal.
Sur quels chapitres porte l'épreuve d'informatique Polytechnique MP 2008 ?
Afficher ou masquer la section
Sur quels chapitres porte l'épreuve d'informatique Polytechnique MP 2008 ?
+
Le sujet porte sur la structure de corde (rope) pour représenter efficacement de grandes chaînes de caractères : opérations de base, complexité algorithmique, et algorithmes d'équilibrage d'arbres dont l'algorithme optimal de Garsia-Wachs.
Quelle est la moyenne à l'épreuve d'informatique Polytechnique MP 2008 ?
+
La note moyenne est de 10,97/20 avec un écart-type de 3,85, sur 739 copies. Les candidats ayant composé en Pascal (7,58 %) ont obtenu une moyenne de 8,99, inférieure à la moyenne générale.
Quelles erreurs le jury a-t-il le plus relevées à cette épreuve d'informatique Polytechnique MP 2008 ?
+
Le jury relève des conditions d'arrêt mal traitées, des solutions de complexité non optimale (quadratique au lieu de linéaire, ou linéaire au lieu de constante), une mauvaise gestion des trois cas de figure d'extraction d'une sous-corde, et une incompréhension de la propriété de Fibonacci garantissant l'équilibrage.
Cette épreuve d'informatique Polytechnique MP 2008 est-elle difficile ?
+
Le sujet est de difficulté progressive : les premières questions affichent des taux de réussite très élevés (plus de 90 %), mais certaines questions des parties III et IV sont parmi les plus difficiles, la question 18 n'étant réussie, même partiellement, que par 12 % des candidats.
Même chapitre : Structures de données… (+1)Centrale Informatique MPI 2024Centrale · 2024Corrigé
Même chapitre : Structures de données… (+1)X ENS Informatique C MPI 2024X-ENS · 2024Corrigé
Même année, CCINPCCINP Option Informatique MP 2008CCINP · 2008Corrigé
Même année, MinesMines Option Informatique MP 2008Mines · 2008Corrigé
