Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

A2019 – INFO MP ÉCOLE DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARISTECH, TELEC

A2019 – INFO MP ÉCOLE DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARISTECH, TELECOM PARISTECH, MINES PARISTECH, MINES SAINT-ÉTIENNE, MINES NANCY, IMT Atlantique, ENSAE PARISTECH, CHIMIE PARISTECH. Concours Centrale-Supélec (Cycle International), Concours Mines-Télécom, Concours Commun TPE/EIVP. CONCOURS 2019 ÉPREUVE D’INFORMATIQUE MP Durée de l’épreuve : 3 heures L’usage de la calculatrice et de tout dispositif électronique est interdit. Cette épreuve concerne uniquement les candidats de la ﬁlière MP. 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 10 pages de texte. 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. Épreuve d’option informatique MP 2019 L’épreuve est composée d’un unique problème, comportant 37 questions. Après un préliminaire, ce problème est divisé en 5 parties. Pour répondre à une question, un candidat pourra réutiliser le résultat d’une question antérieure, même s’il n’est pas parvenu à démontrer ce résultat. Le but du problème est d’étudier les relations qui existent entre des automates qui reconnaissent un même langage grâce à la notion de morphismes d’automates. Préliminaires Concernant la programmation Il faudra coder des fonctions à l’aide du langage de programmation Caml, tout autre langage étant exclu. Lorsque le candidat écrira une fonction, il pourra faire appel à d’autres fonctions déﬁnies dans les questions précédentes ; il pourra aussi déﬁnir des fonctions auxiliaires. Quand l’énoncé demande de coder une fonction, il n’est pas nécessaire de justiﬁer que celle-ci est correcte, sauf si l’énoncé le demande explicitement. Enﬁn, si les paramètres d’une fonction à coder sont supposés vériﬁer certaines hypothèses, il ne sera pas utile de tester si les hypothèses sont bien vériﬁées dans le code de la fonction. Dans tout l’énoncé, un même identiﬁcateur écrit dans deux polices de caractères diﬀérentes désignera la même entité, mais du point de vue mathématique pour la police en italique (par exemple n) et du point de vue informatique pour celle en romain avec espacement ﬁxe (par exemple n). Déﬁnition mathématique d’un automate Déﬁnition : Dans l’ensemble du sujet, le terme automate désigne un automate ﬁni déterministe complet sur l’alphabet {a, b}, c’est-à-dire un quadruplet A = ÈQ, i, ”, FÍ où Q est l’ensemble des états, i l’état initial (i œ Q), ” : Q ◊{a, b} æ Q l’application de transition et F ™Q l’ensemble des états ﬁnals. On note Á le mot vide. Par extension de ”, on appelle ”ú l’application Q ◊{a, b}ú æ Q déﬁnie pour tout état q par ”ú(q, Á) = q et, si ‡ est une lettre de {a, b} et w un mot de {a, b}ú, ”ú(q, ‡w) = ”ú(”(q, ‡), w). Un automate ÈQ, i, ”, FÍ est représenté par un graphe orienté. Les sommets de ce graphe sont les éléments de Q. Ce graphe admet un arc (p, q) œ Q ◊Q étiqueté par la lettre a si et seulement si ”(p, a) = q ; de même, ce graphe admet un arc (p, q) œ Q ◊Q étiqueté par la lettre b si et seulement si ”(p, b) = q. Une ﬂèche venant de nulle part et pointant vers i indique l’état initial. Un état ﬁnal est représenté par un double cercle. Représentation d’automate en Caml Indication Caml : Dans toutes les questions demandant d’implémenter une fonction en Caml, on identiﬁe l’ensemble des états Q d’un automate ÈQ, i, ”, FÍ avec l’ensemble des Page 1 sur 10 Épreuve d’option informatique MP 2019 entiers compris entre 0 et |Q| ≠1. On convient de plus que l’état initial i est toujours identiﬁé à l’entier 0. Les automates seront représentés par des triplets (n, delta, f) où — n, de type int, est le nombre d’états de l’automate ; les états de l’automate sont les entiers de 0 à n-1, — delta, de type (int * int) array de longueur n, est un tableau qui stocke les couples (”(q, a), ”(q, b))qœQ, — f, de type bool array de longueur n, est un tableau qui représente la fonction indicatrice de l’ensemble des états ﬁnals. Dans l’ensemble du sujet, le type automate est déﬁni par l’alias suivant. type automate = int * (int * int) array * bool array;; Ci-dessous sont donnés quelques exemples de son utilisation. — let (n, delta, f) = aut in ... permet de récupérer les composantes d’une variable aut de type automate. — let (succ_a,succ_b) = delta.(q) in ... permet ensuite de récupérer le successeur par la lettre a et le successeur par la lettre b de l’état q (qui est de type int). — if f.(q) then ... permet de tester si l’état q (qui est de type int) est ﬁnal. Indication Caml : On rappelle que la fonction List.length, de type ’a list -> int, renvoie la longueur d’une liste. On rappelle que Array.make n x permet de créer un tableau de longueur n et initialisé avec la valeur x, que Array.copy t renvoie une copie d’un tableau t, que Array.length t renvoie la longueur d’un tableau t. On rappelle enﬁn que Array.make_matrix n m x permet de créer un tableau de tableaux de taille n ◊m dont toutes les cases sont initialisées avec la valeur x. 1 Premiers exemples 1 – Donner, sans preuve, une description courte en langue française du langage reconnu par l’automate A1 de la ﬁgure 1. 2 – Donner, sans preuve, une description courte en langue française du langage reconnu par l’automate A2 de la ﬁgure 2. 3 – Donner, sans preuve, une expression rationnelle qui dénote le langage reconnu par l’automate A1 de la ﬁgure 1. 4 – Donner, sans preuve, une expression rationnelle qui dénote le langage reconnu par l’automate A2 de la ﬁgure 2. 5 – Écrire en Caml, sans justiﬁcation, la construction d’une instance du type automate qui corresponde à l’automate A2 de la ﬁgure 2. Page 2 sur 10 Épreuve d’option informatique MP 2019 A B a, b a, b Figure 1 – Automate A1 C D b b a a Figure 2 – Automate A2 E F G b a b b a a Figure 3 – Automate A3 H I J K b b b b a a a a Figure 4 – Automate A4 Page 3 sur 10 Épreuve d’option informatique MP 2019 2 États accessibles d’un automate 6 – Écrire une fonction numero de type int -> int list -> int array qui, à partir d’un entier n et une liste A d’entiers compris entre 0 et n ≠1, renvoie un tableau T de taille n tel que, pour tout i compris entre 0 et n ≠1, la iième case T[i] de T vaut ≠1 si i est absent de A et T[i] représente l’indice de l’une des occurrences de i dans A sinon. Par exemple, numero 5 [3;2;0];; peut renvoyer [|2; -1; 1; 0; -1|]. Déﬁnition : Un état q d’un automate A = ÈQA, iA, ”A, FAÍ est dit accessible s’il existe un mot w œ {a, b}ú tel que ”ú(iA, w) = q, autrement dit s’il existe un chemin qui relie l’état initial iA à l’état q dans sa représentation graphique. (On notera que l’état initial iA est toujours accessible.). Soit QÕ l’ensemble des états accessibles de l’automate A. On appelle partie accessible de l’automate A le nouvel automate AÕ = ÈQÕ, iA, ”Õ, FA ﬂQÕÍ où ”Õ est la restriction de l’application ”A au domaine QÕ ◊{a, b}. On dit qu’un automate est accessible lorsque tous ses états sont accessibles. 7 – Écrire une fonction etats_accessibles, de type automate -> int list, qui renvoie la liste des états accessibles de l’automate donné en argument et que l’on obtient par un parcours de graphe en profondeur depuis l’état initial. La liste renvoyée doit suivre l’ordre dans lequel les états sont rencontrés pour la première fois et ne doit pas contenir de doublons. Donner la complexité de la fonction écrite. 8 – Écrire une fonction partie_accessible de type automate -> automate qui construit la partie accessible de l’automate donné en argument. On pourra réemployer les fonctions implémentées aux questions 6 et 7. 3 Morphismes d’automates Déﬁnition : Soient deux automates A = ÈQA, iA, ”A, FAÍ et B = ÈQB, iB, ”B, FBÍ. Une application Ï : QA æ QB est appelée morphisme d’automates de l’automate A vers l’automate B, et est notée Ï : A æ B, si elle satisfait les conditions suivantes : Ï est surjective, (1) Ï(iA) = iB, (2) ’q œ QA, ’‡ œ {a, b}, Ï(”A(q, ‡)) = ”B(Ï(q), ‡), (3) ’q œ QA, q œ FA ≈ ∆Ï(q) œ FB (4) Page 4 sur 10 Épreuve d’option informatique MP 2019 Indication Caml : En Caml, on représente un morphisme Ï : A æ B par le ta- bleau [Ï(q)]qœQA de longueur |QA|, de type int array, formé d’entiers compris entre 0 et |QB| ≠1. On pourra utiliser le uploads/Science et Technologie/ info-opt-2019.pdf