ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES, ÉCOLES NATIONALES SUPÉRIEURES DE L'AÉRONAUTIQUE ET DE L'ESPACE, DES TECHNIQUES AVANCÉES, DES TÉLÉCOMMUNICATIONS, DES MINES DE PARIS, DES MINES DE SAINT-ÉTIENNE, DES MINES DE NANCY DES TÉLÉCOMMUNICATIONS DE BRETAGNE, ÉCOLE POLYTECHNIQUE
(Filière T.S.I.)
CONCOURS D'ADMISSION 2004
ÉPREUVE D'INFORMATIQUE
Filière MP
(Durée de l'épreuve : heures)
Sujet mis à la disposition des concours Cycle International, ENSTIM et TPE-EIVP.
Les candidats et les candidates sont priés de mentionner de façon apparente sur la première page de la copie : «INFORMATIQUE - Filière MP»
RECOMMANDATIONS AUX CANDIDATS ET CANDIDATES
L'énoncé de cette épreuve, y compris cette page de garde, comporte 10 pages.
Si, au cours de l'épreuve, un candidat ou une candidate repère ce qui lui semble être une erreur d'énoncé, il ou elle le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il ou elle a décidé de prendre.
Tout résultat fourni dans l'énoncé peut être utilisé pour les questions ultérieures même s’il n’a pas été démontré.
Il ne faut pas hésiter à formuler les commentaires qui semblent pertinents même lorsque l'énoncé ne le demande pas explicitement.
L'utilisation d'une calculatrice ou d'un ordinateur est interdite.
COMPOSITION DE L'ÉPREUVE
L'épreuve comporte deux parties indépendantes:
un problème d'algorithmique et de programmation, page 2 à 7 , à résoudre en 1 h 45 mn environ ;
un problème sur les automates, pages 8 à 10 , à résoudre en 1 h 15 mn environ.
1. 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 d'un tableau sera notée dans l'énoncé du problème.
c) Dans ce problème, nous appelons opérations élémentaires :
un accès en mémoire pour lire ou écrire la valeur d'une variable ou d'une case d'un tableau ;
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.
Soient et deux fonctions d'une même variable entière (resp. de deux mêmes variables entières et ). On dit que la fonction a un ordre de grandeur au plus égal à celui de la fonction s'il existe un entier strictement positif et un entier (resp. deux entiers et ) tels qu'on ait, pour tout (resp. et ), (resp. ). 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 et ont même ordre de grandeur. On pourra aussi dire que est un ordre de grandeur de .
Quand on calculera la complexité d'un algorithme , 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 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 . On étudie dans ce problème des algorithmes de tri d'entiers qui n'opèrent pas par comparaisons entre les données à trier.
e) Tout au long du problème, on fera l'hypothèse qu'il n'y a pas de limitation sur la taille de la mémoire disponible et qu'on peut donc manipuler des tableaux de dimensions quelconques. On ne se préoccupera pas non plus du fait que les entiers codés sur un ordinateur sont bornés et on fera comme s'ils ne l'étaient pas.
f) Indications pour la programmation
Caml : Ce qui est appelé tableau dans l'énoncé correspond à ce qui est appelé vecteur en Caml. En Caml, T. (i) représente la case d'un tableau .
Pascal : Dans tout le problème, on supposera qu'on écrit les différentes fonctions dans un fichier contenant les définitions suivantes:
const
MAX_DIM = 100;
MAX_VAL = 1000;
type
TABLE = array[0..MAX_DIM] of INTEGER;
BACS = array[0..9] of TABLE;
Première 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 entiers dont les valeurs sont toutes comprises entre 0 et une valeur maximum notée . 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 et , avec les données à trier suivantes : , 4 , les données triées sont alors : . - Expliciter un algorithme de tri, de complexité , fondé sur le principe suivant : on compte, pour chaque entier compris entre 0 à , 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é. - Il s'agit de programmer l'algorithme de la question . 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
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_simple telle que si
tableau est de type TABLE,
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.
Deuxième partie Gestion de tables
Dans toute cette partie, on considérera des tableaux dont le plus petit indice vaut et tels que les données du problème n'occupent pas nécessairement toutes les cases. Plus précisément, pour un tableau contenant données significatives du problème (typiquement, des données à trier) :
la case contiendra le nombre ;
les données significatives occuperont les cases .
Par exemple, on pourrait, pour trier les entiers 6, 1 et 7 , disposer d'un tableau dont les indices varient de 0 à 8 , mettre la valeur 3 (nombre de données à trier) dans , dans la valeur 6, dans la valeur 1, dans la valeur 7 et ne pas se préoccuper des contenus des cases d'indice 4 à 8 . Ce tableau peut être représenté ainsi :
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 contient les données 6, 1 et 7 . Une table est dite vide si vaut 0 . Une table sera dite triée si les entiers contenus dans les cases d'indices compris entre 1 et sont croissants au sens large.
Les questions à préparent la programmation du tri par baquets dont le principe sera indiqué après la question . - 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 est de type TABLE, vider(T) vide la table T. - Ajouter un entier à une table consiste à ajouter à 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 est réprésentée ci-dessous (les cases non remplies contiennent des valeurs non significatives) :
ajouter à la table la valeur 5 consiste à transformer en :
Caml : Écrire en Caml une fonction ajouter telle que, si T est un vecteur contenant une table et p un entier, ajouter transforme pour ajouter à la table . On supposera que la dimension de la table permet cet ajout.
Pascal : Écrire en Pascal une procédure ajouter telle que, si T est de type TABLE et p un entier, ajouter ( ) ajoute l'entier p à la table T . On supposera que la dimension de la table permet cet ajout. - Concaténer une table et une table consiste à ajouter successivement dans toutes les données de . Par exemple, si les tables et sont réprésentées ci-dessous :
la table devient après concaténation :
La table est inchangée.
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. - 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. - Il s'agit ici de définir une fonction max_valeurs qui détermine la plus grande valeur d'une table (c'est-à-dire le plus grand des entiers qui se trouvent entre les indices 1 et ).
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 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. - 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_chiffres telle que, si p est un entier positif ou nul, nombre_chiffres 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_chiffres(p) renvoie le nombre de chiffres de l'entier p. Il s'agit de définir une fonction max_chiffres qui calcule le nombre maximum de chiffres dans une écriture décimale des entiers contenus dans une table. Par exemple, si la table est :
le résultat doit valoir 4 .
Caml : Écrire en Caml une fonction max_chiffres 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_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. - Exprimer la complexité de la fonction max_chiffres appliquée à une table à l'aide :
du nombre de données de la table
du nombre maximum maxc de chiffres des données de la table .
On justifiera sommairement le résultat.
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 chiffre de rang d'un entier positif ou nul le -ième chiffre en partant de la droite de l'entier écrit dans la base 10 ; par définition, si est supérieur au nombre total de chiffres de , le chiffre de rang vaut alors 0 . Par exemple, pour l'entier , le chiffre de rang 1 est 7 , celui de rang 2 est 9 , celui de rang 3 est 5 , et le chiffre de rang pour est 0 .
Les données sont dans une table . L'objectif de l'algorithme est de transformer la table 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 . L'algorithme est le suivant :
Calculer le nombre maximum de chiffres des données de la table ; le noter maxc.
Pour qui varie de 1 à maxc, faire :
a) Vider les dix baquets, c'est-à-dire vider baquets[i] pour tout appartenant à ;
b) considérer successivement, de l'indice 1 à l'indice , les entiers de la table : en notant l'entier considéré, déterminer le chiffre de rang de l'entier ; en notant ce chiffre, ajouter à la table baquets ;
c) vider ;
d) pour variant de 0 à 9 , concaténer et baquets (le résultat de la concaténation se trouve dans ).
Indications : on pourra utiliser dans la suite du problème une fonction nommée puiss 10 , supposée déjà définie, qui calcule pour un entier positif ou nul la valeur de . 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 est une variable entière positive ou nulle, on pourra obtenir par puiss10 (p). - On applique l'algorithme du tri par baquets à la table ci-dessous, qui contient 8 données à trier.
8
57
423
50
603
7
20
453
27
Le nombre maximum de chiffres des données de la table vaut 3.
Pendant l'itération correspondant à la valeur 1 de :
à l'issue du point b), les baquets d'indices sont restés vides, baquets[0], baquets[3] et baquets[7] sont représentés ci-dessous :
baquets[0] :
2
50
20
baquets[3] :
3
423
603
453
...
baquets[7] :
3
57
7
27
....
à l'issue du point d), la table est :
8
50
20
423
603
453
57
7
27
Détailler de même les itérations correspondant aux valeurs 2 et 3 de . - Montrer qu'après l'exécution de l'algorithme du tri par baquets, la table est triée. - Il s'agit d'écrire en langage de programmation une fonction ou une procédure nommée distribuer qui effectue le point ) de l'algorithme du tri par baquets.
Caml : écrire en Caml une fonction distribuer telle que si :
T est un vecteur contenant une table,
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 Tr baquets effectue les opérations indiquées dans le point b) de l'algorithme du tri par baquets.
Pascal : écrire en Pascal une procédure distribuer telle que si :
T, de type Table, contient une table,
est un entier au moins égal à 1 ,
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( , , baquets) effectue les opérations indiquées dans le point ) de l'algorithme du tri par baquets. - 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 est un vecteur contenant une table, tri_baquets T transforme la table en 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 en une table triée en utilisant l'algorithme du tri par baquets. - On note le nombre de données à trier et 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 . - En supposant les données à trier toutes distinctes, donner une fonction exprimée uniquement à l'aide du nombre de données à trier telle que :
son ordre de grandeur minore la complexité du tri par baquets ;
son ordre de grandeur peut être atteint. - 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
2. Problème sur les automates - 1 h 15 mn environ
Longueur discriminante de deux automates
Deux automates et 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 et en fonction des nombres d'états de et .
Notations et terminologie
Un alphabet est un ensemble fini d'éléments appelés lettres. Un mot sur est une suite finie de lettres de ; le mot vide est noté . On désigne par l'ensemble des mots sur , y compris le mot vide. La longueur d'un mot , notée , est le nombre de lettres qui le composent. Un langage est une partie de .
Un automate est décrit par une structure , où :
est un alphabet ;
est un ensemble fini et non vide appelé ensemble des états de ;
est appelé l'ensemble des transitions ; étant donnée une transition ( ) , on dit qu'elle va de l'état à l'état et qu'elle est d'étiquette ; on pourra la noter ;
est appelé ensemble des états initiaux de ;
est appelé ensemble des états finals de .
On représente graphiquement l'automate ainsi :
un état est figuré par un cercle marqué en son centre par ; si appartient à , cela est figuré par une flèche entrante sans origine; si un état appartient à , cela est figuré par une flèche sortante sans but ;
une transition est figurée par une flèche allant de l'état vers l'état et étiquetée par la lettre .
Un calcul de est un chemin de la forme , avec pour ; est l'origine du calcul, son extrémité. L'étiquette de est le mot formé par la suite des étiquettes des transitions successives du chemin.
Un calcul de d'origine , d'extrémité et d'étiquette est dit réussi si on a et . Un mot est reconnu par s'il est l'étiquette d'un calcul réussi. Le langage reconnu par , noté , est l'ensemble des mots reconnus par . Deux automates et sont dits équivalents si on a .
L'automate est dit déterministe si ne contient qu'un élément et si, pour tout , il existe au plus un état avec . L'automate est dit complet si et seulement si, pour tout et tout , il existe avec .
On rappelle que tout automate ayant états est équivalent à un automate déterministe complet ayant au plus états.
Première partie
Approche naïve
- Soit un automate, déterministe ou non déterministe, avec états. Montrer que est vide si et seulement s'il ne contient aucun mot de longueur inférieure ou égale à . - Soit un automate déterministe complet ayant états. Donner un automate ayant aussi états qui reconnaît , le complémentaire dans de . Justifier votre réponse. - Soient et deux automates utilisant le même alphabet avec respectivement et états. Donner un automate ayant états qui reconnaît . Justifier votre réponse. Soient et deux automates déterministes complets utilisant le même alphabet avec respectivement et états. Montrer que si et ne sont pas équivalents, il existe un mot de longueur au plus qui est reconnu par l'un et non par l'autre, i.e. la longueur discriminante de et est inférieure ou égale à . - En déduire un majorant pour la longueur discriminante de deux automates non équivalents quelconques avec et é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 et états respectivement, est inférieure ou égale à . - Montrer sur un exemple, avec un alphabet à une seule lettre, qu'il existe des automates déterministes et non équivalents et qui reconnaissent les mêmes mots de longueur strictement inférieure à , où (resp. ) désigne le nombre d'états de (resp. de ).
On introduit un ensemble de définitions et de notations.
Soit un automate déterministe avec états. On identifie l'ensemble des états de avec l'ensemble des premiers entiers naturels non nuls de sorte que chaque état est identifié par un entier compris entre 1 et . On suppose que l'on a .
On note la base canonique de l'espace vectoriel . Pour un entier compris entre 1 et , le vecteur est donc le vecteur de dont toutes les composantes sont nulles sauf la -ième qui vaut 1 . On note 0 le vecteur nul de .
Pour chaque lettre de l'alphabet , on définit une application linéaire de dans par :
L'existence et l'unicité de l'application découlent du fait que est déterministe et de la linéarité de .
Si est un mot non vide de , où sont des lettres de , on pose :
On note l'identité de dans .
On appelle la somme des vecteurs quand décrit l'ensemble des états finals : .
Enfin, si et sont deux vecteurs de , on note le produit scalaire de et de .
Exemple :
On peut aussi constater les égalités suivantes : . Soient et deux entiers et vérifiant et . Montrer qu'il existe un calcul d'origine , d'extrémité et d'étiquette si et seulement si on a . - Soit . Donner les valeurs possibles du produit scalaire et indiquer une condition nécessaire et suffisante portant sur ce produit scalaire pour que soit un mot reconnu par .
Dans la suite du problème, on considère en plus de l'automate déterministe un automate déterministe . Les notations utilisées pour sont les mêmes que celles utilisées pour à cela près que tous les identificateurs sont dotés d'un «prime» (on a donc : et les vecteurs de la base canonique de sont notés ).
Si et sont des vecteurs respectivement de et de , on note ( ) le vecteur de obtenu en concaténant et ; plus précisément, le vecteur est défini par :
Par exemple, si et est le vecteur .
On pose :
Pour tout mot de , on définit une application linéaire de dans par :
pour tout et pour tout
(on admet la linéarité de ). - Soit ; indiquer les valeurs possibles du produit scalaire et, selon ces valeurs, préciser l'appartenance de à et .
Pour , on note le sous-espace vectoriel de engendré par est donc engendré par le vecteur ( ). - Monter que, pour , on a . - Soit ; on suppose que s'écrit sous la forme : , où et . Montrer l'égalité . Soit et montrer : . On suppose qu'il existe tel que ; montrer l'égalité . Montrer qu'il existe un entier tel que, pour tout . - Montrer que si et ne sont pas équivalents, il existe un mot de longueur inférieure ou égale à qui est accepté par l'un et pas par l'autre, i.e. que est un majorant de la longueur discriminante de et . - En déduire un majorant pour la longueur discriminante de deux automates quelconques ayant et états respectivement.
FIN DU PROBLÈME SUR LES AUTOMATES
Mines Option Informatique MP 2004 - Version Web LaTeX | WikiPrépa | WikiPrépa
