X Informatique MP/PC 2004

ÉCOLE POLYTECHNIQUE
ÉCOLE SUPÉRIEURE DE PHYSIQUE ET CHIMIE INDUSTRIELLES

CONCOURS 2004

FILIÈRE MP - OPTION PHYSIQUE ET SCIENCES DE L'INGÉNIEUR FILIÈRE PC

COMPOSITION D'INFORMATIQUE

(Durée : 2 heures)

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.

***

Compression ternaire

On attachera une grande importance à la concision, & la clarté, et à la 
précision de la rédaction.
On supposera que le langage de programmation utilisé possède dear opérations 
:1: div y et r mod y
donnant le quotient et le reste de la division euclidienne de a: par g.

Le temps d'exécution T( f ) d'une fonction f est le nombre d'opérations 
élémentaires (addi--
tion, soustraction, multiplication, division, affectation, etc.) nécessaire au 
calcul de f. Lorsque
ce temps d'exécution dépend d'un paramètre n, il sera noté T,,( f ) On dit que 
la fonction f
s'exécute :

o en temps linéraire en n, s'il existe K > 0 tel que pour tout n, T n( f ) 5 K 
n ;

o en temps quadratique en n, s'il existe K > 0 tel que pour tout n, T,,( ]" ) 5 
K n2.

Nombres ternaires

En base 3, les entiers O, 1, 2, 3, 4, 5, 6, 7, 8 sont représentés par @, O_1_, 
Q2, _1_Q, _1_1, l_2_, @,
21, g. Le chiffre de poids fort de _b_<_: est b ; le chiffre de poids faible est 0. Question 1. Écrire la fonction entier(b, c) retournant l'entier compris entre 0 et 8 qui s'écrit b_c en base 3. Question 2. Soit :13 un entier vérifiant () S a: _<_ 8. Écrire une fonction poidsFort(æ) retournant le chiffre de poids fort de a: en base 3. Ecrire la fonction poidsFaible(oe) retournant le chiffre de poids faible de 51}. Textes ternaires Dans ce problème, les textes sont représentés en représentation ternaire. Un savant russe nous a convaincus de la pertinence de ce choix plus compact que la représentation binaire. Un texte est rangé dans un tableau t de N caractères vérifiant t]z'] E {O, 1, 2} pour tout 7. vérifiant 0 S i < N -- 1; par ailleurs t]N -- 1] = X > 2 (le dernier caractère n'est pas 
ternaire). On
suppose N 2 1.

Quelques définitions sont nécessaires : la chaîne de caractères de longueur EUR 
démarrant en 75
est la suite (t]z'], t]i + 1], . . . t[z' + EUR -- 1]). On dira que deux 
chaînes (t]z'], t]i + 1], . . . t]z' + EUR -- 1]) et
(t]j],t[j + 1], . . . t]j + E' -- 1]> sont égales si EUR = EUR' et t[z' + k] = 
t]j + [EUR] pour 0 5 [EUR < 6. Question 3. Écrire une fonction longueurMotif(t,i, j, m) qui retourne, en temps linéaire par rapport a N, la plus grande longueur [ d'une chaîne démarrant en t' égale à une chaîne démarrant en j. En outre, cette longueur doit vérifier EUR 5 m. Question 4. On suppose 75 < j. Écrire une fonction longueurMotifMax(t, i,j, m) qui retourne, en temps quadratique par rapport a N, la plus grande longueur EUR d'une chaîne démarrant en i+ k égale à une chaîne démarrant en j pour 0 5 la < m. En outre, on exige i+ 16 < j et EUR _<_ .... On suppose qu'il existe trois variables globales entières A, L, C . Question 5. Modifier la fonction précédente pour obtenir la fonction motifMax(t, i, j, m) qui rend, en temps quadratique, dans L la plus grande longueur £ d'une chaîne démarrant en i + k égale à une chaîne démarrant en j pour 0 _<_ [EUR < m ; qui rend dans A la valeur de [EUR pour lequel i + k est l'indice de départ de cette chaîne de longueur maximale ; qui rend enfin dans C' le caractère suivant cette chaîne à partir de j dans t. À nouveau, cette longueur doit vérifier EUR $ m. Et on a i + [EUR < j (cf. l'exemple dans la figure suivante). A=k=3; L=Æ=8; C=2 Compression La méthode de compression de Ziv et Lempel, adoptée dans les commandes zip ou gzip, consiste à repérer les motifs maximaux déjà rencontrés dans un texte et à indiquer pour chacun d'eux le triplet (A, L, C) calculé dans la question précédente entre toute paire d'indices i et j . Pour mesurer le facteur de compression, nous utilisons le même codage pour ces triplets que pour les caractères du texte, c'est--à--dire le système ternaire dans ce problème. Question 6. Ecrire une fonction imprimerTriplet(À, L, C) qui imprime les arguments A, L, C sous forme de cinq chiffres consécutifs, les deux caractères ternaires de A, puis les deux caractères ternaires de L, puis le chiffre C, en imposant O S A < 9, 0 S L < 9 et 0 S C S 9. On suppose a présent que t contient un long texte ternaire commençant par 9 caractères 0; en outre, t finit par un caractère x spécial (a: > 2). On déplace sur ce 
texte une fenêtre
de longueur 18. Au début, cette fenêtre est alignée a gauche sur le début du 
tableau, et on
pose j = 9. En régime décroisière, la dixième case de la fenêtre correspond a 
l'entrée j du
tableau t. On recherche, dans la partie gauche de la fenêtre, la chaîne de 
longueur EUR maximale
vérifiant EUR < 9 et égale à une chaîne de caractères démarrant en j . On imprime, grâce a la fonction imprimerTriplet, le triplet (A,L,C) donné par motifMax. Puis, on recentre la fenêtre sur le caractère suivant le caractère d'arrêt C . Ce processus continue jusqu'au bout du tableau t comme indiqué par la figure. Ainsi pour le texte suivant, on obtient les décompositions de chacune des lignes, soit au total le facteur de compression 30/37 qui serait nettement meilleur dans une base supérieure a 3 et si la taille de la fenêtre était plus grande que 18 (Il y a en effet 30 caractères dans le résultat et 37 dans le texte d'entrée). mmmammmmmmmaumammaæmmæmamæmwaæmwaæmwa mamammmammlllll|lu mammaaæmæmalllllll Efläflfiälflflälfiâflfifill EEE!OEËOEEËËEËËEËEËE EEEËEËEËEEËH rOEOEOEË EHEËH"HOEOEHËHËEËIEHE"E"OEËËËIEËEËH ( >
( )
(aan EEEEOEHOEEËEWËEËE'II
( >
< >
( )

Question 7. Écrire une fonction compresser(t) qui imprime sur le terminal de 
sortie le texte
compressé par la méthode précédente.

Pour la décompression, on produit d'abord 9 caractères 0. On considère ensuite 
tous les
triplets (A, L, C ) représentés par 5 caractères ternaires consécutifs et on 
recrée la chaîne originale
jusqu'au dernier triplet dont la composante C n'est pas comprise entre 0 et 2.

Question 8. Ecrire une fonction décompresser(ta) qui prend un texte ternaire tc 
correspondant
à du texte compressé et imprime sur le terminal de sortie le texte décompressé 
correspondant.

X Informatique MP/PC 2004 -- Corrigé
Ce corrigé est proposé par Jean-Baptiste Rouquier (ENS Lyon) ; il a été relu par
Walter Appel (Professeur en CPGE) et Vincent Puyhaubert (ENS Cachan).

Cette épreuve n'est pas nouvelle à l'École Polytechnique, mais c'est la première
année qu'elle est obligatoire. Elle est commune à la filière MP option sciences 
de
l'ingénieur et ne compte que pour l'admission.
Le thème abordé par le sujet est celui de la compression, qui permet de réduire
la taille d'une donnée (texte, image, vidéo, etc.). Il existe deux grandes 
familles
d'algorithmes de compression : avec ou sans perte d'information, selon que la 
transformation est bijective ou non. Ce sujet donnera une idée générale des 
méthodes non
destructives, qui sont par exemple utilisées dans le format zip.
Toutes les questions demandent d'écrire du code. Nous avons choisi de le rédiger
en Maple car ce langage est le mieux connu en prépa. Les fonctions réalisées 
étant
simples, vous pourrez sans peine les réécrire dans votre langage préféré.
· On trouve tout d'abord deux questions faciles de lecture et d'écriture en
base trois, pour des nombres strictement inférieurs à 9.
· La deuxième partie demande de manipuler des textes, qui sont représentés par
des tableaux d'entiers. Le choix de la base trois n'a aucune incidence.
· La troisième partie utilise les fonctions de la première. La question 6, 
plutôt
facile, demande d'écrire une fonction auxiliaire ; les questions 7 et 8 traitent
enfin de compression et décompression. Ces deux dernières questions réutilisent
toutes les fonction précédemment écrites.
Soyez rigoureux dans la gestion des indices des tableaux : un décalage d'une 
case
apparaît facilement. Des erreurs dans ce domaine sont sanctionnées par le 
correcteur.
Les notions de programmation sont élémentaires : tableaux, boucles for et while,
variables locales et globales.
Ce sujet est très progressif, de particulièrement simple au début à difficile 
dans
les deux dernières questions. La question 6, facile, fait exception. Il 
constitue une
bonne préparation au concours de l'École Polytechnique.

Indications
Nombres ternaires
2 0 6 x 6 8 donc l'écriture de x a exactement deux chiffres selon les 
conventions
de l'énoncé. poidsFort(x) est le quotient de la division euclidienne de x par 3,
poidsFaible(x) en est le reste.
Textes ternaires
3 On peut écrire une fonction récursive : longueurMotif(t, i, j, m) s'exprime 
en fonction de longueurMotif(t, i + 1, j + 1, m - 1). Ne pas oublier la 
condition d'arrêt.
4 Le sujet demande une complexité quadratique en N ; on peut donc utiliser la 
fonction précédente un nombre de fois linéaire en N.
Seconde indication : ici aussi on peut écrire une fonction récursive, en notant 
que
longueurMotifMax(t, i, j, m) s'exprime en fonction de longueurMotif(t, i, j, m)
et de longueurMotifMax(t, i + 1, j, m).
5 Dans la fonction précédente, remplacer les valeurs renvoyées (par exemple la 
valeur
max(len, longueurMotifMax(t, i+1, j, m))) par une affectation des variables
globales.
Seconde indication : remplacer l'appel à max par les deux cas possibles au moyen
d'une structure if ... then ... else ... fi.
Compression
7 Le « régime de croisière » de l'énoncé est une boucle while. Utiliser une 
variable
locale pour stocker la position de la fenêtre. « Jusqu'au bout du tableau » peut
être codé par « jusqu'à ce qu'on lise un caractère non ternaire ».
8 Utiliser une variable locale fenetre stockant les dix-huit éléments de la 
fenêtre,
et la mettre à jour à chaque fois que l'on imprime un caractère. Utiliser une 
autre
variable indiquant la position dans tc des cinq caractères codant le triplet 
(A, L, C)
en cours de décodage. Pour chacun de ces triplets, lire caractère par caractère 
dans
fenetre la chaîne désignée par ce triplet et l'imprimer.

Nombres ternaires
1 L'écriture bc représente l'entier 3 b + c.
2 Comme suggéré par l'énoncé qui suppose dans l'introduction l'existence des 
deux
opérations div et mod, poidsFort(x) est le quotient dans la division 
euclidienne de
x par 3, poidsFaible(x) en est le reste.
La fonction div proposée par l'énoncé n'existe pas en Maple, on écrira à
la place :

Textes ternaires
3 Écrivons une fonction récursive : si t[i] est différent de t[j], la longueur 
cherchée
est nulle. Sinon, c'est 1 plus la longueur de la plus grande chaîne démarrant 
en i + 1
et égale à une chaîne démarrant en j + 1. Enfin si m = 0, comme on exige  6 m,
le résultat est 0.
Cette fonction est bien linéaire en N car il y a au plus m appels récursifs et 
chaque
appel n'effectue qu'un nombre constant d'opérations élémentaires.
Cette fonction n'est utilisée qu'avec des arguments tels que m + j soit
inférieur à la longueur de t. Ceci garantit que la consultation de t[j] est
toujours faite avec l'indice j dans les bornes du tableau. C'est là l'utilité du
paramètre m.
Si l'on veut pouvoir utiliser cette fonction même avec m + j > N, il suffit
de tester si m + j > N, et dans ce cas d'appeler longueurMotif(t, i, j, N - j).
4 Il y a deux cas possibles : soit la chaîne la plus grande est celle 
commençant en i
(pour k = 0), soit c'est la chaîne la plus grande parmi celles commençant en i 
+ 1 + k,
avec i + 1 + k < j. Ceci suggère une fonction récursive dont la condition d'arrêt est la suivante : si i = j - 1, alors la seule chaîne possible est celle commençant en i. Cette fonction est bien quadratique en N car il y a au plus j - i 6 N appels récursifs et chaque appel utilise la fonction linéaire longueurMotif. On pourrait bien sûr écrire à la place une fonction non récursive qui calcule longueurMotif(t, i + k, j, m) pour tous les k autorisés et renvoie le maximum des valeurs trouvées. 5 Adaptons directement la fonction précédente. Dans le cas où i = j - 1, au lieu de renvoyer len, on assigne les bonnes valeurs aux variables locales. Sinon (c'est le cas général, qui correspond au code encadré par else . . . fi), on fait un appel récursif (motifMax(t, i+1, j, m)) comme dans la fonction précédente, qui renvoie son résultat dans les variables globales A, L et C. On distingue alors les deux cas du max : · si len < L (L est égal au résultat qui aurait été renvoyé par longueurMotifMax (t, i+1, j, m)), alors L et C contiennent déjà la bonne valeur et il suffit donc d'indiquer que la chaîne de longueur maximale démarre en i + k + 1, c'est-à-dire d'incrémenter A ; · sinon (len > L), c'est que la chaîne cherchée démarre en i et l'on règle 
alors les
variables globales.

Il faut préciser à Maple que les variables A, L et C sont globales par la
ligne « global A,L,C ; ».