JEUDI 20 AVRIL 2023
14h00-18h00
FILIERE MPI - Epreuve
INFORMATIQUE C (XULSR)
Durée : 4 heures
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve
Cette composition ne concerne qu'une partie des candidats de la filière MP, les autres candidats effectuant simultanément la composition de Physique et Sciences de l'Ingénieur.
Pour la filière MP, il y a donc deux enveloppes de Sujets pour cette séance.
Ordonnabilité des espaces métriques
Le sujet comporte 12 pages, numérotées de 1 à 12.
Début de l'épreuve.
Dans ce sujet, on s'intéresse au problème d'ordonner les éléments d'un espace métrique de sorte que deux éléments successifs soient à distance bornée.
Ce sujet est constitué de quatre parties. La première partie est formée de préliminaires utiles dans le reste du sujet, avec des questions de programmation en C et OCaml . La deuxième partie propose une implémentation en C d'une structure de données utilisée notamment dans la troisième partie. Cette troisième partie considère les graphes, munis de la distance de plus court chemin, comme espace métrique, avec implémentations en C. La quatrième partie, enfin, indépendante des deux précédentes, considère l'ordonnabilité des langages réguliers pour une certaine distance d'édition; cette partie contient de la programmation en OCaml.
Dans les questions de programmation en C ou OCaml, on n'utilisera pas de fonctions qui ne sont pas incluses dans la bibliothèque standard du langage. Pour les codes en C , on pourra supposer que les en-têtes <stdbool.h>, <stdio.h>, <stdlib.h> et <assert.h> ont été inclus.
Espaces métriques et -ordres
Dans ce sujet, on s'intéresse à des collections de données discrètes que l'on cherche à explorer ou engendrer de proche en proche. On modélise ce cadre général à l'aide des notions d'espace métrique, de -suite et de -ordre :
Définition 1 (espace métrique). Un espace métrique est constitué d'un ensemble dénombrable dont les éléments sont appelés points et d'une distance sur , c'est-à-dire une application satisfaisant :
Symétrie. Pour tout .
Séparation. Pour tout si et seulement si .
Inégalité triangulaire. Pour tout .
Pour un espace métrique et , on note le couple ( ), où dénote la restriction de au domaine . On observe que est encore un espace métrique, que l'on appellera sous-espace de .
Définition 2 ( -suite). Pour , une -suite dans un espace métrique est une suite (finie ou infinie dénombrable) de points de telle que :
s ne contient pas de doublons, c'est-à-dire que pour tous de la suite, si alors ;
deux points consécutifs de la suite sont à distance au plus ; formellement, pour tous , de la suite on a .
On dit que commence en et, dans le cas où est finie et a éléments, que termine en .
Définition 3 ( -ordre, -ordonnable). Pour , un -ordre de est une -suite dans contenant tous les points de . L'espace est dit -ordonnable lorsqu'il existe un -ordre de . On dit que est ordonnable lorsque est d-ordonnable pour un certain .
Distances d'édition sur les mots
On fixe dans tout le sujet l'alphabet ayant pour seules lettres et . Un mot est une suite finie de lettres . La longueur de , notée , est . On note le mot vide, de longueur nulle. On note l'ensemble des mots sur . Un langage est un sous-ensemble de .
Un espace métrique d'intérêt, sur l'ensemble des mots d'un langage, est donné par deux distances d'édition sur les mots : la distance push-pop et la distance push-pop-droite, que l'on définit ci-après.
Définition 4 (distance push-pop). La distance push-pop, dénotée , est définie de la manière suivante : pour est le nombre minimal d'opérations nécessaires pour passer de à , où les opérations autorisées sont :
pour un mot , insérer la lettre à la fin, ce qui donne le mot wa;
pour un mot , insérer la lettre au début, ce qui donne le mot ;
pour un mot de la forme wa avec , supprimer la dernière lettre, ce qui donne le mot ;
pour un mot de la forme avec , supprimer la première lettre, ce qui donne le mot .
Exemple 1. Les mots à distance push-pop 1 du mot aab sont aa (on a supprimé la dernière lettre), aaba (on a ajouté un a à la fin), aabb (on a ajouté un à la fin), ab (on a supprimé la première lettre), aaab (on a ajouté un a au début) et baab (on a ajouté un au début).
Définition 5 (distance push-pop-droite). La distance push-pop-droite, dénotée , est définie de la même manière que mais seules les insertions et suppressions à la fin du mot sont autorisées.
Exemple 2. Les mots qui sont à distance push-pop-droite 1 du mot aab sont aa (on a supprimé la dernière lettre), aaba (on a ajouté un a à la fin) et aabb (on a ajouté un à la fin).
Algorithmes d'énumération push-pop et push-pop-droite
Lorsqu'on travaillera sur les mots, on considèrera parfois des programmes produisant une suite (potentiellement infinie) de mots de , en utilisant les instructions spéciales suivantes : ; pushL et pushR pour ; et output () .
Le programme dispose, comme état interne, d'une liste d'éléments de , qui est interprétée comme un mot de . La liste est initialement vide et représente donc le mot vide. Voici ce qu'il se passe lorsque le programme utilise les instructions spéciales :
popL() a pour effet de supprimer la première lettre de la liste (et ne peut être appelée que si la liste est non vide);
popR() a pour effet de supprimer la dernière lettre de la liste (et ne peut être appelée que si la liste est non vide) ;
pushL( ) a pour effet d'ajouter la lettre en début de liste;
pushR( ) a pour effet d'ajouter la lettre en fin de liste;
output() produit le mot étant actuellement représenté par la liste (par exemple, il l'affiche en sortie du programme).
On souligne que la liste n'est accessible par le programme que via ces instructions spéciales. De plus, on fait l'hypothèse que chacune des instructions popL, popR, pushL et pushR a une complexité en .
Un tel programme produit alors la suite de mots , où est le premier mot produit par le programme lors de son exécution, le second et ainsi de suite.
On appellera un tel programme un programme push-pop. De manière similaire, un programme push-pop-droite est un programme push-pop qui n'utilise pas les instructions popL() ni pushL( ) pour .
Exemple 3. On suppose que les fonctions pushL, pushR, popL, popR, output ont été prédéfinies et manipulent toutes une même variable représentant la liste. Le programme suivant est un programme push-pop-droite qui produit la suite de mots où est :
int main(void)
{
pushR('b'); output();
while (true) {
popR(); pushR('a'); pushR('a'); pushR('b'); output();
}
}
On remarque que ce programme ne termine jamais.
En OCaml, on suppose qu'on dispose d'un type lettre défini par :
type lettre = A | B
On représente alors les mots de par des listes OCaml lettre list, dont la tête correspond à la première lettre du mot. Par exemple, le mot est représenté par la liste . On suppose avoir accès en OCaml à des fonctions de type pushR : lettre unit, pushL : lettre -> unit, popR : unit -> unit, popL : unit -> unit, ainsi que output : unit -> unit, qui représentent les instructions spéciales.
Exemple 4. Le programme OCaml push-pop suivant produit la même suite que le programme push-pop-droite de l'exemple 3 :
let main () =
pushR B; output ();
while true do
pushL A; pushL A; output ();
done
Partie I : Préliminaires
Question I.1. Soit un espace métrique tel que est un ensemble fini. Montrer que est ordonnable.
Question I.2. Écrire une fonction OCaml
delta_ppr : lettre list -> lettre list -> int
prenant en entrée deux listes 11,12 représentant des mots et renvoyant , la distance push-pop-droite entre et . On attend de cette fonction que sa complexité soit linéaire en .
Question I.3. On considère la suite , où est . Écrire un programme push-pop-droite en C qui produit la suite .
Question I.4. Montrer que et sont des espaces métriques.
On s'intéresse maintenant aux sous-espaces de et , c'est-à-dire (comme indiqué dans la Définition 1) aux espaces métriques de la forme ou ( ), pour un langage. Par exemple, la suite produite par les programmes push-pop des exemples 3 et 4 est un 4-ordre pour et un 2-ordre pour , où .
Question I.5. Écrire un programme push-pop en C qui produit un -ordre pour , où et un certain . Expliquer comment fonctionne ce programme.
Question I.6. Écrire un programme push-pop en C qui produit un 1-ordre pour , où . [Indice : on peut visualiser le langage comme la grille , où à la position ( ) correspond le mot .] Ne pas hésiter à faire un dessin pour se faire comprendre.
Question I.7. Soit .
a. Écrire un programme push-pop en C qui produit un 1-ordre pour .
b. Prouver que n'est pas ordonnable.
Question I.8. Un chemin hamiltonien dans un graphe non-orienté est un chemin (aussi appelé chaîne) qui visite tous les sommets du graphe exactement une fois. Un graphe grille est un graphe de la forme avec une partie finie de et et , autrement dit, deux sommets sont connectés par une arête s'ils sont à distance 1 dans la grille .
On définit le problème de décision HamGrille de la manière suivante : en entrée on a un graphe grille et la sortie est OUI si possède un chemin hamiltonien et NON sinon. On admettra que ce problème est NP-complet.
Pour un entier naturel non nul, on définit le problème de décision , de la façon suivante : prend en entrée un ensemble fini de mots et la sortie est OUI si est -ordonnable, NON sinon. On fixe maintenant un entier naturel arbitraire. Montrer que pour cet entier , le problème est NP-complet.
Partie II : Implémentation en C des programmes push-pop
Dans cette partie, on souhaite réaliser une implémentation en langage C des opérations des programmes push-pop sur une structure de données liste codant une liste doublement chaînée. Le type de la structure de données liste est défini comme suit :
En particulier, les lettres sont donc représentées par des entiers (on rappelle qu'en C, une variable de type char peut être implicitement interprétée comme variable de type int sans perte d'informations) ; cela permettra de réutiliser cette structure liste dans d'autres contextes.
Dans l'implémentation de cette structure de données, on veillera à ce qu'un pointeur dont la valeur n'est pas NULL pointe toujours vers un espace mémoire valide et pas, par exemple, vers une donnée libérée.
Question II.1. Définir et initialiser une variable globale lg représentant la liste chaînée globale manipulée par les programmes push-pop; on souhaite que cette liste soit initialement vide.
Question II.2. Programmer une fonction est_vide de prototype bool est_vide(void) renvoyant true si représente une liste vide, false sinon.
Question II.3. Programmer des fonctions pushL et pushR de prototypes void pushL(int) et void pushR(int) implémentant les opérations pushL et pushR sur la liste représentée par lg. On utilisera une assertion pour vérifier que l'allocation dynamique de mémoire est bien réalisée. Quelle est la complexité en temps de ces deux fonctions?
Question II.4. Programmer des fonctions popL et popR de prototypes int popL(void) et int popR(void) implémentant les opérations popL et popR sur la liste représentée par (chacune renvoyant également la valeur extraite de la liste). On utilisera une assertion pour s'assurer que la liste n'est pas vide et on veillera à libérer la mémoire devenue inutile. Quelle est la complexité en temps de ces deux fonctions?
Question II.5. Programmer des fonctions output et vide_liste de prototypes respectifs void output(void) et void vide_liste(void) ; output affiche le mot codé par la liste de caractères sur la sortie standard (suivi d'un retour à la ligne), tandis que vide_liste vide la liste (retire tous ses éléments) et libère la mémoire dynamique associée. Quelle est la complexité en temps de ces deux fonctions?
Partie III : Ordonnabilité des graphes
Dans cette partie on s'intéresse à des espaces métriques définis à partir de graphes non-orientés connexes. Pour un graphe non-orienté connexe (où est l'ensemble fini non-vide de nœuds du graphe et son ensemble d'arêtes), on note la fonction qui à un couple de nœuds ( ) de associe la longueur d'un plus court chemin de à dans .
L'objectif est de montrer que les espaces de la forme sont 3-ordonnables et d'étudier des algorithmes qui calculent de tels ordres. On travaillera en langage C.
Question III.1. Soit un graphe non-orienté connexe. Montrer que le couple ( ) est effectivement un espace métrique.
Question III.2. On considère les graphes et représentés ci-dessous.
a. Donner un 3-ordre de (aucune justification n'est attendue).
b. Donner un 2-ordre de (aucune justification n'est attendue).
On souhaite calculer un arbre couvrant d'un graphe non-orienté connexe. Un arbre est un graphe orienté acyclique avec un ensemble fini non vide de nœuds et un ensemble d'arcs tel que :
il existe un unique nœud , appelé la racine de tel que pour tout ,
pour tout nœud qui n'est pas la racine, il existe un unique nœud tel que et on dit que est un fils de .
On définit maintenant un arbre couvrant d'un graphe non-orienté connexe comme un arbre tel que : ;
pour tout .
On va travailler avec la représentation en matrice d'adjacence des graphes : on suppose que le nombre de nœuds est prédéfini en C comme une constante globale N , que les nœuds de sont et que est représenté par un tableau bidimensionnel bool graphe [N] [N] où et valent tous les deux true si est une arête de , et false sinon.
L'arbre couvrant sera également représenté par un tableau bool arbre , où cette fois arbre vaut true si est un fils de et false sinon.
qui remplit la structure arbre pour que celle-ci représente un arbre couvrant quelconque du graphe représenté par graphe, avec le nœud 0 comme racine. On supposera connexe et on ne vérifiera pas ce point dans le code. On pourra utiliser les fonctions définies dans la partie II pour gérer une file (ou une pile) de nœuds à traiter. Justifier brièvement la correction de votre algorithme.
On supposera par la suite que arbre représente effectivement un arbre couvrant comme indiqué plus haut et que le nœud 0 est la racine de celui-ci.
Question III.4. On considère la fonction C suivante :
void visite(bool arbre[N][N], int noeud, bool mystere) {
if(!mystere)
pushR(noeud);
for (int fils = 0; fils<N; ++fils) {
if (arbre[noeud][fils])
visite(arbre, fils, !mystere);
}
if(mystere)
pushR(noeud);
}
On suppose que la liste utilisée par la fonctions pushR est initialement vide et qu'on appelle visite(arbre, 0, false) sur un arbre arbre de racine 0 .
a. Que vaut le troisième argument mystere lors d'un appel récursif à visite avec comme deuxième argument un nœud de l'arbre, en fonction de la position de dans l'arbre?
b. Que contient la liste à la fin de l'exécution de ce programme sur le graphe de la question III.2, vu comme un arbre enraciné en 0 ?
Question III.5. Montrer que l'appel visite(a, 0, false), lorsque a est la représentation d'un arbre couvrant d'un graphe non-orienté connexe de racine 0 , calcule (dans la liste ) un 3-ordre pour .
Question III.6. Quelle est la complexité en temps de l'appel à visite(a, 0 , false), en fonction du nombre de nœuds? Peut-on améliorer cette complexité (par exemple en changeant notre méthode de représentation des graphes) ?
Question III.7. On observe que la fonction visite est une fonction récursive.
a. Quel(s) problème(s) cela pourrait-il poser ?
b. Proposer une méthode pour rendre ce calcul non récursif. On ne s'attend pas ici à du code, mais à une explication qui puisse être facilement transformée en du code.
Partie IV : Ordonnabilité des langages réguliers pour la distance push-pop-droite
Dans cette partie on souhaite caractériser les langages réguliers ordonnables pour la distance push-pop-droite. On travaillera en OCaml.
Automates et langages réguliers. Le terme automate désignera systématiquement un automate fini déterministe. Formellement, un automate , trans consiste en un ensemble fini d'états, un état initial , un ensemble d'états finaux, ainsi qu'une fonction de transition trans: , où signifie que la transition n'est pas définie. Un chemin dans d'un état à un état est une suite finie de la forme où les sont des états de et les des lettres de , telle que et telle que pour tout on a ; l'étiquette d'un tel chemin est alors le mot . En particulier, il y a toujours un chemin de longueur nulle, avec étiquette , entre n'importe quel état et lui-même (la suite comprenant ce seul état). Le langage accepté par , noté , est l'ensemble des mots qui étiquettent un chemin depuis jusqu'à un état final. Un langage est régulier s'il est accepté par un automate ou, de manière équivalente, s'il est représenté par une expression régulière.
On rappelle qu'un automate , trans est émondé si tout état est à la fois accessible depuis l'état initial (c'est-à-dire qu'il y a un chemin depuis à ) et co-accessible depuis un état final (c'est-à-dire qu'il y a un chemin depuis vers un état final). Pour tout automate , on peut calculer en temps linéaire un automate émondé tel que .
Automates poêle. D'après la question I.1, si est fini alors est ordonnable. On supposera infini dans cette partie. On définit dans ce qui suit la notion d'automate poêle-à-frire (ou automate poêle), puis on montre que est ordonnable si et seulement si n'importe quel automate émondé acceptant est un automate poêle.
Soit , trans un automate. Un cycle dans est un chemin de longueur non nulle dans depuis un état vers lui-même sans répétition d'état (à part ). On observe que ce chemin est possiblement de longueur 1 , dans le cas où pour . On note que si est un cycle, alors et plus généralement pour tout sont également des cycles : on dit que ce sont les mêmes cycles à permutation près.
Un chemin strict vers un cycle dans est un chemin sans répétition d'état depuis l'état initial jusqu'à un état faisant partie d'un cycle tel que tous les états sauf le dernier ne font pas partie d'un cycle dans ; formellement, c'est un chemin pour avec tel que fait partie d'un cycle et, pour ne fait partie d'aucun cycle. En particulier, si fait partie d'un cycle alors le seul tel chemin est de longueur nulle.
On dit de qu'il est pseudo-acyclique s'il a au plus un cycle à permutation près. On note qu'un automate tel que n'est jamais pseudo-acyclique, car et sont deux cycles différents.
Un automate est alors un automate poêle s'il est pseudo-acyclique et a un unique chemin strict vers un cycle.
Exemple 5. Considérons l'automate ci-dessous :
Son ensemble d'états est , son état initial , ses états finaux et ; les transitions non spécifiées par des flèches sont non définies. Cet automate est clairement déterministe et il est aisé de vérifier qu'il est émondé.
L'automate est également pseudo-acyclique : il comporte en effet un unique cycle, le cycle (qu'on peut également écrire ou encore ). Et comme il a un unique chemin strict vers un cycle (le chemin ), c'est un automate poêle.
Si une transition de à étiquetée par était ajoutée, ce ne serait plus un automate pseudo-acyclique car et seraient deux cycles différents. De même, si une transition étiquetée par a de à l'un des états du cycle était ajoutée, l'automate aurait deux chemins stricts distincts vers un cycle et ne serait donc plus un automate poêle.
Question IV.1. Proposer une méthode permettant de déterminer si un automate émondé est un automate poêle, en supposant n'importe quelle représentation raisonnable des automates (on supposera l'automate émondé). On ne demande pas du code, mais on attend une explication qui puisse être facilement transformée en du code.
Lorsque est un automate poêle, on appelle état d'entrée l'état qui se trouve à la fin de l'unique chemin strict vers l'unique cycle de (cet état peut être l'état initial si celui-ci fait partie du cycle). Dans l'exemple 5 , l'état est l'état d'entrée.
Question IV.2. Si est un automate poêle, montrer que peut s'écrire de la forme
où et sont des ensembles finis de mots et sont des mots avec .
Question IV.3. On suppose que est un automate poêle. Écrire un programme push-popdroite en OCaml qui calcule un -ordre pour , pour un certain que l'on ne cherchera pas à calculer, étant donnés les mots et ensembles de la question précédente représentés en OCaml par des variables :
u : lettre list
v : lettre list
f : (lettre list) list
f' : (lettre list) list
On a ainsi établi que lorsqu'un langage est accepté par un automate poêle alors il est ordonnable pour la distance push-pop-droite. On montre dans la suite de cette partie que c'est en fait une condition nécessaire, dans le sens où si est ordonnable, alors n'importe quel automate émondé pour est un automate poêle.
Pour ce faire, on considère l'arbre infini de défini ainsi : les nœuds de sont les mots de , le mot vide est la racine de et si alors et sont les fils de dans . Une branche infinie dans est une suite infinie de la forme , où et avec pour tout . Pour , on note le sous-arbre infini de enraciné en .
Pour un langage , une branche lourde est une branche infinie dans telle que pour tout contient une infinité de mots de .
Question IV.4. Montrer que, pour n'importe quel langage , si est infini alors a (au moins) une branche lourde.
Question IV.5. Montrer que, pour n'importe quel langage , si est ordonnable alors a au plus une branche lourde.
Question IV.6. Soit un automate émondé qui a au moins deux chemins stricts (distincts) vers des cycles (potentiellement identiques) et soient et des mots étiquetant deux tels chemins.
a. Montrer que n'est pas un préfixe de et que n'est pas un préfixe de .
b. Montrer que a au moins deux branches lourdes.
Question IV.7. Soit un automate émondé qui a un seul chemin strict vers un cycle. Montrer que si n'est pas pseudo-acyclique alors a au moins deux branches lourdes. En déduire que pour un langage régulier infini, est ordonnable si et seulement si n'importe quel automate émondé acceptant est un automate poêle.
Fin du sujet.
X ENS Informatique C MPI 2023 - Version Web LaTeX | WikiPrépa | WikiPrépa
