Sujet mis à disposition des concours : ENSAE ParisTech, TELECOM SudParis (ex INT), TPE-EIVP
Les candidats sont priés de mentionner de façon apparente sur la première page de la copie :
INFORMATIQUE - MP

L'énoncé de cette épreuve comporte 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

L'épreuve comporte deux problèmes indépendants :

un problème sur les automates, pages 2 et 3 ;
un problème d'algorithmique, pages 4 à 8 .

Préliminaire pour l'ensemble de l'épreuve concernant la programmation

Il faudra écrire des fonctions ou des procédures à l'aide d'un 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 d'une fonction ou d'une procédure à écrire sont supposés vérifier certaines hypothèses, il ne sera pas utile dans l'é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

) et du point de vue informatique pour l'autre (en romain; par exemple a).

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 d'éléments appelés lettres. Un mot sur

est une suite finie de lettres de

; la longueur d'un mot est le nombre de lettres le composant; le mot de longueur nulle est noté

. On désigne par

l'ensemble des mots sur

, y compris le mot

. Un langage sur

est une partie de

Un automate fini

est décrit par une structure

, où :

est un alphabet ;
est un ensemble fini et non vide appelé ensemble des états de ;
est appelé l'ensemble des transitions; étant donnée une transition , on dit qu'elle est d'origine , d'extrémité et qu'elle est d'étiquette ; on pourra la noter ;
est appelé ensemble des états initiaux de ;
est appelé ensemble des états finals de .

Dans ce problème, on considérera uniquement des automates ayant un seul état initial, noté

.
Un chemin de

est une suite de transitions de la forme

. On dit alors que ce chemin va de

. Dans un automate fini, un état

est dit utile s'il existe à la fois un chemin de l'état initial

et un chemin de

à un état final.

On rappelle le théorème de Kleene: un langage sur un alphabet

est rationnel si et seulement s'il existe un automate fini d'alphabet

qui le reconnaît.

On ne considère dans tout ce problème que l'alphabet

. Tous les mots et langages considérés seront définis sur cet alphabet.

On définit une application

dans

de la façon suivante :

;
si un mot de longueur s'écrit où, pour appartient à , alors ;
si un mot de longueur s'écrit où, pour , appartient à , alors .
La fonction agit donc en échangeant chaque lettre d'indice pair avec la lettre (d'indice impair) qui la précède immédiatement. Ainsi, .
-Soit un mot dans . Établir une condition nécessaire et suffisante pour que, quel que soit le mot dans , l'égalité soit vérifiée.

On note

l'ensemble des mots

tels que

-Caractériser les mots de

-Proposer, preuve à l'appui, une expression rationnelle décrivant

; on privilégiera une expression rationnelle simple.

-Dessiner un automate fini reconnaissant

; on privilégiera un automate ayant peu d'états.
On note

le langage décrit par l'expression rationnelle

-Proposer une expression rationnelle décrivant

). Justifier brièvement la réponse.

-Dessiner un automate fini reconnaissant

. Justifier brièvement la réponse.

On se propose de montrer que si

est un langage rationnel, alors

est aussi un langage rationnel. Les questions

permettent d'obtenir ce résultat.

est un langage, on note

l'ensemble des mots de

de longueur paire et

l'ensemble des mots de

de longueur impaire.
7 -Montrer que si

est rationnel,

sont rationnels.
8 -On considère un automate fini

reconnaissant un langage

ne contenant que des mots de longueur paire ; soit

un état utile de

. Montrer que

ne possède pas de transition dont l'origine et l'extrémité soient

.
9 - On considère un automate fini

reconnaissant un langage

ne contenant que des mots de longueur paire; soit

un état utile de

. Montrer que les chemins de

sont soit tous de longueur paire, soit tous de longueur impaire.

Soit

un automate fini. Soit

un état de

. On suppose que :

est un état utile ;
n'est ni l'état initial, ni un état final ;
il n'existe dans aucune transition dont l'origine et l'extrémité soient simultanément , c'est-à-dire aucune transition qui s'écrive quelle que soit l'étiquette considérée ;
il existe au moins deux transitions d'origine ou au moins deux transitions d'extrémité .

On considère l'automate obtenu à partir de

de la façon suivante : pour chaque quadruplet

, où

sont deux états de

deux lettres de

distinctes ou non, et tel que

contienne les transitions

, on ajoute un nouvel état

et les transitions

; on ajoute donc autant d'états que de tels quadruplets ; chaque état ajouté est extrémité d'une unique transition et origine d'une unique transition. Enfin, on supprime l'état

et toutes les transitions d'origine ou d'extrémité

. On note

l'automate ainsi obtenu.
10 -Soit

un état vérifiant les hypothèses ci-dessus. Montrer que les automates

reconnaissent le même langage.
11 -Montrer que, si

est un langage rationnel, alors

est aussi un langage rationnel.
Soit

un langage rationnel. Soit

une lettre de

. On note

le langage défini comme suit : pour tout mot

sur l'alphabet

, le mot

appartient à

si et seulement si le mot

est dans

.
12 -Montrer que si

est un langage rationnel et

appartient à

, le langage

est rationnel.
13 -Soit

un langage. Donner une relation entre

.
14 -Soit

un langage rationnel. Montrer que

est aussi un langage rationnel.
15 -Soit

un langage non rationnel. Indiquer si

peut être un langage rationnel.
16 -Il s'agit d'écrire la fonction

en langage de programmation.
Caml :
On utilise le type suivant pour représenter les lettres de l'alphabet

:
type lettre = a | b ;;
Un mot est codé par une liste de type lettre list ; par exemple, le mot

est codé par la liste [

]. La liste vide [] code le mot de longueur nulle

.
Écrire en Caml une fonction phi telle que, si un mot

sur l'alphabet

est codé par une liste u de type lettre list, alors phi u renvoie une liste de type lettre list codant

).
Attention : l'emploi 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

sur l'alphabet

de longueur

inférieure ou égale à

, alors phi

renvoie un tableau de type Mot codant

Problème 2. Algorithmique

L'objectif de ce problème est de compter le nombre d'arbres enracinés, non ordonnés et étiquetés de nombre de nœuds donné. Pour cela, on étudie un codage particulier de ces arbres appelé codage de Prüfer.

Un arbre possède un nombre fini d'éléments appelés nœuds. Les arbres considérés dans ce problème possèdent tous au moins un nœud. Un arbre enraciné non ordonné

est défini récursivement de la façon suivante : il est constitué d'un nœud particulier appelé racine de

et d'un ensemble fini non ordonné, éventuellement vide, d'arbres enracinés non ordonnés appelés sous-arbres de

. Les racines des sous-arbres de

sont les fils de la racine de

et la racine de

est le père de ces derniers. Dans un arbre, deux nœuds sont dits frères s'ils ont même père. L'arité d'un nœud est son nombre de fils; dans ce problème, l'arité d'un nœud peut être quelconque. Les nœuds d'arité 0 sont les feuilles de l'arbre.

Un arbre est dit étiqueté si à chaque nœud est associé un entier positif ou nul, ces entiers étant deux à deux distincts; l'entier associé à un nœud est l'étiquette du nœud. On pourra nommer un nœud par son étiquette; si

est un entier, on pourra donc parler du nœud

pour le nœud d'étiquette

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 d'un même arbre nommé

. L'étiquette de la racine de

est

'ensemble des étiquettes des fils de la racine est

'ensemble des étiquettes des fils du nœud d'étiquette 6 est

; le nœud d'étiquette 3 possède un seul fils: le nœud d'étiquette 0 ; les nœuds d'étiquettes

n'ont pas de fils. Les représentations graphiques d'un arbre donné diffèrent par l'ordre dans lequel on dessine les fils d'un même nœud.

L'arbre

, première représentation

L'arbre

représenté ci-contre est différent de l'arbre

L'arbre

, seconde représentation

On dira qu'un arbre est un arbre étiqueté consécutivement s'il s'agit d'un arbre étiqueté et que l'ensemble de ses étiquettes forme un intervalle d'entiers de plus petite valeur 0 ; autrement dit, pour un arbre ayant

nœuds et étiqueté consécutivement, l'ensemble des étiquettes est

. Les arbres

sont des arbres étiquetés consécutivement.

Première partie : d'un codage racine-fils-frères d'un arbre au codage de Prüfer

-Donner la liste des arbres possédant trois nœuds et étiquetés consécutivement.
Soit

un arbre étiqueté consécutivement ayant

nœuds. Pour coder

, on définit un codage nommé codage racine-fils-frères. Pour cela, on fixe une représentation graphique de

; on

à l'aide de :

l'étiquette de la racine (qui ne dépend pas de la représentation);
un tableau nommé fils; pour compris entre 0 et , la case d'indice du tableau fils contient la valeur -1 si le nœud est une feuille de l'arbre et, sinon, l'étiquette du fils du nœud se situant le plus à gauche dans la représentation graphique choisie ;
un tableau nommé freres; pour compris entre 0 et , la case d'indice du tableau freres contient la valeur -1 si le nœud n'a aucun frère sur sa droite et, sinon, l'étiquette de son frère qui se trouve le premier sur sa droite.

Pour l'arbre

, si on choisit la première représentation, on obtient le codage suivant :

la racine est le nœud 4 ;
pour le tableau fils: les cases d'indices et 5 contiennent la valeur -1 , la case d'indice 3 contient 0 , la case d'indice 4 contient 1 , la case d'indice 6 contient 2 ;
pour le tableau freres: les cases d'indices et 5 contiennent la valeur -1 , la case d'indice 1 contient 6 , la case d'indice 2 contient 5 , la case d'indice 6 contient 3 .

Ainsi, l'arbre

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	0	1	2	3	4	5	6
freres	-1	6	5	-1	-1	-1	3

On définit aussi deux tableaux qui peuvent être calculés à partir du codage racine-fils-frères :

un tableau nommé peres ; pour compris entre 0 et , la case d'indice contient la valeur -1 s'il s'agit de la racine de l'arbre et, dans les autres cas, l'étiquette du père du nœud ; pour l'arbre , la case d'indice 4 contient la valeur -1 , la case d'indice 0 contient 3 , les cases d'indices 1,3 et 6 contiennent 4 , les cases d'indices 2 et 5 contiennent la valeur 6 ;
un tableau nommé arites ; pour compris entre 0 et , la case d'indice de ce tableau contient l'arité du nœud ; pour l'arbre , les cases d'indices et 5 contiennent la valeur 0 , la case d'indice 3 contient 1 , la case d'indice 4 contient 3 , la case d'indice 6 contient 2 .
Pour l'arbre , 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	0	1	2	3	4	5	6
arites	0	0	0	1	3	0	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 nœuds des arbres considérés.

Fin des indications pour la programmation en Pascal

-Il s'agit d'écrire en langage de programmation une fonction nommée calculer_peres qui, à partir du codage racine-fils-frères d'un 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

possédant

nœuds et étiqueté consécutivement et si :

racine est un entier qui contient l'étiquette de la racine de ,
fils et freres sont deux vecteurs de longueur qui représentent respectivement les tableaux fils et freres d'un codage racine-fils-frères de ,
alors calculer_peres racine fils freres renvoie un vecteur de longueur correspondant au tableau peres défini plus haut.

Pascal : Écrire en Pascal une fonction calculer_peres telle que, si on considère un arbre

étiqueté consécutivement et si :

racine est un entier qui contient l'étiquette de la racine de ,
fils et freres sont de type Tableau et représentent respectivement les tableaux fils et freres d'un codage racine-fils-frères de ,
n est un entier qui contient le nombre de nœuds de , alors calculer_peres(racine, fils, freres, n) renvoie un tableau de type Tableau contenant, entre les indices 0 et , le tableau peres défini plus haut.
-Indiquer, en fonction du nombre de nœuds de l'arbre considéré, la complexité de la fonction calculer_peres.
-Il s'agit d'écrire en langage de programmation une fonction nommée calculer_arites qui, à partir du codage racine-fils-frères d'un arbre étiqueté consécutivement, renvoie le tableau arites correspondant à cet arbre.
Caml : Écrire en Caml une fonction calculer_arites telle que, pour un arbre possédant nœuds et étiqueté consécutivement, si fils et freres sont deux vecteurs de longueur qui représentent respectivement les tableaux fils et freres d'un codage racine-fils-frères de , 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

étiqueté consécutivement, si :

fils et freres sont de type Tableau et représentent respectivement les tableaux fils et freres d'un codage racine-fils-frères de ,
n est un entier qui contient le nombre de nœuds de ,
alors calculer_arites(fils, freres, n) renvoie un tableau de type Tableau contenant entre les indices 0 et les arités des nœuds de l'arbre.
-Indiquer, en fonction du nombre de nœuds de l'arbre considéré, la complexité de la fonction calculer_arites.
-Il s'agit d'écrire en langage de programmation une fonction inserer qui prend en arguments un tableau table d'entiers non nécessairement distincts triés par valeurs décroissantes et un entier ; cette fonction modifie le tableau table pour insérer l'entier en respectant l'ordre décroissant. L'entier est inséré même s'il figure déjà dans table.
Caml : Écrire en Caml une fonction inserer telle que, si :
table est un vecteur d'entiers,
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 d'indices compris entre 0 et , 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 l'ordre décroissant. La fonction renvoie , c'est-à-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 des entiers classés par valeurs décroissantes, les autres cases du tableau table étant ignorées,
alors inserer(table, nb, d) insère la donnée d dans le tableau table en respectant l'ordre décroissant. La fonction renvoie , c'est-à-dire le nouveau nombre de données figurant dans table.

23 -Indiquer, en fonction du nombre

d'entiers contenus dans un tableau trié table, la complexité de la fonction inserer quand elle insère un nouvel entier dans table.

Soit

un arbre possédant

nœuds; on note

l'ensemble des étiquettes de

; les étiquettes de

étant toutes distinctes, l'ensemble

possède

éléments. Le codage de Prüfer d'un arbre étiqueté ayant

nœuds est une suite de

entiers appartenant à

, suite notée

; ce codage est défini récursivement de la façon suivante. Si

est réduit à un nœud, sa racine, son codage de Prüfer est la suite vide. Sinon, soit

la feuille de

d'étiquette minimum et soit

le père de

; on note

l'arbre obtenu en enlevant de

la feuille

; par définition, le codage de Prüfer de

est la suite dont le premier élément est l'étiquette de

, ce premier élément étant suivi du codage de Prüfer de

Ainsi, le codage de Prüfer de l'arbre

est :

; le codage de Prüfer de l'arbre

est:

24 -Indiquer le codage de Prüfer de l'arbre

ci-contre.

25 -On considère un arbre

étiqueté consécutivement. Il s'agit d'écrire en langage de programmation une fonction qui calcule le codage de Prüfer de

. La fonction commencera par calculer les tableaux peres et arites; puis elle construira un tableau contenant les feuilles de l'arbre 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

étiqueté consécutivement et si :

racine est un entier qui contient l'étiquette de la racine de ,
fils et freres sont deux vecteurs de longueur qui représentent respectivement les tableaux fils et freres d'un codage racine-fils-frères de ,
alors calculer_Prufer racine fils freres renvoie un vecteur de longueur contenant le codage de Prüfer de l'arbre .

Pascal : Écrire en Pascal une fonction calculer_Prufer telle que, si on considère un arbre

étiqueté consécutivement et si :

racine est un entier qui contient l'étiquette de la racine de ,
fils et freres sont de type Tableau et représentent respectivement les tableaux fils et freres d'un codage racine-fils-frères de ,
n est un entier qui contient le nombre de nœuds de ,
alors calculer_Prufer(racine, fils, freres, n) renvoie un tableau, de type Tableau, contenant le codage de Prüfer de l'arbre entre les indices 0 et .
26 -Indiquer la complexité du calcul du codage de Prüfer d'un arbre possédant nœuds, étiqueté consécutivement et codé avec le codage racine-fils-frères.

Seconde partie : d'un codage de Prüfer d'un arbre à un codage racine-fils-frères

27 - On suppose qu'on connaît le codage de Prüfer d'un arbre

étiqueté consécutivement. Il s'agit d'écrire une fonction calculer_arites_par_Prufer qui calcule les arités des nœuds de l'arbre

à partir de ce codage.
Caml : Écrire en Caml une fonction calculer_arites_par_Prufer telle que, pour un arbre

possédant

nœuds et étiqueté consécutivement, si Prufer est un vecteur de longueur

contenant le codage de Prüfer de

, alors calculer_arites_par_Prufer Prufer renvoie un vecteur de longueur

contenant les arités des nœuds de

.
Avant d'é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

étiqueté consécutivement, si :

Prufer est de type Tableau et contient le codage de Prüfer de ,
n est un entier qui contient le nombre de nœuds de ,
alors calculer_arites_par_Prufer(Prufer, n) renvoie un tableau, de type Tableau, contenant les arités des nœuds de .
Avant d'écrire la fonction calculer_arites_par_Prufer, on en donnera rapidement le principe.
-Déterminer un arbre étiqueté consécutivement dont le codage de est: . On détaillera la démarche utilisée.
- On considère un arbre ; on suppose que l'ensemble des étiquettes de est l'arbre n'est donc pas étiqueté consécutivement ; on suppose enfin que le codage de Prüfer de est: 3, 10, 3, 7, 7, 5, 7, 5. Déterminer l'arbre . On décrira succinctement la démarche utilisée.
-Il s'agit d'écrire en langage de programmation une fonction calculer_arbre qui, à partir du codage de Prüfer d'un arbre étiqueté consécutivement, calcule un codage racine-fils-frères de .
Caml : Écrire en Caml une fonction calculer_arbre telle que, pour un arbre possédant nœuds et étiqueté consécutivement, si :
Prufer est un vecteur de longueur contenant le codage de Prüfer de ,
fils et freres sont deux vecteurs de longueur , alors calculer_arbre Prufer fils freres modifie les vecteurs fils et freres pour qu'ils correspondent respectivement aux tableaux fils et freres d'un codage racine-fils-frères de et renvoie l'étiquette de la racine de .

Pascal : Écrire en Pascal une fonction calculer_arbre telle que, pour un arbre

possédant

nœuds et étiqueté consécutivement, si :

Prufer est de type Tableau et contient le codage de Prüfer de ,
fils et freres sont de type Tableau,
n est un entier qui contient le nombre de nœuds de , alors calculer_arbre(Prufer, fils, freres, n) modifie les tableaux fils et freres pour qu'ils correspondent respectivement aux tableaux fils et freres d'un codage racine-fils-frères de et renvoie l'étiquette de la racine de .

Soit

un ensemble de

entiers distincts positifs ou nuls ; soit

l'ensemble des suites de longueur

dont tous les éléments sont dans

, distincts ou non ; soit enfin

l'ensemble des arbres enracinés non ordonnés, possédant

nœuds et étiquetés par les éléments de

-Montrer que l'application

qui, à un arbre appartenant à

, associe son codage de Prüfer est une bijection entre

-Déterminer le cardinal de