CONCOURS 2004

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

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 deux opérations et donnant le quotient et le reste de la division euclidienne de par .

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

En base 3 , les entiers sont représentés par , . Le chiffre de poids fort de est le chiffre de poids faible est .

Question 1. Écrire la fonction entier(b,c) retournant l'entier compris entre 0 et 8 qui s'écrit bc en base 3 .

Question 2. Soit un entier vérifiant . Écrire une fonction poidsFort( ) retournant le chiffre de poids fort de en base 3 . Écrire la fonction poidsFaible retournant le chiffre de poids faible de .

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 de caractères vérifiant pour tout vérifiant ; par ailleurs (le dernier caractère n'est pas ternaire). On suppose .

Quelques définitions sont nécessaires : la chaîne de caractères de longueur démarrant en est la suite . On dira que deux chaînes et sont égales si et pour .

Question 3. Écrire une fonction longueurMotif qui retourne, en temps linéaire par rapport à , la plus grande longueur d'une chaîne démarrant en égale à une chaîne démarrant en . En outre, cette longueur doit vérifier .

Question 4. On suppose . Écrire une fonction longueurMotifMax qui retourne, en temps quadratique par rapport à , la plus grande longueur d'une chaîne démarrant en égale à une chaîne démarrant en pour . En outre, on exige et .

On suppose qu'il existe trois variables globales entières .

Question 5. Modifier la fonction précédente pour obtenir la fonction motifMax( ) qui rend, en temps quadratique, dans la plus grande longueur d'une chaîne démarrant en égale à une chaîne démarrant en pour ; qui rend dans la valeur de pour lequel est l'indice de départ de cette chaîne de longueur maximale ; qui rend enfin dans le caractère suivant cette chaîne à partir de dans . À nouveau, cette longueur doit vérifier . Et on a (cf. l'exemple dans la figure suivante).

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 ( ) calculé dans la question précédente entre toute paire d'indices et . 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. Écrire une fonction imprimerTriplet qui imprime les arguments sous forme de cinq chiffres consécutifs, les deux caractères ternaires de , puis les deux caractères ternaires de , puis le chiffre , en imposant et .

On suppose à présent que contient un long texte ternaire commençant par 9 caractères 0 ; en outre, finit par un caractère x spécial ( ). On déplace sur ce texte une fenêtre de longueur 18. Au début, cette fenêtre est alignée à gauche sur le début du tableau, et on pose . En régime de croisière, la dixième case de la fenêtre correspond à l'entrée du tableau . On recherche, dans la partie gauche de la fenêtre, la chaîne de longueur maximale vérifiant et égale à une chaîne de caractères démarrant en . On imprime, grâce à la fonction imprimerTriplet, le triplet ( ) donné par motifMax. Puis, on recentre la fenêtre sur le caractère suivant le caractère d'arrêt . Ce processus continue jusqu'au bout du tableau 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 qui serait nettement meilleur dans une base supérieure à 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).

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 ( ) 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 n'est pas comprise entre 0 et 2 .

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