N.B. : le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction. Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il le signalera sur sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.
RAPPEL DES CONSIGNES
Utiliser uniquement un stylo noir ou bleu foncé non effaçable pour la rédaction de votre composition ; d'autres couleurs, excepté le vert, bleu clair ou turquoise, peuvent être utilisées, mais exclusivement pour les schémas et la mise en évidence des résultats.
Ne pas utiliser de correcteur.
Écrire le mot FIN à la fin de votre composition.
Les calculatrices sont interdites.
Le sujet est composé de trois parties, toutes indépendantes.
Partie I - Algorithme Single Pass
Cette partie comporte des questions nécessitant un code en langage .
On cherche à classer documents textuels dans lesquels les termes et apparaissent un certain nombre de fois, ces occurrences étant décrites dans le tableau suivant :
1
2
0
1
1
3
1
1
3
0
3
0
0
1
1
Chaque document est donc représenté par un ensemble de valeurs. On notera un vecteur de , de composantes , indiquant le nombre d'occurrences du terme dans le document .
On cherche à voir si des textes traitent des mêmes thématiques, en faisant l'hypothèse que des textes sont sémantiquement proches si des termes communs apparaissent.
Q1. Recopier et remplir le tableau suivant en appliquant l'algorithme des k-moyennes avec et et comme centres de classe initiaux. On utilisera la distance . On notera de plus les centres de classe et les classes correspondantes.
Itération
1
2
3
On souhaite maintenant traiter ce problème par une méthode dite "single pass" décrite dans l'algorithme 1.
Algorithme 1 - Algorithme Single Pass
Entrées : $\left(d_{1} \cdots d_{n}\right)$ les vecteurs des documents, $\theta$ un seuil appartient à $\mathbb{R}$.
Sorties: $\left(\mathcal{A}_{1} \cdots \mathcal{A}_{j}\right)$ les classes de centres $\left(c_{1} \cdots c_{j}\right)$
début
$c_{1}=d_{1} ;$ // Initialisation
$\mathcal{A}_{1}=\left\{d_{1}\right\}$;
$j=1$;
pour $i$ de 2 à $n$ faire
pour $k$ de 1 à $j$ faire
Étape (i) Calculer $\delta\left(d_{i}, c_{k}\right)$;
si Étape (ii) $\delta\left(d_{i}, c_{k}\right)>\theta \forall c_{k}$ alors
$j=j+1$; // Création d’une nouvelle classe
$\mathcal{A}_{j}=\left\{d_{i}\right\} ;$
$c_{j}=d_{i} ;$
sinon
// Indice du centre de classe le plus proche de $d_{i}$ au sens de $\delta$
Étape (iii) $\ell=\arg \min _{1 \leq k<i}\left(\delta\left(d_{i}, c_{k}\right)\right)$;
$\mathcal{A}_{\ell}=\mathcal{A}_{\ell} \cup\left\{d_{i}\right\} ; ~ / /$ Affectation de $d_{i}$ à la classe $\ell$
$c_{\ell}=\frac{1}{\left|A_{\ell}\right|} \sum_{d_{i} \in \mathcal{A}_{\ell}} d_{i} ; \quad / /$ Recalcul de $c_{\ell}$
Q2. Appliquer l'algorithme 1 avec . Détailler les résultats des étapes de l'algorithme.
On propose d'implémenter cet algorithme en langage . À cet effet, on définit un type structuré vecteur permettant d'encoder les centres de classe et les textes.
struct vecteur_s {
double *v; // pointeur vers les coordonnées
int taille; // taille du vecteur
int num_classe; // classe du vecteur
};
typedef struct vecteur_s vecteur;
Puisque le nombre de centres de classe varie au cours de l'algorithme, on utilise une liste chaînée de vecteurs pour représenter l'ensemble des centres de classe.
Q3. Écrire une fonction de prototype void ajoutVecteur(vecteur *vec, noeud **tete) permettant d'ajouter un vecteur vec en tête de la liste des centres de classe pointée par tete. On prendra soin de vérifier que l'allocation mémoire s'est bien passée.
On suppose dans la suite disposer :
de la variable vecteur *documents[nb_documents] qui contient l'ensemble des documents, où pour tout , nb_documents - , documents [i] est égal à .
d'une fonction void recalculCentre (vecteur *documents, noeud **tete, int l) qui effectue le recalcul du centre et met à jour le nœud correspondant dans la liste chaînée des centres de classe.
Q4. Écrire une fonction de prototype double delta(vecteur *di, vecteur *c) qui calcule la distance entre le document di et le centre de classe c (étape (i) de l'algorithme 1). On suppose que et ont la même taille.
Q5. Écrire une fonction de prototype bool distmax (double dists[],int j,double theta) qui réalise l'étape (ii) de l'algorithme 1. Le tableau dists contient les distances de à tous les : pour tout l'élément dists[k] du tableau dists contient la distance de à . La fonction renvoie true si et false sinon.
Q6. Écrire une fonction de prototype int distmin(double dists[], int j) qui réalise l'étape (iii) de l'algorithme 1. Le tableau dists contient les distances de à tous les comme dans la question précédente. La fonction renvoie l'entier décrit dans l'algorithme.
Q7. À l'aide des questions précédentes et de la fonction recalculCentre, proposer une implémentation de l'algorithme 1 sous la forme d'une fonction de prototype noeud *algorithme1(vecteur *documents, int nb_documents, double theta). Évaluer la complexité de l'algorithme 1.
Partie II - Langages réguliers
Soit un alphabet. est l'ensemble des mots de longueur finie sur l'alphabet . Pour , désigne la longueur du mot . On note la i-ème lettre de . Pour , on note le préfixe de de longueur , c'est-à-dire le mot .
On définit sur la relation symétrique de la manière suivante: s'il existe tels que et . On note la fermeture réflexive transitive de si ou s'il existe des mots tels que:
(i). ,
(ii). pour ,
(iii). .
Q8. Montrer que est une relation d'équivalence.
Soit . La classe de modulo est l'ensemble des mots vérifiant . Tous les mots de cette classe ont la même longueur. Ainsi, par exemple, {abcabb, abcbab, abcbba, bacabb, bacbab, bacbba} est une classe modulo .
Q9. Montrer que les classes modulo sont des langages réguliers.
Q10. Donner les classes de mots de longueur 3.
On définit la relation sur telle que par : pour si l'une des deux conditions suivantes est réalisée :
(i). ,
(ii). il existe tel que et .
Q11. Montrer que la relation est réflexive et transitive. En déduire que est un ordre total sur .
Soit une classe modulo . Le représentant de est le plus petit élément de cette classe pour l'ordre . On note l'ensemble des représentants des classes modulo .
Q12. Donner le représentant de la classe contenant le mot bacbab.
Q13. Donner une expression régulière du langage régulier .
Q14. Proposer un automate fini déterministe complet reconnaissant .
Partie III - Correspondance de Burge
La correspondance de Burge permet d'exprimer une bijection entre des graphes simples et des tableaux de Young semi-standards. Ces objets combinatoires ont de nombreuses applications, notamment dans l'étude de groupes symétriques et la géométrique algébrique. En théorie des graphes, ils permettent également de trouver, s'ils existent, les graphes simples dont les sommets sont contraints à avoir des degrés donnés.
Cette partie comporte des questions nécessitant un code OCaml. Pour ces questions, les réponses ne feront pas appel aux fonctionnalités impératives du langage (références, champs mutables, exceptions).
Notations
Dans toute la suite on notera :
l'ensemble des entiers naturels de 1 à ,
le cardinal de l'ensemble ,
un graphe simple, c'est-à-dire un graphe non orienté à sommets et arêtes, sans boucles ni arêtes multiples,
le degré du sommet dans le graphe .
De plus, les sommets de seront ordonnés par degrés décroissants, de sorte que .
Définition 1 (Suite de degrés d'un graphe)
Soit un graphe simple. Si est le degré du sommet , avec , la suite de degrés de est le -uplet ( ).
III. 1 - Partitions d'un entier
Définition 2 (Partition)
Une partition d'un entier , notée , est une suite décroissante de nombres entiers strictement positifs de somme .
Par exemple, a cinq partitions : (4), (3,1), (2,2), (2,1,1) et (1,1,1,1).
Une partition peut être vue comme une suite de degrés sous certaines conditions.
Q15. Montrer que si est impaire, alors la partition ne peut pas générer de graphe simple ayant la suite de degrés .
Dans la suite, on considérera que la somme des termes de la suite d'entiers ( ) est paire. Même avec cette contrainte, cette suite peut ne pas pouvoir générer de graphe simple.
Définition 3 (Suite graphique)
Une suite d'entiers est dite graphique s'il existe un graphe simple dont la suite des degrés est .
Notons qu'une suite graphique vérifie par définition .
Pour déterminer si une suite d'entiers donnée est graphique, on peut utiliser l'algorithme d'HavelHakimi, basé sur le théorème suivant :
Théorème 1 (Havel-Hakimi)
(i). Pour tout , si est graphique, alors et toute permutation décroissante de est graphique.
(ii). Réciproquement, pour tout , si est graphique, alors pour , la suite ( ) est graphique.
Q16. Montrer que si ( ) est graphique, alors il existe un graphe simple à sommets, de sommet 1 de degré tel que ( ) soit la suite des degrés des sommets de .
Q17. On suppose que ( ) est graphique. Montrer qu'il existe , le degré du sommet étant pour tout , tel que : . Pour cela, on pourra raisonner par l'absurde et supposer que le sommet 1 est adjacent à un maximum de sommets dans , mais pas à tous.
Q18. En déduire que si , alors ( ) est graphique.
Q19. Déterminer si les suites et sont graphiques.
Q20. Écrire une fonction de signature compare_entiers : int -> int -> int qui compare deux entiers et telle que l'appel à compare_entiers m n renvoie et 0 sinon.
Q21. Écrire une fonction de signature decr_n : n -> int list -> int list option telle que pour tout l'appel decr_n n l retourne Some l', avec l' la liste 1 dont les premiers éléments sont décrémentés, s'ils étaient tous supérieurs à 1 et None sinon.
Q22. Écrire une fonction récursive de signature havel_hakimi : int list bool qui retourne true si la liste passée en entrée, triée par ordre décroissant, est graphique et false sinon. À chaque étape utilisant le théorème 1, il sera nécessaire de réordonner par ordre décroissant la liste list construite, ce qui pourra être fait à l'aide de l'appel à List.sort compare_entiers list.
Q23. Donner deux graphes simples à sommets ayant une même suite de degrés . Ainsi, il n'existe pas de correspondance univoque entre suite de degrés et graphe simple.
III. 2 - Diagramme et tableau de Young
Définition 4 (Diagramme de Young d'une partition)
Le diagramme de Young de forme , noté , d'une partition est un tableau de cases constitué de lignes alignées à gauche, chaque ligne ayant cases.
Par convention, la ligne associée à est la première ligne du tableau.
Par exemple, les diagrammes de Young des partitions de l'entier 4 sont
Définition 5 (Diagonale d'un diagramme de Young)
Soit un diagramme de Young. La diagonale de est définie par les cases ( .
Dans le tableau suivant, et les cases de la diagonale sont grisées.
Définition 6 (Partition conjuguée)
Soit un diagramme de Young associé à . La partition conjuguée de , notée , est la partition obtenue en énumérant le nombre de cases de par colonne, en partant de la colonne de gauche.
On remarque immédiatement que pour tout .
Q24. Soit . Donner .
Définition 7 (Représentation de Frobenius d'un diagramme de Young)
Soient une partition, son diagramme de Young et la taille de sa diagonale. Pour , soient le nombre de cases à droite de la case ( ) dans la i-ème ligne de et le nombre de cases en-dessous de la case ( ) dans la i-ème colonne de . Alors , et la notation de Frobenius de est donnée par .
Q25. Soit . Donner la représentation de Frobenius de .
Définition 8 (Tableau de Young)
Soit une partition de . Un -tableau de Young est un tableau obtenu en remplissant les cases d'un diagramme par des entiers dans .
Par exemple, pour , les tableaux suivants sont des -tableaux
Dans la suite, on notera l'entier en position ( ) dans le tableau .
Définition 9 (Tableau de Young (semi)standard)
Un tableau de Young est dit semi standard si les éléments de chaque ligne (respectivement colonne) forment une suite croissante de gauche à droite (respectivement strictement croissante de haut en bas). Il est dit standard s'il est semi-standard et si les entiers de 1 à n'apparaissent qu'une et une seule fois.
Dans les exemples précédents, les premier, troisième et septième tableaux sont semi standards. Les premier et troisième tableaux sont standards.
III. 3 - Insertion de Schensted
Pour construire un tableau de Young semi-standard à partir d'une suite d'entiers , on utilise une méthode d'insertion proposée par Schensted.
On cherche à insérer dans un tableau de Young semi standard un entier , de sorte à ce que le tableau créé (contenant une case de plus) soit toujours un tableau de Young semi standard. On note cette opération d'insertion .
L'entier est inséré dans en le comparant aux valeurs de la première ligne et en déplaçant le premier entier plus grand que en lisant la ligne de gauche à droite. S'il n'y a pas de plus grand élément, est ajouté à la fin de la ligne. Si un élément est déplacé, il est inséré dans la deuxième ligne et les lignes suivantes du tableau sont traitées de la même manière. L'algorithme 2 décrit l'insertion de dans la -ème ligne de .
Soit le tableau de Young semi standard
1
1
2
2
4
2
3
3
3
4
Q26. Insérer la valeur 5 dans et donner le tableau de Young semi standard résultant. Même question pour l'insertion de la valeur 1 dans .
Q27. Énoncer une précondition de l'algorithme 2 permettant de prouver sa correction, c'est-à-dire qu'il retourne bien un tableau de Young semi standard contenant .
Pour coder les tableaux de Young, on choisit d'utiliser un type OCaml type tableau = int list list et on encode la structure par liste de lignes.
Algorithme 2 - Algorithme d'insertion d'un entier $k$ dans la ligne $i$ d'un tableau de Young semi
standard
Insertion( $T, k, i$ )
Entrées : un tableau de Young semi standard $T$, un entier $k$ à insérer, $i$ la ligne traitée
Sorties : un tableau de Young semi standard contenant $k$
début
si (la ligne $i$ est vide) OU ( $k$ plus grand que l'élément le plus à droite de la ligne $i$ ) alors
Ajouter $k$ en bout de la ligne $i$ de $T$
sinon
Soit $j$ le plus petit indice tel que $k<T(i, j)$
$p=T(i, j)$
$T(i, j)=k$
Insertion( $T, p, i+1$ )
Q28. Écrire une fonction récursive de signature insereligne :int -> int list -> int*int list qui, à partir d'un entier et d'une ligne d'un tableau de Young semi standard, retourne un couple ( ) où
et est la ligne où a été ajouté en queue, si est plus grand que tous les éléments de la ligne ,
, qui est dans la ligne et est la ligne où a été remplacé par sinon.
Q29. En déduire une fonction récursive de signature insertion : int tableau tableau réalisant l'algorithme 2.
Q30. Écrire une fonction récursive de signature construit_tableau :int list -> tableau qui construit un tableau semi standard à partir d'une suite d'entiers.
L'algorithme 2 permet de définir une position ( ), coordonnées de la case où a été ajouté à .
III. 4 - Correspondance de Burge
Définition 10 (Tableau de Burge)
Soit un graphe simple, . Le tableau de Burge associé à est défini par
où pour tout est une arête de , avec , le tableau étant formé de sorte que pour et si alors .
Soit le graphe de la figure 1.
Figure 1 - Graphe exemple
Q31. Donner le tableau correspondant au graphe de la figure 1.
On utilise alors pour associer à un diagramme de Young représenté par une forme de Frobenius particulière, notée , où est le nombre de cases de la diagonale principale du diagramme de Young associé.
Q32. Montrer que, dans ce cas, pour tout .
Ainsi, est divisé en deux parties symétriques. La partie inférieure est constituée de toutes les cases qui se trouvent strictement sous la diagonale et la partie supérieure est constituée du reste. Chaque position dans la partie supérieure (inférieure) du diagramme de Young correspond à une position unique, appelée position opposée, dans la partie inférieure (supérieure) de . Par exemple, dans le diagramme de Young suivant, ayant comme représentation de Frobenius , les positions opposées sont codées par le même symbole.
Q33. Soit une case. Donner la position opposée en fonction de et .
L'algorithme 3 utilise alors la représentation d'un graphe pour construire un tableau de Young semi standard dont le diagramme correspondant admet une représentation de Frobenius du type . Dans cet algorithme, insère la valeur dans le tableau de Young semi standard .
Algorithme 3 - Algorithme de Burge
Entrées : $\mathcal{B}_{G}$ de taille $m \times 2$
Sorties : tableau de Young semi standard $T$ dont la représentation de Frobenius du diagramme
correspondant est du type $\mathcal{F}_{Y}$
début
$T$ = tableau vide; // Initialisation
pour $i$ de 1 à $m$ faire
$(s, t)=T \leftarrow v_{i}$
Placer $u_{i}$ dans la position opposée à ( $s, t$ )
Cet algorithme produit, à partir du graphe de la figure 1, le tableau:
1
1
2
3
2
3
5
4
5
5
6
6
Q34. Donner les tableaux de Young semi standard intermédiaires produits à chaque itération.
Q35. À quoi correspond le nombre d'apparitions de chaque entier contenu dans les cases du tableau de Young résultat de l'algorithme 3 ?
Notons pour terminer qu'il est à l'inverse possible de produire un tableau bidimensionnel (et donc un graphe ) à partir d'un tableau de Young semi standard de type .
FIN
CCINP Informatique MPI 2024 - Version Web LaTeX | WikiPrépa | WikiPrépa
