Mines Informatique MP 2009

Thème de l'épreuve Étude d'une fonction sur les langages et arbres enracinés non ordonnés
Principaux outils utilisés langages rationnels, automates finis, parcours d'arbre, listes triées

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                       

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


Épreuve deinformatique 2009

A 2009 INFO. MP
ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES,
ÉCOLES NATIONALES SUPÉRIEURES DE LeAÉRONAUTIQUE ET DE LeESPACE,
DE TECHNIQUES AVANCÉES, DES TÉLÉCOMMUNICATIONS,
DES MINES DE PARIS, DES MINES DE SAINT-ÉTIENNE, DES MINES DE NANCY,
DES TÉLÉCOMMUNICATIONS DE BRETAGNE,
ÉCOLE POLYTECHNIQUE (FILIÈRE TSI)
CONCOURS DeADMISSION 2009
ÉPREUVE D'INFORMATIQUE
Filière MP
Durée de l'épreuve : 3 heures.
L'usage de calculettes est autorisé. L'utilisation d'un ordinateur est 
interdite.
Sujet mis à disposition des concours : ENSAE ParisTech, TELECOM SudParis (ex 
INT), TPE-EIVP
Les candidats sunt priés de mentiunner de façun apparente sur la première page 
de la cupie :
INFORMATIQUE - MP

L'énuncé de cette épreuve cumpurte 8 pages.

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
Leépreuve comporte deux problèmes indépendants :
· un problème sur les automates, pages 2 et 3 ;
· un problème dealgorithmique, pages 4 à 8.

Préliminaire pour l'ensemble de l'épreuve concernant la programmation
Il faudra écrire des fonctions ou des procédures à leaide deun langage de 
programmation qui pourra être
soit Caml, soit Pascal, tout autre langage étant exclu. Indiquer en début 
d'épreuve le langage de
programmation choisi ; il est interdit de modifier ce choix au cours de 
l'épreuve. Certaines questions des
problèmes sont formulées différemment selon le langage de programmation ; cela 
est indiqué chaque fois que
cela est nécessaire. Lorsque le candidat écrira une fonction ou une procédure, 
il pourra faire appel à une autre
fonction ou procédure définie dans les questions précédentes. Enfin, si les 
paramètres deune fonction ou deune
procédure à écrire sont supposés vérifier certaines hypothèses, il ne sera pas 
utile dans leécriture de cette fonction
ou de cette procédure de tester si les hypothèses sont bien vérifiées.
Dans les énoncés des problèmes, 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 une 
police (en italique ; par
exemple a) et du point de vue informatique pour leautre (en romain ; par 
exemple a).
Page 1 sur 8

Épreuve deinformatique 2009

Problème 1. Automates
Les quelques rappels de définitions qui suivent permettent de fixer la 
terminologie et les notations.
Un alphabet  est un ensemble fini deéléments appelés lettres. Un mot sur  est 
une suite finie de
lettres de  ; la longueur deun mot est le nombre de lettres le composant ; le 
mot de longueur nulle est noté .
On désigne par  * leensemble des mots sur  , y compris le mot . Un langage sur  
est une partie de  *.
Un autumate fini A est décrit par une structure < , Q, T, I, F>, où :
·  est un alphabet ;
· Q est un ensemble fini et non vide appelé ensemble des états de A ;
· T  Q ×  × Q est appelé leensemble des transitiuns ; étant donnée une 
transition (p, x, q)  T, on
x

 q ;
dit queelle est deurigine p, deextrémité q et queelle est deétiquette x ; on 
pourra la noter p 
· I  Q est appelé ensemble des états initiaux de A ;
· F  Q est appelé ensemble des états finals de A.
Dans ce problème, on considérera uniquement des automates ayant un seul état 
initial, noté q0.
x

x

x

1
2
k
Un chemin de A est une suite de transitions de la forme p0 
p1 
p2 ... 
pk. On dit
alors que ce chemin va de p0 à pk. Dans un automate fini, un état q est dit 
utile seil existe à la fois un chemin de
leétat initial q0 à q et un chemin de q à un état final.

On rappelle le théorème de Kleene : un langage sur un alphabet  est rationnel 
si et seulement seil
existe un automate fini dealphabet  qui le reconnaît.
On ne considère dans tout ce problème que l'alphabet  = {a, b}. Tous les mots 
et langages
considérés seront définis sur cet alphabet.
On définit une application  de  dans  de la façon suivante :
· () =  ;
· si un mot u de longueur 2k > 0 seécrit u = u1u2 ... u2k­1u2k où, pour i  {1, 
2, ..., 2k}, ui appartient
à  , alors (u) = u2u1u4u3 ... u2ku2k­1 ;
· si un mot u de longueur 2k + 1 > 0 seécrit u = u1u2 ... u2ku2k+1 où, pour i  
{1, 2, ..., 2k, 2k + 1},
ui appartient à  , alors (u) = u2u1u4u3 ... u2ku2k­1u2k+1.
La fonction  agit donc en échangeant chaque lettre deindice pair avec la lettre 
(deindice impair) qui la
précède immédiatement. Ainsi, (a) = a, (abba) = baab, (aabab) = aaabb.
 1 - Soit u un mot dans  *. Établir une condition nécessaire et suffisante pour 
que, quel que soit le
mot v dans  *, leégalité (uv) = (u)(v) soit vérifiée.
On note L1 leensemble des mots u tels que (u)  u.
 2 - Caractériser les mots de L1.
 3 - Proposer, preuve à leappui, une expression rationnelle décrivant L1 ; on 
privilégiera une
expression rationnelle simple.
 4 - Dessiner un automate fini reconnaissant L1 ; on privilégiera un automate 
ayant peu deétats.
On note L2 le langage décrit par leexpression rationnelle a*b*.
 5 - Proposer une expression rationnelle décrivant (L2). Justifier brièvement 
la réponse.
 6 - Dessiner un automate fini reconnaissant (L2). Justifier brièvement la 
réponse.
On se propose de montrer que si L est un langage rationnel, alors (L) est aussi 
un langage rationnel.
Les questions  7 à  14 permettent deobtenir ce résultat.
Page 2 sur 8

Épreuve deinformatique 2009

Si L est un langage, on note P(L) leensemble des mots de L de longueur paire et 
I(L) leensemble des
mots de L de longueur impaire.
 7 - Montrer que si L est rationnel, P(L) et I(L) sont rationnels.
 8 - On considère un automate fini A reconnaissant un langage L ne contenant 
que des mots de
longueur paire ; soit q un état utile de A. Montrer que A ne possède pas de 
transition dont leorigine et
leextrémité soient q.
 9 - On considère un automate fini A = < , Q, T, {q0}, F> reconnaissant un 
langage L ne contenant
que des mots de longueur paire ; soit q un état utile de A. Montrer que les 
chemins de q0 à q sont soit
tous de longueur paire, soit tous de longueur impaire.
Soit A un automate fini. Soit q un état de A. On suppose que :
· q est un état utile ;
· q neest ni leétat initial, ni un état final ;
· il neexiste dans A aucune transition dont leorigine et leextrémité soient 
simultanément q,
x

ceest-à-dire aucune transition qui seécrive q 
 q quelle que soit leétiquette x considérée ;
· il existe au moins deux transitions deorigine q ou au moins deux transitions 
deextrémité q.
On considère leautomate obtenu à partir de A et q de la façon suivante : pour 
chaque quadruplet
(q , q, x, y), où q  et q sont deux états de A, x et y deux lettres de  
distinctes ou non, et tel que A contienne les
x

y

x

y

transitions q  
 q et q  q, on ajoute un nouvel état r et les transitions q 
 r et r  q ;
on ajoute donc autant deétats que de tels quadruplets ; chaque état ajouté est 
extrémité deune unique transition et
origine deune unique transition. Enfin, on supprime leétat q et toutes les 
transitions deorigine ou deextrémité q.
On note S A, q) leautomate ainsi obtenu.
 10 - Soit q un état vérifiant les hypothèses ci-dessus. Montrer que les 
automates A et S(A, q)
reconnaissent le même langage.
 11 - Montrer que, si L est un langage rationnel, alors (P(L)) est aussi un 
langage rationnel.
Soit L un langage rationnel. Soit x une lettre de . On note M(L, x) le langage 
défini comme suit : pour
tout mot u sur lealphabet  , le mot u appartient à M(L, x) si et seulement si 
le mot ux est dans L.
 12 - Montrer que si L est un langage rationnel et x appartient à , le langage 
M(L, x) est rationnel.
 13 - Soit L un langage. Donner une relation entre (I(L)), (M(I(L), a)) et 
(M(I(L), b)).
 14 - Soit L un langage rationnel. Montrer que (L) est aussi un langage 
rationnel.
 15 - Soit L un langage non rationnel. Indiquer si (L) peut être un langage 
rationnel.
 16 - Il seagit deécrire la fonction  en langage de programmation.
Caml :
On utilise le type suivant pour représenter les lettres de lealphabet  :
type lettre = a | b ;;
Un mot est codé par une liste de type lettre list ; par exemple, le mot abbab 
est codé par la liste
[a;b;b;a;b]. La liste vide [] code le mot de longueur nulle .
Écrire en Caml une fonction phi telle que, si un mot u sur lealphabet  est codé 
par une liste u de type
lettre list, alors phi u renvoie une liste de type lettre list codant (u).
Attention : leemploi de références ou de vecteurs est interdit.
Pascal :
On définit la constante et les types suivants :
const MAX = 100;
type Sigma = (a, b);
type Mot = array[1 .. MAX] of Sigma;
Écrire en Pascal une fonction phi telle que, si u de type Mot code un mot u sur 
lealphabet  de
longueur k inférieure ou égale à MAX, alors phi(u, k) renvoie un tableau de 
type Mot codant (u).
Page 3 sur 8

Épreuve deinformatique 2009

Problème 2. Algorithmique
Leobjectif de ce problème est de compter le nombre dearbres enracinés, nun 
urdunnés et étiquetés de
nombre de noeuds donné. Pour cela, on étudie un codage particulier de ces 
arbres appelé cudage de Prüfer.
Un arbre possède un nombre fini deéléments appelés noeuds. Les arbres 
considérés dans ce problème
possèdent tous au moins un noeud. Un arbre enraciné nun urdunné A est défini 
récursivement de la façon
suivante : il est constitué deun noeud particulier appelé racine de A et deun 
ensemble fini non ordonné,
éventuellement vide, dearbres enracinés nun urdunnés appelés suus-arbres de A. 
Les racines des sous-arbres de
A sont les fils de la racine de A et la racine de A est le père de ces 
derniers. Dans un arbre, deux noeuds sont dits
frères seils ont même père. Learité deun noeud est son nombre de fils ; dans ce 
problème, learité deun noeud peut
être quelconque. Les noeuds dearité 0 sont les feuilles de learbre.
Un arbre est dit étiqueté si à chaque noeud est associé un entier positif ou 
nul, ces entiers étant deux à
deux distincts ; leentier associé à un noeud est leétiquette du noeud. On 
pourra nommer un noeud par son
étiquette ; si i est un entier, on pourra donc parler du noeud i pour le noeud 
deétiquette i.
Dans ce problème, le terme d'arbre désignera toujours un arbre enraciné non 
ordonné étiqueté.
Les deux dessins ci-dessous sont deux représentations graphiques deun même 
arbre nommé A1.
Leétiquette de la racine de A1 est 4 ; leensemble des étiquettes des fils de la 
racine est {1, 3, 6} ; leensemble des
étiquettes des fils du noeud deétiquette 6 est {2, 5} ; le noeud deétiquette 3 
possède un seul fils : le noeud
deétiquette 0 ; les noeuds deétiquettes 0, 1, 2, 5 neont pas de fils. Les 
représentations graphiques deun arbre donné
diffèrent par leordre dans lequel on dessine les fils deun même noeud.

4

1

4

6

2

3

3

0

0

5

Learbre A1, première représentation

1

6

5

2

Learbre A1, seconde représentation

1
Learbre A2 représenté
différent de learbre A1.

ci-contre

est

0

6

2

4

3

5

Learbre A2
On dira queun arbre est un arbre étiqueté cunsécutivement seil seagit deun 
arbre étiqueté et que
leensemble de ses étiquettes forme un intervalle deentiers de plus petite 
valeur 0 ; autrement dit, pour un arbre
ayant n noeuds et étiqueté consécutivement, leensemble des étiquettes est {0, 
1, 2, ..., n ­ 1}. Les arbres A1 et A2
sont des arbres étiquetés consécutivement.

Page 4 sur 8

Épreuve deinformatique 2009

Première partie : d'un codage racine-fils-frères d'un arbre au codage de Prüfer
 17 - Donner la liste des arbres possédant trois noeuds et étiquetés 
consécutivement.
Soit A un arbre étiqueté consécutivement ayant n noeuds. Pour coder A, on 
définit un codage nommé
cudage racine-fils-frères. Pour cela, on fixe une représentation graphique de A 
; on code A à leaide de :
· leétiquette de la racine (qui ne dépend pas de la représentation) ;
· un tableau nommé fils ; pour i compris entre 0 et n ­ 1, la case deindice i 
du tableau fils contient la
valeur ­1 si le noeud i est une feuille de learbre et, sinon, leétiquette du 
fils du noeud i se situant le
plus à gauche dans la représentation graphique choisie ;
· un tableau nommé freres ; pour i compris entre 0 et n ­ 1, la case deindice i 
du tableau freres
contient la valeur ­1 si le noeud i nea aucun frère sur sa droite et, sinon, 
leétiquette de son frère qui se
trouve le premier sur sa droite.
Pour learbre A1, si on choisit la première représentation, on obtient le codage 
suivant :
· la racine est le noeud 4 ;
· pour le tableau fils : les cases deindices 0, 1, 2 et 5 contiennent la valeur 
­1, la case deindice 3
contient 0, la case deindice 4 contient 1, la case deindice 6 contient 2 ;
· pour le tableau freres : les cases deindices 0, 3, 4 et 5 contiennent la 
valeur ­1, la case deindice 1
contient 6, la case deindice 2 contient 5, la case deindice 6 contient 3.

Ainsi, learbre A1 est représenté par la valeur 4 pour la racine et par les deux 
tableaux ci-dessous :
indice
0
1
2
3
4
5
6
fils
­1
­1
­1
0
1
­1
2
indice
freres

0
­1

1
6

2
5

3
­1

4
­1

5
­1

6
3

On définit aussi deux tableaux qui peuvent être calculés à partir du codage 
racine-fils-frères :
· un tableau nommé peres ; pour i compris entre 0 et n ­ 1, la case deindice i 
contient la valeur ­1 seil
seagit de la racine de learbre et, dans les autres cas, leétiquette du père du 
noeud i ; pour learbre A1, la
case deindice 4 contient la valeur ­1, la case deindice 0 contient 3, les cases 
deindices 1, 3 et 6
contiennent 4, les cases deindices 2 et 5 contiennent la valeur 6 ;
· un tableau nommé arites ; pour i compris entre 0 et n ­ 1, la case deindice i 
de ce tableau contient
learité du noeud i ; pour learbre A1, les cases deindices 0, 1, 2 et 5 
contiennent la valeur 0, la case
deindice 3 contient 1, la case deindice 4 contient 3, la case deindice 6 
contient 2.
Pour learbre A1, les tableaux peres et arites sont représentés ci-dessous :
indice
0
1
2
3
4
5
6
peres
3
4
6
4
­1
6
4
indice
arites

0
0

1
0

2
0

3
1

4
3

5
0

6
2

Indications pour la programmation en Pascal
On définit la constante et le type suivant :
const MAX = 100;
type Tableau = array[0 .. MAX - 1] of Integer;
La constante MAX est un majorant du nombre de noeuds des arbres considérés.
Fin des indications pour la programmation en Pascal
 18 - Il seagit deécrire en langage de programmation une fonction nommée 
calculer_peres qui, à
partir du codage racine-fils-frères deun arbre étiqueté consécutivement, 
calcule le tableau peres
correspondant à cet arbre.
Caml : Écrire en Caml une fonction calculer_peres telle que, si on considère un 
arbre A
possédant n noeuds et étiqueté consécutivement et si :
· racine est un entier qui contient leétiquette de la racine de A,
· fils et freres sont deux vecteurs de longueur n qui représentent 
respectivement les tableaux fils
et freres deun codage racine-fils-frères de A,

Page 5 sur 8

Épreuve deinformatique 2009

alors calculer_peres racine fils freres renvoie un vecteur de longueur n 
correspondant
au tableau peres défini plus haut.
Pascal : Écrire en Pascal une fonction calculer_peres telle que, si on 
considère un arbre A
étiqueté consécutivement et si :
· racine est un entier qui contient leétiquette de la racine de A,
· fils et freres sont de type Tableau et représentent respectivement les 
tableaux fils et freres
deun codage racine-fils-frères de A,
· n est un entier qui contient le nombre de noeuds de A,
alors calculer_peres(racine, fils, freres, n) renvoie un tableau de type Tableau
contenant, entre les indices 0 et n ­ 1, le tableau peres défini plus haut.
 19 - Indiquer, en fonction du nombre de noeuds de learbre considéré, la 
complexité de la fonction
calculer_peres.
 20 - Il seagit deécrire en langage de programmation une fonction nommée 
calculer_arites qui, à
partir du codage racine-fils-frères deun arbre étiqueté consécutivement, 
renvoie le tableau arites
correspondant à cet arbre.
Caml : Écrire en Caml une fonction calculer_arites telle que, pour un arbre A 
possédant n
noeuds et étiqueté consécutivement, si fils et freres sont deux vecteurs de 
longueur n qui
représentent respectivement les tableaux fils et freres deun codage 
racine-fils-frères de A, alors
calculer_arites fils freres renvoie un vecteur correspondant au tableau arites 
défini plus
haut.
Pascal : Écrire en Pascal une fonction calculer_arites telle que, pour un arbre 
A étiqueté
consécutivement, si :
· fils et freres sont de type Tableau et représentent respectivement les 
tableaux fils et freres
deun codage racine-fils-frères de A,
· n est un entier qui contient le nombre de noeuds de A,
alors calculer_arites(fils, freres, n) renvoie un tableau de type Tableau 
contenant
entre les indices 0 et n ­ 1 les arités des noeuds de learbre.
 21 - Indiquer, en fonction du nombre de noeuds de learbre considéré, la 
complexité de la fonction
calculer_arites.
 22 - Il seagit deécrire en langage de programmation une fonction inserer qui 
prend en arguments un
tableau table deentiers non nécessairement distincts triés par valeurs 
décroissantes et un entier d ; cette
fonction modifie le tableau table pour insérer leentier d en respectant leordre 
décroissant. Leentier d est
inséré même seil figure déjà dans table.
Caml : Écrire en Caml une fonction inserer telle que, si :
· table est un vecteur deentiers,
· nb est un entier positif ou nul ne dépassant pas la dimension du vecteur 
table diminuée de 1,
· d est un entier,
· on suppose que le vecteur table contient des entiers classés par valeurs 
décroissantes dans les
cases deindices compris entre 0 et nb ­ 1, les autres cases du vecteur table 
étant ignorées,
alors inserer table nb d insère la donnée d dans le vecteur table en respectant 
leordre
décroissant. La fonction renvoie nb + 1, ceest-à-dire le nouveau nombre de 
données figurant dans
table.
Pascal : Écrire en Pascal une fonction inserer telle que, si :
· table est de type Tableau,
· nb est un entier positif ou nul ne dépassant pas MAX ­ 1,
· d est un entier ;
· on suppose que le tableau table contient entre les indices 0 et nb ­ 1 des 
entiers classés par
valeurs décroissantes, les autres cases du tableau table étant ignorées,

Page 6 sur 8

Épreuve deinformatique 2009

alors inserer(table, nb, d) insère la donnée d dans le tableau table en 
respectant leordre
décroissant. La fonction renvoie nb + 1, ceest-à-dire le nouveau nombre de 
données figurant dans
table.
 23 - Indiquer, en fonction du nombre nb deentiers contenus dans un tableau 
trié table, la complexité
de la fonction inserer quand elle insère un nouvel entier dans table.
Soit A un arbre possédant n noeuds ; on note E(A) leensemble des étiquettes de 
A ; les étiquettes de A
étant toutes distinctes, leensemble E(A) possède n éléments. Le codage de 
Prüfer deun arbre étiqueté ayant n
noeuds est une suite de n ­ 1 entiers appartenant à E(A), suite notée Pr(A) ; 
ce codage est défini récursivement de
la façon suivante. Si A est réduit à un noeud, sa racine, son codage de Prüfer 
est la suite vide. Sinon, soit f la
feuille de A deétiquette minimum et soit p le père de f ; on note A learbre 
obtenu en enlevant de A la feuille f ; par
définition, le codage de Prüfer de A est la suite dont le premier élément est 
leétiquette de p, ce premier élément
étant suivi du codage de Prüfer de A.
Ainsi, le codage de Prüfer de learbre A1 est : 3, 4, 6, 4, 6, 4 ; le codage de 
Prüfer de learbre A2 est :
1, 2, 2, 1, 6, 1.
 24 - Indiquer le codage de Prüfer
de learbre A3 ci-contre.

3

1

2

9

6

4

0

7

5

10

8

Learbre A3
 25 - On considère un arbre A étiqueté consécutivement. Il seagit deécrire en 
langage de
programmation une fonction qui calcule le codage de Prüfer de A. La fonction 
commencera par calculer
les tableaux peres et arites ; puis elle construira un tableau contenant les 
feuilles de learbre initial
classées par étiquettes décroissantes ; après cette partie préparatoire, la 
fonction calculera le codage de
Prüfer.
Caml : Écrire en Caml une fonction calculer_Prufer telle que, si on considère 
un arbre A étiqueté
consécutivement et si :
· racine est un entier qui contient leétiquette de la racine de A,
· fils et freres sont deux vecteurs de longueur n qui représentent 
respectivement les tableaux fils
et freres deun codage racine-fils-frères de A,
alors calculer_Prufer racine fils freres renvoie un vecteur de longueur n ­ 1
contenant le codage de Prüfer de learbre A.
Pascal : Écrire en Pascal une fonction calculer_Prufer telle que, si on 
considère un arbre A
étiqueté consécutivement et si :
· racine est un entier qui contient leétiquette de la racine de A,
· fils et freres sont de type Tableau et représentent respectivement les 
tableaux fils et freres
deun codage racine-fils-frères de A,
· n est un entier qui contient le nombre de noeuds de A,
alors calculer_Prufer(racine, fils, freres, n) renvoie un tableau, de type 
Tableau,
contenant le codage de Prüfer de learbre A entre les indices 0 et n ­ 2.
 26 - Indiquer la complexité du calcul du codage de Prüfer deun arbre A 
possédant n noeuds, étiqueté
consécutivement et codé avec le codage racine-fils-frères.
Page 7 sur 8

Épreuve deinformatique 2009

Seconde partie : d'un codage de Prüfer d'un arbre à un codage racine-fils-frères
 27 - On suppose queon connaît le codage de Prüfer deun arbre A étiqueté 
consécutivement. Il seagit
deécrire une fonction calculer_arites_par_Prufer qui calcule les arités des 
noeuds de learbre A à partir de
ce codage.
Caml : Écrire en Caml une fonction calculer_arites_par_Prufer telle que, pour 
un arbre A
possédant n noeuds et étiqueté consécutivement, si Prufer est un vecteur de 
longueur n ­ 1 contenant
le codage de Prüfer de A, alors calculer_arites_par_Prufer Prufer renvoie un 
vecteur de
longueur n contenant les arités des noeuds de A.
Avant deécrire la fonction calculer_arites_par_Prufer, on en donnera rapidement 
le
principe.
Pascal : Écrire en Pascal une fonction calculer_arites_par_Prufer telle que, 
pour un arbre A
étiqueté consécutivement, si :
· Prufer est de type Tableau et contient le codage de Prüfer de A,
· n est un entier qui contient le nombre de noeuds de A,
alors calculer_arites_par_Prufer(Prufer, n) renvoie un tableau, de type Tableau,
contenant les arités des noeuds de A.
Avant deécrire la fonction calculer_arites_par_Prufer, on en donnera rapidement 
le
principe.
 28 - Déterminer un arbre A étiqueté consécutivement dont le codage de Prüfer 
Pr(A) est :
2, 3, 0, 2, 2. On détaillera la démarche utilisée.
 29 - On considère un arbre A ; on suppose que leensemble des étiquettes E(A) 
de A est
{1, 3, 5, 6, 7, 9, 10, 12, 13} ; learbre A neest donc pas étiqueté 
consécutivement ; on suppose enfin que
le codage de Prüfer Pr(A) de A est : 3, 10, 3, 7, 7, 5, 7, 5. Déterminer 
learbre A. On décrira
succinctement la démarche utilisée.
 30 - Il seagit deécrire en langage de programmation une fonction 
calculer_arbre qui, à partir du
codage de Prüfer deun arbre A étiqueté consécutivement, calcule un codage 
racine-fils-frères de A.
Caml : Écrire en Caml une fonction calculer_arbre telle que, pour un arbre A 
possédant n noeuds
et étiqueté consécutivement, si :
· Prufer est un vecteur de longueur n ­ 1 contenant le codage de Prüfer de A,
· fils et freres sont deux vecteurs de longueur n,
alors calculer_arbre Prufer fils freres modifie les vecteurs fils et freres pour
queils correspondent respectivement aux tableaux fils et freres deun codage 
racine-fils-frères de A et
renvoie leétiquette de la racine de A.
Pascal : Écrire en Pascal une fonction calculer_arbre telle que, pour un arbre 
A possédant n
noeuds et étiqueté consécutivement, si :
· Prufer est de type Tableau et contient le codage de Prüfer de A,
· fils et freres sont de type Tableau,
· n est un entier qui contient le nombre de noeuds de A,
alors calculer_arbre(Prufer, fils, freres, n) modifie les tableaux fils et 
freres
pour queils correspondent respectivement aux tableaux fils et freres deun 
codage racine-fils-frères de A
et renvoie leétiquette de la racine de A.
Soit E un ensemble de n entiers distincts positifs ou nuls ; soit S (E) 
leensemble des suites de longueur
n ­ 1 dont tous les éléments sont dans E, distincts ou non ; soit enfin A (E) 
leensemble des arbres enracinés non
ordonnés, possédant n noeuds et étiquetés par les éléments de E.
 31 - Montrer que leapplication Pr qui, à un arbre appartenant à A(E), associe 
son codage de Prüfer
est une bijection entre A(E) et S (E).
 32 - Déterminer le cardinal de A(E).

Page 8 sur 8

Extrait du corrigé obtenu par reconnaissance optique des caractères



Mines Informatique MP 2009 -- Corrigé
Ce corrigé est proposé par Olivier Levillain (École Polytechnique) ; il a été 
relu
par Vincent Danjean (Enseignant-chercheur en école d'ingénieur) et Guillaume 
Batog
(ENS Cachan).

Ce sujet est composé de deux problèmes indépendants, de longueurs comparables.
· Le premier traite de langages et d'automates ; il a pour thème une 
transformation  sur les mots définis sur l'alphabet  = {a, b}. Par extension on 
s'intéresse
à (L) = {(u) | u  L}, l'application de cette transformation à un langage.
Le problème commence par six questions relativement indépendantes sur 
l'application de  à certains langages, et sur la construction d'automates 
reconnaissant ces langages. Puis les questions 7 à 15 amènent à montrer que  
transforme
un langage rationnel en un autre langage rationnel. Plusieurs de ces questions 
se
basent sur la construction d'automates finis, qui permettent de montrer qu'un
langage est rationnel. La dernière question concerne l'écriture de la fonction 
dans un langage de programmation (Pascal ou Caml).
· Le second problème, intitulé « algorithmique », aborde deux représentations
différentes des arbres enracinés, non ordonnés et étiquetés : le codage « 
racinefils-frères » et le codage de Prüfer. Ce problème est également composé de
16 questions distribuées en deux parties ; les questions 17 à 26 concernent le
passage d'une représentation « racine-fils-frères » à une représentation de 
Prüfer, et les questions 27 à 30 traitent du problème inverse.
Le premier problème est le plus difficile bien que les constructions demandées 
restent proches du cours, par exemple pour démontrer que la réunion de deux 
langages
rationnels est un langage rationnel. Le second comporte plusieurs questions de 
programmation, souvent accompagnées de questions sur la complexité des 
algorithmes
écrits. L'ensemble permet d'aborder une grande partie du programme 
d'informatique
de prépa, ce qui fait de ce sujet une bonne planche de révision et 
d'entraînement.

Les conseils du jury
Le problème sur les automates demande de rédiger des démonstrations
par doubles inclusions ou doubles implications. Les deux sens doivent être
justifiés pleinement : le rapport du jury regrette « une ébauche de 
démonstration pour un autre sens [...] laissant au correcteur le soin de 
conclure » ou des
tournures telles que c'est évident, c'est trivial, il est clair que... 
N'espérez pas
« grapiller des points alors que [le jury] demande une justification bien 
réelle. »
En programmation, le rapport du jury rappelle que la mauvaise indentation d'un 
programme rend sa lecture difficile (donc le risque est de perdre
bêtement des points si le correcteur ne comprend pas dans les dix secondes où
il lit le programme !) Il indique également que le choix d'une programmation
itérative ou récursive n'est qu'une question de « préférence » personnelle,
le tout étant, pour le problème sur les arbres, « de bien visualiser les 
déplacements effectués dans [un] arbre puis de les programmer à l'aide de la
structure imposée. »

Indications
Premier problème
1 Considérer séparément les différents cas selon la parité de |u|.
5 Penser à décomposer L2 en éléments simples. On étudiera ensuite l'image
par  de ces éléments.
7 Écrire P(L) et I(L) chacun comme l'intersection de deux langages rationnels.
8 Si A possède une telle transition, il est possible d'exhiber deux mots 
acceptés
par l'automate de parité différente, passant tous deux par q.
9 La technique à employer pour cette question est très proche de celle 
permettant de résoudre la question précédente.
11 Pour réussir cette question, il faut utiliser les questions 8, 9 et 10, en 
s'intéressant particulièrement aux états dont la « distance » à q0 est impaire.
On pourra alors créer un automate équivalent à l'automate reconnaissant le
langage P(L) en appliquant la transformation S(·, q) pour ces états, puis le
modifier pour reconnaître (P(L)).
12 Il suffit de modifier l'ensemble des états finals de l'automate 
reconnaissant L
pour obtenir un nouvel automate répondant à la question.
14 Les réponses aux questions 7, 11, 12 et 13 sont nécessaires à la résolution 
de
cette question.
15 Que fait    ?
Second problème
18 Le tableau peres se calcule par un parcours en profondeur de l'arbre.
22 L'insertion d'un élément dans un tel tableau trié par ordre décroissant est
plus simple à réaliser en partant de la fin du tableau : tant que l'on a pas
trouvé l'emplacement où insérer l'élément, on décale les cases vers la droite.
25 Pour écrire le début de la fonction calculer_Prufer, l'énoncé donne de
précieuses indications. La suite se fait en retirant de la liste des feuilles 
celle
de plus petite étiquette. À chaque étape, cette liste pourra nécessiter une
mise à jour : un père dont toutes les feuilles ont été retirées devra être 
inséré.
27 Dans le codage de Prüfer, à chaque fois qu'une feuille est retirée de 
l'arbre,
on note son père dans un tableau, donc le nombre de fils d'un noeud donné
correspond à son nombre d'apparitions dans le codage final.
28 ­ 30 Ces trois questions forment un tout concernant la transformation d'un 
codage de Prüfer en un codage racine-fils-frères : les deux premières proposent
des exemples à traduire, alors que la troisième a pour objet la définition
de l'algorithme générique. Cet algorithme utilise le tableau des arités 
précédemment calculé, et une liste des feuilles à rattacher. Cette liste pourra 
être
calculée à partir de la liste des étiquettes E(A) et du tableau des arités.
31 Pour cette question, il faut trouver une fonction qui pourrait jouer le rôle
d'inverse de Pr , une telle fonction ne devant pas se trouver bien loin. Montrer
pour cela que toute suite de S(E) est un codage de Prüfer valide.

I. Problème sur les automates
Dans tout le problème, la notation usuelle |u| désigne la longueur du mot u.
1 On cherche à caractériser l'ensemble des mots u vérifiant la propriété 
suivante :
v  

(uv) = (u)(v)

Si u est un mot de longueur paire 2k, noté u1 · · · u2k , et si l'on considère 
v un mot
quelconque de  , que l'on note v1 v2 · · · vn , alors d'après la définition,
(
u2 u1 · · · u2k u2k-1 v2 v1 · · · vn vn-1
si n est pair
(uv) =
u2 u1 · · · u2k u2k-1 v2 v1 · · · vn-1 vn-2 vn si n est impair
Dans les deux cas, (uv) = (u)(v) : si |u| est pair, la propriété est vérifiée.
À l'inverse, si u est de longueur impaire 2k + 1, considérons un mot constitué
d'une unique lettre x 6= u2k+1 (ce qui est possible car l'alphabet  contient au 
moins
deux lettres). L'application de  à u, x et ux donne alors :
(u) = u2 u1 · · · u2k u2k-1 u2k+1
(x) = x
(ux) = u2 u1 · · · u2k u2k-1 xu2k+1
L'égalité entre (ux) et (u)(x) n'est vérifiée que si u2k+1 x = xu2k+1 , ce qui 
est
faux car x 6= u2k+1 . Il existe donc un mot x tel que (ux) 6= (u)(x). Ainsi, 
aucun
mot de longueur impaire ne vérifie la propriété.
Il est nécessaire et suffisant que u soit un mot de
longueur paire pour obtenir la propriété demandée.
2 L'application de  à un mot u consiste à échanger chaque lettre d'indice pair
avec la lettre la précédant. Pour que (u) soit différent de u, il est donc 
nécessaire et
suffisant qu'il existe une lettre d'indice pair qui soit différente de la 
lettre la précédant.
(u  L1 )  (k  {1, . . . , |u|/2}

u2k-1 6= u2k )

Soyez attentifs dans la lecture de l'énoncé, surtout pour les toutes premières
questions : le rapport du jury signale que « beaucoup de candidats [...] 
traitent
ici le cas d'égalité » (u) = u au lieu de (u) 6= u, ce qui a des répercussions
dans les questions suivantes !
3 On déduit de la question précédente qu'un mot de L1 contient un nombre pair de
lettres quelconques, puis deux lettres distinctes l'une de l'autre (ab ou ba), 
et enfin
un nombre quelconque de lettres.

L1 est décrit par l'expression rationnelle (a + b) (a + b) (ab + ba) (a + b) .

Un mot de L1 est caractérisé par l'existence d'un couple de lettres différentes 
précédé d'un nombre pair de lettres. En considérant le premier couple
de lettres différentes au lieu d'un couple quelconque, on peut dire qu'un mot
de L1 commence par un nombre arbitraire de couples de lettres identiques,
suivi d'un couple de lettres différentes, terminé par des lettres arbitraires :
L1 peut aussi être décrit par l'expression rationnelle
(aa + bb) (ab + ba)(a + b)
Le jury a observé que « la notion d'expression rationnelle semble parfois mal 
perçue » : les ensembles (, {a, b},...) et leurs opérations ( c , , )
ne doivent pas figurer dans une expression rationnelle. En outre, essayer de
donner des écritures les plus simples possibles. Par exemple, pour  , le jury
préférait (a + b) à (a b ) .
4 L'automate A1 ci-dessous reconnaît le langage L1 :
4

a
2

a, b
a, b

1

b

b
5

a
3

a, b
En considérant l'expression rationnelle alternative (aa + bb) (ab + ba)(a + b)
de la remarque précédente, on obtient un automate avec 4 états seulement,
qui est de plus déterministe :
a
a
1

3
b

b
a

4

2
b

a, b

5 Afin de caractériser l'image par  du langage L2 , commençons par distinguer 
les
mots de L2 suivant la parité du nombre de lettres a ( désigne l'équivalence 
entre
expressions rationnelles) :
a b  (aa) ( + a)b
 (aa) b + (aa) ab
a b  (aa) b + (aa) a + (aa) abb

(car b   + bb )

Puisque (aa) et (aa) ab représentent des ensembles de mots de longueur paire,
le résultat de la question 1 permet d'écrire

(a b )   (aa) (b ) +  (aa) (a) +  (aa) (ab)(b )

Pour une expression rationnelle E décrivant un langage L, on utilise le 
raccourci (E) pour désigner une expression rationnelle décrivant (L).

Comme  (aa) = (aa) , (b ) = b et (ab) = ba, on en déduit que
(L2 ) est décrit par l'expression rationnelle (aa) b + (aa) a + (aa) bab .