CCMP 2004 informatique classe prepa mp

Publié par

A 2004 − INF − MP ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES, ÉCOLES NATIONALES SUPÉRIEURES DE L’AÉRONAUTIQUE ET DE L’ESPACE, DES 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 T.S.I.) CONCOURS D’ADMISSION 2004 ÉPREUVE D’INFORMATIQUE Filière MP (Durée de l’épreuve : 3 heures) Sujet mis à la disposition des concours Cycle International, ENSTIM et TPE-EIVP. Les candidats et les candidates sont priés de mentionner de façon apparente sur la première page de la copie : « INFORMATIQUE – Filière MP » RECOMMANDATIONS AUX CANDIDATS ET CANDIDATES • L’énoncé de cette épreuve, y compris cette page de garde, comporte 10 pages. • Si, au cours de l’épreuve, un candidat ou une candidate repère ce qui lui semble être une erreur d’énoncé, il ou elle le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu’il ou elle a décidé de 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. • L’utilisation d’une calculatrice ou d’un ordinateur est interdite. COMPOSITION DE L’ÉPREUVE L’épreuve comporte deux parties indépendantes : • un problème d’algorithmique et de ...
Publié le : jeudi 21 juillet 2011
Lecture(s) : 255
Tags :
bac
Nombre de pages : 10
Voir plus Voir moins
A 2004INFMP
  
 
ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES, ÉCOLES NATIONALES SUPÉRIEURES DE LAÉRONAUTIQUE ET DE LESPACE, DES 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 T.S.I.) CONCOURS DADMISSION 2004 ÉPREUVE D’INFORMATIQUE Filière MP (Durée de l’épreuve : 3 heures) Sujet mis à la disposition des concours Cycle International, ENSTIM et TPE-EIVP. Les candidats et les candidates sont priés de mentionner de façon apparente sur la première page de la copie : « INFORMATIQUE – Filière MP »   RECOMMANDATIONS AUX CANDIDATS ET CANDIDATES
 L’énoncé de cette épreuve, y compris cette page de garde, comporte 10 pages.  Si, au cours de l’épreuve, un candidat ou une candidate repère ce qui lui semble être une erreur d’énoncé, il ou elle le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu’il ou elle a décidé de 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.  L’utilisation d’une calculatrice ou d’un ordinateur est interdite.
 COMPOSITION DE L’ÉPREUVE Lépreuve comporte deux parties indépendantes :  à 7, à résoudre en 1 h 45 mn environ ;un problème dalgorithmique et de programmation, page 2  un problème sur les automates, pages 8 à 10, à résoudre en 1 h 15 mn environ.
Épreuve dinformatique
1. Problème d’algorithmique et de programmation – 1 h 45 mn environ  
Le tri par baquets Préliminaire concernant la programmationdes fonctions ou des procédures à laide dun: il faudra écrire langage de programmation qui pourra être soitCaml, 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 cela est nécessaire. Par ailleurs, lorsquun candidat ou une candidate écrira une fonction ou une procédure en langage de programmation, il ou elle précisera si nécessaire le rôle des variables locales et pourra définir des fonctions ou procédures auxiliaires quil ou elle explicitera. Enfin, lorsque le candidat ou la candidate écrira une fonction ou une procédure, il ou elle pourra, lorsque cela sy prête, faire appel à une autre fonction ou procédure définie dans les questions précédentes.
Terminologie, notations et indications a) Dans lénoncé, les identificateurs sont écrits en police de caractères New Courierdans le contexte du langage de programmation et enitaliquesinon. b) Un tableau est constitué decasestype donné. Le nombre total de cases dupouvant contenir des valeurs d'un tableau sappelle ici sadimension. La case dindiceidun tableauTsera notéeT[i] dans lénoncé du problème. c) Dans ce problème, nous appelonsopérations élémentaires:  en mémoire pour lire ou écrire la valeur dune variable ou dune case dun tableau ;un accès  une opération arithmétique entre entiers : addition, soustraction, multiplication, division entière, calcul du reste dans une division entière ;  une comparaison (>, <,,, =,) entre deux entiers. Soientfetgdeux fonctions dune même variable entièren(resp. de deux mêmes variables entièresnetm). On dit que la fonctionfa un ordre de grandeur au plus égal à celui de la fonctiongsil existe un entier strictement positifk un entier etN (resp. deux entiersN etM)tels quon ait, pour toutnN (resp.nN etmM), f(n)kg(n) (resp.f(n,m)kg(n,m)). On dit que les deux fonctions ont même ordre de grandeur si lordre de grandeur de lune est au moins égal à lordre de grandeur de lautre, et réciproquement. Par exemple, les fonctionsf(n) = 3n2 5n+ 4 etg(n)n2ont même ordre de grandeur. On pourra aussi dire quegest un ordre = de grandeur def. Quand on calculera la complexité dun algorithmeA, on lexprimera sous la forme dun ordre de grandeur du nombre dopérations élémentaires effectuées pendant le déroulement deA; cette complexité sera exprimée à laide de paramètres caractéristiques du problème à traiter. d) Si lon se préoccupe de trier une liste den on sait alors que les algorithmes de tri données,opérant par comparaisons et échanges des données de la listeont une complexité dans le cas le plus défavorable au moins de lordre de grandeur denln(n). On étudie dans ce problème des algorithmes de tri dentiers qui nopèrent pas par comparaisons entre les données à trier. e) Tout au long du problème, on fera lhypothèse quil ny a pas de limitation sur la taille de la mémoire disponible et quon peut donc manipuler des tableaux de dimensions quelconques. On ne se préoccupera pas non plus du fait que les entiers codés sur un ordinateur sont bornés et on fera comme sils ne létaient pas. f)Indications pour la programmation Caml: Ce qui est appelé tableau dans lénoncé correspond à ce qui est appelévecteur Caml. En Caml, en T.(i)représente la caseT[i] dun tableauT.
Page 2 sur 10
Épreuve commune 2004
Pascal: Dans tout le problème, on supposera quon écrit les différentes fonctions dans un fichier contenant les définitions suivantes : const _  MAX DIM = 100;  MAX VAL = 1000; _   type _  TABLE = array[0..MAX DIM] of INTEGER;  BACS = array[0..9] of TABLE;PREMIÈRE PARTIEntiers comp is e_ Tri de r ntre 0 etMAX VALCette partie est consacrée à un algorithme qui peut être considéré comme la version la plus simple du tri par baquets étudié dans la seconde partie. On suppose dans cette première partie quon veut trier par ordre croissant un ensemble den entiers dont les valeurs sont toutes comprises entre 0 et une valeur maximum notéeMAX_VAL. Certaines valeurs peuvent figurer plusieurs fois dans lensemble des données à trier ; ces valeurs figureront alors avec le même nombre doccurrences après le tri. Exemple: _10 etn , ecles données à trier suivantes : 6, 4, 2, 8, 4, 2, 3, 6, 4, les données triées sont PourMAX VAL= = 9 av alors : 2, 2, 3, 4, 4, 4, 6, 6, 8. G1 Expliciter un algorithme de tri, de complexitéMAX_VAL+n on :, fondé sur le principe suivant compte, pour chaque entier compris entre 0 àMAX_VAL, son nombre doccurrences parmi les entiers à trier, puis on en déduit la liste triée. On justifiera sommairement la complexité de lalgorithme proposé. 
G2Il sagit de programmer lalgorithme de la questionG1. Les données à trier se trouvent initialement dans un tableau ; après le tri, les données doivent occuper globalement les mêmes cases du tableau mais en étant cette fois-ci ordonnées par ordre croissant.  une fonctiontri_telle q Caml: Écrire en Camlsimple ue, si  tableauest un vecteur de dimension suffisante,  tableau.(0)contient le nombre de données à trier,  à trier, de valeurs comprises entre 0 etles données MAX_VAL, se trouvent danstableauconsécutivement à partir de lindice 1, alorstri_simple tableau ordonne les données du vecteurtableau ordre croissant. La par _pposée déjà définie. constante entièreMAX VALest su
Pascal: Écrire en Pascal une procéduretri_simpletelle que si  tableauest de typeTABLE,  tableau[0] le nombre de données à trier, nombre qui ne dépasse pas la constante contient MAX DIM, _  à trier, de valeurs comprises entre 0 etles données MAX VAL, se trouvent danstableau_ consécutivement à partir de lindice 1, _p alorstri simple(tableau)ordre croissant les données contenues dansordonne ar tableau.
Page 3 sur 10 Tournez la page S.V.P.
Épreuve dinformatique
DEUXIÈME PARTIEGestion de tables Dans toute cette partie, on considérera des tableauxdont le plus petit indice vaut 0et tels que les données du problème noccupent pas nécessairement toutes les cases. Plus précisément, pour un tableauT contenantndonnées significatives du problème (typiquement, des données à trier) :  la caseT[0] contiendra le nombren; les données significatives occuperont les casesT[1],T[2], ,T[n].  Par exemple, on pourrait, pour trier les entiers 6, 1 et 7, disposer dun tableauTdont les indices varient de 0 à 8, mettre la valeur 3 (nombre de données à trier) dansT[0], dansT[1] la valeur 6, dansT[2] la valeur 1, dansT[3] la valeur 7 et ne pas se préoccuper des contenus des cases dindice 4 à 8. Ce tableau peut être représenté ainsi : T:3 6 1 7 On appelleratableun tableau conçu selon ce modèle. Une table contiendra toujoursdes entiers positifs ou nuls. Ainsi, pour lexemple précédent, la tableTles données 6, 1 et 7. Une tablecontient Test ditevidesiT[0] vaut 0. Une table sera ditetriéecontenus dans les cases dindices compris entre 1 etsi les entiers T[0] sont croissants au sens large. Les questionsG3 àGdont le principe sera indiqué après la10 préparent la programmation du tri par baquets questionG10. G3la transformer en une table vide.Vider une table consiste à Caml: Écrire en Caml une fonctionvidertelle que, siTest un vecteur contenant une table,vider T vide la tableT. Pascal: Écrire en Pascal une procédurevider que, si telleT de type estTABLE,vider(T) vide la tableT.G4Ajouter un entierpà une table consiste à ajouterpà la suite des données figurant déjà dans la table et à actualiser le nombre des données de la table. Par exemple, si la tableTest réprésentée ci-dessous (les cases non remplies contiennent des valeurs non significatives) : T 6 1 7: 3
ajouter à la tableTla valeur 5 consiste à transformerTen : T 6 1 7 5: 4 Caml: Écrire en Caml une fonctionajoutertelle que, siTest un vecteur contenant une table etpun entier,ajouter T p transformeT pour ajouterp à la tableT. On supposera que la dimension de la tableTpermet cet ajout. Pascal: Écrire en Pascal une procédureajouter telle que, siT est de typeTABLE etp entier, un ajouter(T, p)ajoute lentierpà la tableT.On supposera que la dimension de la tableTpermet cet ajout.
G5Concaténer une table T1 et une tableT2 consiste à ajouter successivement dansT1 les toutes données deT2 exemple, si les tables. ParT1etT2sont réprésentées ci-dessous : T1: 3 6 1 7 T2: 2 12 4
la tableT1devient après concaténation : T1: 5 6 1
Page 4 sur 10
7
12
4
 
Épreuve commune 2004
La tableT2est inchangée. Caml: Écrire en Caml une fonctionconcatenertelle que, siT1etT2sont deux vecteurs contenant des tables, T2concatener T1concatène les tablesT1etT2. On supposera que la dimension deT1est suffisante pour cette concaténation. Pascal: Écrire en Pascal une procédureconcatener telle que, siT1 etT2 sont de typeTABLE, concatener(T1, T2) concatène les tablesT1 etT2. On supposera que la dimension deT1 est suffisante pour cette concaténation.G6Indiquer la complexité de la fonction ou de la procédureconcateneren lexprimant à laide des nombres de données contenues par les tablesT1etT2.On justifiera sommairement le résultat._ G7Il sagit ici de définir une fonction max valeursqui détermine la plus grande valeur dune tableT (cest-à-dire le plus grand des entiers qui se trouvent entre les indices 1 etT[0]). Caml: Écrire en Caml une fonctionmax_valeurs que, si telleT est un vecteur contenant une table, max_valeurs Tla valeur du plus grand entier derenvoie T. La fonctionmax_valeursrenverra la valeur 1 si la table est vide.Pascal: Écrire en Pascal une fonctionmax valeurs que, si telleT est de typeTABLE, _ _ sr du p grand entier deT. La fonctionmax_valeursrenverra la max valeurs(T)renvoie la valeu lu valeur 1 si la table est vide. 
G8Il sagit de déterminer le nombre de chiffres dun entier positif ou nul donné écrit dans la base 10 ; par exemple, le nombre de chiffres de 5973 vaut 4. Caml: Écrire en Caml une fonctionnombre chiffres telle que, sip est un entier positif ou nul, _ nombre chiffres prenvoie le nombre de chiffres de lentierp. _ Pascal: Écrire en Pascal une fonctionnombre_chiffres telle que, sip est un entier positif ou nul, nombre chiffres(p)renvoie le nombre de chiffres de lentierp.   _
G9Il sagit de définir une fo_ ffresqui calcule nctionmax chile nombre maximum de chiffres dans une écriture décimale des entiers contenus dans une table. Par exemple, si la table est : T: 5 13 2408 1 97 892 le résultat doit valoir 4. Caml: Écrire en Caml une fonctionmax_chiffrestelle que, siTest un vecteur contenant une table, _ max chiffresTde chiffres des données de la table renvoie le nombre maximum T. La fonction renverra la valeur 0 si la table est vide.
Pascal: Écrire en Pascal une fonctionmax_chiffres que, si telleT de type estTABLE, _ max chiffres(T) renvoie le nombre maximum de chiffres des données de la tableT. La fonction renverra la valeur 0 si la table est vide.
G10Exprimer la complexité de la fonctionsmaxc_ihfferappliquée à une tableTà laide :  du nombrende données de la tableT du nombre maximummaxcde chiffres des données de la tableT. On justifiera sommairement le résultat.
Page 5 sur 10 Tournez la page S.V.P.
Épreuve dinformatique
TROISIÈME PARTIETri dentiers écrits en base 10 à laide de baquets  Dans la description de lalgorithme du tri par baquets, on appellechiffre de rangr(r1)dun entier positif ou nulpler-ième chiffre en partant de ladroitede lentierpécrit dans la base 10 ; par définition, sirest supérieur au nombre total de chiffres dep, le chiffre de rangrvaut alors 0. Par exemple, pour lentierp= 597, le chiffre de rang 1 est 7, celui de rang 2 est 9, celui de rang 3 est 5, et le chiffre de rangipouri4 est 0. Les données sont dans une tableT. Lobjectif de lalgorithme est de transformer la tableTen une table triée de manière croissante contenant les mêmes données. On dispose par ailleurs dun tableau appelébaquets, dont les indices varient de 0 à 9, de 10 tables ; ces 10 tables peuvent contenir chacune au moins autant de données que le nombre de données contenues par la tableT. Lalgorithme est le suivant :  Calculer le nombre maximum de chiffres des données de la tableT; le notermaxc.  Pourrqui varie de 1 àmaxc, faire : a) Vider les dix baquets, cest-à-dire viderbaquets[i] pour toutiappartenant à {0, 1, , 9} ; b) considérer successivement, de lindice 1 à lindiceT[0], les entiers de la tableT: en notantplentier considéré, déterminer le chiffre de rangrde lentierp; en notantkce chiffre, ajouterpà la tablebaquets[k] ; c) viderT; d) pourivariant de 0 à 9, concaténerTetbaquets[irésultat de la concaténation se trouve dans] (le T). Indications: on pourra utiliser dans la suite du problème une fonction nomméepuiss10, supposée déjà définie, qui calcule pour un entierppositif ou nul la valeur de 10p. Dans les calculs de complexité, on considérera que les appels à cette fonction sont négligeables, ce qui signifie quon ne comptabilisera pas les opérations correspondantes. Lors de lécriture dune fonction ou dune procédure en langage de programmation, sipest une variable entière positive ou nulle, on pourra obtenir 10pparpuiss10(p). G11On applique lalgorithme du tri par baquets à la tableTci-dessous, qui contient 8 données à trier. T: 8 57 423 50 603 7 20 453 27
Le nombre maximum de chiffres des données de la table vaut 3. Pendant litération correspondant à la valeur 1 der:  à lissue du point b), les baquets dindices 1, 2, 4, 5, 6, 8, 9 sont restés vides,baquets[0],baquets[3] et baquets[7] sont représentés ci-dessous : baquets 50 20 2[0] : baquets 603 453[3] : 3 423
baquets 57 7 27 3[7] :  à lissue du point d), la tableTest : T 423 603 453: 8 50 20 57 7 2 Détailler de même les itérations correspondant aux valeurs 2 et 3 der.
7
G12quaprès lexécution de lalgorithme du tri par baquets, la tableMontrer Test triée. G13Il sagit décrire en langage de programmation une fonction ou une procédure nomméedistribuerqui effectue le point b) de lalgorithme du tri par baquets. Caml: écrire en Caml une fonctiondistribuertelle que si :  Test un vecteur contenant une table,  rest un entier au moins égal à 1,  baquetsest un vecteur de dimension 10 de vecteurs dentiers ; chacun de ces 10 vecteurs contient une table vide et est supposé de dimension suffisante pour contenir les données quon voudra y mettre,
Page 6 sur 10
 
 
Épreuve commune 2004
alorsdistribuer T r baquetseffectue les opérations indiquées dans le point b) de lalgorithme du tri par baquets.  
Pascal: écrire en Pascal une procéduredistribuertelle que si :  T, de typeTable, contient une table,  rest un entier au moins égal à 1,  baquetsest de typeBACS(voir au début du problème) ; chacune des dix tables (de typeTABLE) debaquetscontient une table vide supposée de dimension suffisante pour contenir les données quon voudra y mettre, alorsdistribuer(T, r, baquets)indiquées dans le point b) deeffectue les opérations lalgorithme du tri par baquets.
G14Il sagit décrire en langage de programmation une fonction ou une procédure nomméestqaeut_briqui effectue le tri par baquets.  Caml: écrire en Caml une fonctiontri_baquets si telle queT est un vecteur contenant une table, tri_baquets Ttransforme la tableTtable triée en utilisant lalgorithme du tri par baquets.en une   Pascal: écrire en Pascal une procéduretri_baquetstelle que siT, de typeTable, contient une table, _algorithme du tri par baque tri baquets(T)transforme la tableT ts.en une table triée en utilisant l G15On notenle nombre de données à trier etmaxcmaximum de chiffres des données de lale nombre table. Montrer que la complexité de lalgorithme du tri par baquets est de lordre demaxc×n. 
G16trier toutes distinctes, donner une fonction exprimée uniquement àEn supposant les données à laide du nombrende données à trier telle que :  ordre de grandeur minore la complexité du tri par baquets ;son   son ordre de grandeur peut être atteint. 
G17Il sagit dans  decette question de modifier le tri par baquets pour que la complexité devienne lordre de la somme du nombre des chiffres des données de la table. Cette nouvelle version du tri par baquets devra commencer directement par la mise dans les baquets sans nécessiter le calcul préalable du nombre maximum de chiffres des données ni lutilisation dun autre algorithme préparatoire. Pour définir un tel algorithme, donner son principe, justifier rapidement son exactitude et sa complexité, puis écrire ou réécrire en langage de programmation les fonctions ou procédures ajoutées ou modifiées ; on sera sans doute conduit à récriredistribuer ettri baquet les nommant endistribuer bis et _ _ tri baquet bis. _ _
FIN DU PROBLÈME D’ALGORITHMIQUE ET DE PROGRAMMATION
Page 7 sur 10 Tournez la page S.V.P.
Épreuve dinformatique
2. Problème sur les automates – 1 h 15 mn environ
Longueur discriminante de deux automates Deux automatesAetAsont équivalents sils reconnaissent le même langage. Sils ne sont pas équivalents, alors il existe des mots qui sont reconnus par lun et pas par lautre. La longueur minimum des mots qui ont cette propriété est ditediscriminante. Lobjet de ce problème est dévaluer, par deux méthodes, un majorant de la longueur discriminante deAetAen fonction des nombres détats deAetA . Notations et terminologie UnalphabetΣest un ensemble fini déléments appeléslettres. UnmotsurΣest une suite finie de lettres deΣ; le mot vide est notéε. On désigne parΣ*lensemble des mots surΣ, y compris le mot vide. Lalongueurdun motm, notée |m|, est le nombre de lettres qui le composent. Unlangageest une partie deΣ*. UnautomateAest décrit par une structure <Σ,Q,T,I,F>, où :  Σest un alphabet ;  Qest un ensemble fini et non vide appeléensemble des étatsdeA;  TQ×Σ×Qest appelé lensemble des transitions ; étant donnée une transition (p,a,q)T, on dit quelle va de létatpà létatqet quelle est détiquettea; on pourra la noterpaq;  IQest appelé ensemble desétatsinitiauxdeA;  FQest appelé ensemble desétats finalsdeA. On représente graphiquement lautomateA ainsi :  un étatppar un cercle marqué en son centre parest figuré p; sipappartient àI, cela est figuré par une flèche entrante sans origine ; si un étatqappartient àF, cela est figuré par une flèche sortante sans but ;  une transition (p,a,q)Test figurée par une flèche allant de létatpvers létatqet étiquetée par la lettrea.
Un calculcdeAest un chemin de la formep0⎯⎯a1⎯→p1a2⎯→p2⎯⎯akpk, avecpi1ai⎯→piTpour 1ik;p0 est lorigine du calcul,pk sonextrémité. Létiquette dec le mot formé par la suite des étiquettes des est transitions successives du chemin. Un calcul deAdoriginep, dextrémitéqet détiquettemest ditréussisi on apIetqF. Un motmΣ*est reconnu par Aest létiquette dun calcul réussi. Le  sillangage reconnu parA, noté L(A), est lensemble des mots reconnus parA. Deux automatesAetAsont ditstnsavelqéiusi on a L(A) = L(A). LautomateAest ditmierétdestnisiIne contient quun élément et si, pour tout (p,a)Q×Σ, il existe au plus un étatqQavec (p,a,q)T. LautomateAest ditcompletsi et seulement si, pour toutpQet toutaΣ, il existeqQavec (p,a,q)T. On rappelle que tout automate ayantnétats est équivalent à un automate déterministe complet ayant au plus 2nétats. PREMIÈRE PARTIEApproche naïve
G18SoitAun automate, déterministe ou non déterministe, avecnétats. Montrer que L(A) est vide si et seulement sil ne contient aucun mot de longueur inférieure ou égale àn1.
G19SoitAun automate déterministe complet ayantnétats. Donner un automate ayant aussinétats qui reconnaît L(A), le complémentaire dansΣ*de L(A). Justifier votre réponse.
Page 8 sur 10
Épreuve commune 2004
G20 SoientA etA deux automates utilisant le même alphabetΣ respectivement avecn etn états. Donner un automate ayantn×nétats qui reconnaît L(A)L(A). Justifier votre réponse.
G21 SoientA etAdeux automates déterministes complets utilisant le même alphabetΣ avec respectivementnetnétats. Montrer que siAetAne sont pas équivalents, il existe un mot de longueur au plusn×n1 qui est reconnu par lun et non par lautre,i.e.la longueur discriminante deAetAest inférieure ou égale àn×n1.
G22 déduire un majorant pour la longueur discriminante de deux automates non équivalents En quelconques avecnetnétats respectivement.
SECONDE PARTIEApproche plus fine Lobjectif de cette partie est de démontrer que la longueur discriminante de deux automates déterministes non équivalents, avecnetnétats respectivement, est inférieure ou égale àn+n1. G23 sur un exemple, avec un alphabet à une seule lettre, quil existe des automates Montrer déterministesA etA équivalents et qui reconnaissent les mêmes mots de longueur strictement non inférieure àn+n1, oùn(resp.n) désigne le nombre détats deA(resp. deA). On introduit un ensemble de définitions et de notations. SoitA = <Σ,Q,T,I,F> un automate déterministe avecn états. On identifie lensembleQ états de desA avec lensemble {1, 2,  ,n} desn entiers naturels non nuls de sorte que  premierschaque état est identifié par un entier compris entre 1 etn.On suppose que l’on aI= {1}. On note {e1, e2, , en} la base canonique de lespace vectorielRn. Pour un entieri entre 1 et comprisn, le vecteur eiest donc le vecteur deRndont toutes les composantes sont nulles sauf lai-ième qui vaut 1. On note 0 le vecteur nul deRn. Pour chaque lettreade lalphabetΣ, on définit une application linéaireϕa deRndansRnpar : pour toutiavec 1in: sil existej, 1jn, tel que(i,a,j)T, alorsϕa(ei) ej, =  sinonϕa(ei) = 0. Lexistence et lunicité de lapplicationϕa découlent du fait queAest déterministe et de la linéarité deϕa. Sim=a1a2ak1akest un mot non vide deΣ*, oùa1,a2, ,ak1,aksont des lettres deΣ, on pose : ϕ = ϕ ϕ ϕ ϕo o L o o m akak1a2a1 On noteϕεlidentité deRndansRn. On appellezla somme des vecteurs eiquandidécrit lensembleFdes états finals :z=ei. iF n Enfin, siuetvsont deux vecteurs deRn, on noteu.vle produit scalaire deuet dev:u.v=uivi. i=1 Exemple: aϕa(e1) = e2,ϕa(e2) = 0,ϕa(e3) = e3 3) e2 = 1 2zϕbe((=11,=e)10,3),.ϕb(e2) = e1,ϕb(e bOn peut aussi constater les égalités suivantes : bϕabb(e1) = e3,ϕba(e3) = 0,ϕba(e2) = e2. b
a
3
Page 9 sur 10 Tournez la page S.V.P.
Épreuve dinformatique
G24SoientmΣ*et deux entiersietjvérifiant 1inet 1jn. Montrer quil existe un calcul doriginei, dextrémitéjet détiquettemsi et seulement si on aϕm(ei) = ej. G25 SoitmΣ*Donner les valeurs possibles du produit scalaire. ϕm(e1).z indiquer une condition et nécessaire et suffisante portant sur ce produit scalaire pour quemsoit un mot reconnu parA. Dans la suite du problème, on considère en plus de lautomate déterministeAun automate déterministeA. Les notations utilisées pourAsont les mêmes que celles utilisées pourAà cela près que tous les identificateurs sont nt notés ei). dotés dun « prime » (on a donc :n,ϕa,ϕm,zet les vecteurs de la base canonique deRson Siu etv des vecteurs respectivement de sontRn et deRn, on note (u;v) le vecteurw deRn+n obtenu en concaténantuetv; plus précisément, le vecteurwest défini par : 1issin+i1ni,win=+nui,wi=vinPar exemple, siu= (0, 1, 0) etv= (1, 2), (u;v) est le vecteur (0, 1, 0, 1, 2). On pose : E= (e1;  e1) (bien noter le signe  ) Z= (z;z). Pour tout motmdeΣ*, on définit une application linéaireΦm deRn+ndansRn+npar : pour toutuRnet pour toutuRn,m((u;u))= (m(u) ;m(u))(on admet la linéarité deΦm). G26 SoitmΣ* indiquer les valeurs possibles du produit scalaire ;Φm(E).Z selon ces valeurs, et, préciser lappartenance demà L(A) et L(A). kle sous-espace vectoriel deRn+nndré{Φm(E)mΣ*,|m|k};V0est donc PourkN, on noteVenge par engendré par le vecteur (e1;e1). G27Monter que, pourk0, on aVkVk 1. +
G28 SoitmΣ* ; on suppose quem sous la forme sécrit :m =µa, oùµΣ* etaΣ. Montrer légalitéΦ=ΦoΦ.
m aµ  G29SoitwVketaΣ; montrer :Φa(w)Vk+ 1.
G30On suppose quil existek0 tel queVk=Vk+ 1; montrer légalitéVk+ 2=Vk 1 +.
31Montrer quil existe un entierhn+n 1tel que, pour toutkh,Vk=Vh. G
G32Montrer que siAetAne sont pas équivalents, il existe un mot de longueur inférieure ou égale à n+n 1 qui est accepté par lun et pas par lautre,i.e. que n +n est un majorant de la longueur 1 discriminante deAetA.
G33En déduire un majorant pour la longueur discriminante de deux automates quelconques ayantnet nétats respectivement.
Page 10 sur 10
FIN DU PROBLÈME SUR LES AUTOMATES
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.