Thème de l'épreuve | Compression de suites ternaires |
Principaux outils utilisés | tableaux, boucles for et while, variables locales et globales, récursivité |
É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 ; ».