X Informatique MP/PC 2007

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

CONCOURS D'ADMISSION 2007

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.

On attachera une grande importance a la concision, a la clarté, et a la 
précision de la rédaction.

***

Compression bzip

Le temps d'exécution T( f ) d'une fonction f est le nombre d'opérations 
élémentaires (addition,
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é Tn( f ) On dit que la 
fonction f s'exécute :

en temps O(n°'), s'il existe K > 0 tel que pour tout n, T,,(f) £ KnO'.

Dans ce sujet, il sera question de l'algorithme de Burrows--Wheeler qui 
compresse très effica--
cement des données textuelles. Le texte d'entrée a compresser sera représenté 
par un tableau 15
contenant des entiers compris entre 0 et 255 inclus.

1 Compression par redondance

La compression par redondance compresse un texte d'entrée qui possède des 
répétitions consé--
cutives de lettres (ou d'entiers dans notre cas). Dans un premier temps, on 
calcule les fréquences
d'apparition de chaque entier dans le texte d'entrée. Puis on compresse le 
texte.

Question 1 Écrire la fonction occurrences(t, 77.) qui prend en argument un 
tableau d'entrée 15 de
longueur n, et qui retourne un tableau 7" de taille 256 tel que r[i] est le 
nombre d'occurrences de i
dans 15 pour 0 S i < n. Question 2 Écrire la fontion min(t, 77.) qui prend en argument le tableau 15 de longueur n, et qui retourne le plus petit entier de l'intervalle [O, 255] qui apparaît le moins souvent dans le tableau 15. (Le nombre d'occurrences de cet entier peut être nul) L'entier min(t,n) servira de marqueur. On note # pour ce marqueur et, pour simplifier, on suppose que son nombre d'occurrences est nul. Donc r[#] = 0 quand 7" : occurrences(t,n). La compression par redondance du texte 15 fonctionne comme suit : toute répétition maximale contigüe d'une lettre où t[i] = t[i + 1] = : t[j] : k est codée par les trois entiers #, (j -- i),k; toute apparition unique d'une lettre k est codée par cette même lettre. 1 Par exemple, si le tableau 15 contient les valeurs <0, 0, 3, 2, 3, 3, 3, 3, 3, 3, 5). Le marqueur est donc 1 car 1 n'apparaît pas dans ce tableau. Le texte t' compressé est alors 1 ,1,1,0, 3 , 2 , 1,5,3, 5 v, *VV \ , V # 0,0 3 2 3,3,3,3,3,3 5 Question 3 Écrire la fonction tailleCodage(t, 77.) qui prend comme argument le tableau 15 et calcule la taille n' du texte compressé (n' = 10 dans l'exemple ci--dessus). Question 4 Écrire la fonction codage(t, 77.) qui prend comme paramètre le tableau 15 et retourne un tableau d'entiers t' représentant le texte compressé. Pour pouvoir décoder un texte t' ainsi compressé, il suffit de connaître le marqueur utilisé. Or ce marqueur est le premier entier du texte compressé. 2 Transformation de Burrows-WheeIer Le codage par redondance n'est efficace que si le texte présente de nombreuses répétitions consé-- cutives de lettres. Oe n'est évidemment pas le cas pour un texte pris au hasard. La transformation de Burrows--Wheeler est une transformation qui, a partir d'un texte donné, produit un autre texte contenant exactement les mêmes lettres mais dans un autre ordre où les répétitions de lettres ont tendance a être contigües. Cette transformation est bijective. Considérons par exemple le texte d'entrée concours. Pour simplifier la présentation, nous uti-- lisons ici des caractères pour le tableau d'entrée. Cependant, dans les programmes, on considère toujours (comme dans la première partie) que le texte d'entrée est un tableau d'entiers compris entre 0 et 255 inclus. Le principe de la transformation suit les trois étapes suivantes : 1 -- On regarde toutes les rotations du texte. 2 -- On trie ces rotations par ordre lexi-- Dans notre cas, il y en a 8 qui sont : cographique (l'ordre du dictionnaire). concours concours oncoursc courscon ncoursco ncoursco courscon oncoursc oursconc oursconc ursconco rsconcou rsconcou sconcour sconcour ursconco 3 -- Le texte résultant est formé par toutes les dernières lettres des mots dans l'ordre précédent, soit snoccuro dans l'exemple, ainsi que de l'indice de la lettre dans ce texte résultant qui est la première lettre du texte original, soit 3 dans notre exemple. On appelle cet entier la clé de la transformation. On remarque que les deux c du texte de départ se retrouvent côte a côte après la transforma-- tion. En effet, comme le tri des rotations regroupe les mêmes lettres sur la première colonne, cela conduit a rapprocher aussi les lettres de la dernière colonne qui les précédent dans le texte d'entrée. 2 On le constate aussi sur la chaîne : concours...de...l...ecole...polytechnique dont la transformée par Burrows--Wheeler est sleeeeen...dlt...ucn...ooohcpcc...iuryqo. En pratique, on ne va pas calculer et stocker l'ensemble des rotations du mot d'entrée. On se contente de noter par rot[i] la i--ème rotation du mot. Ainsi, dans l'exemple, rot[0] représente le texte d'entrée concours, rot... représente oncoursc, rot[2] représente ncoursco, etc. Question 5 Écrire la fonction comparerRotations(t, n, i, j) qui prend comme arguments le texte 15 de longueur 77. et deux indices @, j , et qui renvoie, en temps linéaire par rapport a n : 1 si rot[i] est plus grand que rot[j] dans l'ordre lexicographique, --1 si rot[i] est plus petit que rot[j] dans l'ordre lexicographique, 0 sinon. On suppose disposer d'une fonction triRotations(t, 77.) qui trie les rotations du texte donné dans le tableau 15 en utilisant la fonction com parerRotation. Elle retourne un tableau d'entiers 7" représentant les numéros des rotations (rot[r[0H £ rot[r[1]] £ £ rot[r[n -- 1]]). Cette fonction réalise dans le pire des cas O(n ln 77.) appels a la fonction de comparaison. Question 6 Écrire une fonction codageBW(t,n) qui prend en paramètre le tableau 15, et qui renvoie un tableau contenant le texte après transformation. (La clé sera stockée dans la dernière case de ce tableau) Question 7 Donner un ordre de grandeur du temps d'exécution de la fonction codageBW en fonction de n. Pour réaliser l'ensemble du codage, il ne reste plus qu'à réaliser la compression par redondance sur la transformée t' du texte d'entrée 15. 3 Transformation de Burrows-WheeIer inverse Pour décoder le texte t' (snoccur03 dans l'exemple) de taille n' = n + 1 obtenu après transfor-- mation, on construit d'abord un tableau triCars de taille 77. qui contient les mêmes lettres que le texte t' mais dans l'ordre lexicographique croissant. Dans l'exemple, triCars : .

Question 10 Écrire la fonction trouverlndices(t' ,n' ) prenant en paramètre le 
texte t' codé de
longueur n' , et qui retourne le tableau indices précédemment décrit. Quel est 
son temps d'exécution
en fonction de n' ?

Question 11 Écrire une fonction decodageBW(t' , n' ) qui prend comme paramètre 
un texte t' de
longueur n' , et retourne le texte 15 d'origine. Quel est son temps d'exécution 
en fonction de n' ?