Centrale Informatique MP 2009

Thème de l'épreuve La chasse aux fantômes, Automates finis
Principaux outils utilisés automates, combinatoire, complexité

Corrigé

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

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                 

Énoncé obtenu par reconnaissance optique des caractères


- version du 12 mars 2009 10h19

INFORMATIQUE

Cette notation exprime bien le lien entre les points Pi et Pj lorsque j = c[i].

Filière

MP

P5

P6

P4

c1
c2

1
2
2

P7

P3

2
1
1

P2

3
6
7

P8

1

P

4
5
5

5
4
4

P5

P6

6
3
8
P4

7
8
3

P7

P3

8
7
6

P8

P2

1

P

I.B - Soit i, j, k, l quatre entiers distincts tels que : 1 6 i < j 6 2n et 1 6 
k < l 6 2n.
I.B.1) Donner une condition nécessaire et suffisante, portant uniquement sur ces
entiers, pour que les segments [Pi Pj ] et [Pk Pl ] se croisent.

I.A.1) Dans le cas n = 3, donner le nombre de stratégies possibles, admissibles 
ou
non.
I.A.2) Préciser le nombre de stratégies de taille 3 qui sont admissibles. Les 
représenter sur une figure.
I.A.3) Déterminer le nombre de stratégies de taille n entier positif (qu'elles 
soient
ou non admissibles).

La figure de gauche correspond
à c1 qui est donc admissible, et
celle de droite à c2 qui, elle, ne
l'est pas.

Par exemple, pour les stratégies
de taille 4, c1 et c2 ci-contre :

En Pascal, on représente le vecteur par un tableau avec un type tr défini par :
st     {de taille suffisante pour tout le problème}
 tr  rr   tr 
En Caml, on représente le vecteur avec le type « tr » de Caml. On peut utiliser
la fonction t. Les éléments des vecteurs en Caml sont numérotés de 0 à
N - 1. On prendra des vecteurs de taille 2n + 1, dont le premier élément ne 
sera pas
utilisé, pour que les points soient bien aux indices 1 à 2n dans le vecteur 
Caml.
On considère des stratégies où les points d'une paire sont reliés par des 
segments
de droites situés dans un même plan. Une stratégie est dite « admissible » si 
les
segments ainsi formés ne se coupent pas. On admet que cette propriété ne dépend
pas de la position des points sur la circonférence mais seulement de la 
stratégie.

Page 1/3

Dans toute la suite on fixe un entier n > 0 et on appelle stratégie de taille n 
un
vecteur c[1], c[2], . . . , c[2n] , tel que pour tout entier i vérifiant 1 6 i 
6 2n on ait :
 
1 6 c[i] 6 2n,
c c[i] = i,
c[i] 6= i.

i) chaque point est une extrémité d'une et une seule corde,
ii) les différentes cordes ne doivent pas se couper.

I.A - Les 2n protagonistes sont représentés par des points distincts P1 , P2 , 
..., P2n
répartis dans l'ordre des indices croissants sur la circonférence d'un cercle 
parcouru
dans le sens trigonométrique ; n sont des chasseurs, n des fantômes, mais, dans
cette section I.A, on cherche les liens possibles entre les Pi sans s'occuper 
de qui
est chasseur et qui est fantôme. Les points doivent être reliés deux à deux par 
une
corde du cercle selon une stratégie gagnante pour les chasseurs. Pour cela, il 
faut
donc respecter les deux conditions :

Un groupe de n chasseurs de fantômes combat un groupe de n fantômes. Chaque
chasseur est armé d'un canon à ions, capable d'éradiquer un fantôme d'un coup de
rayon. Un rayon se propage en ligne droite et termine sa course en touchant le 
fantôme. Les chasseurs sont confrontés à deux problèmes : il est nécessaire 
d'éliminer
tous les fantômes en même temps, sinon ils se multiplient pour revenir au nombre
initial de n fantômes ; il est très dangereux que deux rayons se croisent, cela 
ne doit
donc pas se produire. Le combat se déroule dans une grotte cylindrique creuse,
dont la base est un disque. Les déplacements (chasseurs et fantômes) ne sont 
possibles que sur un rebord confondu avec la circonférence, mais les tirs se 
font entre
deux points de la circonférence, selon des cordes du cercle.

Les candidats devront indiquer clairement en tête de copie le langage
de programmation choisi (Pascal ou Caml). Les fonctions et procédures demandées 
seront rédigées dans ce langage.

Partie I - La chasse aux fantômes

Note : les parties I, II.A, II.B et II.C sont indépendantes.

trs trsés

Épreuve :

Concours Centrale - Supélec 2009

- version du 12 mars 2009 10h19

INFORMATIQUE

Cette notation exprime bien le lien entre les points Pi et Pj lorsque j = c[i].

Filière

MP

P5

P6

P4

c1
c2

1
2
2

P7

P3

2
1
1

P2

3
6
7

P8

1

P

4
5
5

5
4
4

P5

P6

6
3
8
P4

7
8
3

P7

P3

8
7
6

P8

P2

1

P

I.B - Soit i, j, k, l quatre entiers distincts tels que : 1 6 i < j 6 2n et 1 6 
k < l 6 2n.
I.B.1) Donner une condition nécessaire et suffisante, portant uniquement sur ces
entiers, pour que les segments [Pi Pj ] et [Pk Pl ] se croisent.

I.A.1) Dans le cas n = 3, donner le nombre de stratégies possibles, admissibles 
ou
non.
I.A.2) Préciser le nombre de stratégies de taille 3 qui sont admissibles. Les 
représenter sur une figure.
I.A.3) Déterminer le nombre de stratégies de taille n entier positif (qu'elles 
soient
ou non admissibles).

La figure de gauche correspond
à c1 qui est donc admissible, et
celle de droite à c2 qui, elle, ne
l'est pas.

Par exemple, pour les stratégies
de taille 4, c1 et c2 ci-contre :

En Pascal, on représente le vecteur par un tableau avec un type tr défini par :
st     {de taille suffisante pour tout le problème}
 tr  rr   tr 
En Caml, on représente le vecteur avec le type « tr » de Caml. On peut utiliser
la fonction t. Les éléments des vecteurs en Caml sont numérotés de 0 à
N - 1. On prendra des vecteurs de taille 2n + 1, dont le premier élément ne 
sera pas
utilisé, pour que les points soient bien aux indices 1 à 2n dans le vecteur 
Caml.
On considère des stratégies où les points d'une paire sont reliés par des 
segments
de droites situés dans un même plan. Une stratégie est dite « admissible » si 
les
segments ainsi formés ne se coupent pas. On admet que cette propriété ne dépend
pas de la position des points sur la circonférence mais seulement de la 
stratégie.

Page 1/3

Dans toute la suite on fixe un entier n > 0 et on appelle stratégie de taille n 
un
vecteur c[1], c[2], . . . , c[2n] , tel que pour tout entier i vérifiant 1 6 i 
6 2n on ait :
 
1 6 c[i] 6 2n,
c c[i] = i,
c[i] 6= i.

i) chaque point est une extrémité d'une et une seule corde,
ii) les différentes cordes ne doivent pas se couper.

I.A - Les 2n protagonistes sont représentés par des points distincts P1 , P2 , 
..., P2n
répartis dans l'ordre des indices croissants sur la circonférence d'un cercle 
parcouru
dans le sens trigonométrique ; n sont des chasseurs, n des fantômes, mais, dans
cette section I.A, on cherche les liens possibles entre les Pi sans s'occuper 
de qui
est chasseur et qui est fantôme. Les points doivent être reliés deux à deux par 
une
corde du cercle selon une stratégie gagnante pour les chasseurs. Pour cela, il 
faut
donc respecter les deux conditions :

Un groupe de n chasseurs de fantômes combat un groupe de n fantômes. Chaque
chasseur est armé d'un canon à ions, capable d'éradiquer un fantôme d'un coup de
rayon. Un rayon se propage en ligne droite et termine sa course en touchant le 
fantôme. Les chasseurs sont confrontés à deux problèmes : il est nécessaire 
d'éliminer
tous les fantômes en même temps, sinon ils se multiplient pour revenir au nombre
initial de n fantômes ; il est très dangereux que deux rayons se croisent, cela 
ne doit
donc pas se produire. Le combat se déroule dans une grotte cylindrique creuse,
dont la base est un disque. Les déplacements (chasseurs et fantômes) ne sont 
possibles que sur un rebord confondu avec la circonférence, mais les tirs se 
font entre
deux points de la circonférence, selon des cordes du cercle.

Les candidats devront indiquer clairement en tête de copie le langage
de programmation choisi (Pascal ou Caml). Les fonctions et procédures demandées 
seront rédigées dans ce langage.

Partie I - La chasse aux fantômes

Note : les parties I, II.A, II.B et II.C sont indépendantes.

trs trsés

Épreuve :

Concours Centrale - Supélec 2009

- version du 12 mars 2009 10h19

INFORMATIQUE

Cette notation exprime bien le lien entre les points Pi et Pj lorsque j = c[i].

Filière

MP

P5

P6

P4

c1
c2

1
2
2

P7

P3

2
1
1

P2

3
6
7

P8

1

P

4
5
5

5
4
4

P5

P6

6
3
8
P4

7
8
3

P7

P3

8
7
6

P8

P2

1

P

I.B - Soit i, j, k, l quatre entiers distincts tels que : 1 6 i < j 6 2n et 1 6 
k < l 6 2n.
I.B.1) Donner une condition nécessaire et suffisante, portant uniquement sur ces
entiers, pour que les segments [Pi Pj ] et [Pk Pl ] se croisent.

I.A.1) Dans le cas n = 3, donner le nombre de stratégies possibles, admissibles 
ou
non.
I.A.2) Préciser le nombre de stratégies de taille 3 qui sont admissibles. Les 
représenter sur une figure.
I.A.3) Déterminer le nombre de stratégies de taille n entier positif (qu'elles 
soient
ou non admissibles).

La figure de gauche correspond
à c1 qui est donc admissible, et
celle de droite à c2 qui, elle, ne
l'est pas.

Par exemple, pour les stratégies
de taille 4, c1 et c2 ci-contre :

En Pascal, on représente le vecteur par un tableau avec un type tr défini par :
st     {de taille suffisante pour tout le problème}
 tr  rr   tr 
En Caml, on représente le vecteur avec le type « tr » de Caml. On peut utiliser
la fonction t. Les éléments des vecteurs en Caml sont numérotés de 0 à
N - 1. On prendra des vecteurs de taille 2n + 1, dont le premier élément ne 
sera pas
utilisé, pour que les points soient bien aux indices 1 à 2n dans le vecteur 
Caml.
On considère des stratégies où les points d'une paire sont reliés par des 
segments
de droites situés dans un même plan. Une stratégie est dite « admissible » si 
les
segments ainsi formés ne se coupent pas. On admet que cette propriété ne dépend
pas de la position des points sur la circonférence mais seulement de la 
stratégie.

Page 1/3

Dans toute la suite on fixe un entier n > 0 et on appelle stratégie de taille n 
un
vecteur c[1], c[2], . . . , c[2n] , tel que pour tout entier i vérifiant 1 6 i 
6 2n on ait :
 
1 6 c[i] 6 2n,
c c[i] = i,
c[i] 6= i.

i) chaque point est une extrémité d'une et une seule corde,
ii) les différentes cordes ne doivent pas se couper.

I.A - Les 2n protagonistes sont représentés par des points distincts P1 , P2 , 
..., P2n
répartis dans l'ordre des indices croissants sur la circonférence d'un cercle 
parcouru
dans le sens trigonométrique ; n sont des chasseurs, n des fantômes, mais, dans
cette section I.A, on cherche les liens possibles entre les Pi sans s'occuper 
de qui
est chasseur et qui est fantôme. Les points doivent être reliés deux à deux par 
une
corde du cercle selon une stratégie gagnante pour les chasseurs. Pour cela, il 
faut
donc respecter les deux conditions :

Un groupe de n chasseurs de fantômes combat un groupe de n fantômes. Chaque
chasseur est armé d'un canon à ions, capable d'éradiquer un fantôme d'un coup de
rayon. Un rayon se propage en ligne droite et termine sa course en touchant le 
fantôme. Les chasseurs sont confrontés à deux problèmes : il est nécessaire 
d'éliminer
tous les fantômes en même temps, sinon ils se multiplient pour revenir au nombre
initial de n fantômes ; il est très dangereux que deux rayons se croisent, cela 
ne doit
donc pas se produire. Le combat se déroule dans une grotte cylindrique creuse,
dont la base est un disque. Les déplacements (chasseurs et fantômes) ne sont 
possibles que sur un rebord confondu avec la circonférence, mais les tirs se 
font entre
deux points de la circonférence, selon des cordes du cercle.

Les candidats devront indiquer clairement en tête de copie le langage
de programmation choisi (Pascal ou Caml). Les fonctions et procédures demandées 
seront rédigées dans ce langage.

Partie I - La chasse aux fantômes

Note : les parties I, II.A, II.B et II.C sont indépendantes.

trs trsés

Épreuve :

Concours Centrale - Supélec 2009

2n

Filière MP

Un automate (fini) non déterministe est un quintuplet A = (Q, A, I, , F) avec 
cette
fois I  Q l'ensemble des états initiaux et  : Q × A  P(Q) la fonction de
transition : si p  Q et   A, (p, ) désigne l'ensemble (éventuellement vide)
des q  Q tels qu'il existe une transition étiquetée par  de p vers q. Si on 
choisit
de représenter les transitions par un ensemble inclus dans Q × A × Q, la 
condition
(D) n'a plus à être vérifiée.
Pour présenter un automate, les candidats pourront, bien entendu, les 
représenter
par un schéma. Ils veilleront alors à bien identifier l'état initial (ou les 
états initiaux)
et les états terminaux par une notation adaptée.

Lorsque  est défini sur l'ensemble Q × A tout entier, on parle d'automate fini 
complet. Que l'automate soit complet, ou non, on peut choisir de représenter 
les transitions non par une fonction de transition , mais par un ensemble de 
transitions
T  Q × A × Q (le graphe de ), avec la condition de déterminisme :
(D)
si (q, , q1 ), (q, , q2 )  T, alors q1 = q2 .

Un automate (sous entendu fini) déterministe est un quintuplet A = (Q, A, i, , 
F)
avec :
· Q l'ensemble fini non vide des états ;
· A l'alphabet c'est-à-dire l'ensemble fini non vide des lettres ;
· i  Q l'état initial ;
·  : Q × A  Q la fonction de transition (éventuellement partielle) ;
· F  Q l'ensemble des états terminaux.

Définitions et notations

On rappelle que les sections II.A, II.B, II.C sont indépendantes et peuvent 
être traitées dans un ordre quelconque.

Partie II - Automates finis

de fantômes que de chasseurs. Écrire une fonction s, qui prend en paramètre
le vecteur p (et en Pascal, le nombre n de chasseurs) et qui renvoie la liste 
des indices
(i, j) des couples (Pi , Pj ) (où Pi est un chasseur et Pj un fantôme), 
composant une
stratégie admissible du problème.

i=1

 p[i] = 0 puisqu'il y a autant

Un vecteur p contient la nature des points Pi : p[i] = 1 pour un chasseur,

p[i] = -1 pour un fantôme (1 6 i 6 2n). On a donc

I.D.4)

Page 2/3

I.D - La méthode précédente teste si une stratégie est admissible. On souhaite 
maintenant, le statut (chasseur ou fantôme) des points étant donné, déterminer 
directement une stratégie admissible, de façon également efficace.
I.D.1) Montrer que si Pi est un chasseur (1 6 i 6 2n), alors il existe j 6= i, 
avec
1 6 j 6 2n tel que Pj est un fantôme et tel que le nombre de chasseurs soit 
égal au
nombre de fantômes de chaque côté de l'axe Pi Pj .
I.D.2) En déduire un algorithme simple pour construire une stratégie admissible.
I.D.3) On se propose d'évaluer la complexité de cette méthode.
a) Déterminer la complexité dans le pire des cas.
b) Évaluer, sans démonstration, la complexité moyenne.

I.C - On souhaite tester la stratégie de façon plus efficace. Pour cela on 
utilise une
fonction «  » qui prend deux entiers i et j comme paramètres (i et j étant 
compris entre 1 et 2n) et dont le résultat est tr si et seulement si les deux 
propositions
suivantes sont vraies :
· (i 6 k 6 j)  (i 6 c[k] 6 j)
· les segments ayant leurs extrémités dans l'arc (fermé) [Pi Pj ] ne se 
croisent pas.
I.C.1) Donner la valeur de   dans les trois cas particuliers a, b et c
suivants :
c) j > i et c[i] > j.
a) j < i ;
b) j > i et c[i] < i ;
I.C.2) Pour i < c[i] < j, montrer que   se déduit de   
   et de    .
I.C.3) Écrire une fonction tsttrt qui prend en paramètre un vecteur (et
en Pascal le nombre n de chasseurs) et renvoie un booléen dont la valeur est tr
si la stratégie est admissible. Cette fonction devra être de complexité O(n).
I.C.4) Démontrer avec soin que la fonction tsttrt est bien de complexité
O(n).

I.B.2) Écrire une fonction « rs » prenant les quatre entiers pour paramètres et
renvoyant un booléen dont le résultat est tr si et seulement si les segments 
[Pi Pj ]
et [Pk Pl ] se croisent. On suppose que les paramètres donnés à la fonction 
satisfont
les conditions données en introduction du I.B.
I.B.3) En utilisant la fonction rs, écrire une fonction « stss » qui
prend en paramètre le vecteur (et en Pascal, le nombre n de chasseurs) et 
renvoie
un booléen dont le résultat est tr si la stratégie est admissible.
I.B.4) Donner, en la justifiant, la complexité de cette méthode, en terme de 
temps
de calcul (on se contentera d'une évaluation du type O(n ), en précisant la 
valeur
de ).

INFORMATIQUE

2n

Filière MP

Un automate (fini) non déterministe est un quintuplet A = (Q, A, I, , F) avec 
cette
fois I  Q l'ensemble des états initiaux et  : Q × A  P(Q) la fonction de
transition : si p  Q et   A, (p, ) désigne l'ensemble (éventuellement vide)
des q  Q tels qu'il existe une transition étiquetée par  de p vers q. Si on 
choisit
de représenter les transitions par un ensemble inclus dans Q × A × Q, la 
condition
(D) n'a plus à être vérifiée.
Pour présenter un automate, les candidats pourront, bien entendu, les 
représenter
par un schéma. Ils veilleront alors à bien identifier l'état initial (ou les 
états initiaux)
et les états terminaux par une notation adaptée.

Lorsque  est défini sur l'ensemble Q × A tout entier, on parle d'automate fini 
complet. Que l'automate soit complet, ou non, on peut choisir de représenter 
les transitions non par une fonction de transition , mais par un ensemble de 
transitions
T  Q × A × Q (le graphe de ), avec la condition de déterminisme :
(D)
si (q, , q1 ), (q, , q2 )  T, alors q1 = q2 .

Un automate (sous entendu fini) déterministe est un quintuplet A = (Q, A, i, , 
F)
avec :
· Q l'ensemble fini non vide des états ;
· A l'alphabet c'est-à-dire l'ensemble fini non vide des lettres ;
· i  Q l'état initial ;
·  : Q × A  Q la fonction de transition (éventuellement partielle) ;
· F  Q l'ensemble des états terminaux.

Définitions et notations

On rappelle que les sections II.A, II.B, II.C sont indépendantes et peuvent 
être traitées dans un ordre quelconque.

Partie II - Automates finis

de fantômes que de chasseurs. Écrire une fonction s, qui prend en paramètre
le vecteur p (et en Pascal, le nombre n de chasseurs) et qui renvoie la liste 
des indices
(i, j) des couples (Pi , Pj ) (où Pi est un chasseur et Pj un fantôme), 
composant une
stratégie admissible du problème.

i=1

 p[i] = 0 puisqu'il y a autant

Un vecteur p contient la nature des points Pi : p[i] = 1 pour un chasseur,

p[i] = -1 pour un fantôme (1 6 i 6 2n). On a donc

I.D.4)

Page 2/3

I.D - La méthode précédente teste si une stratégie est admissible. On souhaite 
maintenant, le statut (chasseur ou fantôme) des points étant donné, déterminer 
directement une stratégie admissible, de façon également efficace.
I.D.1) Montrer que si Pi est un chasseur (1 6 i 6 2n), alors il existe j 6= i, 
avec
1 6 j 6 2n tel que Pj est un fantôme et tel que le nombre de chasseurs soit 
égal au
nombre de fantômes de chaque côté de l'axe Pi Pj .
I.D.2) En déduire un algorithme simple pour construire une stratégie admissible.
I.D.3) On se propose d'évaluer la complexité de cette méthode.
a) Déterminer la complexité dans le pire des cas.
b) Évaluer, sans démonstration, la complexité moyenne.

I.C - On souhaite tester la stratégie de façon plus efficace. Pour cela on 
utilise une
fonction «  » qui prend deux entiers i et j comme paramètres (i et j étant 
compris entre 1 et 2n) et dont le résultat est tr si et seulement si les deux 
propositions
suivantes sont vraies :
· (i 6 k 6 j)  (i 6 c[k] 6 j)
· les segments ayant leurs extrémités dans l'arc (fermé) [Pi Pj ] ne se 
croisent pas.
I.C.1) Donner la valeur de   dans les trois cas particuliers a, b et c
suivants :
c) j > i et c[i] > j.
a) j < i ;
b) j > i et c[i] < i ;
I.C.2) Pour i < c[i] < j, montrer que   se déduit de   
   et de    .
I.C.3) Écrire une fonction tsttrt qui prend en paramètre un vecteur (et
en Pascal le nombre n de chasseurs) et renvoie un booléen dont la valeur est tr
si la stratégie est admissible. Cette fonction devra être de complexité O(n).
I.C.4) Démontrer avec soin que la fonction tsttrt est bien de complexité
O(n).

I.B.2) Écrire une fonction « rs » prenant les quatre entiers pour paramètres et
renvoyant un booléen dont le résultat est tr si et seulement si les segments 
[Pi Pj ]
et [Pk Pl ] se croisent. On suppose que les paramètres donnés à la fonction 
satisfont
les conditions données en introduction du I.B.
I.B.3) En utilisant la fonction rs, écrire une fonction « stss » qui
prend en paramètre le vecteur (et en Pascal, le nombre n de chasseurs) et 
renvoie
un booléen dont le résultat est tr si la stratégie est admissible.
I.B.4) Donner, en la justifiant, la complexité de cette méthode, en terme de 
temps
de calcul (on se contentera d'une évaluation du type O(n ), en précisant la 
valeur
de ).

INFORMATIQUE

bn,m

m

=1

 bi, 2-1 pour tout 1 6 i 6 n.

On appelle relation dans N n tout sous-ensemble de N n .
On dit qu'une relation R  N n est rationnelle, lorsqu'il existe un automate 
fini A qui reconnaît exactement l'ensemble des mots de (Bn )
représentant les n-uplets de R.

a) Donner une représentation des n-uplets suivants :
(4);
(2, 3, 0);
(2, 3, 5).

xi =

représente le n-uplet d'entiers naturels (x1 , · · · , xn ) tel que

bn,1

Pour les deux questions b) et c) suivantes, on demande de donner,
pour chacune des relations Eg, In f et Add, un automate fini la reconnaissant 
effectivement.

Filière MP

· · · FIN · · ·

II.C.4) Déterminiser l'automate proposé dans la question C.2), lorsque N = 1.
II.C.5) Démontrer qu'il n'existe pas d'automate déterministe complet 
reconnaissant D N et possédant strictement moins de 2 N+1 états.
II.C.6) Démontrer qu'il n'existe pas d'automate fini (non-déterministe) 
reconnaissant D N et possédant strictement moins de N + 2 états. Même question 
pour le
langage GN .

On pourra raisonner par l'absurde et prouver que les états atteints en
lisant ak depuis l'état initial sont distincts, pour certaines valeurs k.

II.C - Automate minimal
Soit A = {a, b}. Pour chaque entier N  N, on définit les langages GN et D N de 
la
manière suivante :
· GN = {uav | u  A N , v  A }.
· D N = {uav | u  A , v  A N }.
II.C.1) Donner un automate déterministe complet, à N + 3 états reconnaissant GN 
.
II.C.2) Donner un automate non-déterministe, à N + 2 états reconnaissant D N .
II.C.3) Démontrer qu'il n'existe pas d'automate déterministe complet 
reconnaissant GN et possédant strictement moins de N + 3 états.

b) Montrer que les relations :

et In f = (x, y)  N2 | x < y
Eg = (x, y)  N2 | x = y
sont rationnelles.
c) Montrer que la relation :

Add = (x, y, z)  N3 | x + y = z
est rationnelle.
d) On suppose la relation R  N n rationnelle et on définit les relations Q  N 
n-1
et S  N n-1 par :
(x1 , . . . , xn-1 )  Q si, et seulement si, il existe x  N tel que (x1 , . . . 
, xn-1 , x)  R.
(x1 , . . . , xn-1 )  S si, et seulement si, pour tout x  N, (x1 , . . . , xn-1 
, x)  R.
Montrer que les relations Q et S sont rationnelles.

Page 3/3

II.B - Logique de Presburger
Soit n un entier strictement positif et B = {0, 1}. On prend comme alphabet 
l'ensemble Bn . Un mot

b1,1
b1,m

u =  ...  · · ·  ...   (Bn )

L = {u | w  A , u 6= w2 }.
a) On suppose que A est réduit à une lettre.
Montrer alors que L est reconnaissable par automate fini et donner un automate
reconnaissant effectivement L, ainsi qu'une expression rationnelle décrivant L.
b) On suppose maintenant que A n'est pas réduit à une lettre. Montrer que L 
n'est
pas reconnaissable.
c) Soit p un entier strictement plus grand que 2. Reprendre les deux questions 
précédentes en remplaçant L par L p défini par :
L p = {u | w  A , u 6= w p }

II.A - Mots répétés
II.A.1) Soit A un alphabet. On s'intéresse au langage L  A constitué des mots
u qui ne sont de la forme w2 (c'est-à-dire ww) pour aucun w  A :

On note A l'ensemble des mots écrits dans l'alphabet A (y compris le mot vide). 
Un
langage sur l'alphabet A est un sous-ensemble de A . On note en particulier L(A 
)
le langage de A , c'est-à-dire l'ensemble des mots acceptés par A (permettant de
passer d'un état initial à un état terminal).
Étant donné un mot u  A , on note |u| la longueur de u, c'est-à-dire le nombre 
de
ses lettres.

INFORMATIQUE

bn,m

m

=1

 bi, 2-1 pour tout 1 6 i 6 n.

On appelle relation dans N n tout sous-ensemble de N n .
On dit qu'une relation R  N n est rationnelle, lorsqu'il existe un automate 
fini A qui reconnaît exactement l'ensemble des mots de (Bn )
représentant les n-uplets de R.

a) Donner une représentation des n-uplets suivants :
(4);
(2, 3, 0);
(2, 3, 5).

xi =

représente le n-uplet d'entiers naturels (x1 , · · · , xn ) tel que

bn,1

Pour les deux questions b) et c) suivantes, on demande de donner,
pour chacune des relations Eg, In f et Add, un automate fini la reconnaissant 
effectivement.

Filière MP

· · · FIN · · ·

II.C.4) Déterminiser l'automate proposé dans la question C.2), lorsque N = 1.
II.C.5) Démontrer qu'il n'existe pas d'automate déterministe complet 
reconnaissant D N et possédant strictement moins de 2 N+1 états.
II.C.6) Démontrer qu'il n'existe pas d'automate fini (non-déterministe) 
reconnaissant D N et possédant strictement moins de N + 2 états. Même question 
pour le
langage GN .

On pourra raisonner par l'absurde et prouver que les états atteints en
lisant ak depuis l'état initial sont distincts, pour certaines valeurs k.

II.C - Automate minimal
Soit A = {a, b}. Pour chaque entier N  N, on définit les langages GN et D N de 
la
manière suivante :
· GN = {uav | u  A N , v  A }.
· D N = {uav | u  A , v  A N }.
II.C.1) Donner un automate déterministe complet, à N + 3 états reconnaissant GN 
.
II.C.2) Donner un automate non-déterministe, à N + 2 états reconnaissant D N .
II.C.3) Démontrer qu'il n'existe pas d'automate déterministe complet 
reconnaissant GN et possédant strictement moins de N + 3 états.

b) Montrer que les relations :

et In f = (x, y)  N2 | x < y
Eg = (x, y)  N2 | x = y
sont rationnelles.
c) Montrer que la relation :

Add = (x, y, z)  N3 | x + y = z
est rationnelle.
d) On suppose la relation R  N n rationnelle et on définit les relations Q  N 
n-1
et S  N n-1 par :
(x1 , . . . , xn-1 )  Q si, et seulement si, il existe x  N tel que (x1 , . . . 
, xn-1 , x)  R.
(x1 , . . . , xn-1 )  S si, et seulement si, pour tout x  N, (x1 , . . . , xn-1 
, x)  R.
Montrer que les relations Q et S sont rationnelles.

Page 3/3

II.B - Logique de Presburger
Soit n un entier strictement positif et B = {0, 1}. On prend comme alphabet 
l'ensemble Bn . Un mot

b1,1
b1,m

u =  ...  · · ·  ...   (Bn )

L = {u | w  A , u 6= w2 }.
a) On suppose que A est réduit à une lettre.
Montrer alors que L est reconnaissable par automate fini et donner un automate
reconnaissant effectivement L, ainsi qu'une expression rationnelle décrivant L.
b) On suppose maintenant que A n'est pas réduit à une lettre. Montrer que L 
n'est
pas reconnaissable.
c) Soit p un entier strictement plus grand que 2. Reprendre les deux questions 
précédentes en remplaçant L par L p défini par :
L p = {u | w  A , u 6= w p }

II.A - Mots répétés
II.A.1) Soit A un alphabet. On s'intéresse au langage L  A constitué des mots
u qui ne sont de la forme w2 (c'est-à-dire ww) pour aucun w  A :

On note A l'ensemble des mots écrits dans l'alphabet A (y compris le mot vide). 
Un
langage sur l'alphabet A est un sous-ensemble de A . On note en particulier L(A 
)
le langage de A , c'est-à-dire l'ensemble des mots acceptés par A (permettant de
passer d'un état initial à un état terminal).
Étant donné un mot u  A , on note |u| la longueur de u, c'est-à-dire le nombre 
de
ses lettres.

INFORMATIQUE

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



Centrale Informatique MP 2009 -- Corrigé
Ce corrigé est proposé par Antoine Taveneaux (ENS Lyon) et Vincent Puyhaubert
(Professeur en CPGE) ; il a été relu par Olivier Levillain (École 
Polytechnique) et
Vincent Danjean (Enseignant-chercheur en école d'ingénieur).

Le sujet de Centrale de cette année comporte, comme souvent, deux problèmes
touchant à des parties bien distinctes du programme d'informatique de MP.
· Le premier est un problème d'algorithmique classique qui se place dans un
contexte assez général de « matching », c'est-à-dire d'appariement. Il s'agit
de réaliser des couplages entre des éléments d'un ensemble tout en respectant
certaines contraintes, comme on chercherait à le faire sur un site de rencontres
par exemple. Dans le cadre de cet énoncé, les éléments à coupler sont des points
d'un cercle ; la contrainte est que les cordes ne doivent pas se chevaucher.
Les questions sont très classiques : un peu de combinatoire pour s'échauffer,
écriture de méthodes naïves puis écriture et preuve de codes plus efficaces.
On répond finalement à deux questions : comment tester si un couplage est
correct, et comment obtenir un tel couplage de manière automatique ?
· Le second problème est un sujet un peu fourre-tout sur les automates 
(reconnaissance, automate minimal, déterminisation). Il est composé de trois 
exercices
complètement indépendants les uns des autres. Le deuxième est le plus délicat,
en grande partie à cause de notations compliquées. On avait intérêt le jour du
concours à le sauter pour s'intéresser au dernier, beaucoup plus classique et
largement abordable.
Au final, tout ceci donne une épreuve assez longue, variée et plutôt 
intéressante.
Si elle n'offre pas la satisfaction de traiter un sujet difficile dans sa 
globalité, elle a
le mérite de permettre de s'exercer en une ou deux heures sur une partie ciblée 
du
programme, quitte à ne pas traiter immédiatement le problème en totalité.

Indications
Partie I
I.A.1 Raisonner sur le nombre de façons de construire une stratégie : combien y
a-t-il de candidats susceptible d'être relié à P6 ? Une fois ce candidat choisi,
de combien de façons peut-on relier les autres ?
I.A.2 Raisonner comme précédemment en respectant cette fois le fait que les
cordes ne sont plus autorisées à se croiser. Remarquer par exemple que
cela impose que |c[i] - i| soit impaire pour tout i  [[ 1 ; 6 ]].
I.A.3 Généraliser le raisonnement effectué en I.A.1 et conclure par récurrence.
I.B.1 Utiliser le fait que la position exacte des points ne compte pas pour 
placer
les 4 points à des endroits simples. Conclure à l'aide de dessins exhibant les
différents ordres possibles de ces points sur le cercle.
I.B.3 Tester naïvement si les segments [Pi Pc[i] ] et [Pj Pc[j] ] se croisent 
pour tout
(i, j)  [1, 2n]2 .
I.C.2 Justifier que pour tous i, j  [[ 1 ; 2n ]],
evalue(i,j) = evalue(i+1,c[i]-1) && evalue(c[i]+1,j)
I.C.3 Calculer récursivement evalue(1,2n) grâce aux deux questions précédentes.
I.C.4 Raisonner par récurrence sur la quantité j - i pour majorer la complexité
de evalue(i,j).
I.D.1 Utiliser l'application  qui à un entier k compris entre 1 et 2n associe le
nombre de chasseurs parmi {P1 , . . . , Pk } moins le nombre de fantômes de
ce même ensemble.
I.D.2 Décrire une fonction récursive en utilisant les questions précédentes.
Partie II
II.A.1.a Montrer que le langage complémentaire de L (ie A r L) est l'ensemble 
des
mots de longueur paire.
II.A.1.b Raisonner de préférence sur le complémentaire du langage L. Ce type de
question se résout souvent avec le lemme de l'étoile ou avec une démonstration 
directe proche de la démonstration de ce théorème.
II.A.1.c Les résultats sont identiques à ceux qui précèdent : il suffit 
d'adapter les
preuves.
II.B.a Déterminer l'écriture en base 2 des entiers 0, 2, 3, 4, 5. Utiliser ces 
décompositions pour écrire les « lignes » des représentations des n-uplets.
II.B.b Remarquer que les représentations des éléments de Eg ne comportent que
les lettres (0, 0) ou (1, 1). Les éléments de Inf, de leur coté, comportent
nécessairement la lettre (0, 1) suivie uniquement de lettres (0, 0) ou (1, 1).
II.B.c Un automate à deux états suffit : la lecture d'un mot représentant un 
triplet
(x, y, z) simule le calcul de x + y bit à bit, avec une retenue éventuelle.
II.B.d Pour reconnaître les représentations des éléments de Q, il suffit « 
d'effacer »
la dernière composante de chacune des lettres apparaissant dans les transitions 
d'un automate reconnaissant les représentations d'un élément de R.

II.C.2 Construire un automate avec un unique état final, qui n'est l'origine 
d'aucune transition et qui ne peut être atteint que si l'on a lu la lettre a 
puis N
lettres quelconques.
II.C.3 Considérer les états visités par une exécution réussie sur aN+1 pour 
montrer
qu'il y a au moins N + 2 états distincts. Ensuite, considérer les états visités
par une exécution qui échoue sur aN b et montrer que l'on accède ainsi à un
nouvel état.
II.C.4 Appliquer directement les méthodes de déterminisation du cours, en 
éliminant les états non accessibles.
II.C.5 Considérer tous les états auxquels on accède par des mots de longueur N 
+ 1
et montrer qu'ils sont deux à deux distincts.
II.C.6 Considérer les états visités par un chemin réussi d'étiquette aN+1 et 
montrer
qu'ils sont deux à deux distincts.

Les conseils du jury
D'après le rapport du jury, cette épreuve consistait à évaluer les candidats 
sur leurs capacités à concevoir et prouver de petits algorithmes et sur
ce qu'ils « comprennent des automates ». La production de programmes
et d'automates (qu'il faut dessiner !) a été jugée globalement satisfaisante.
En revanche, les questions plutôt mathématiques (validité d'un algorithme,
non-reconnaissabilité d'un langage) ont posé plus de difficultés.

I. La chasse aux fantômes
I.A.1 Il s'agit de compter le nombre de façons de partitionner 6 éléments en 
groupes
de 2. Soit c une stratégie. L'entier c[6] est un élément de {1, . . . , 5}. Il 
y a donc 5
possibilités pour le choisir. Ceci étant fait, il ne reste plus qu'à apparier 4 
éléments
deux à deux, ce qui ramène au cas n = 2.
Lorsque n = 2, il y a 3 choix pour c[4] et les 2 éléments restants sont 
nécessairement associés. Chacun de ces choix produit une stratégie différente 
et toutes les
stratégies peuvent être décrites par une suite de tels choix. Ainsi, il y a 3 
choix de
stratégie pour n = 2. Finalement,
Il y a exactement 15 stratégies (admissibles ou non).
I.A.2 Remarquons dans un premier temps que si c est une stratégie admissible,
alors pour tout entier i la quantité |c[i] - i| est nécessairement impaire. 
Dans le cas
contraire, l'intervalle I = [[ i ; c[i] ]] (resp. [[ c[i] ; i ]] si i > c[i]) 
contiendrait un nombre
impair d'entiers. Il existerait ainsi nécessairement un entier j de cet 
ensemble tel
que c[j] ne soit pas élément de I, et les cordes [Pi Pc[i] ] et [Pj Pc[j] ] 
seraient sécantes.
Cette condition nécessaire d'admissibilité permet d'éliminer de nombreux cas.
On considère maintenant une stratégie admissible c de taille 3. D'après ce qui
précède, c[1] est un élément de {2, 4, 6}.
· Si c[1] = 2, la condition nécessaire impose c[3] 6= 5. Il ne reste que les 
stratégies
pour lesquelles c[3] = 4 et c[5] = 6 ou c[3] = 6 et c[4] = 5, qui sont toutes 
deux
admissibles.
· Si c[1] = 4, on a c[2] = 3 donc c[2] = 3 et c[5] = 6.
· Si c[1] = 6, on est dans le cas symétrique du cas c[1] = 2 d'où deux 
possibilités :
c[2] = 3 et c[4] = 5 ou c[2] = 5 et c[3] = 4.
Finalement,

Il y a 5 stratégies admissibles de taille 3.

Les graphes qui suivent représentent ces 5 stratégies, que l'on résume 
également dans
le tableau ci-dessous :
i

c[i]

P2

1
2
2
4
6
6

3
4
6
2
2
4

4
3
5
1
5
3

5
6
4
6
4
2

6
5
3
5
1
1
P3

P2

P3

P3

P3

P4

P1
P6 P4

P1 P4
P6 P5

P5

2
1
1
3
3
5

P5

P3
P
P1 4
P6

P2
P1

P2

P1
P4

P5 P6

P2

P5

P6