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;;