Concours 2015
Épreuve d'Informatique
Filière: MP
Durée de l'épreuve: 3 heures.
L'utilisation d'une calculatrice est autorisée.
Sujet mis à la disposition des concours:Cycle international, Écoles des Mines, Télécom Sud Paris, TPE-Eivp.L'énoncé de cette épreuve comporte 10 pages.Les candidats sont priés de mentionner de façon apparentesur la première page de la copie:INFORMATIQUE - MP
Recommandations aux candidats
Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.
Tout résultat fourni dans l'énoncé peut être utilisé pour les questions ultérieures même s'il n'a pas été démontré.
Il ne faut pas hésiter à formuler les commentaires qui semblent pertinents même lorsque l'énoncé ne le demande pas explicitement.
Composition de l'épreuve
L'épreuve comporte un unique problème (pages 2 à 10), comportant 32 questions.
Problème : Automates d'arbre
Préliminaire concernant la programmation
Il faudra coder des fonctions à l'aide du langage de programmation Caml, tout autre langage étant exclu. Lorsque le candidat écrira une fonction, il pourra faire appel à d'autres fonctions définies dans les questions précédentes; il pourra aussi définir des fonctions auxiliaires. Quand l'énoncé demande de coder une fonction, il n'est pas nécessaire de justifier que celle-ci est correcte, sauf si l'énoncé le demande explicitement. Enfin, si les paramètres d'une fonction à coder sont supposés vérifier certaines hypothèses, il ne sera pas utile dans l'écriture de cette fonction de tester si les hypothèses sont bien vérifiées.
Dans les énoncés du problème, un même identificateur écrit dans deux polices de caractères différentes désignera la même entité, mais du point de vue mathématique pour la police en italique (par exemple n ) et du point de vue informatique pour celle en romain avec espacement fixe (par exemple n ).
Fonctions utilitaires
Dans cette partie, on code quelques fonctions générales qui seront utiles par la suite. On ne cherchera pas à proposer l'implémentation la plus efficace possible de chaque fonction.
Quand il est question de donner la complexité d'une fonction, il s'agit de calculer la complexité asymptotique en temps, en notation O(⋅), de cette fonction dans le pire des cas. Il est inutile de donner une preuve de cette complexité. ◻1 - Coder une fonction Caml contient: 'a list -> 'a -> bool telle que contient li x renvoie un booléen qui vaut Vrai si et seulement si la liste li contient l'élément x . Donner la complexité de cette fonction. ◻2 - En utilisant la fonction contient, coder une fonction Caml union: 'a list -> 'a list -> 'a list telle que union 1112 , où 11 et 12 sont deux listes d'éléments sans doublon dans un ordre arbitraire, renvoie une liste sans doublon contenant l'union des éléments des deux listes, dans un ordre arbitraire. Donner la complexité de cette fonction. ◻3 - En utilisant la fonction union, coder une fonction Caml fusion: 'a list list -> 'a list telle que fusion 1 , où 1 est une liste de listes d'éléments, chacune de ces listes étant sans doublon, renvoie une liste de tous les éléments contenus dans au moins une des listes de la liste 1 , sans doublon et dans un ordre arbitraire. En notant l = (l_1, …, l_k) la liste codée par 1 et en posant L:=∑_(j = 1)^k|l_j|, donner la complexité de la fonction fusion en fonction de L. ◻4 - Coder produit: 'a list -> 'b list -> ('a * 'b) list, telle que produit 1112 renvoie une liste de tous les couples ( x, y ) avec x un élément de 11 et y un élément de 12 . On supposera les listes 11 et 12 sans doublon. La liste résultante doit avoir pour longueur le produit des longueurs des deux listes. Donner la complexité de cette fonction.
Arbres binaires étiquetés
Soit Σ = {α_0, …, α_(m − 1)} un ensemble fini non vide de m symboles, appelé alphabet. En Caml, on représentera le symbole α_k (pour 0 ⩽ k ⩽ m − 1 ) par l'entier k. Cet alphabet sera supposé fixé dans tout l'énoncé.
Un arbre binaire étiqueté par Σ (simplement appelé, dans ce problème, arbre) est soit l'arbre vide (noté ε ), soit un quintuplet ( S, r, λ, g, d ), où :
(i) S est un ensemble fini non vide dont les éléments sont appelés nœuds;
(ii) r ∈ S est la racine de S;
(iii) λ : S → Σ est une application associant à chaque nœud de S une étiquette de Σ;
(iv) g : S_g → S∖{r}, où S_g ⊆ S, est une application injective associant à un noeud u de S_g un noeud appelé fils gauche de u;
(v) d : S_d → S∖{r}, où S_d ⊆ S, est une application injective associant à un noud u de S_d un nœud appelé fils droit de u.
On dit qu'un nœud v est descendant d'un nœud u s'il existe une séquence de nœuds u_0, u_1, …, u_p ∈ S avec p > 0 telle que u_0 = u, u_p = v et, pour tout 0 ⩽ k ⩽ p − 1, soit u_(k + 1) = g(u_k), soit u_(k + 1) = d(u_k).
On requiert que tout nœud sauf la racine soit le fils gauche ou droit d'un unique nœud, et qu'aucun nœud ne soit à la fois fils gauche et fils droit :
∀u ∈ S∖{r}, |g^(− 1)({u})| + |d^(− 1)({u})| = 1
Par ailleurs, tout nœud de S∖{r} doit être descendant de r.
Un arbre admet une représentation graphique naturelle. Par exemple, l'arbre t_0 = ({u_0, u_1, u_2, u_3}, u_0, λ, g, d) est représenté ci-contre, avec :
On utilisera en Caml le type de données suivant pour coder un arbre :
type Arbre = Noeud of Noeud | Vide
and Noeud = { etiquette: int; gauche: Arbre; droit: Arbre; };;
Dans ce codage, un arbre non vide est représenté par une instance du type Noeud décrivant sa racine; un nœud est décrit par son étiquette (codée comme un entier), son fils gauche, son fils droit; le fils gauche et le fils droit peuvent, à nouveau, être décrits par une instance du type Noeud, ou par le constructeur Vide, qui décrit leur absence.
Par exemple, l'arbre t_0 pourra être décrit par la variable to comme suit :
5 - Pour simplifier l'écriture d'arbres, coder en Caml une fonction arbre telle que si x représente une étiquette x et ag et ad représentent deux arbres a_g et a_d, alors arbre x ag ad représente un arbre dont la racine est étiquetée par x, avec pour fils gauche la racine de a_g (avec ses propres fils) et pour fils droit la racine de a_d (avec ses propres fils). Ainsi, cette fonction doit permettre de construire t_0 avec :
let t0 = arbre 1 (arbre 1 Vide Vide)
(arbre 0 (arbre 1 Vide Vide) Vide);;
◻6 - Coder en Caml une fonction taille_arbre prenant en argument une variable t représentant un arbre t et renvoyant le nombre de nœuds de l'arbre t.
Langages d'arbres
Soit T^Σ l'ensemble de tous les arbres étiquetés par Σ. Un langage d'arbres sur un alphabet Σ est un ensemble (fini ou infini) d'arbres étiquetés par Σ, c'est-à-dire un sous-ensemble de T^Σ.
On considère dans ce problème certains langages particuliers, tous définis sur l'alphabet {α_0, α_1} :
L_0 est l'ensemble des arbres dont au moins un nœud est étiqueté par α_0.
Un arbre est complet s'il ne contient aucun nœud ayant un seul fils (c'est-à-dire, tout nœud a un fils gauche si et seulement s'il a un fils droit); conventionnellement, ε est considéré comme complet. Le langage L_(complet) est l'ensemble de tous les arbres complets.
Un arbre ( S, r, λ, g, d ) est un arbre-chaîne s'il a uniquement des fils gauches : d^(− 1)(S∖{r}) = ∅; conventionnellement, ε est également un arbre-chaîne. Le langage L_(chaîne) est l'ensemble de tous les arbres-chaînes.
Un arbre ( S, r, λ, g, d ) est impartial s'il a autant de fils gauches que de fils droits, c'est-à-dire si on a |g(S)| = |d(S)|; conventionnellement, ε est également impartial. On note L_(impartial) l'ensemble de tous les arbres impartiaux. ◻7 - Pour chacun des quatre langages L_0, L_(complet), L_(chaîne), L_(impartial), donner (sans justification) un exemple d'arbre avec au moins deux nœuds qui appartient au langage, et un exemple d'arbre avec au moins deux nœuds qui n'y appartient pas. ◻8 - Démontrer que tout arbre complet est impartial, mais que la réciproque est fausse. ◻9 - Démontrer que tout arbre impartial non vide a un nombre impair de nœuds.
Automates d'arbres descendants déterministes
Un automate d'arbres descendant déterministe (ou simplement automate descendant déterministe) sur l'alphabet Σ est un quadruplet A^↓ = (Q, q_0, F, δ) où :
(i) Q est un ensemble fini non vide dont les éléments sont appelés états;
(ii) q_0 ∈ Q est appelé état initial ;
(iii) F ⊆ Q est un ensemble dont les éléments sont appelés états finals;
(iv) δ : Q × Σ → Q × Q est une application appelée fonction de transition; pour tout q ∈ Q, pour tout α ∈ Σ, δ(q, α) est un couple d'états (q_g, q_d).
Un automate descendant déterministe A^↓ = (Q, q_0, F, δ) reconnaît un arbre t si :
soit t = ε et q_0 ∈ F;
soit t = (S, r, λ, g, d) et il existe une application φ : S → Q avec :
(i) φ(r) = q_0;
(ii) pour tout u ∈ S, si (q_g, q_d) = δ(φ(u), λ(u)) :
si g(u) est défini (u ∈ S_g), alors on a φ(g(u)) = q_g, sinon on a q_g ∈ F;
si d(u) est défini (u ∈ S_d), alors on a φ(d(u)) = q_d, sinon on a q_d ∈ F.
Noter que quand une telle application φ existe, elle est nécessairement unique.
Le langage reconnu par un automate descendant déterministe A^↓, noté L(A^↓), est l'ensemble de tous les arbres reconnus par A^↓. ◻10 - Donner un automate descendant déterministe reconnaissant le langage L_(chaîne); aucune justification n'est demandée. ◻11 - Montrer qu'il n'existe pas d'automate descendant déterministe qui reconnaît L_0.
En Caml, un état q_i de Q = {q_0, …, q_(n − 1)} est codé par l'entier i. L'ensemble des états finals F est codé par un vecteur de booléens finals_desc de taille n, tel que finals_desc. (i) contient Vrai si et seulement si q_i ∈ F. Enfin, les transitions sont codées par une matrice de couples d'entiers, telle que transitions_desc.(i).(k) est le couple (g, d) vérifiant (q_g, q_d) = δ(q_i, α_k).
On représente ainsi en Caml un automate descendant déterministe ( Q, q_0, F, δ ) avec le type suivant :
12 - Pour un automate descendant déterministe A^↓ = (Q, q_0, F, δ) et q ∈ Q, on note A_q^↓ l'automate descendant déterministe ( Q, q, F, δ ) identique à A^↓ sauf pour l'état initial. Coder une fonction applique_desc telle que applique_desc add q t , où add représente un automate descendant déterministe A^↓ = (Q, q_0, F, δ), q un état q ∈ Q et t un arbre t = (S, r, λ, g, d), renvoie un booléen qui vaut Vrai si et seulement A_q^↓ reconnait t. ◻13 - En utilisant applique_desc, coder une fonction evalue_desc telle que evalue_desc add t, où add représente un automate descendant déterministe A^↓ et t un arbre t, renvoie un booléen qui vaut Vrai si et seulement si A^↓ reconnaît t.
Automates descendants et langages rationnels de mots
À tout mot non vide x = x_1…x_l avec x_1, …, x_l ∈ Σ, on associe un arbre-chaîne chaîne(x) = ({u_1…u_l}, u_1, λ, g, d) vérifiant : pour 1 ⩽ i ⩽ l, λ(u_i) = x_i et pour 1 ⩽ i ⩽ l − 1, g(u_i) = u_(i + 1), d n'étant défini pour aucun u_i, et g(u_l) étant non défini. Par convention, chaîne (ε) = ε (où le premier ε est le mot vide, le second l'arbre vide).
Pour un langage de mots L, on définit le langage d'arbres chaîne (L):={ chaîne (x)|x ∈ L}. ◻14 - Soit L un langage de mots, supposé rationnel. Il existe donc un automate de mots déterministe A = (Q, Σ, q_0, F, δ) reconnaissant L. Soient q_1^′, q_2^′ ∉ Q. On construit l'automate d'arbres descendant déterministe A^↓ = (Q ∪ {q_1^′, q_2^′}, q_0, F ∪ {q_1^′}, δ^′) avec pour (q, α) ∈ Q × Σ, δ^′(q, α):=(δ(q, α), q_1^′) et, pour q ∈ {q_1^′, q_2^′} et pour α ∈ Σ, δ^′(q, α):=(q_2^′, q_2^′). Démontrer que A^↓ reconnaît chaîne (L). ◻15 - Montrer que pour tout langage de mots L, si chaîne (L) est reconnu par un automate d'arbres descendant déterministe, alors L est rationnel. ◻16 - Soit L_(égal) le langage de mots sur l'alphabet {α_0, α_1} formé des mots contenant autant de α_0 que de α_1. Supposons par l'absurde qu'il existe un automate (de mots) déterministe A_(égal) reconnaissant L_(égal) et soit k le nombre d'états de A_(égal). En considérant le mot x = α_0^k α_1^k, montrer que l'on aboutit à une contradiction, et que donc L_(égal) n'est pas un langage rationnel.
En déduire qu'il n'existe aucun automate descendant déterministe reconnaissant chaîne(L_(égal)).
Automates d'arbres ascendants
Un automate d'arbres ascendant (ou simplement automate ascendant) sur l'alphabet Σ est un quadruplet A^↑ = (Q, I, F, Δ) où :
(i) Q est un ensemble fini non vide dont les éléments sont appelés états;
(ii) I ⊆ Q est un ensemble dont les éléments sont appelés états initiaux;
(iii) F ⊆ Q est un ensemble dont les éléments sont appelés états finals;
(iv) Δ : Q × Q × Σ → P(Q), où P(X) désigne l'ensemble des parties de X, est une application appelée fonction de transition; pour tout (q_g, q_d) ∈ Q × Q, et tout α ∈ Σ, Δ(q_g, q_d, α) est un ensemble d'états.
Par exemple, on définit un automate ascendant A_0^↑ = (Q, I, F, Δ) sur l'alphabet {α_0, α_1} avec :
(i) Q = {q_0, q_1};
(ii) I = {q_0};
(iii) F = {q_1};
(iv) Δ est donnée par la table de transition suivante :
Σ
Q × Q
α_0
α_1
(q_0, q_0)
{q_1}
{q_0}
(q_0, q_1)
{q_1}
{q_1}
(q_1, q_0)
{q_1}
{q_1}
(q_1, q_1)
{q_1}
{q_1}
Un automate ascendant A^↑ = (Q, I, F, Δ) reconnaît un arbre t si :
soit t = ε et I ∩ F ≠ ∅;
soit t = (S, r, λ, g, d) et il existe une application φ : S → Q avec :
(i) φ(r) ∈ F;
(ii) pour tout u ∈ S, il existe (q_g, q_d) ∈ Q × Q tels que φ(u) ∈ Δ(q_g, q_d, λ(u)) et :
si g(u) est défini (u ∈ S_g), alors on a φ(g(u)) = q_g, sinon q_g ∈ I;
si d(u) est défini (u ∈ S_d), alors on a φ(d(u)) = q_d, sinon q_d ∈ I.
Noter que, contrairement au cas des automates descendants déterministes, quand une telle application φ existe, elle n'est pas nécessairement unique.
On observe que A_0^↑ ne reconnaît pas ε(car{q_0} ∩ {q_1} = ∅) et que A_0^↑ reconnaît l'arbre t_0 défini page 3 via l'application représentée ci-dessous :
Le langage reconnu par un automate ascendant A^↑, noté L(A^↑), est l'ensemble de tous les arbres reconnus par A^↑. On dit qu'un langage d'arbres L est rationnel s'il existe un automate ascendant A^↑ qui reconnaît L. ^1
On dit qu'un automate ascendant ( Q, I, F, Δ ) est déterministe si |I| = 1 et, pour tout (q_g, q_d, α) ∈ Q × Q × Σ, |Δ(q_g, q_d, α)| = 1. ◻17 - Montrer que l'on a L(A_0^↑) = L_0. ◻18 - Soit L un langage d'arbres. Montrer que s'il existe un automate descendant déterministe A^↓ reconnaissant L, alors L est un langage d'arbres rationnel.
En Caml, un état q_i de Q = {q_0, …, q_(n − 1)} est codé par l'entier i. L'ensemble des états initiaux I est codé par leur liste initiaux_asc, dans un ordre arbitraire; l'ensemble des états finals F est codé par un vecteur de booléens finals_asc de taille n, dont la composante de position i contient Vrai si et seulement si q_i ∈ F. Finalement, les transitions sont codées par un tableau tridimensionnel de listes d'entiers, telle que transitions_asc. (i). (j). (k) est une liste dans un ordre arbitraire des états q avec q ∈ Δ(q_i, q_j, α_k).
On représente ainsi en Caml un automate ascendant ( Q, I, F, Δ ) avec le type cidessous :
type Automate_Ascendant = {
initiaux_asc: int list;
finals_asc: bool vect;
transitions_asc: int list vect vect vect
};;;
19 - Coder une fonction nombre_etats_asc prenant en argument la représentation aa d'un automate ascendant et renvoyant le nombre d'états de cet automate. ◻20 - Coder une fonction nombre_symboles_asc prenant en argument la représentation aa d'un automate ascendant et renvoyant le nombre de symboles de l'alphabet sur lequel cet automate est défini. ◻21 - Coder une fonction Caml applique_asc telle que applique_asc aa t, où aa représente un automate ascendant A^↑ = (Q, I, F, Δ) et t un arbre t, renvoie une liste sans doublon des états q pour lesquels il existe une application φ : S → Q avec φ(r) = q qui vérifie la condition (ii) de la définition de reconnaissance d'un arbre par un automate ascendant page 7. Si t = ε, la fonction applique_asc doit renvoyer la liste des états initiaux de A^↑. On pourra utiliser les fonctions utilitaires des questions 1 à 4 . ◻22 - En utilisant applique_asc, coder une fonction evalue_asc telle que evalue_asc aa t, où aa représente un automate ascendant A^↑ et t un arbre t, renvoie un booléen qui vaut Vrai si et seulement si A^↑ reconnaît t. On pourra utiliser la fonction contient. ◻23 - Montrer qu'un langage d'arbres L est un langage d'arbres rationnel si et seulement s'il existe un automate ascendant déterministe reconnaissant L. ◻24 - Coder deux fonctions Caml identifiant_partie: int list -> int et partie_identifiant: int -> int list réciproques l'une de l'autre, codant une bijection entre les parties de [ [0; n − 1] ] (une partie étant représentée par une liste d'entiers sans doublon, dans un ordre arbitraire) et les entiers de 0 à 2^n − 1. On rappelle qu'en Caml l'expression 1 lsl i calcule l'entier 2^i.
25 - En s'appuyant sur identifiant_partie et partie_identifiant et sur la réponse à la question 23, coder une fonction determinise_asc prenant en argument la représentation aa d'un automate ascendant A^↑ et renvoyant la représentation d'un automate ascendant déterministe reconnaissant le même langage que A^↑. ◻26 - Montrer que si L est un langage d'arbres rationnel, alors T^Σ∖L est un langage d'arbres rationnel. ◻27 - Coder une fonction complementaire_asc prenant en entrée la représentation aa d'un automate ascendant reconnaissant un langage L et renvoyant la représentation d'un automate ascendant reconnaissant T^Σ∖L. ◻28 - Montrer que si L_1 et L_2 sont deux langages d'arbres rationnels, alors L_1 ∪ L_2 est un langage d'arbres rationnel. ◻29 - Coder une fonction union_asc prenant en entrée les représentations aa1 et aa2 de deux automates ascendants reconnaissant respectivement les langages L_1 et L_2 et renvoyant la représentation d'un automate ascendant reconnaissant L_1 ∪ L_2. ◻30 - Montrer que si L_1 et L_2 sont deux langages d'arbres rationnels, alors L_1 ∩ L_2 est un langage d'arbres rationnel. ◻31 - Coder une fonction intersection_asc prenant en entrée les représentations aa1 et aa2 de deux automates ascendants reconnaissant respectivement les langages L_1 et L_2 et renvoyant la représentation d'un automate ascendant reconnaissant L_1 ∩ L_2. ◻32 - Sans chercher à utiliser les propriétés de clôture par union, complémentation ou intersection, montrer que le langage L_(impartial) n'est pas un langage d'arbres rationnel.
Fin de l'épreuve
La notion de langages d'arbres rationnels est distincte de la notion de langages de mots rationnels.
Pas de description pour le moment
Commentaires• Mines Option Informatique MP 2015
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Même année, X-ENSX ENS Option Informatique MP 2015X-ENS · 2015Corrigé
Même année, CentraleCentrale Option Informatique MP 2015Centrale · 2015Corrigé
Même année, CCINPCCINP Option Informatique MP 2015CCINP · 2015Corrigé
Même année, E3AE3A Option Informatique MP 2015E3A · 2015Corrigé
