Informatique 2004 Classe Prepa MP Concours Mines-Ponts
Description
Concours du Supérieur Concours Mines-Ponts. Sujet de Informatique 2004. Retrouvez le corrigé Informatique 2004 sur Bankexam.fr.
Sujets
Informations
| Publié par | bankexam |
| Publié le | 27 février 2007 |
| Nombre de lectures | 168 |
| Langue | Français |
Extrait
A 2004−INF−MP
ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES, ÉCOLES NATIONALES SUPÉRIEURES DE LAÉRONAUTIQUE ET DE LESPACE, 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 DADMISSION 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 dalgorithmique et de programmation, page 2 • un problème sur les automates, pages 8 à 10, à résoudre en 1 h 15 mn environ.
Épreuve dinformatique
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 à laide dun: 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, lorsquun 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 quil ou elle explicitera. Enfin, lorsque le candidat ou la candidate écrira une fonction ou une procédure, il ou elle pourra, lorsque cela sy 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 sappelle ici sadimension. La case dindiceidun 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 dune variable ou dune case dun 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 dune 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 fonctiongsil existe un entier strictement positifk un entier etN (resp. deux entiersN etM)tels quon ait, pour toutn≥N (resp.n≥N etm≥M), f(n)≤kg(n) (resp.f(n,m)≤kg(n,m)). On dit que les deux fonctions ont même ordre de grandeur si lordre de grandeur de lune est au moins égal à lordre de grandeur de lautre, 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é dun algorithmeA, on lexprimera sous la forme dun ordre de grandeur du nombre dopérations élémentaires effectuées pendant le déroulement deA; cette complexité sera exprimée à laide de paramètres caractéristiques du problème à traiter. d) Si lon 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 lordre de grandeur denln(n). On étudie dans ce problème des algorithmes de tri dentiers qui nopèrent pas par comparaisons entre les données à trier. e) Tout au long du problème, on fera lhypothèse quil ny a pas de limitation sur la taille de la mémoire disponible et quon 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 sils 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] dun tableauT.
Page 2 sur 10
Épreuve commune 2004
Pascal: Dans tout le problème, on supposera quon é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 de 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 quon 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 lensemble des données à trier ; ces valeurs figureront alors avec le même nombre doccurrences 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 doccurrences parmi les entiers à trier, puis on en déduit la liste triée. On justifiera sommairement la complexité de lalgorithme proposé.
G2−Il sagit de programmer lalgorithme 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 lindice 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 lindice 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 dinformatique
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 noccupent 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 dun 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 dindice 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 lexemple 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 dindices 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. G3−la 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.G4−Ajouter 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 lentierpà la tableT.On supposera que la dimension de la tableTpermet cet ajout.
G5−Concaté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.G6−Indiquer la complexité de la fonction ou de la procédureconcateneren lexprimant à laide des nombres de données contenues par les tablesT1etT2.On justifiera sommairement le résultat._ G7−Il sagit ici de définir une fonction max valeursqui détermine la plus grande valeur dune tableT (cest-à-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.
G8−Il sagit de déterminer le nombre de chiffres dun 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 lentierp. _ 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 lentierp. _
G9−Il sagit 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.
G10−Exprimer la complexité de la fonctionsmaxc_ihfferappliquée à une tableTà laide : • 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 dinformatique
TROISIÈME PARTIETri dentiers écrits en base 10 à laide de baquets Dans la description de lalgorithme du tri par baquets, on appellechiffre de rangr(r≥1)dun entier positif ou nulpler-ième chiffre en partant de ladroitede lentierpé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 lentierp= 597, le chiffre de rang 1 est 7, celui de rang 2 est 9, celui de rang 3 est 5, et le chiffre de rangipouri≥4 est 0. Les données sont dans une tableT. Lobjectif de lalgorithme est de transformer la tableTen une table triée de manière croissante contenant les mêmes données. On dispose par ailleurs dun 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. Lalgorithme 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, cest-à-dire viderbaquets[i] pour toutiappartenant à {0, 1, , 9} ; b) considérer successivement, de lindice 1 à lindiceT[0], les entiers de la tableT: en notantplentier considéré, déterminer le chiffre de rangrde lentierp; 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 quon ne comptabilisera pas les opérations correspondantes. Lors de lécriture dune fonction ou dune procédure en langage de programmation, sipest une variable entière positive ou nulle, on pourra obtenir 10pparpuiss10(p). G11−On applique lalgorithme 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 litération correspondant à la valeur 1 der: • à lissue du point b), les baquets dindices 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] : • à lissue 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
G12−quaprès lexécution de lalgorithme du tri par baquets, la tableMontrer Test triée. G13−Il sagit décrire en langage de programmation une fonction ou une procédure nomméedistribuerqui effectue le point b) de lalgorithme 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 dentiers ; chacun de ces 10 vecteurs contient une table vide et est supposé de dimension suffisante pour contenir les données quon voudra y mettre,
Page 6 sur 10
Épreuve commune 2004
alorsdistribuer T r baquetseffectue les opérations indiquées dans le point b) de lalgorithme 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 quon voudra y mettre, alorsdistribuer(T, r, baquets)indiquées dans le point b) deeffectue les opérations lalgorithme du tri par baquets.
G14−Il sagit 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 lalgorithme 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 G15−On notenle nombre de données à trier etmaxcmaximum de chiffres des données de lale nombre table. Montrer que la complexité de lalgorithme du tri par baquets est de lordre demaxc×n.
G16−trier toutes distinctes, donner une fonction exprimée uniquement àEn supposant les données à laide 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.
G17−Il sagit dans decette question de modifier le tri par baquets pour que la complexité devienne lordre 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 lutilisation dun 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 dinformatique
2. Problème sur les automates 1 h 15 mn environ
Longueur discriminante de deux automates Deux automatesAetA′sont équivalents sils reconnaissent le même langage. Sils ne sont pas équivalents, alors il existe des mots qui sont reconnus par lun et pas par lautre. La longueur minimum des mots qui ont cette propriété est ditediscriminante. Lobjet de ce problème est dévaluer, par deux méthodes, un majorant de la longueur discriminante deAetA′en 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Σ*lensemble des mots surΣ, y compris le mot vide. Lalongueurdun 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; • T⊆Q×Σ×Qest appelé lensemble des transitions ; étant donnée une transition (p,a,q)∈T, on dit quelle va de létatpà létatqet quelle est détiquettea; on pourra la noterp⎯⎯a→q; • I⊆Qest appelé ensemble desétatsinitiauxdeA; • F⊆Qest appelé ensemble desétats finalsdeA. On représente graphiquement lautomateA 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⎯→p1⎯a⎯2⎯→p2⎯⎯a⎯k→pk, avecpi−1⎯a⎯i⎯→pi∈Tpour 1≤i≤k;p0 est lorigine du calcul,pk sonextrémité. Létiquette dec le mot formé par la suite des étiquettes des est transitions successives du chemin. Un calcul deAdoriginep, dextrémitéqet détiquettemest ditréussisi on ap∈Ietq∈F. Un motm∈Σ*est reconnu par Aest létiquette dun calcul réussi. Le sillangage reconnu parA, noté L(A), est lensemble des mots reconnus parA. Deux automatesAetA′sont ditstnsavelqéiusi on a L(A) = L(A′). LautomateAest ditmierétdestnisiIne contient quun élément et si, pour tout (p,a)∈Q×Σ, il existe au plus un étatq∈Qavec (p,a,q)∈T. LautomateAest ditcompletsi et seulement si, pour toutp∈Qet touta∈Σ, il existeq∈Qavec (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
G18−SoitAun automate, déterministe ou non déterministe, avecnétats. Montrer que L(A) est vide si et seulement sil ne contient aucun mot de longueur inférieure ou égale àn−1.
G19−SoitAun 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 etA′deux automates déterministes complets utilisant le même alphabetΣ avec respectivementnetn′états. Montrer que siAetA′ne sont pas équivalents, il existe un mot de longueur au plusn×n′−1 qui est reconnu par lun et non par lautre,i.e.la longueur discriminante deAetA′est inférieure ou égale àn×n′−1.
G22− déduire un majorant pour la longueur discriminante de deux automates non équivalents En quelconques avecnetn′états respectivement.
SECONDE PARTIEApproche plus fine Lobjectif 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+n′−1. G23− sur un exemple, avec un alphabet à une seule lettre, quil existe des automates Montrer déterministesA etA′ équivalents et qui reconnaissent les mêmes mots de longueur strictement non inférieure àn+n′−1, 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 lensembleQ états de desA avec lensemble {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 lespace 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 lalphabetΣ, on définit une application linéaireϕa deRndansRnpar : pour toutiavec 1≤i≤n:• sil existej, 1≤j≤n, tel que(i,a,j)∈T, alorsϕa(ei) ej, = • sinonϕa(ei) = 0. Lexistence et lunicité de lapplicationϕa découlent du fait queAest déterministe et de la linéarité deϕa. Sim=a1a2ak−1akest un mot non vide deΣ*, oùa1,a2, ,ak−1,aksont des lettres deΣ, on pose : ϕ = ϕ ϕ ϕ ϕo o L o o m akak−1a2a1 On noteϕεlidentité deRndansRn. On appellezla somme des vecteurs eiquandidécrit lensembleFdes états finals :z=∑ei. i∈F 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 dinformatique
G24−Soientm∈Σ*et deux entiersietjvérifiant 1≤i≤net 1≤j≤n. Montrer quil existe un calcul doriginei, dextré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 lautomate déterministeAun automate déterministeA′. Les notations utilisées pourA′sont les mêmes que celles utilisées pourAà cela près que tous les identificateurs sont n′t notés e′i). dotés dun « prime » (on a donc :n′,ϕ′a,ϕ′m,z′et 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≤+i1≤≤ni,≤win=+nu′i,wi=vi−nPar exemple, siu= (0, 1, 0) etv= (1, 2), (u;v) est le vecteur (0, 1, 0, 1, 2). On pose : E= (e1; e′1) (bien noter le signe ) Z= (z;z′). Pour tout motmdeΣ*, on définit une application linéaireΦm deRn+n′dansRn+n′par : pour toutu∈Rnet pour toutu′∈Rn′,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 lappartenance demà L(A) et L(A′). kle sous-espace vectoriel deRn+n′ndré{Φm(E)⏐m∈Σ*,|m|≤k};V0est donc Pourk∈N, on noteVenge par engendré par le vecteur (e1;−e′1). G27−Monter que, pourk≥0, on aVk⊆Vk 1. +
G28− Soitm∈Σ* ; on suppose quem sous la forme sécrit :m =µa, oùµ∈Σ* eta∈Σ. Montrer légalitéΦ=ΦoΦ.
m aµ G29−Soitw∈Vketa∈Σ; montrer :Φa(w)∈Vk+ 1.
G30−On suppose quil existek≥0 tel queVk=Vk+ 1; montrer légalitéVk+ 2=Vk 1 +.
31−Montrer quil existe un entierh≤n+n′ 1tel que, pour toutk≥h,Vk=Vh. G
G32−Montrer que siAetA′ne sont pas équivalents, il existe un mot de longueur inférieure ou égale à n+n′− 1 qui est accepté par lun et pas par lautre,i.e. que n +n′− est un majorant de la longueur 1 discriminante deAetA′.
G33−En 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
© 2010-2024 YouScribe