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 de longueur est représenté dans ce problème par la liste des entiers codant ses caractères . Ainsi le mot ATT est représenté par une liste . 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 et un mot , et qui renvoie le caractère . On supposera .
(* 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 et un mot , et qui renvoie le mot c'est-à-dire le mot constitué des premiers caractères de . On supposera .
(* 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 et un mot , et qui renvoie le mot c'est-à-dire le mot obtenu en supprimant les premiers caractères de . On supposera .
(* 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 , on a et ;
dans une corde de la forme , on a Vide, Vide et est la longueur totale de la corde, c'est-à-dire la somme des longueurs de et .
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 et une corde représentant le mot , et qui renvoie le caractère . On supposera .
(* 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 , un entier et une corde représentant le mot , et qui renvoie une corde représentant le mot c'est-à-dire la sous-corde de débutant au caractère et de longueur . On supposera .
(* 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 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 composée de feuilles, et donc de nœuds internes. Notons ces feuilles lorsqu'on les considère de la gauche vers la droite, si bien que représente
le mot . La profondeur de la feuille dans est notée prof et est définie comme la distance de à la racine de . Voici un exemple de corde pour 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 est défini comme la profondeur de cette feuille dans , soit prof (on ne considère donc pas le coût de l'accès dans le mot 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 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 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 contient soit la corde vide (Vide), soit une corde de hauteur inférieure ou égale à et dont la longueur est comprise dans l'intervalle où désigne le -ème terme de la suite de Fibonacci. La hauteur d'une corde , notée hauteur(c), est la profondeur maximale de ses feuilles, c'est-à-dire :
Pour équilibrer la corde dont les feuilles sont les mots , dans cet ordre, on procède ainsi :
On insère successivement chaque feuille 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 se fait ainsi :
(a) La corde à insérer est concaténée à droite de la corde se trouvant dans la case ; soit le résultat. Si la longueur de est comprise dans l'intervalle , on affecte à la case et on a terminé l'insertion de cette corde.
(b) Sinon, on affecte Vide à la case et on retourne à l'étape (a) pour effectuer l'insertion de à partir de la case d'indice .
On garantit l'invariant suivant : après l'insertion de la feuille , 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 .
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 est définie par
Afin d'éviter tout débordement arithmétique en calculant , 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 et on calcule les valeurs de pour 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 et un entier , tels que , hauteur et longueur , et réalise l'insertion de dans le tableau file à partir de la case d'indice .
(* Caml *) inserer : corde -> int -> unit
{ Pascal } procedure inserer(c : corde ; i : integer)
Question 13 Montrer que l'invariant hauteur et longueur est préservé par cette fonction pour toutes les valeurs non vides des cases du tableau file ( tailleMax).
Question 14 Écrire la fonction equilibrer qui réalise l'équilibrage d'une corde par l'algorithme ci-dessus.
Question 15 Soit une corde non vide renvoyée par la fonction equilibrer ci-dessus. Soit sa longueur et sa hauteur. Montrer que l'on a
En déduire qu'il existe une constante (indépendante de ) telle que
où est le nombre d'or et désigne le logarithme à base . On admettra que l'on a pour tout .
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 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 .
La première partie de l'algorithme opère sur une liste de cordes et procède de la manière suivante :
Initialement, la liste est la liste des feuilles de .
Tant que la liste contient au moins deux éléments, on effectue l'opération suivante:
(a) Déterminer le plus petit indice tel que
le cas échéant, et poser sinon.
(b) Ôter et de la liste et former leur concaténation; soit la corde obtenue.
(c) Déterminer le plus grand indice tel que
le cas échéant, et poser sinon.
(d) Insérer dans la liste juste après (et donc au début de la liste si ).
3. Le résultat est l'unique élément restant dans la liste .
Il est clair que le résultat de cet algorithme est une corde ayant les mêmes feuilles que 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 de feuilles est inférieur à une certaine valeur (ici maxf ) et que la liste est représentée dans un tableau global
(* 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 , remplit les premiers éléments de avec les feuilles de (c'est-à-dire des cordes de la forme Feuille), et renvoie la valeur de . On supposera 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 et renvoie la corde obtenue par l'algorithme ci-dessus.
La deuxième étape de l'algorithme procède ainsi. Soit la corde obtenue à l'issue de la première étape de l'algorithme. Chaque feuille de se trouve dans à une certaine profondeur; notons cette profondeur. On admet la propriété suivante : il existe une corde dont les feuilles sont exactement dans cet ordre et où la profondeur de chaque est exactement . On peut alors construire en ne connaissant que les , et est dès lors un rééquilibrage optimal de .
Question 17 Les profondeurs 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 et et range dans le tableau prof, à l'indice , la profondeur de la feuille (de ) dans pour . On pourra avantageusement réutiliser le tableau q et la fonction initialiserQ.
Indication : on admettra que, pour comparer les feuilles de et , on peut utiliser l'égalité fournie par le langage, i.e. le symbole .
Question 18 Écrire la fonction reconstruire qui construit à partir de la seule donnée des tableaux q et prof. Attention : pour des profondeurs quelconques, il n'existe pas nécessairement de corde où chaque a la profondeur . 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.
