Centrale Informatique MP 2009

Thème de l'épreuve La chasse aux fantômes, Automates finis
Principaux outils utilisés automates, combinatoire, complexité
Mots clefs couplages, dénombrement, automates minimaux, récursivité

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


- 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