Mines Informatique MP 2004

Thème de l'épreuve Algorithme de tri par baquets; longueur discriminante d'automates
Principaux outils utilisés tri par baquets, invariants de boucles, tables, déterminisation d'automates, automate complémentaire, produit, algèbre linéaire

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                             

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


J. 0794

A 2004 -- INF -- MP

- ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES,
ECOLES 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.

0 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 :

0 un problème d'algorithmique et de programmation, page 2 à 7, à résoudre en 1 
h 45 mn environ ;
0 un problème sur les automates, pages 8 à 10, à résoudre en 1 h 15 mn environ.

Tournez la page S.V.P.

Épreuve d'informatique

]. Problème d'algorithmique et de programmation -- 1 h 45 mn environ

Le tri par baquets

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 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 
Courier New dans le contexte du
langage de programmation et en italique sinon.

b) Un tableau est constitué de cases pouvant contenir des valeurs d'un type 
donné. Le nombre total de cases du
tableau s'appelle ici sa dimension. La case d'indice i d'un tableau T sera 
notée T[i] dans l'énoncé du problème.

c) Dans ce problème, nous appelons opérations élémentaires :
0 un accès en mémoire pour lire ou écrire la valeur d'une variable ou d'une 
case d'un tableau ;
0 une opération arithmétique entre entiers : addition, soustraction, 
multiplication, division entière, calcul
du reste dans une division entière ;
o une comparaison (>, <, 2, S, =, #) entre deux entiers. Soient f et g deux fonctions d'une même variable entière n (resp. de deux mêmes variables entières n et m). On dit que la fonction f a un ordre de grandeur au plus égal à celui de la fonction g s'il existe un entier strictement positif k et un entier N (resp. deux entiers N et M) tels qu'on ait, pour tout n ?. N (resp. n 2 N et m 2 M), f(n) .<. k g(n) (resp. f(n, m) S k g(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 fonctions f(n) : 3 n2 -- 5 n + 4 et g(n) : n2 ont même ordre de grandeur. On pourra aussi dire que g est un ordre de grandeur de f. Quand on calculera la complexité d'un algorithme 54, on l'exprimera sous la forme d'un ordre de grandeur du nombre d'opérations élémentaires effectuées pendant le déroulement de %; 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 de n données, on sait alors que les algorithmes de tri opérant par comparaisons et échanges des données de la liste ont une complexité dans le cas le plus défavorable au moins de l'ordre de grandeur de nln(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. 0 Indications pour la programmation Caml: Ce qui est appelé tableau dans l'énoncé correspond à ce qui est appelé vecteur en Caml. En Caml, T . (i ) représente la case T[i] d'un tableau T. 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 = lOQD: type TABLE : array[0..MAX_DIM] of INTEGER; BACS = array[0..9] of TABLE; PREMIÈRE PARTIE Tri d'entiers compris entre 0 et MAX_VAL Cette 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 de n entiers dont les valeurs sont toutes comprises entre 0 et une valeur maximum notée MAX_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 : Pour MAX_VAL : 10 et n = 9, avec les données à trier suivantes : 6, 4, 2, 8, 4, 2, 3, 6, 4, les données triées sont alors : 2, 2, 3, 4, 4, 4, 6, 6, 8. Cl 1 -- Expliciter un algorithme de tri, de complexité MAX_VAL + n, fondé sur le principe suivant: on 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é. D 2 -- Il s'agit de programmer l'algorithme de la question Cl 1. 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. ' Caml : Écrire en Caml une fonction tri_simple telle que, si 0 tableau est un vecteur de dimension suffisante, . tableau . ( 0 ) contient le nombre de données à trier, . les données à trier, de valeurs comprises entre 0 et MAX_VAL, se trouvent dans tableau consécutivement à partir de l'indice 1, alors tri_simple tableau ordonne les données du vecteur tableau par ordre croissant. La constante entière MAX_VAL est supposée déjà définie. Pascal : Écrire en Pascal une procédure tri_s imple telle que si 0 tableau est de type TABLE, 0 tableau [ 0] contient le nombre de données à trier, nombre qui ne dépasse pas la constante MAX_DIM, . les données à trier, de valeurs comprises entre 0 et MAX_VAL, se trouvent dans tableau consécutivement à partir de l'indice 1, alors tri_simple (tableau) ordonne par ordre croissant les données contenues dans tableau. Page 3 sur 10 Tournez la page S.V.P. Épreuve d'informatique DEUXIÈME PARTIE Gestion de tables Dans toute cette partie, on considérera des tableaux dont le plus petit indice vaut 0 et tels que les données du problème n'occupent pas nécessairement toutes les cases. Plus précisément, pour un tableau T contenant n données significatives du problème (typiquement, des données à trier) : 0 la case T[O] contiendra le nombre n ; o les données significatives occuperont les cases T[l], T[2], T[n]. Par exemple, on pourrait, pour trier les entiers 6, l et 7, disposer d'un tableau T dont les indices varient de 0 à 8, mettre la valeur 3 (nombre de données à trier) dans T[O], dans T[l] la valeur 6, dans T[2] la valeur 1, dans T[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= ---fl----- On appellera table un tableau conçu selon ce modèle. Une table contiendra toujours des entiers positifs ou nuls. Ainsi, pour l'exemple précédent, la table Tcontient les données 6, l et 7. Une table Test dite vide si T[O] vaut 0. Une table sera dite triée si les entiers contenus dans les cases d'indices compris entre 1 et T[O] sont croissants au sens large. Les questions Cl 3 à D 10 préparent la programmation du tri par baquets dont le principe sera indiqué après la question D 10. D 3 -- Vider une table consiste à la transformer en une table vide. Caml : Écrire en Caml une fonction vider telle que, si T est un vecteur contenant une table, vider T vide la table T. Pascal : Écrire en Pascal une procédure vider telle que, si T est de type TABLE, vider (T) vide la table T. D 4 --- Ajouter un entier p a une table consiste à ajouter p a 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 table T est réprésentée ci-dessous (les cases non remplies contiennent des valeurs non significatives) : Tr ---fl---- ajouter à la table T la valeur 5 consiste à transformer Ten : Tr ___-"__- Caml : Écrire en Caml une fonction ajouter telle que, si T est un vecteur contenant une table et p un entier, ajouter T p transforme T pour ajouter p a la table T. On supposera que la dimension de la table Tpermet cet ajout. Pascal: Écrire en Pascal une procédure ajouter telle que, si T est de type TABLE et p un entier, ajouter (T, p) ajoute l'entier p a la table T. On supposera que la dimension de la table T permet cet ajout. DS ---- Concatêner une table T 1 et une table T2 consiste à ajouter successivement dans TI toutes les données de T2. Par exemple, si les tables TI et T2 sont réprésentées ci--dessous : TI : ___--___- T2: --------- la table T] devient après concaténation : TI : --...-- La table T2 est inchangée. Page 4 sur 10 Épreuve commune 2004 Caml : Écrire en Caml une fonction concatener telle que, si T1 et T2 sont deux vecteurs contenant des tables, concatener T1 T2 concatène les tables T1 et T2. On supposera que la dimension de T1 est suffisante pour cette concaténation. Pascal: Écrire en Pascal une procédure concatener telle que, si T1 et T2 sont de type TABLE, concatener (T1, T2) concatène les tables T1 et T2. On supposera que la dimension de T1 est suffisante pour cette concaténation. Cl 6 -- Indiquer la complexité de la fonction ou de la procédure concatener en l'exprimant à l'aide des nombres de données contenues par les tables T1 et T2. On justifiera sommairement le résultat. E] 7 --- Il s'agit ici de définir une fonction max_valeurs qui détermine la plus grande valeur d'une table T (c'est--à-dire le plus grand des entiers qui se trouvent entre les indices 1 et T[O]). Caml : Écrire en Caml une fonction max_valeurs telle que, si T est un vecteur contenant une table, max_valeurs T renvoie la valeur du plus grand entier de T. La fonction max_valeurs renverra la valeur --1 si la table est vide. Pascal : Écrire en Pascal une fonction max_valeurs telle que, si T est de type TABLE, max_valeurs (T) renvoie la valeur du plus grand entier de T. La fonction max_valeurs renverra la valeur --1 si la table est vide. D 8 --- Il 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 fonction nombre_chiffires telle que, si p est un entier positif ou nul, nombre_chi f fres p renvoie le nombre de chiffres de l'entier p. Pascal : Écrire en Pascal une fonction nombre_chiffres telle que, si p est un entier positif ou nul, nombre_chi f f res ( p) renvoie le nombre de chiffres de l'entier p. Cl 9 ---- Il s'agit de définir une fonction max_chszres qui calcule le nombre maximum de chiffres dans une écriture décimale des entiers contenus dans une table. Par exemple, si la table est : Tr ___-___- le résultat doit valoir 4. Caml : Écrire en Caml une fonction max_chiff res telle que, si T est un vecteur contenant une table, max_chiffres T renvoie le nombre maximum de chiffres des données de la table T. La fonction renverra la valeur 0 si la table est vide. Pascal : Écrire en Pascal une fonction max_chiffres telle que, si T est de type TABLE, max_chiff res (T) renvoie le nombre maximum de chiffres des données de la table T. La fonction renverra la valeur 0 si la table est vide. CI 10 -- Exprimer la complexité de la fonction max_chiflres appliquée à une table T à l'aide : 0 du nombre n de données de la table T 0 du nombre maximum maxc de chiffres des données de la table T. On justifiera sommairement le résultat. Page 5 sur 10 Tournez la page S.V.P. Épreuve d'informatique TROISIÈME PARTIE Tri d'entiers écrits en base 10 à l'aide de baquets Dans la description de l'algorithme du tri par baquets, on appelle chiflre de rang r (r 2 1) d'un entier positif ou nul p le r--ième chiffre en partant de la droite de l'entier p écrit dans la base 10 ; par définition, si r est supérieur au nombre total de chiffres de p, le chiffre de rang r vaut alors 0. Par exemple, pour l'entier p = 597, le chiffre de rang 1 est 7, celui de rang 2 est 9, celui de rang 3 est 5, et le chiffre de rang i pour i 2 4 est 0. Les données sont dans une table T. L'objectif de l'algorithme est de transformer la table T en 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 table T. L'algorithme est le suivant : 0 Calculer le nombre maximum de chiffres des données de la table T; le noter maxc. . Pour r qui varie de 1 à maxc, faire : a) Vider les dix baquets, c'est-à-- dire vider baquets... pour tout i appartenant à {O, 1, 9.,}, b) considérer successivement, de l'indice là l' indice T[O], les entiers de la table T: en notant p l' entier considéré, déterminer le chiffre de rang r de l'entier p , en notant k ce chiffre, ajouter p à la table baquets[k] ; c) vider T; d) pour i variant de 0 à 9, concaténer T et baquets[i] (le résultat de la concaténation se trouve dans 7). Indications : on pourra utiliser dans la suite du problème une fonction nommée puiss]0, supposée déjà définie, qui calcule pour un entier p positif ou nul la valeur de 10" . 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, si p est une variable entière positive ou nulle, on pourra obtenir 10p par puiss l 0 (p) . D 11 --- On applique l'algorithme du tri par baquets à la table T ci-dessous, qui contient 8 données à trier. T= "___--___-- Le nombre maximum de chiffres des données de la table vaut 3. Pendant l'itération correspondant à la valeur 1 de r: . àl' issue du point b), les baquets d'indices 1, 2, 4, 5, 6, 8, 9 sont restes vides, baquets[0], baquets[3] et baquets[7] sont représentés ci- -:dessous ""WOE= ----::: '"'f"EUR"...= ...: baquetsl7lr ÏZÇ-ÏÏÇ . à l'issue du point d), la table Test : T= ... ÏÏ-ËÊÏ Détailler de même les itérations correspondant aux valeurs 2 et 3 de r. D 12 -- Montrer qu'après l'exécution de l'algorithme du tri par baquets, la table T est triée. CI 13 --- Il s'agit d'écrire en langage de programmation une fonction ou une procédure nommée distribuer qui effectue le point b) de l'algorithme du tri par baquets. Caml : écrire en Caml une fonction distribuer telle que si : 0 T est un vecteur contenant une table, 0 r est un entier au moins égal à 1, . baquets est 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, alors distribuer T r baquets effectue les opérations indiquées dans le point b) de l'algorithme du tri par baquets. Page 6 sur 10 Épreuve commune 2004 Pascal : écrire en Pascal une procédure distribuer telle que si : 0 T, de type Table, contient une table, 0 r est un entier au moins égal à l, . baquets est de type BACS (voir au début du problème) ; chacune des dix tables (de type TABLE) de baquets contient une table vide supposée de dimension suffisante pour contenir les données qu'on voudra y mettre, alors distribuer(T, r, baquets) effectue les opérations indiquées dans le point b) de l'algorithme du tri par baquets. D 14-- Il s'agit d'écrire en langage de programmation une fonction ou une procédure nommée tri_baquets qui effectue le tri par baquets. Caml : écrire en Caml une fonction tri_baquets telle que si T est un vecteur contenant une table, tri_baquets T transforme la table Ten une table triée en utilisant l'algorithme du tri par baquets. Pascal : écrire en Pascal une procédure tri_baquets telle que si T, de type Table, contient une table, tri_baquets (T) transforme la table Ten une table triée en utilisant l'algorithme du tri par baquets. CJ 15 --- On note n le nombre de données à trier et maxc le nombre maximum de chiffres des données de la table. Montrer que la complexité de l'algorithme du tri par baquets est de l'ordre de maxc x n. [3 16 --- En supposant les données à trier toutes distinctes, donner une fonction exprimée uniquement à l'aide du nombre n de données à trier telle que : 0 son ordre de grandeur minore la complexité du tri par baquets ; 0 son ordre de grandeur peut être atteint. E] 17 -- Il s'agit dans cette question de modifier le tri par baquets pour que la complexité devienne de 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écrire distribuer et tri_baquet en les nommant distribuer_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 12. Problème sur les automates -- 1 h 15 mn environ Longueur discriminante de deux automates Deux automates 2 et fll'sont é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 dite discriminante. L'objet de ce problème est d'évaluer, par deux méthodes, un majorant de la longueur discriminante de 54 et ñ'en fonction des nombres d'états de 54 et fll'. Notations et terminologie Un alphabet 27 est un ensemble fini d'éléments appelés lettres. Un mot sur 27 est une suite finie de lettres de Z ; le mot vide est noté 8. On désigne par 27* l'ensemble des mots sur 2, y compris le mot vide. La longueur d'un mot m, notée Iml, est le nombre de lettres qui le composent. Un langage est une partie de Z*. Un automate flest décrit par une structure , où :

0 2 est un alphabet ;
0 Q est un ensemble fini et non vide appelé ensemble des états de fll ;

0 T ç; Q >< 2 >< Q est appelé l'ensemble des transitions ; étant donnée une transition (p, a, q) EUR T, on dit qu'elle va de l'état p à l'état q et qu'elle est d'étiquette a ; on pourra la noter p L q ; 0 I g Q est appelé ensemble des états initiaux de R; 0 F g Q est appelé ensemble des états finals de 2. On représente graphiquement l'automate fll ainsi : 0 un état p est figuré par un cercle marqué en son centre par p ; si p appartient à I, cela est figuré par une flèche entrante sans origine ; si un état q appartient à F, cela est figuré par une flèche sortante sans but ; 0 une transition (p, a, q) EUR T est figurée par une flèche allant de l'état p vers l'état q et étiquetée par la lettre a. Un calculcdeñest un chemin dela formepo --£-1----+pl _?!qu _a_L.pk, avecp,-l ip,--EUR Tpour 1 SiSk; po est l'origine du calcul, pk son extrémité. L'étiquette de c est le mot formé par la suite des étiquettes des transitions successives du chemin. Un calcul de % d'origine p, d'extrémité q et d'étiquette m est dit réussi si on a p EUR I et q EUR F. Un mot m EUR 2?" est reconnu par 2 s'il est l'étiquette d'un calcul réussi. Le langage reconnu par fil, noté L(fl), est l'ensemble des mots reconnus par 51 Deux automates % et ñ'sont dits équivalents si on a L(fll) : L(fl). L'automate 54 est dit déterministe si 1 ne contient qu'un élément et si, pour tout (p, a) EUR Q >< 2, il existe au plus un état q EUR Q avec (p, a, q) EUR T. L'automate Hest dit complet si et seulement si, pour tout p EUR Q et tout a EUR 2, il existe q EUR Q avec (p, a, q) EUR T. On rappelle que tout automate ayant n états est équivalent à un automate déterministe complet ayant au plus 2" états. PREMIÈRE PARTIE Approche naïve D 18 -- Soit 54 un automate, déterministe ou non déterministe, avec n états. Montrer que L(fi) est vide si et seulement s'il ne contient aucun mot de longueur inférieure ou égale à n -- 1. Cl 19 -- Soit fit un automate déterministe complet ayant n états. Donner un automate ayant aussi n états qui reconnaît L(fll) , le complémentaire dans 2* de L(fl). Justifier votre réponse. Page 8 sur 10 Épreuve commune 2004 D 20 -- Soient % et 2' deux automates utilisant le même alphabet 2 avec respectivement n et n' états. Donner un automate ayant n x n' états qui reconnaît L(fl) n L(fl'). Justifier votre réponse. D 21 --- Soient 54 et fll' deux aùtomates déterministes complets utilisant le même alphabet ): avec respectivement n et n' états. Montrer que si 2 et 54' ne sont pas équivalents, il existe un mot de longueur au plus n X n' -- 1 qui est reconnu par l'un et non par l'autre, i. e. la longueur discriminante de 2 et R' est inférieure ou égale à n >< n' -- l. [322 -- En déduire un majorant pour la longueur discriminante de deux automates non équivalents quelconques avec n et n' états respectivement. SECONDE PARTIE Approche plus fine L'objectif de cette partie est de démontrer que la longueur discriminante de deux automates déterministes non équivalents, avec n et n' états respectivement, est inférieure ou égale à n + n' -- l. D23 -- Montrer sur un exemple, avec un alphabet à une seule lettre, qu'il existe des automates déterministes H et 2' non équivalents et qui reconnaissent les mêmes mots de longueur strictement inférieure à n + n' -- 1, où n (resp. n') désigne le nombre d'états de 54 (resp. de R'). On introduit un ensemble de définitions et de notations. Soit fll : <2, Q, T, [, F> un automate déterministe avec n états. On identifie 
l'ensemble Q des états de 54 avec

l'ensemble {1, 2, , n} des n premiers entiers naturels non nuls de sorte que 
chaque état est identifié par un
entier compris entre l et n. On suppose que l'on a I = { 1}.
On note { el, ez, en} la base canonique de l'espace vectoriel R". Pour un 
entier i compris entre 1 et n, le

vecteur e,- est donc le vecteur de R" dont toutes les composantes sont nulles 
sauf la i -ième qui vaut 1. On note 0
le vecteur nul de R".

Pour chaque lettre a de l'alphabet S, on définit une application linéaire (pa 
de R" dans R" par :
pour tout i avec 1 S i S n : 0 s'il existej, 1 .<.j _ 

Extrait du corrigé obtenu par reconnaissance optique des caractères



Mines Informatique MP 2004 -- Corrigé
Ce corrigé est proposé par Vincent Puyhaubert (Professeur en CPGE) ; il a été
relu par Samuel Mimram (ENS Lyon).

Ce problème est composé de deux problèmes complètement indépendants. Le premier 
problème propose l'écriture et l'étude d'un algorithme de tri, tandis que le 
second porte sur une notion de longueur discriminante de deux automates : 
c'est-à-dire
la longueur minimale d'un mot qui soit reconnu par l'un des automates et pas par
l'autre.
· L'algorithme de tri proposé dans le premier problème est celui du tri par 
baquets
(« bucket sort »). Le principe de tri est le suivant : pour trier une liste de
nombres, on commence par partitionner cette liste en 10 piles, suivant la valeur
du premier chiffre de chaque nombre. Puis on concatène les piles (sans changer
l'ordre de chaque pile), et on recommence en séparant cette fois selon la valeur
du second chiffre et ainsi de suite. Ce tri a l'avantage de fonctionner en temps
linéaire en la longueur de la liste, si l'on suppose que le nombre de chiffres 
de
chaque nombre est inférieur à une certaine valeur fixée maxc.
Ce problème comporte beaucoup de programmes à rédiger. La difficulté est bien
dosée, puisque les questions et les codes à écrire pour les deux premières 
parties sont très simples. Les difficultés techniques commencent lors de la 
troisième
partie avec notamment une preuve de terminaison de programme et des questions 
de complexité délicates à rédiger, ainsi que certains codes plus compliqués
à composer. Les dernières questions sont vraiment difficiles.
· Le second problème porte sur les automates et n'exige la rédaction d'aucun
code. Étant donnés deux automates A et A à n et n états qui ne reconnaissent
pas le même langage, on cherche une majoration de la longueur d'un plus
petit mot reconnu par seulement l'un des deux automates. Cette longueur 
est exprimée en fonction de n et n et est appelée longueur discriminante des
automates.
L'étude débute par des questions de cours concernant quelques constructions
très classiques sur les automates (construction d'un automate reconnaissant le
complémentaire d'un langage, l'intersection de deux langages). On en déduit
une première borne grossière de .
Dans la seconde partie, on utilise une représentation, assez inhabituelle en 
classe
préparatoire, d'automates par des applications linéaires. Il en résulte une 
borne
plus fine de cette longueur discriminante. Cette partie est plutôt formelle, 
mais
raisonnablement difficile si l'on garde les idées claires : aucune question ne 
nécessite de longue démonstration ou une dextérité particulière.
Il s'agit d'un sujet particulièrement intéressant et bien rédigé. Il touche à 
deux
parties importantes du programme d'informatique en classe préparatoire et permet
même de découvrir une approche originale des automates grâce à l'algèbre 
linéaire.
Il s'agit donc d'un entraînement idéal aux épreuves d'informatique des concours 
!

Indications
Problème d'algorithmique et de programmation
1 Commencer par écrire un programme qui compte, pour tout entier k compris
entre 0 et MAX_VAL le nombre d'occurrences de la valeur k dans la table.
3 Remarquer que vider une table revient simplement à mettre la première valeur
de la table à 0.
4 Ajouter un élément revient à exécuter trois opérations : récupérer la 
longueur n
de la table, mettre sa valeur dans la case d'indice n, puis incrémenter n.
5 Le plus simple consiste à faire une boucle pendant laquelle on ajoute l'un 
après
l'autre les éléments de la table T2 à la table T1.
6 Exprimer le nombre d'opérations élémentaires effectuées en fonction de la 
longueur de la boucle de la question 5.
8 Prouver que le nombre de chiffres de p est le plus grand entier k tel que 
10k-1
soit inférieur à p.
9 Combiner les deux programmes précédents.
10 Il s'agit de la somme des complexité des programmes précédents.
11 Remarquer qu'à la fin de la première étape, les données sont triées par ordre
croissant de leur chiffre de rang 1.
12 Utiliser l'invariant de boucle suivant :
P(i) :

À l'issue de la ie boucle, la table tronquée au rang i est triée.

où la table tronquée au rang i est la table obtenue en ne conservant que les 
chiffres
de rang 0 à i de chaque donnée.
13 Traduire quasiment mot pour mot l'étape b) proposée par l'énoncé en début de
troisième partie.
14 Même remarque en reprenant cette fois l'algorithme tout entier.
15 Compter le nombre d'opérations élémentaires effectuées lors de chaque boucle,
en utilisant les résultats des questions de complexité précédentes.
16 Remarquer que si les n données sont distinctes, leur maximum est de l'ordre 
de n
et en déduire l'ordre du nombre de chiffres de ce maximum.
17 Modifier l'étape d) de l'algorithme, en ne remettant dans la table T, à la 
fin de
l'étape r, que les données supérieures à 10r . Les autres données sont recopiées
dans une autre table table_finale au fur et à mesure.

Problème sur les automates
18 Un des sens est évident. Pour l'autre, considérer le plus petit mot de L(A) 
et
raisonner par l'absurde.
19 Considérer un automate avec les mêmes états, transitions et états initiaux, 
mais
avec pour états finaux Q r F.
20 Considérer un automate dont les états sont Q×Q , les états initiaux I×I , 
les états
finaux F × F et les transitions bien choisies.
21 Remarquer que les automates ne sont pas équivalents si et seulement si l'un 
des
deux langages L(A)  L(A ) ou L(A )  L(A) est non vide.
22 Déterminiser les deux automates.
23 Chercher des exemples d'automates tous deux à un seul état.
24 C'est extrêmement formel : pour un des sens, partir d'un calcul de i à j 
d'étiquette m. Écrire m = a1 . . . ak et utiliser la définition de m comme la 
composée
des applications a1 , . . . , ak et la définition de ces applications.
Pour la réciproque, introduire les vecteurs a1 (ei ), a2 (a1 (ei )) , . . . et 
remarquer
qu'ils sont tous non nuls, et donc des éléments de la base canonique.
25 Le produit scalaire d'un vecteur de la base canonique avec z vaut 0 ou 1. 
Déterminer dans quel cas il peut valoir 1, étant donnée la définition de z.
26 Remarquer que l'on a, par définition du produit scalaire canonique,
(E) · Z = m (e1 ) · z - m (e1 ) · z 
27 Utiliser le fait que si A et B sont deux ensembles de vecteurs et que A est 
inclus
dans B, alors Vect A est inclus dans Vect B.
28 C'est une conséquence de la même propriété pour les applications m , a et µ
(respectivement m , a et µ ).
29 Si w est un élément de Vk , introduire un mot m de longueur au plus k tel que
w = m (E), puis utiliser le résultat de la question précédente.
30 Prendre w appartenant à Vk+2 , introduire un mot de longueur inférieure ou 
égale
à k + 2 tel que w = m (E). Poser alors m = µa et utiliser l'hypothèse de la
question pour l'élément µ (E).
31 Remarquer que V0 est de dimension 1 et que les espaces (Vk )kN sont de 
dimension
au plus n + n .
32 Il existe par hypothèse un mot m de longueur k tel que m (E) · Z soit non 
nul.
Montrer alors qu'on peut trouver un mot m de longueur h qui satisfait cette
même propriété, en utilisant le résultat de la question précédente.
33 Raisonner comme pour la question 22.

I. Problème d'algorithmique et de programmation
Première partie
Tri d'entiers compris entre 0 et MAX_VAL
1 La méthode la plus rapide consiste à utiliser un tableau occurrences de 
longueur
MAX_VAL, dont toutes les cases sont initialisées à 0. On ne parcourt alors 
qu'une fois
le tableau : pour chaque valeur T[i] rencontrée, on incrémente de 1 la valeur 
de la
T[i]e case de occurrence .
Si l'on reprend mot à mot le principe de l'énoncé, on est tenté d'effectuer
deux boucles : pour tout entier k compris entre 0 et MAX_VAL, on parcourt
les n cases du tableau en comptant le nombre d'occurrence de la valeur k.
Ce faisant, la complexité de l'algorithme est donnée par le produit n MAX_VAL
ce qui ne correspond à celle demandée !
Cette première étape utilise 2n opérations élémentaires (on effectue n fois un
accès au tableau suivi d'une écriture dans occurrences). Une fois celle-ci 
terminée,
il n'y a plus qu'à réécrire le tableau T
2 Les programmes ci-dessous reprennent les principes de la question précédente.
Le premier programme crée le tableau occurrence. Le second utilise ce dernier 
pour
reconstituer une version triée du tableau T.
let occurrence T =
let n = T.(0) in
let a = make_vect MAX_VAL 0 in
for i=1 to n do
a.(T.(i)) <- a.(T.(i)) + 1; done; a;; On remarque que le code de ce premier programme utilise la variable MAX_VAL qu'il faut penser à définir avant de rédiger le programme. Il faudra donc, par exemple, commencer par écrire let MAX_VAL = 10 ;; let tri_simple T = let s = ref 1 in let p = occurrence T in for i=0 to (MAX_VAL - 1) do for j=1 to p.(i) do T.(!s) <- i; incr s done; done;;