Mines Informatique MP 2014

A 2014 INFO. MP
ECOLE DES PONTS PARISTECH,

SUPAERO (ISAE), ENSTA PARISTECH,
TELECOM PARISTECH, MINES PARISTECH,
MINES DE SAINT-ETIENNE, MINES DE NANCY,
TELECOM BRETAGNE, ENSAE PARISTECH (FILIERE MP)
ECOLE POLYTECHNIQUE (FILIERE TSI)

CONCOURS 2014
EPREUVE d'INFORMATIQUE
Filière : MP
Durée de l'épreuve : 3 heures.
L'utilisation d'une calculatrice est autorisée.

Sujet mis àla disposition des concours :
CYCLE INTERNATIONAL, ECOLES DES MINES, TELECOM SUDPARIS, TPE--EIVP.

L'én0ncé de cette épreuve comporte 8 pages.
Les candidats sont priés de mentionner de façon apparente

sur la première page de la copie :
INFORMATIQUE - MP

Recommandations aux candidats

0 Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une 
erreur
d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant 
les

raisons des initiatives qu'il est amené à prendre.

0 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é.

0 Il ne faut pas hésiter à formuler les commentaires qui semblent pertinents 
même

lorsque l'énoncé ne le demande pas explicitement.

Composition de l'épreuve
L'épreuve est constituée :

0 d'un exercice sur les automates et les langages : pages 2 et 3 ;
' d'un problème d'algorithmique et programmation : pages 3 à 8.

Épreuve d'informatique 2014

Première partie : automates et langages

Un alphabet Z est un ensemble fini d'éléments appelés lettres. Un mot sur 2 est 
une suite
finie, éventuellement vide, de lettres de Z ; la longueur d'un mot a est le 
nombre de lettres
composant a et est notée |a ; le mot de longueur nulle est noté 8. On note par 
E* l'ensemble
de tous les mots sur Z. Un langage sur X'. est une partie de Z*.

Soit a un mot sur un alphabet Z ; pour toute lettre x de 2, on note |a|x le 
nombre d'occurrences
de la lettre x dans le mot a.

On note N l'ensemble des entiers naturels.

On considère dans cet exercice l'alphabet Z = {a, 19}.
Soit f une application quelconque définie sur N et à valeurs dans N. On note 
L(f) l'ensemble
des mots a appartenant à Z* vérifiant l'égalité |a|a =f(|a|b).

El 1--On considère la fonction f1 définie par: Vn & N, f1(n) : 2. Dessiner un
automate reconnaissant le langage L(f1).

On considère la fonction f2 définie par : V n & N, fg(n) : 1 si n est pair et 
fg(n) : () sinon.

Cl 2 -- Décrire L(fg) par une expression rationnelle de la forme oc(bab + a + 
b)[3, où oc

et B sont des expressions rationnelles à déterminer. Justifier la réponse.
Remarque : on note aussi | l'opérateur noté + dans l'expression rationnelle 
ci-dessus.

Cl 3 -- Dessiner un automate non nécessairement déterministe reconnaissant le 
langage
décrit par l'expression rationnelle bab + a + 19. Cet automate devra 
nécessairement
posséder un seul état initial et un seul état final.

Cl 4 -- En s'appuyant sur l'expression rationnelle obtenue à la question Cl 2, 
compléter
l'automate obtenu à la question précédente pour obtenir un automate non 
déterministe
reconnaissant le langage L(f2). Cet automate devra nécessairement posséder un 
seul

état initial et un seul état final.

Cl 5 -- Déterminiser l'automate obtenu à la question précédente. On utilisera un
algorithme vu en cours et on ne fera apparaître que les états accessibles 
depuis l'état
initial.

El 6--Montrer que si f n'est pas majorée par une constante, alors L(f) n'est pas
rationnel.

Cl 7 -- On considère le langage L: sur 2 défini par L: = {a EUR 2* vérifiant 
|a|a : |a|b}.
Le langage L= est-il rationnel ?

Cl 8 -- On considère le langage Lg sur 2 défini par : Lg : {a EUR 2* avec |a|a 
S |a|b}. Le
langage Lg est-il rationnel ? On utilisera le résultat de la question 
précédente.

Épreuve d'informatique 2014

Cl 9 -- On considère le langage L> sur 2 défini par : L> : {u e 2* avec |u|a > 
|u|b}. Le
langage L> est-il rationnel ? On utilisera le résultat de la question 
précédente.

CI 10 -- Montrer que la réciproque de la proposition énoncée dans la question 
Cl 6 est
fausse.

Indication : on pourra admettre que le langage P des mots de la forme 19" où la 
est une
lettre et n est un entier premier n'est pas rationnel.

Seconde partie : logique et programmation
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
d'épreuve 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. Lorsque le
candidat écrira une fonction ou une procédure, il pourra faire appel a une 
autre fonction ou
procédure définie dans les questions précédentes ; il pourra aussi définir une 
procédure ou une
fonction auxiliaire. Enfin, si les paramètres d'une fonction ou d'une procédure 
à écrire sont
supposés vérifier certaines hypothèses, il ne sera pas utile, dans l'écriture 
de cette fonction ou
de cette procédure, de tester si les hypothèses sont bien vérifiées.

Dans les énoncés du problème, un même identificateur écrit dans deux polices de 
caractères
différentes désignera la même entité, mais du point de vue mathématique pour la 
police en
italique (par exemple n) et du point de vue informatique pour celle en romain 
(par
exemple n).

On ne se préoccupera pas d'un éventuel dépassement du plus grand entier codable 
dans le
langage de programmation choisi.

Indications pour la programmation

Caml

Si n est un entier, l'instruction

let A = make_matrix n n false;;

permet de construire une matrice carrée booléenne A a n lignes et n colonnes, 
et dont les
cases sont initialisées a false.

Fin des indications pour Caml

Pascal
On utilisera dans tout le sujet les déclarations ci-dessous.
CONST MAX = 100;

type Tableau_Boolean = array [O .. MAX -- 1] of Boolean;

type Matrice_Boolean = array [O .. MAX -- 1] of Tableau_Boolean;

Épreuve d'informatique 2014

On supposera que la constante MAX est suffisamment grande pour que les tableaux 
et matrices
de types Tableau_Boolean et Mat rice_Boolean puissent coder les tableaux et
matrices considérés dans ce problème.

Fin des indications pour Pascal

On considère un ensemble fini [7 de n propositions logiques distinctes : H : 
{Po, P1, ...,
Pn _ 1}. On suppose qu'un ensemble d'implications entre ces propositions, 
appelé ensemble

des implications initiales et noté ], a déjà été établi. On peut en général 
déduire d'autres
implications a partir de l'ensemble des implications initiales en utilisant la 
transitivité des
implications : pour deux propositions P et Q appartenant à 17, si Q se déduit 
de P a l'aide
d'une suite d'implications appartenant à ], on dit que << Pimplique Q >>, ce 
que l'on note

P => Q. Dans toute la suite, on s'intéresse aux implications que l'on peut 
déduire de I .
Pour tout P dans 17, on suppose que 1 contient l'implication P => P ; une telle 
implication,
nommée boucle, est notée P =>O P.

Si P et Q sont dans 17, la notation P =>1 Q signifie que l'implication P => Q 
appartient a I
(pour tout P dans 17, on a donc aussi P =>1 P).

EXEURHIpIBIZIOE=4,I= {P030P0, P130P1, P230P2, P3 30P3,P031P2,P231P3,
P3 31P0,P3 31P1}.

EXEURHIpIBZZ n=4,l= {P030P0, P130P1, P230P2, P330P3, P031P1, P131P2,
P231P1, P3 31P2}.

Pour P et Q dans 17, P implique Q (autrement dit, P => Q) s'il existe un entier 
k 2 () et k + 1
propositions PiO, Pi1, ..., Pi], Pi0 ..., Pik appartenant à IÎ tels que l'on 
ait :
. Pi0 : P,
' P@=Q,

. pour j vérifiant O 5 j 5 k -- ], l'implication Pi], => Pi0 + 1) appartient a 
I .

+ 1)'

Avec les notations ci-dessus, on dit alors qu'il existe une preuve de longueur 
k de
l'implication P => Q, ce que l'on note P =>k Q. Les implications de I sont donc 
les preuves de

longueur 0 (si P = Q) ou 1.

Dans l'exemple 1, on a PO =>2 P3 car on a PO =>1 P2 et P2 =>1 P3 ; on a aussi 
PO =>3 P3 car
on peut ajouter une boucle en considérant les trois implications PO =>O P0, P0 
=>1 P2 et
P2 =>1 P3. En revanche, on n'a pas : PO =>2 P1.

Dans l'exemple 1, les implications qui peuvent être prouvées mais qui 
n'appartiennent pas a I
sont : PO => P1, P0 => P3, P2 => P0, P2 => P1, P3 => P2.

CI 11 -- Pour l'exemple 2, donner la liste des implications qui peuvent être 
prouvées
mais qui n'appartiennent pas a I .

Cl 12 -- Soient P et Q dans 17 ; soient h et k deux entiers positifs ou nuls 
vérifiant:
h 5 k. Montrer que si on a P :>}, Q, alors on a aussi P =>k Q.

Épreuve d'informatique 2014

Cl 13 -- Soient P et Q dans 17. Montrer qu'on a l'implication P => Q si et 
seulement si
on a P :>" _ 1 Q.

Une matrice booléenne est une matrice dont les coefficients prennent uniquement 
les valeurs
faux et vrai (false et true en langage de programmation). Le produit de matrices
booléennes s'obtient selon la formule habituelle en prenant comme somme de deux 
valeurs
booléennes le << ou logique >> (disjonction, notée v) et comme produit de deux 
valeurs

booléennes le << et logique >> (la conjonction, notée A) ; le produit de deux 
matrices A et B est
noté A >< B. . . . . vrai vrai faux vrai Par exemple, s1 on cons1dere les deux matr1ces : AO : . et B = . , le faux vra1 vra1 faux . vrai vrai rodu1tA >< B vaut . . p 0 0 (vra1 faux) On ne s'intéressera dans ce probléme qu'à des matrices carrées ; la dimension d'une matrice carrée est son nombre de lignes (et donc de colonnes). Si k est un entier strictement positif, on obtient la matrice Ak en multipliant k -- 1 fois la matrice A par elle--même. Cl 14 -- On considère deux matrices carrées booléennes A et B de même dimension d. Il s'agit d'écrire en langage de programmation le calcul du produit A >< B. Caml : Écrire en Caml une fonction nommée mult telle que, si A et B codent A et B, alors mult A B renvoie une matrice codant le produit A >< B. Pascal : Écrire en Pascal une fonction nommée mult telle que si : 0 A et B, de type Mat rice_Boolean, codentA et B, 0 d, de type Integer, contient la valeur de d, alors mult (A, B, 01) renvoie une matrice, de type Matrice_Boolean, codant le produit A >< B. On considère encore l'ensemble [7 des n propositions logiques P0, P1, ..., Pn _ 1 et l'ensemble ] d'implications initiales entre ces propositions. On associe a 17 et 1 une matrice A carrée booléenne de dimension n définie de la façon suivante : - les lignes et les colonnes de A sont indicées de 0 a n -- 1 ; - soient i et j deux entiers vérifiant O S i S n -- 1 et O 5 j 5 n -- 1 ; en notant A[i, j] le coefficient de A situé sur la ligne d'indice i et la colonne d'indice j, A[i, j] vaut vrai si et seulement si l'implication P,-- => Pj appartient a I .

Ainsi, les matrices A1 et A2 correspondant respectivement à l'exemple 1 et à 
l'exemple 2
sont:

vrai faux vrai faux vrai vrai faux faux
faux vrai faux faux faux vrai vrai faux
faux faux vrai vrai faux vrai vrai faux
vrai vrai faux vrai faux faux vrai vrai
Matrice A1 Matrice A2

CI 15 --Montrer que, pour i etj vérifiant O S i S n -- 1, 0 5j S n -- 1 et pour 
tout k
strictement positif, le coefficient Ak[i, j] vaut vrai si et seulement si on a 
P,-- =>k Pj.

Épreuve d'informatique 2014

Cl 16 -- Montrer que, pour tout k 2 n -- 1, on aAk : A" _1.
On appelle fermeture transitive de A et on note F T(A) la matrice A" _ 1.

Cl 17 -- Il s'agit d'écrire en langage de programmation une fonction nommée FT 
qui
calcule la fermeture transitive de A en utilisant des multiplications de 
matrice.
Caml : Écrire en Caml la fonction FT telle que, si A code la matrice A, alors 
FT A
renvoie la matrice F T(A).
Pascal : Écrire en Pascal la fonction FT telle que si :

0 A, de type Mat ri ce_Boolean, code la matrice A,

0 n, de type Integer, contient la dimension de A,
alors FT (A, n) , de type Mat rice_Boolean, renvoie la matrice FT(A).

Cl 18 -- Soit P une proposition appartenant à H. Il s'agit d'écrire en langage 
de
programmation une fonction nommée deduction qui détermine toutes les 
propositions
Q appartenant à H telles que l'on ait P => Q. On utilisera pour cela la 
récursivité.
ATTENTION : On exige que la complexité de cette fonction soit de l'ordre de 112.
On ne justifiera pas la complexité de la fonction qui sera écrite.
Caml : Écrire en Caml la fonction de du et ion telle que si :

0 A code la matrice A,

0 i est un entier compris entre 0 et n -- 1,
alors de du ction A i renvoie un tableau de booléens de longueur n tel que, 
pour j
compris entre 0 et n -- 1, la valeur d'indice j de ce tableau vaut true si et 
seulement
si on a Pi => PJ,.
Pascal : Écrire en Pascal la fonction deduction telle que si :

0 A, de type Matrice_Boolean, code la matrice A,

0 n, de type Integer, contient la valeur de n,

0 i, de type Integer, contient un entier compris entre 0 et n -- 1,
alors deduction (A, n, i) renvoie un tableau de type Tableau_Boolean tel
que, pour j compris entre 0 et n -- 1, la valeur d'indice j de ce tableau vaut 
true si et
seulement si on a Pi => PJ_.

CI 19 -- Il s'agit d'écrire en langage de programmation une fonction nommée F 
T_bis
de complexité n3 calculant la matrice F T (A).
Caml : En utilisant la fonction de du et ion, écrire en Caml la fonction FT_bi 
s telle
que si A code la matrice A, alors FT_bi s A renvoie la matrice F T(A).
Pascal : En utilisant la fonction deduction, écrire en Pascal la fonction FT_bis
telle que si :

0 A, de type Matrice_Boolean, code la matrice A,

0 n, de type Integer, contient la valeur de n,
alors FT_bi s (A, n) renvoie la matrice F T(A).

Soient P et Q deux propositions appartenant à H. On dit que les propositions P 
et Q sont
équivalentes si on a : P => Q et Q => P.

Soit P appartenant à H. On dit ici que P est un axiome si on a la propriété 
suivante : quelle
que soit la proposition Q appartenant à 17, si on a Q => P, alors on a aussi P 
=> Q et donc
P et Q sont équivalentes ; autrement dit, P est équivalente à toute proposition 
qui l'implique.

-6-

Épreuve d'informatique 2014

Cl 20 -- Donner tous les axiomes dans l'exemple 1.
CI 21 -- Donner tous les axiomes dans l'exemple 2.

On pose B = F T(A). Des questions précédentes, on déduit que, si i et j sont 
deux entiers
compris entre 0 et n -- 1, on a Pi => Pj si et seulement si B[i, j] vaut vrai.

CI 22 -- Il s'agit, connaissant la matrice B, de programmer une fonction 
est_axiome qui
indique si une proposition donnée est ou non un axiome.
Caml : Écrire en Caml la fonction est_axiome telle que si :
0 B code la matrice B,
0 i est un entier compris entre 0 et n -- 1,
alors est_axiome B i renvoie la valeur true si Pi est un axiome et la valeur
fa 1 s e sinon.
Pascal : Écrire en Pascal la fonction est_axiome telle que si :
0 B, de type Matrice_Boolean, code la matrice B,
0 n, de type Integer, contient la valeur de n,
0 i, de type Integer, contient un entier compris entre 0 et n -- 1,
alors est_axiome (B, n, i) renvoie la valeur true si Pi est un axiome et la

valeur fa 1 s e sinon.

On appelle suite unidirectionnelle de propositions une suite (Q0, Q1, ..., Qh), 
où h est un
entier positif ou nul, telle que :

1. pour i vérifiant O S i 5 h, Qi appartient à H,

2. pour i vérifiant O S i 5 h -- 1, Qi => Qi+1,

3. pour i vérifiant O S i 5 h -- 1, Qi + 1 n'implique pas Qi-

El 23 -- Montrer que les propositions d'une suite unidirectionnelle de 
propositions sont
deux a deux distinctes.

Cl 24 -- Soit Q une proposition appartenant à 17. Montrer qu'il existe un 
axiome P avec
P => Q.

On admet le résultat suivant : on peut partitionner H en sous--ensembles de 
sorte que deux
propositions de H soient équivalentes si et seulement si elles appartiennent au 
même sous-
ensemble. On appelle classes d'équivalence ces sous--ensembles.
Par définition : les classes d'équivalence sont non vides, l'union des classes 
d'équivalence est
égale à H, l'intersection de deux classes d'équivalence est vide.

Dans l'exemple 1, il y a deux classes d'équivalence : les classes {Po, P2, P3} 
et {P1 }.

Cl 25 -- Donner les classes d'équivalence dans l'exemple 2.

CI 26 -- On considère une classe d'équivalence C contenant un axiome. Montrer 
que
toutes les propositions contenues dans C sont des axiomes.

Épreuve d'informatique 2014

On dit qu'une classe d'équivalence est une classe source si elle contient un 
axiome (auquel
cas tous les éléments de la classe source sont des axiomes).

Soit X une partie de 17. On dit ici que X est une axiomaîique si, quelle que 
soit la proposition
Q appartenant à 17, il existe une proposition P appartenant à X vérifiant P => 
Q.

Cl 27 -- Montrer qu'on obtient une axiomatique de cardinal minimum en 
choisissant
une et une seule proposition dans chacune des classes sources.

Cl 28 -- On pose encore B = F T(A). Il s'agit d'écrire en langage de 
programmation une
fonction nommée axiomatique qui détermine une axiomatique de cardinal minimum.
On pourra utiliser un tableau pour éliminer, lorsqu'on a choisi un axiome, les 
axiomes
qui lui sont équivalents.
Caml : Écrire en Caml la fonction axiomatique telle que, si B code la matrice B,
alors axiomatique B renvoie une liste d'entiers contenant les indices de
propositions de 17 formant une axiomatique de cardinal minimum.
Pascal :
On définit le type suivant :
type Pile = record

table : array [O .. MAX -- 1] of Integer;

nb : Integer;
end;
Si P est de type Pile, P code une pile de P . nb entiers situés dans P . table 
entre
les indices O et P . nb -- 1.

Écrire en Pascal la fonction axiomat ique telle que si :

0 B, de type Matrice_Boolean, code la matrice B,

0 n, de type Integer, contient la valeur de n,
alors axiomatique (B, n) renvoie un résultat de type Pile contenant les indices
de propositions de 17 formant une axiomatique de cardinal minimum.