Remerciez-le!

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

Mines mp info 2011 sujet Épreuve d ? informatique A 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- ÉTIE

Épreuve d ? informatique A 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 ÉPREUVE D ? INFORMATIQUE Filière MP Durée de l ? épreuve 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 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 ? un problème d ? algorithmique et programmation pages à Page sur CÉpreuve d ? informatique Exercice sur les automates On considère dans cet exercice des mots dé ?nis sur l ? alphabet ? a b Le transposé ou miroir d ? un mot u u ? un o? les ui ? i ? n sont des éléments de ? est le mot noté u qui s ? écrit un ? u 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é ?xe respectivement su ?xe de longueur k d ? un mot u de longueur au moins k est le sousmot formé des k premiers respectivement derniers symboles de u Ainsi le pré ?xe de longueur de abbbbaba est abb tandis que son su ?xe de longueur est baba Pour tout entier n ? on dé ?nit le langage Ln sur l ? alphabet ? de la manière suivante Ln est l ? ensemble des mots de longueur supérieure ou égale à n dont le su ?xe de longueur n est le transposé du pré ?xe de longueur n Ainsi abbbbaba appartient à L car a est le transposé de a et à L car ba est le transposé de ab mais abbbbaba n ? est pas dans L ? ?? Donner une expression rationnelle décrivant le langage L ? ?? Construire un automate A non déterministe reconnaissant le langage L On impose que A ait un seul état initial et un seul état ?nal par ailleurs les transitions de A seront étiquetées