Examen de TP [2018-2019]

Examen de TP [2018-2019] - Anagrammes.

$\def\ab#1#2{\llbracket #1\,,\,#2\rrbracket}$Le barème est donné à titre indicatif et est susceptible d'être adapté. Lisez attentivement les explications. Commentez vos fonctions.

L'objectif de cet examen est d'écrire un programme en langage C qui récupère une liste de mots sur la ligne de commande et qui partitionne cette liste selon la relation d'équivalence suivante : un mot u est en relation avec un mot v si v est une anagramme de u (i.e. les lettres de v sont une permutation de celles de u). Par exemple logarithme est une anagramme d'algorithme.

L'algorithme qui va réaliser cette opération opère en deux étapes. On note $\alpha:A^*\rightarrow A^*$, où $A$ est un alphabet et $A^*$ l'ensemble des mots sur cet alphabet, l'application qui trie les lettres d'un mot dans l'ordre alphabétique, par exemple $\alpha(rasait)=aairst$ :

On fait agir $\alpha$ sur chaque mot de la liste initiale L pour créer une nouvelle liste L_$\alpha$ : L_$\alpha$ := $\alpha$(L). Ainsi si v est une anagramme de u, $\alpha$ (u) = $\alpha$ (v). Dans l'exemple ci-dessus, on aurait L = [un, relais, logarithme, nu, algorithme, lieras, test].
L_$\alpha$ = [nu, aeilrs, aeghilmort, nu, aeghilmort, aeilrs, estt].
On trie la liste L_$\alpha$ dans l'ordre lexicographique en mémorisant la permutation σ ∈ S_n des indices associée. Ici on aurait : TriLex(L_$\alpha$) = [aeghilmort, aeghilmort, aeilrs, aeilrs, estt, nu, nu]. et σ = (3, 5, 2, 6, 7, 4, 1) La liste TriLex(L_$\alpha$) combinée avec la permutation σ permet de faire les regroupements. Les deux premiers mots aeghilmort étant identiques, les deux mots correspondants dans la liste L sont des anagrammes l'un de l'autre et on les retrouve grâce à la permutation σ construite durant le tri : L⚬σ [1]= L[3] = logarithme et L⚬σ [2]= L[5] = algorithme.

Sauvez le fichier source prérempli anagrammes.c dans votre répertoire EXAM-I41. Une fois complété et compilé, le fichier exécutable devra s'intituler anagrammes et son appel devra renvoyer les classes d'équivalence pour cette relation. Par exemple ($ désigne le prompt du terminal) :

./anagrammes un relais logarithme nu algorithme lieras test
( logarithme algorithme ) ( relais lieras ) ( test ) ( nu un )

Vous utiliserez librement les fonctions de la bibliothèque string.h, notamment la fonction de comparaison lexicographique strcmp entre chaînes de caractères et strlen qui renvoie la longueur d'une chaîne de caractère. On rappelle qu'une chaîne de caractères de n caractères est un tableau de taille n + 1 dont le dernier caractère est le caractère \0.

Question 1 [+4] Complétez la fonction TriAlpha qui renvoie une copie triée dans l'ordre alphabétique du mot passé en paramètre en utilisant l'algorithme du tri par dénombrement. Indications : on suppose que les mots sur la ligne de commande sont composés uniquement des lettres de a à z dont le codage est compris entre 0 et 127. D'autre part, pensez à transtyper vos variables en cas de Warning du compilateur.

Question 2 [+2] Complétez la fonction TriLocal qui renvoie la liste L_$\alpha$ à partir de la liste L passée en paramètre.

Question 3 [+1] Complétez la fonction CreerPermId qui renvoie la permutation identité sous forme de tableau T de n entiers tel que T[i] = i pour tous les entiers i ∈ [0,n-1].

Question 4 [+6] Complétez la fonction TriGlobal qui trie sur place la liste de mots passee en parametre et qui renvoie la permutation des positions correspondante. Indication~: il ne faut pas utiliser le tri lexicographique mais un tri classique avec comme relation d'ordre l'ordre lexicographique et mettre à jour la permutation (initialement l'identité) conformément aux échanges réalisés dans la liste de mots.

Question 5 [+4] Complétez la fonction Partitionner qui affiche les classes d'équivalences de la liste $L$ de mots passée en parametre et qui utilise pour cela la liste $L_{\alpha}$ ainsi que la permutation σ.

Question 6 [+1] Quelle sont les classes d'équivalence de cette liste de mots ?

Question 7 [+2] Quelle est la complexité de l'algorithme utilisé pour résoudre ce problème ? Justifiez.