Remerciez-le!

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

Épreuve d’informatique 2011 Page 1 sur 8 A 2011 INFO. MP ÉCOLE NATIONALE DES PO

Épreuve d’informatique 2011 Page 1 sur 8 A 2011 INFO. MP ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES, ÉCOLES NATIONALES SUPÉRIEURES DE L’AÉRONAUTIQUE ET DE L’ESPACE, DE TECHNIQUES AVANCÉES, DES TÉLÉCOMMUNICATIONS, DES MINES DE PARIS, DES MINES DE SAINT-ÉTIENNE, DES MINES DE NANCY, DES TÉLÉCOMMUNICATIONS DE BRETAGNE, ÉCOLE POLYTECHNIQUE (FILIÈRE TSI) CONCOURS D’ADMISSION 2011 ÉPREUVE D’INFORMATIQUE Filière MP Durée de l’épreuve : 3 heures. L’utilisation d’une calculatrice est autorisée. Sujet mis à disposition des concours : ENSAE ParisTech, TELECOM SudParis (ex-INT), TPE-EIVP L’énoncé de cette épreuve comporte 8 pages. Les candidats sont priés de mentionner de façon apparente sur la première page de la copie : INFORMATIQUE - MP 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 : • un exercice sur les automates : page 2 • un problème d’algorithmique et programmation : pages 2 à 8 Épreuve d’informatique 2011 Page 2 sur 8 Exercice sur les automates On considère dans cet exercice des mots définis sur l’alphabet Σ = {a, b}. Le transposé (ou miroir) d’un mot u = u1 … un, où les ui (1 ≤ i ≤ n) sont des éléments de Σ, est le mot, noté u , qui s’écrit un … u1. Ainsi, le transposé de abbbbaba est ababbbba. Un mot u est un palindrome s’il est identique à son transposé : u = u . Pour un entier k donné, le préfixe (respectivement, suffixe) de longueur k d’un mot u de longueur au moins k est le sous- mot formé des k premiers (respectivement, derniers) symboles de u. Ainsi, le préfixe de longueur 3 de abbbbaba est abb tandis que son suffixe de longueur 4 est baba. Pour tout entier n ≥ 1, on définit le langage Ln sur l’alphabet Σ de la manière suivante : Ln est l’ensemble des mots de longueur supérieure ou égale à 2n dont le suffixe de longueur n est le transposé du préfixe de longueur n. Ainsi, abbbbaba appartient à L1 (car a est le transposé de a) et à L2 (car ba est le transposé de ab) mais abbbbaba n’est pas dans L3. Ì 1 – Donner une expression rationnelle décrivant le langage L1. Ì 2 – Construire un automate A non déterministe reconnaissant le langage L2. On impose que A ait un seul état initial et un seul état final ; par ailleurs, les transitions de A seront étiquetées par des éléments de Σ. Ì 3 – Déterminiser l’automate obtenu à la question précédente. Il n’est pas nécessaire de détailler le processus de déterminisation. Ì 4 – En s’inspirant des questions précédentes, montrer que Ln est un langage rationnel pour tout n ≥ 1. Ì 5 – Soit n ≥ 1. On considère maintenant le langage n L′ formé de tous les mots de longueur strictement inférieure à 2n, ainsi que des mots de longueur supérieure ou égale à 2n dont le suffixe de longueur n est le transposé du préfixe de longueur n. Indiquer si n L′ est un langage rationnel et prouver la réponse. Ì 6 – Montrer que le langage des palindromes sur l’alphabet {a, b} n’est pas rationnel. Ì 7 – Montrer que l’intersection d’une suite infinie de langages rationnels n’est pas nécessairement un langage rationnel. Problème d’algorithmique et programmation : ordres pour un tournoi Préliminaire 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 de problème le langage de programmation choisi ; il est interdit de modifier ce choix au cours de l’épreuve. Certaines questions du problème sont formulées différemment selon le langage de programmation ; cela est indiqué chaque fois que nécessaire. Par ailleurs, pour écrire une fonction ou une procédure en langage de programmation, le candidat pourra définir des fonctions ou des procédures auxiliaires qu’il explicitera, ou faire appel à d’autres fonctions ou procédures définies dans les questions précédentes. Dans l’énoncé du problème, un même identificateur écrit dans deux polices de caractères différentes désigne la même entité, mais du point de vue mathématique pour la police écrite en italique (par exemple : T) et du point de vue informatique pour celle écrite en romain (par exemple : T). Épreuve d’informatique 2011 Page 3 sur 8 Dans ce problème, on note faux et vrai les deux valeurs possibles d’une variable booléenne. On considérera des matrices carrées ; les colonnes et les lignes d’une matrice carrée de dimension n × n seront toujours numérotées de 0 à n – 1. Si T est une matrice carrée de dimension n × n, pour 0 ≤ i ≤ n – 1 et 0 ≤ j ≤ n – 1, ti, j représentera le coefficient de T situé sur la ligne i et la colonne j. On appelle tournoi une matrice carrée T à coefficients booléens qui, si la matrice est de dimension n × n, vérifie • pour 0 ≤ i ≤ n – 1 et 0 ≤ j ≤ n – 1 avec i ≠ j : ti, j = vrai ⇔ tj, i = faux ; • pour 0 ≤ i ≤ n – 1, ti, i = faux. Si la matrice est de dimension n × n, le tournoi est dit d’ordre n. L’ordre n des tournois considérés dans ce problème sera toujours au moins égal à 1. On représentera un tournoi T par un dessin de la façon suivante : à chaque entier i vérifiant 0 ≤ i ≤ n – 1, on fait correspondre un cercle contenant l’entier i ; pour tout couple d’entiers i et j vérifiant 0 ≤ i ≤ n – 1, 0 ≤ j ≤ n – 1 et i ≠ j, si ti,j vaut vrai on trace une flèche du cercle contenant i au cercle contenant j ; on dira que ce dessin est un graphe G qui représente T. Le tournoi T4 défini à gauche ci-dessous est représenté par le graphe G4 qui se trouve à sa droite.               faux vrai vrai faux faux faux faux vrai faux vrai faux vrai vrai faux faux faux Le tournoi T4 3 2 0 1 Le graphe G4 On utilisera aussi le tournoi T5 défini à gauche ci-dessous et représenté par le graphe G5 qui se trouve à sa droite.                 faux faux faux vrai vrai vrai faux faux faux vrai vrai vrai faux faux faux faux vrai vrai faux faux faux faux vrai vrai faux Le tournoi T5 3 0 4 2 1 Le graphe G5 On utilisera enfin le tournoi T6 défini à gauche ci-dessous et représenté par le graphe G6 qui se trouve à sa droite. Épreuve d’informatique 2011 Page 4 sur 8                     faux faux vrai vrai vrai faux vrai faux vrai faux vrai vrai faux faux faux vrai faux faux faux vrai faux faux vrai vrai faux faux vrai faux faux faux vrai faux vrai faux vrai faux Le tournoi T6 5 3 2 0 1 4 Le graphe G6 On s’intéresse à un jeu nommé J qui se joue à deux joueurs ; pour chaque partie du jeu J, il y a un gagnant et un perdant, il n’y a pas de match nul. Soit n un entier strictement positif. On considère un ensemble de n joueurs. Une compétition C du jeu J effectuée par les n joueurs consiste à ce que chaque joueur joue une et une seule fois au jeu J contre chaque autre joueur. Les joueurs sont identifiés par des numéros allant de 0 à n – 1. Le résultat de cet ensemble de n(n – 1)/2 parties est représenté par un tournoi T d’ordre n : pour i et j distincts vérifiant les inégalités 0 ≤ i ≤ n – 1 et 0 ≤ j ≤ n – 1, le coefficient ti,j de T vaut vrai si le joueur i a gagné contre le joueur j et faux sinon ; pour 0 ≤ i ≤ n – 1, le coefficient ti,i vaut faux. On dira que le tournoi T représente le résultat de la compétition C. Par exemple, s’il y a quatre joueurs et que la compétition est représentée par le tournoi T4 ci- dessus : • le joueur 0 a gagné contre le joueur 3 et uploads/Sports/ mines-mp-info-2011-sujet.pdf