É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.
