Mines Informatique MP 2009

É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