É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 2000
ÉPREUVE D'INFORMATIQUE
Filière MP(Durée de l'épreuve: heures)
Sujet mis à la disposition des concours ENSAE (Statistique), ENSTIM, INT 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 11 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 est inutile et interdite.
COMPOSITION DE L'ÉPREUVE
L'épreuve comprend un exercice et deux problèmes.
Exercice: l'exercice de théorie des automates, page 2, à résoudre en 30 minutes environ. Cet exercice est indépendant du reste de l'épreuve.
Premier problème: le problème de logique, page 2 , à résoudre en 75 minutes environ. Attention! Ce problème servira de base au deuxième problème. La résolution totale du premier problème n'est pas nécessaire à la résolution du deuxième problème, seule la compréhension de l'énoncé est nécessaire.
Deuxième problème: un problème de programmation au choix parmi deux, à résoudre en 75 minutes environ. Attention ! Pour le deuxième problème, un seul choix est possible. Le candidat ou la candidate précisera son choix sur sa copie et seul le problème correspondant sera corrigé. Les deux choix possibles sont:
le problème de programmation en langage Pascal, page 5 , pour les candidats et les candidates désirant choisir ce langage;
le problème de programmation en langage Caml, page 8, pour les candidats et les candidates désirant choisir ce langage.
1 Exercice sur les automates - 30 mn environ
Il est demandé aux candidats et candidates une grande rigueur dans la rédaction. Si la première question est l'application d'une méthode ne demandant aucune justification, toutes les affirmations dans les solutions des autres questions doivent être rigoureusement justifiées.
L'alphabet est fixé. On considère l'automate représenté ainsi:
L'ensemble des états de l'automate est . Les états initiaux et sont marqués par une flèche entrante et sans origine. Les états terminaux et sont marqués par une flèche sortante et sans destination. On note l'ensemble des mots sur .
Déterminiser l'automate , i.e. calculer un automate déterministe équivalent à .
Montrer que , le langage des mots acceptés par , est formé des mots de qui ne contiennent pas le facteur aaa.
Montrer que le langage associé à l'expression rationnelle est l'ensemble de tous les mots sur , c'est-à-dire .
En déduire une expression rationnelle dont le langage associé est .
FIN DU PROBLÈME SUR LES AUTOMATES
2 Problème de logique - 75 mn environ
Dans ce problème, on se propose de définir et de démontrer une méthode permettant de savoir si une formule de la logique des propositions est une tautologie.
Rappels et notations
Soit l'ensemble contenant les entiers 0 et 1 . On définit les opérations binaires et par et où et sont respectivement le plus grand et le plus petit des deux entiers et . On définit l'opération unaire par et . On admettra les propriétés élémentaires de ces trois opérations: commutativité, associativité, éléments neutres et absorbants, diverses distributivités, etc.
Soit un ensemble dénombrable de variables propositionnelles. On note l'ensemble des formules bien formées construites à partir des variables de , de deux constantes notées pour vrai et pour faux, du connecteur unaire de négation noté , des connecteurs binaires de disjonction noté , de conjonction noté et d'implication noté et, enfin, des parenthèses.
Les variables de et les constantes et sont appelées des formules atomiques.
Une valuation est une application . Une valuation se prolonge en une interprétation définie par:
si alors
et ;
si alors: ; .
Soit et deux formules, si pour toute valuation on a alors on dit que et sont logiquement équivalentes et on le note . Si alors est appelée une tautologie. Si alors est appelée une contradiction.
Une formule conjonctive est soit une formule atomique soit une conjonction de formules avec . Une formule conjonctive élémentaire est soit une formule atomique soit une conjonction de formules atomiques.
Une formule disjonctive est soit une formule atomique soit une disjonction de formules avec . Une formule disjonctive élémentaire est soit une formule atomique soit une disjonction de formules atomiques.
Une implication élémentaire est une implication où est une formule conjonctive élémentaire et est une formule disjonctive élémentaire.
Afin de vérifier si une formule est une tautologie, on se propose de se ramener à la vérification qu'une ou plusieurs implications élémentaires sont des tautologies.
Problème
Dans ce problème, on utilisera pour désigner des variables propositionnelles tandis que les lettres majuscules désigneront des formules quelconques.
Démontrer que pour que soit une tautologie, il faut et il suffit que pour toute valuation on ait lorsque .
À quelles conditions une implication élémentaire est-elle une tautologie? Les implications élémentaires suivantes sont-elles des tautologies?
(a)
(b)
(c)
(d)
Démontrer que si alors .
Démontrer que si alors .
Démontrer .
Démontrer .
Démontrer et .
On a , en déduire et .
Démontrer que est une tautologie si et seulement si et sont des tautologies. Puis démontrer que pour que soit une tautologie il faut et il suffit que et soient des tautologies.
On a , démontrer que est une tautologie, si et seulement si et sont des tautologies. Puis démontrer que pour que soit une tautologie, il faut et il suffit que et soient des tautologies.
On a , démontrer . Puis démontrer .
Démontrer que est une tautologie, si et seulement si et sont des tautologies. Puis démontrer que pour que soit une tautologie, il faut et il suffit que et soient des tautologies.
Déduire des questions précédentes un algorithme prenant en arguments deux formules et et qui permet de savoir si une implication est une tautologie en se ramenant à la vérification qu'une ou plusieurs implications élémentaires sont des tautologies. L'algorithme sera exprimé en langage naturel.
Expliquer comment utiliser l'algorithme de la question 13 pour savoir si une formule est une tautologie.
Expliquer comment utiliser l'algorithme de la question 13 pour savoir si une formule est une contradiction.
La -mesure d'une formule , notée , est définie comme étant le nombre d'occurrences de connecteurs qu'elle contient. Ainsi puisque la formule contient deux occurrences du connecteur de conjonction, une occurrence du connecteur de disjonction et une occurrence du connecteur de négation.
La g-mesure ou mesure à gauche d'une formule , notée est définie par :
La -mesure ou mesure à droite d'une formule , notée est définie par :
La i-mesure d'une implication , notée , est définie comme étant la somme de et de .
(a) Démontrer que la i-mesure d'une implication élémentaire est nulle.
(b) Démontrer que et que .
(c) Démontrer que et que .
(d) Expliquer comment démontrer la terminaison de l'algorithme de la question 13 en vous servant de la i-mesure . La rédaction complète de la démonstration étant particulièrement longue, les candidats et les candidates se contenteront de l'esquisser en donnant quelques éléments de celle-ci.
Démontrer que la formule est une tautologie en utilisant l'algorithme construit dans ce problème.
FIN DU PROBLÈME DE LOGIQUE
3 Problème de programmation en Pascal - 75 mn environ
UNIQUEMENT POUR LES CANDIDATS ET LES CANDIDATES CHOISISSANT LE LANGAGE PASCAL
Dans ce problème de programmation, on se propose de mettre en œuvre l'algorithme trouvé dans le problème de logique page 2 . Il n'est pas nécessaire d'avoir totalement résolu le problème de logique pour résoudre le problème de programmation : la connaissance et une bonne compréhension du sujet du problème de logique doivent suffire.
N.B. Dans les programmes, procédures et fonctions, qui seront demandés, on ne traitera pas les cas d'erreurs. On supposera que les arguments ont toujours des valeurs admissibles.
Mise en œuvre des formules
On se donne une constante exprimée en langage Pascal VMAX . On suppose que l'ensemble des variables propositionnelles est composé des variables pour entier compris entre 1 et VMAX. On se donne les constantes suivantes exprimées en langage Pascal: CSTE_F , CSTE_V , CSTE_VARI , CSTE_ET , CSTE_OU , CSTE_IMPL et CSTE_NON .
On suppose l'existence d'un type formule décrivant des données Pascal servant à représenter les formules de la logique des propositions pour le programme qui sera écrit. On appellera représentation d'une formule la donnée du langage correspondant à cette formule. Les représentations des formules sont construites à l'aide des fonctions suivantes que l'on suppose déjà programmées et utilisables:
function vrai : formule ;
dont le résultat est la représentation de la constante ;
function faux : formule ;
dont le résultat est la représentation de la constante ;
function variable(K : integer) : formule ;
telle que si l'argument est compris entre 1 et VMAX alors variable (K) est la représentation de la variable propositionnelle ;
function et ( : formule) : formule ;
telle que si U et V sont les représentations respectives des formules et alors et ( ) est la représentation de la formule ;
function ou ( : formule) : formule ;
telle que si U et V sont les représentations respectives des formules et alors ou ( ) est la représentation de la formule ;
function implique( : formule) : formule ;
telle que si U et V sont les représentations respectives des formules et alors implique( ) est la représentation de la formule ;
function non ( : formule) : formule ;
telle que si U est la représentation d'une formule alors non ( U ) est la représentation de la formule .
Toutes les représentations de formules bien formées que nous considèrerons sont construites à l'aide des fonctions précédentes. Les fonctions suivantes sont aussi supposées être programmées et utilisables. Elles permettent d'identifier la nature d'une formule et d'accéder à ses sous-formules éventuelles.
function code(F : formule) : integer ;
qui renvoie un code numérique, CSTE_V, CSTE_F, CSTE_VARI, CSTE_ET, CSTE_OU, CSTE_IMPL, ou CSTE_NON, selon que la formule dont la représentation est est la constante , la constante , une variable propositionnelle, une conjonction, une disjonction, une implication ou une négation;
function indice(F : formule) : integer ;
qui prend en argument la représentation d'une variable propositionnelle avec , VMAX et qui renvoie l'indice de cette variable ;
function gauche(F : formule) : formule ;
qui prend en argument la représentation d'une formule ou ou et renvoie la représentation de la formule ;
function droite(F : formule) : formule ;
qui prend en argument la représentation d'une formule ou ou et renvoie la représentation de la formule ;
function argument(F : formule) : formule ;
qui prend en argument la représentation d'une formule et renvoie la représentation de la formule .
Mise en œuvre des listes de formules
Pour représenter les ensembles de formules, on utilisera des listes de formules de type liste_de_formules. Les fonctions de construction relatives à ce type devront être les suivantes:
function liste_vide : liste_de_formules ;
qui renvoie la représentation d'une liste vide de formules;
function ajoute(F : formule, L : liste_de_formules) : liste_de_formules ; qui prend en argument une formule et une liste de formules et renvoie une liste contenant F et les formules déjà présentes dans .
Les fonctions d'accès aux listes de formules devront être les suivantes:
function est_vide(L : liste_de_formules) : boolean ;
qui renvoie true si son argument est une liste vide de formules, false sinon;
function un_element(L : liste_de_formules) : formule ;
qui prend en argument une liste non vide de formules et qui renvoie une formule de la liste;
function reste(L : liste_de_formules) : liste_de_formules ;
qui prend en argument une liste non vide et qui renvoie une liste de formules contenant les formules présentes dans L à l'exception de un_element (L).
1 - Donner une définition du type liste_de_formules.
2 - Écrire les deux fonctions de construction.
3 - Écrire les trois fonctions d'accès.
Mise en œuvre des ensembles de formules
4 - Dans la suite du problème, on suppose toujours qu'il y a au plus VMAX variables propositionnelles indicées de 1 à VMAX où VMAX est une constante entière strictement positive. En raison du rôle particulier des variables propositionnelles, on décide de représenter un ensemble de formules par un enregistrement de type ensemble_de_formules contenant:
un booléen valant true si et seulement si la constante appartient à l'ensemble;
un booléen valant true si et seulement si la constante appartient à l'ensemble;
un tableau de VMAX booléens, le -ième élément de ce tableau valant true si et seulement si la -ième variable propositionnelle appartient à l'ensemble;
une liste de formules de type liste_de_formules contenant les formules qui ne sont pas des formules atomiques.
N.B. On acceptera que la liste de formules puisse contenir plusieurs fois une même formule. On dira alors que la liste contient plusieurs occurrences de la formule.
Donner une définition du type ensemble_de_formules.
5 - Écrire la fonction
function ensemble_vide : ensemble_de_formules ;
dont le résultat est un ensemble vide de formules.
6 - Écrire la fonction
function que_des_variables(E : ensemble_de_formules) : boolean ;
dont le résultat est true si l'ensemble E est vide ou bien ne contient que des formules atomiques, false sinon.
7 - Écrire la fonction
function intersection(E1,E2 : ensemble_de_formules) : boolean ;
qui renvoie true si l'ensemble des variables propositionnelles éléments de E1 a une intersection non vide avec celui des variables propositionnelles éléments de E2, false sinon.
8 - Écrire la fonction
function ajouter_formule(E : ensemble_de_formules ;
F : formule ) : ensemble_de_formules ;
qui a pour résultat l'ensemble de formules contenant et les formules éléments de .
9 - Écrire la procédure
procedure formule_suivante( E : ensemble_de_formules ; : ensemble_de_formules ; : formule) ;
Cette procédure prend en argument un ensemble de formules et deux variables et . On suppose que E ne contient pas que des formules atomiques. La procédure choisit une formule dans , n'importe laquelle sauf une formule atomique, et la met dans . Elle met dans , un ensemble contenant les formules de à l'exception d'une occurrence de la formule .
page 7/11
TOURNEZ LA PAGE S'IL VOUS PLA
Mise en œuvre de l'algorithme
10 - Soit U la représentation d'un ensemble de formules avec et V la représentation d'un ensemble de formules avec , écrire la fonction
function verifier( : ensemble_de_formules) : boolean ;
dont le résultat est true si la formule est une tautologie, false sinon. On s'inspirera utilement du problème de logique page 2.
11 - À l'aide des procédures et fonctions précédentes, écrire la fonction
function tautologie (F : formule) : boolean ;
qui renvoie true si est une tautologie, false sinon.
FIN DU PROBLÈME DE PROGRAMMATION EN PASCAL
4 Problème de programmation en Caml - 75 mn environ
UNIQUEMENT POUR LES CANDIDATS ET LES CANDIDATES CHOISISSANT LE LANGAGE CAML
Dans ce problème de programmation, on se propose de mettre en œuvre l'algorithme trouvé dans le problème de logique page 2 . Il n'est pas nécessaire d'avoir totalement résolu le problème de logique pour résoudre le problème de programmation : la connaissance et une bonne compréhension du sujet du problème de logique doivent suffire.
N.B. Dans les programmes qui seront demandés, on ne traitera pas les cas d'erreurs. On supposera que les arguments ont toujours des valeurs admissibles.
Mise en œuvre des formules
On se donne une constante exprimée en langage Caml : let VMAX ; On suppose que l'ensemble des variables propositionnelles est composé des variables pour entier compris entre 1 et VMAX.
On désire définir un type formule décrivant des données Caml servant à représenter les formules de la logique des propositions pour le programme qui sera écrit. On appellera représentation d'une formule la donnée du langage correspondant à cette formule. Les fonctions de construction ou constructeurs de formules qui devront être disponibles sont les suivantes:
vrai de type formule
qui est la représentation de la constante ;
faux de type formule
qui est la représentation de la constante ;
variable : integer -> formule
telle que si l'argument est compris entre 1 et VMAX alors variable est la représentation de la variable propositionnelle ;
et : formule * formule -> formule
telle que si les arguments U et V sont les représentations respectives des formules et alors et ( ) est la représentation de la formule ;
ou : formule * formule -> formule
telle que si les arguments U et V sont les représentations respectives des formules et alors ou ( ) est la représentation de la formule ;
implique : formule * formule -> formule
telle que si les arguments U et V sont les représentations respectives des formules et alors implique ( ) est la représentation de la formule ;
non : formule -> formule
telle que si l'argument U est la représentation d'une formule alors non ( U ) est la représentation de la formule .
1 - Donner une définition du type formule.
Mise en œuvre des listes de formules
Pour représenter les ensembles de formules, on utilisera des listes de formules de type liste_de_formules. Les fonctions de construction relatives à ce type devront être les suivantes:
liste_vide : unit -> liste_de_formules
qui construit la représentation d'une liste vide de formules;
ajoute : formule * liste_de_formules -> liste_de_formules
qui prend en argument une formule et une liste de formules et renvoie une liste contenant et les formules déjà présentes dans .
Les fonctions d'accès aux listes de formules devront être les suivantes:
est_vide : liste_de_formules -> bool
qui renvoie true si son argument est une liste vide, false sinon;
un_element : liste_de_formules -> formule
qui prend en argument une liste non vide de formules et qui renvoie une formule de la liste;
reste : liste_de_formules -> liste_de_formules
qui prend en argument une liste non vide et qui renvoie une liste de formules contenant les formules présentes dans L à l'exception de un_element (L).
2 - Donner une définition du type liste_de_formules.
3 - Écrire les deux fonctions de construction.
4 - Écrire les trois fonctions d'accès.
Mise en œuvre des ensembles de formules
5 - Dans la suite du problème, on suppose toujours qu'il y a au plus VMAX variables propositionnelles indicées de 1 à VMAX où VMAX est une constante entière strictement positive. En raison du rôle particulier des variables propositionnelles, on décide de représenter un ensemble de formules par une donnée de type ensemble_de_formules contenant:
un booléen valant true si et seulement si la constante appartient à l'ensemble;
un booléen valant true si et seulement si la constante appartient à l'ensemble;
un tableau de VMAX booléens, le -ième élément de ce tableau valant true si et seulement si la -ième variable propositionnelle appartient à l'ensemble;
une liste de formules de type liste_de_formules contenant les formules qui ne sont pas des formules atomiques.
N.B. On acceptera que la liste de formules puisse contenir plusieurs fois une même formule. On dira alors que la liste contient plusieurs occurrences de la formule.
Donner une définition du type ensemble_de_formules.
6 - Écrire la fonction
ensemble_vide : unit -> ensemble_de_formules
dont le résultat est un ensemble vide de formules.
7 - Écrire la fonction
que_des_variables : ensemble_de_formules -> bool
dont le résultat est true si l'argument est vide ou bien ne contient que des représentations de formules atomiques, false sinon.
8 - Écrire la fonction
intersection : ensemble_de_formules * ensemble_de_formules -> bool
qui prend en arguments deux ensembles de formules E1 et E2; elle renvoie true si l'ensemble des variables propositionnelles éléments de E1 a une intersection non vide avec celui des variables propositionnelles éléments de E2, false sinon.
9 - Écrire la fonction
ajouter_formule : ensemble_de_formules * formule -> ensemble_de_formules
Cette fonction a pour résultat l'ensemble de formules contenant les formules éléments de son premier argument et son deuxième argument.
10 - Écrire la fonction
formule_suivante : ensemble_de_formules -> ensemble_de_formules * formule
Cette fonction prend en argument un ensemble E de formules. On suppose que E ne contient pas que des formules atomiques. La fonction choisit une formule dans , n'importe laquelle sauf une formule atomique. Elle a pour résultat le couple ( ) où est un ensemble de formules contenant les formules de à l'exception d'une occurrence de la formule .
Mise en œuvre de l'algorithme
11 - Écrire la fonction
verifier : ensemble_de_formules * ensemble_de_formules -> bool
prenant en arguments deux ensembles de formules et . Si est la représentation d'un ensemble de formules avec et si V est la représentation d'un ensemble de formules avec alors le résultat de cette fonction doit être true si la formule est une tautologie, false sinon. On s'inspirera utilement du problème de logique page 2 .
12 - À l'aide des fonctions précédentes, écrire la fonction
tautologie : formule -> bool
qui renvoie true si son argument est une tautologie, false sinon.
FIN DU PROBLÈME DE PROGRAMMATION EN CAML
FIN DE L'ÉPREUVE
Mines Option Informatique MP 2000 - Version Web LaTeX | WikiPrépa | WikiPrépa
