Mines Informatique MP 2002

J . 2062

A 2002 -- INF -- MP

ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES,
ÉCOLES NATIONALES SUPÉRIEURES DE L' AÉRONAUTIQUE ET DE L'ESPACE,
DES TECHNIQUES AVANCÉES, DES TELECOMMUNICATIONS,
DES MINES DE PARIS, DES MINES DE SAINT--ÊTOENNE, DES MINES DE NANCY,
DES TÉLÉCOMMUNÏCATIONS DE BRETAGNE
ÉCOLE POLYTECHNIQUE
(Filière T.S.I.)

CONCOURS D'ADMISSION 2002

É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 8 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.

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

. Il ne faut pas hésiter à formuler les commentaires qui semblent pertinents 
même lorsque
l'énoncé ne les demande pas explicitement.

. L'utilisation d'une calculatrice ou d'un ordinateur est interdite.

COMPOSITION DE L'ÉPREUVE

L'épreuve comprend trois parties indépendantes :

0 un exercice de logique des propositions, n° 1 page 2, à résoudre en 30 mn 
environ ;
0 un problème d'algofithmique, n° 2 page 3, à résoudre en 120 mn environ ;
- un exercice sur les automates, n° 3 page 7, à résoudre en 30 mn environ.

page I/8
Tournez la page S.V.P.

Épreuve d'Informatique

1 Exercice de logique des propositions ---- 30 mn environ

Définitions et notations

On considère un ensemble fini de n variables propositionnelles V : {p1, . . . 
,pn}, et l'ensemble 3"v des
formules construites à partir des variables propositionnelles de V, des 
connecteurs usuels de conjonction

(noté A) et de disjonction (noté V), et de la négation (--.), On considère que 
la formule sans aucune variable

propositionnelle (formule vide), notée T, est un élément de S'y.
Toutes les formules considérées dans cet exercice sont des formules de 3'v.
Pour toute formule F, VF désigne l'ensemble des variables propositionnelles qui 
apparaissent dans F.
On appelle littéral une variable propositionnelle ou bien la négation d'une 
variable propositionnelle. Le

littéral est dit positif dans le premier cas, et négatif dans le second cas.
On appelle clause toute formule de la forme 11 V . . . V lq, où q ; 1 et 11, . 
. . ,lq sont des littéraux deux

à deux distincts.
On dit qu'une formule est sous forme normale conjonctive si elle est sous la 
forme C1 /\ . . . A C..., où

m > 0 et C1, . . . ,C... sont des clauses (pour m = 0, on obtient T).
Une formule de Ham est une formule sous forme normale conjonctive telle que 
chacune de ses clauses

comporte au plus un littéral positif.
Enfin, rappelons qu'une formule est satisfiable s'il existe une valuation à 
valeurs dans {vrai, faux}

de ses variables propositionnelles qui rende la formule vraie. La formule T est 
considérée comme étant
satisfiable.

Énoncé de l'exercice

1 -- Dans les exemples suivants, préciser si les formules sont satisfiables ou 
non. Quand cela est possible,
donner un exemple de valuation des variables propositionnelles qui rende la 
formule vraie.
i) ("Pi VP2) A(P1 V "1292 V "P3)
ii) (P2) /\ ("'P1 V "'P3) /\ ("'P2) A (P1 V "'P3 V "'P4)
iii) (P2) A ("1171 V "';02) A (Pi V "*P2) /\ (P1 V '"P2 V "*P3)

2 -- Soit H une formule sous forme normale conjonctive telle que chacune de ses 
clauses contienne au
moins un littéral négatif. Montrer que H est satisfiable en exhibant une 
valuation de V.

3 -- Soit H une formule de Horn telle qu'une de ses clauses soit restreinte à 
un littéral positif Pk (où le est
dans {l, . . . , n}), et qu'aucune autre de ses clauses ne soit restreinte à 
fipk. Montrer que l'on peut
construire à partir de H une formule de Horn H' telle que:

-- VH' Ç VH\{Pk},
-- H est satisfiable si et seulement si H ' est satisfiable.

4 -- Déduire des deux questions précédentes un algorithme permettant de 
déterminer si une formule de
Horn H est satisfiable ; la complexité dans le pire des cas de cet algorithme 
doit être majorée par un
polynôme en n et m (où n et m désignent respectivement le nombre de variables 
propositionnelles et
le nombre de clauses de H), propriété que l'on justifiera. Cet algorithme sera 
explicité sans utiliser un

langage de programmation.
5 -- Appliquer l'algorithme de la question 4 à l'exemple iii) de la question ].

FIN DE L'EXERCICE DE LOGIQUE DES PROPOSITIONS

page 2/8

Épreuve commune 2002

2 Problème d'algorithmique -- 120 mn environ

Préüminaire. Il faudra écrire des programmes à l'aide d'un langage de 
programmation qui pourra être
soit Pascal, soit Caml, tout autre langage étant exclu. Indiquer le langage de 
programmation choisi.

Attention! Il est interdit de modifier ce choix au cours de l'épreuve.

Le problème du sac à dos

On considère le problème suivant : Madame X doit partir en voyage ; elle 
emporte un sac à dos qui peut
supporter au maximum un poids Q, poids qui est un entier strictement positif. 
Par ailleurs, elle dispose de
n objets numérotés par 0, l, , n -- 1. Pour tout z' appartenant à O, 1, , n -- 
l, l'objet de numéro
z' possède deux caractéristiques : son utilité notée u,-- et son poids noté 
p,-- qui sont des entiers strictement
positifs. Madame X désire emporter certains de ces objets dans son sac à dos; 
le poids total des objets
emportés ne doit pas dépasser Q ; elle cherche à maximiser la somme des 
utilités des objets qu'elle emporte

parmi les contenus possibles ne dépassant pas au total le poids Q.

Attention: pour la programmation que vous aurez à faire ultérieurement:

-- le nombre n est mémorisé dans une variable entière nommée aussi n;

-- les quantités u,-- et p,-- sont mémorisées dans des tableaux d'entiers 
nommés respectivement u et p et
indicés de 0 à n -- 1 ;

-- la quantité Q est mémorisée dans une variable entière nommée aussi Q.

Quand on écrira une fonction (ou une procédure) dans le langage de 
programmation choisi, les tableaux u
et p ainsi que les variables Q et n seront supposés déjà définis comme 
variables globales et initialisés avec

les données du problème. Après l'initialisation, à l'indice i du tableau u 
(resp. p) se trouve la valeur u,--
(fEURSP- Pi)-

Notaüon. Si a: est un nombre réel, Læj désigne la partie entière par défaut de 
a: (c'est--à--dire le plus grand
entier inférieur ou égal à a:) tandis que [a:] désigne sa partie entière par 
excès (c'est--à--dire le plus petit
entier supérieur ou égal à a:).

PREMIÈRE PARTIE
Sac à dos fractionnaîre

Dans cette partie, les objets sont fractionnables. On note a:,-- la quantité de 
l'objet de numéro z' emportée par
Madame X. Le problème s'écrit:

n---1
Maximiser z = z u,--æ,--
i=0
avec les contraintes :
n--1
ZPi--"OE < Q i=0 et pouri EUR {0,1, . .. ,n ---1}, an, EUR [0,1] page 3/8 Tournez la page S.V.P. Épreuve d'Informatique l -- On suppose que, pour tout i appartenant à {l, . . . , n -- 1} : Ui--l Ui Pi-1 Pi On définit un entier z'* compris entre 0 et n par: n--1 si Zp,- < Q, alors z'* : i=0 sip0, > Q, alors lz'*- -- 0
i ----1

sipo ,

i=0 i=0

a -- Montrer qu'une solution maximale pour le problème est donnée par:

pourivérifiant0 --3 sont
Pi--1 Pi

vérifiées, écrire, dans le langage de programmation choisi, une fonction qui 
calcule z' *.

2 -- Remarque: le reste du problème ne dépend pas de cette question 2.

a -- On cherche à déterminer la solution du problème du sac à dos fractionnaire 
sans faire l'hypothèse

que, pour tout z' appartenant à {l, . .. , n -- l} :
U'_1 'U.'
3 > _1 .
Pi--1 Pi

En revanche, on suppose que l'on a Z?____1_0 p,--> , Q.

page 4/8

Épreuve commune 2002

On cherche à déterminer i* appartenant à {0,1, . .. ,n -- 1} et une partition 
de l'ensemble
{0,1, . . . ,n -- l} \ {i*} en deux sous--ensembles I ' et I " de façon à avoir 
simultanément:
pourtoutz EUR I', --3 2 '
Pi Pi*
pour tout] EUR I", ' ; --l
Pi* PJ"
21%" < Q ieI' Fr + 21%" 2 Q ieI' On dit qu'un algorithme est linéaire en une variable 11 liée aux données traitées s'il existe une fonction linéaire de v majorant le nombre d'opérations élémentaires (opérations arithmétiques, comparaisons...) effectuées par cet algorithme pour traiter ces données. On admet qu'on dispose d'un algorithme A qui, étant donné un ensemble E de m éléments ayant chacun une valeur, partitionne cet ensemble en deux sous--ensembles E' et E" de cardinaux res- pectifs L%_| et [%'-l de telle sorte que toutes les valeurs des éléments de E' soient supérieures ou égales à toutes les valeurs des éléments de E" ; on suppose de plus que A est linéaire en m. Expliciter, sans utiliser de langage de programmation, un algorithme récursif (qu'il ne sera pas nécessaire de prouver) utilisant l'algorithme A qui détermine z'*, I ' et I " ; cet algorithme devra être linéaire en n. b -- Prouver la linéarité en n de l'algorithme proposé ci--dessus. Pour simplifier cette preuve, on pourra se restreindre aux valeurs de n qui sont des puissances de 2; on admettra alors que l'algorithme est aussi linéaire lorsque n est quelconque. c -- Déduire des questions 1 - a, 2 -- a et 2 - b qu'on peut résoudre le problème du sac à dos fractionnaire portant sur n objets en un temps majoré par une fonction linéaire de n même si les objets ne sont u- . . , . pas au préalable classés pour que les rapports ---'-- (2 EUR {0,1, . . . ,n ---- 1}) sownt decrmssants. Pi SECONDE PARTIE Sac à dos en 0--1 Dans cette partie, les objets ne sont plus fractionnables : chaque objet est pris ou laissé. Le problème s'écrit : n--1 Maximiser z = 2 u,-æ,-- i=0 avec les contraintes : n----l z Pi$i < Q i=0 et pourz' EUR {0,1, . .. ,n -- 1}, a:,-- E {0,1} On dit que EE : (î5, :::--1, . . . , a:n__1) EUR {0,1}" est réalisable si on a Z?_Çâ p,--îä,'- { Q. On appelle valeur d'une telle solution la valeur correspondante de la fonction 2 ou, autrement dit, la quantité ZÎQJ u,--àÎ,--. Le page 5/8 Tournez la page S.V.P. Épreuve d'Informatique problème consiste donc à déterminer la meilleure solution réalisable, c'est--à--dire celle qui a la plus grande valeur. 3 -- Montrer que le maximum du problème du sac à dos en 0--1 est inférieur ou égal au maximum du 4.. problème de sac à dos fractionnaire ayant les mêmes données numériques. Méthode par séparation Écrire, dans le langage de programmation choisi, un algorithme fondé sur la stratégie diviser pour régner qui exhibe tour à tour toutes les solutions réalisables et mémorise la meilleure. Cet algorithme utilisera le principe esquissé ci-après : la meilleure solution réalisable peut être cherchée successivement parmi les solutions réalisables avec 500 = 1 (s'il en existe) puis parmi celles avec a:0 : 0. La meilleure solution réalisable pour laquelle m0 = 1 peut être cherchée successivement parmi les solutions réalisables avec :r1 : 1 (s'il en existe) puis parmi celles avec oe1 : 0, etc. Avant d'écrire l'algorithme en langage de programmation : - on donnera la signification des différentes variables utilisées (autres que celles introduites par l'énoncé) ; -- on précisera le rôle des fonctions ou procédures utilisées. Indiquer la complexité dans le pire des cas de la méthode par séparation. Méthode par séparation et évaluation Remarque : cette question peut être traitée sans avoir résolu les deux questions précédentes. La méthode par séparation et évaluation améliore la méthode par séparation en utilisant la résolution du problème de sac à dos fractionnaire ; elle se place dans l'hypothèse où, pour tout z' appartenant à u -_ u-- {1,... ,n--1},onaz ' 1) --'- _ pi--l Pi On ne fera qu'esqursser cette méthode à travers un exemple. On associe au problème de sac à dos en 0--1 un arbre binaire décrit ci-dessous. La racine de l'arbre représente l'ensemble de toutes les solutions réalisables. À un sommet (noeud ou feuille) quelconque de l'arbre correspondent un indice z'0 (0 < z'0 < n) et un io-uplet (îîÿ,îzîî, . . . , cc,--0-1) EUR {0,1}io ; ce sommet représente l'ensemble, qui doit être non vide, des solutions réalisables (550,331, . . . ,xn_1) pour lesquelles on a: 550 : EEE, xl : "ff, . . . , æ,0_1 : æ,--0_1 ; ces solutions réalisables seront dites contenues par ce sommet. Si io # n, un tel sommet possède 1 ou 2 fils: un fils correspondant à l'indice du + 1 et à (î'5,âî, . . . ,:r,--0_1, O) et, si p,-O + ZÊ°=BI p,-î{ < Q, un second fils correspondant à l'indice io + 1 et à (55, îî, . . . , su,-0-1, 1). On appelle évaluation d'un sommet un majorant commun aux valeurs de toutes les solutions réalisables contenues par ce sommet. On considère dans toute la fin du problème l'exemple suivant, qui sera appelé le problème ("P) : Maximiser z = 16550 + 21351 + 19332 + 15563 + 13504 + 7335 avec les contraintes : 15OE0 + 22m1 + 20332 + 1733 + 15124 + 9325 < 51 et pourz' E {O, 1,2,3,4,5}, a:,-- E {0,1} (79) page 6/8 Épreuve commune 2002 Une partie de l'arbre associé est dessinée ci--dessous : a -- Déterminer directement la meilleure solution réalisable contenue par le sommet C (obtenu en fixant 1130 = 121 = 1). b -- Déterminer directement la meilleure solution réalisable contenue par le sommet E (obtenu en fixant a:0 : 1, 551 = 0, mg =1). c -- Résoudre le problème de sac à dos fractionnaire ci--dessous : Maximiser 15553 + 13354 + 7335 avec les contraintes : 175133 + 15274 + 9235 < 36 et pouri EUR {3,4, 5}, a:,-- E [0,1] En déduire une évaluation du sommet F (obtenu en fixant 1120 = 1, 931 : æ2 : 0). La solution réalisable optimale du problème (P) peut--elle être contenue dans F ? d -- Montrer, en utilisant la même démarche que dans la question précédente, que la solution réalisable optimale du problème (P) n'est pas contenue dans le sommet G (obtenu en fixant m0 = 0). e -- Déduire des questions précédentes la solution optimale du problème (P). FIN DU PROBLÈME D'ALGORITHMIQUË 3 Exercice sur les automates finis -- 30 mn environ Rappels pour fixer les notations Un alphabet A est un ensemble fini d'éléments, appelés lettres. L'ensemble des suites finies de lettres de A, appelées mots, est noté A'". Le mot vide est noté 1A*. Un langage est une partie de A'". Un automate fini A est un graphe orienté et étiqueté, noté par un quintuplet < Q,A,E,I,T > : A est

un alphabet; Q est l'ensemble (fini) des états de A: ce sont les sommets du 
graphe; I et T, deux sous-
ensembles de Q, sont respectivement l'ensemble des états initiaux et des états 
terminaux de A. Enfin, E,
sous--ensemble de Q >< A >< Q, est appelé ensemble des transitions de A. Une transition (p,a,q) est un arc du graphe, allant de l'état p à l'état q et étiqueté par a ; on la note également p --°> q.

Un calcul de A est un chemin c dans le graphe: (: : pg --cÏï--> p1 --a2--> pg - 
-- &) p... où, pour tout i,

0 < z' { n -- 1, p,-- & p,--+1 appartient à E. L'état pg est l'origine du calcul c, pn l'extrémité de c. La page 7/8 Tournez la page S.V.P. Épreuve d'Informatique longueur du calcul est donnée par le nombre n d'arcs de c. L'étiquette de c est le mot f formé par la suite des étiquettes des transitions successives du calcul c: f : a1a2 . . . an. Le calcul 0 peut aussi être noté pg --î--> p,, ; il est réussi si pg est initial et p,, terminal.

Un mot de A* est reconnu ar l'automate A si c'est l'éti nette d'(au moins) un 
calcul réussi de A. Le
P q

langage reconnu par A, noté L(A), est l'ensemble des mots reconnus par A. Un 
langage est reconnaissable
s'il est reconnu par un automate fini.

On dira qu'un automate A = < Q,A,E,I,T > est normalisé si:
i) 1 est un singleton, I = {2}, qui n'est l'extrémité d'aucune transition de A;
ii) T est un singleton, T = {t}, qui n'est l'origine d'aucune transition de A.

Un automate normalisé est donc naturellement représenté par le schéma 
ci-dessous (noter que certaines
transitions peuvent aussi aller de i à t, même si elles n'apparaissent pas sur 
le schéma).

Énoncé de l'exercice

Si un mot f de A* se factorise en f : uv, avec u et U dans A'", le mot 9 = ou 
est un conjugué de f.
Soit Con j: A* --> P(A*) l'application qui à un mot f fait correspondre 
l'ensemble de ses conjugués :

Conj(f) : {ou | (u,v) EUR (A')2 avec uv : f}.
En particulier, pour tout f, f E Conj(f) puisque f = 1,4- f : f1A- et, pour 
tout f E A U {1A.},
Conj( f ) = {f}. L'application s'étend par additivité : si L est un langage, 
Conj(L) : U fe L Conj( f ).

Dans tout l'exercice, L est un langage reconnu par un automate fini. L'objet de 
l'exercice est de
montrer que Conj (L) est reconnaissable.

l -- Montrer que L \ {l A--} est reconnu par un automate (fini) normalisé.
2 -- Soient A = < Q,A,E,{i},{t} > un automate normalisé qui reconnaît le 
langage L \ { 1 A--} et q un
état de A distinct de z' et t. A chaque calcul réussi de A qui passe par q (et 
donc de longueur au moins

égale à 2) d'étiquette f : f1f2: z' --Ê--> q --â--> t, on associe le conjugué g 
: f2f1 de f et on note G'q

l'ensemble des mots obtenus de cette façon:

GQ = {g : f2f1 | i --Î--l--> q --Ë> test un calcul réussi de A}.

Construire un automate qui reconnaît le langage G.,.
3 -- Montrer que Conj(L) est reconnaissable.

FIN DE L'EXERCICE SUR LES AUTOMATES

FIN DE L'ÉPREUVE

page 8/8