Centrale Informatique MP 2004

Thème de l'épreuve Affectation de candidats à des postes et dérivée de fonctions booléennes
Principaux outils utilisés algorithmes, graphes, logique booléenne, tables de vérité, lois de De Morgan

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
              

Énoncé obtenu par reconnaissance optique des caractères


 

0038=OE OOE:FmOE - OE=bm.fi_ccm 1.53 _<=U

L'épreuve est constituée de deux parties indépendantes. Le candidat peut les 
trai-
ter dans l'ordre de son choix à condition de respecter les numérotations.

Partie I - Algorithmique

On appelle graphe un ensemble fini de points du plan (nommés noeuds). Cer--
tains de ces noeuds sont reliés par un arc orienté. Un graphe permet de repré-
senter simplement une relation binaire définie sur un ensemble fini.

I.A - Affectation de candidats à des postes

Dans cette partie, on s'intéresse au problème de l'affectation de candidats à 
des
postes ouverts par des écoles. Chaque candidat classe les écoles dans lesquelles
il souhaite obtenir un poste par ordre de préférence strictement décroissante.
Chaque école offre un nombre connu de postes, et classe tous les candidats qui
postulent par ordre de préférence strictement décroissante. Les choix des candi-
dats et des écoles peuvent être représentés par un graphe dans lequel chaque
noeud représente une candidature : les noeuds du graphe sont sur une grille à
deux dimensions, les candidats étant placés en abscisses et les écoles en
ordonnées ; ainsi les arcs verticaux représentent la relation de préférence des
candidats pour les écoles et les arcs horizontaux la relation de préférence des

écoles pour les candidats. Ces relations sont des relations d'ordre : elle sont 
donc
transitives.

I.B - Notations

On note (Ci, E ]) la candidature du candidat Ci à un poste ouvert par l'école E 
j .
On note Pc la relation de préférence des candidats pour les écoles, et Pe la 
rela-
tion de préférence des écoles pour les candidats. Ainsi Pc( (Ci, E j), (Ci, E 
k)) , indi-
que que le candidat Ci préfère l'école E j à l'école Ek , et Pe((Cj,Ei), (Ck, 
Ei))
indique que l'école Ei préfère le candidat C]. au candidat Ck. On note N i le
nombre de postes ouverts par l'école Ei .

Dans toute cette partie [I, n] désigne l'ensemble {1, ..., n} .

I.C - Exemple

Considérons le graphe ayant pour sommets :
 >  , (Cz, E1> ,  E2> ,  E3> ,

 ,  ? E1> , E2>

pour arcs « verticaux » :
Pc( E3>' (C], E2>) ,

Pc(' )' Pc(, ),
Pc(' (C3,E3>),
Pc(> (C4, Ez>)

et pour arcs « horizontaux » ':
Pe( 9) )

Pe(' ), Pe(> ) , Pe(a E2>)7
Pe(' ) , Pe(' )

avec, comme nombres de postes ouverts, N1 : 1 , N 2 = 2 et N 3 = 1 .
Ce graphe peut être représenté comme suit :

Ce graphe indique que le candidat C1
postule pour les écoles E2 et E3 , et
qu'il préfère E3 à E2. De même, le
candidat 02 postule pour les 3 écoles
et préfère E3 à E2 et E2 à E1 et donc,
par transitivité, il préfère E3 à E1--
Le candidat C3 postule pour E2 et
E3, dans cet ordre de préférence
décroissante, et C4 postule pour E1 et E2 dans cet ordre. L'école E1 ouvre un
seul poste, et elle préfère la candidature de 02 à celle de C4 . L' école E2 
ouvre 2
postes, elle préfère C4 à C3 , C3 à C1 et C1 à 02 ; par transitivité, elle 
préfère
donc C4 à C1 , C4 à 02 et C3 à C2 . Enfin E3 n'ouvre qu'un poste et préfère C1
à 02 qu'elle préfère à C3.

I.D - Affectations méritoirés

Une affectation % est un ensemble de noeuds tel que dans chaque colonne, au
plus un noeud appartient à l'affectation (un candidat ne peut pas être affecté à
plusieurs postes) et tel que sur chaque ligne, le nombre de noeuds appartenant
à l'affectation est au plus égal au nombre de postes ouverts par l'école 
correspon-
dante. Une affectation vérifie donc les propriétés suivantes :

A1 vz, ((Ci,EJ-)EJZÎ et e%=>j =k) ,

. .P*q
A2 (V1,3n>NJ-;VkE[l,n],(Cik,Ej)EVQ/)=>Bp,qe[l,n],{ip : iq.

Une affectation est dite « totale » si tous les postes ouverts sont attribués, 
ou si
tous les candidats obtiennent un poste (le nombre de postes ouverts et le nombre
de candidats ne sont pas forcément égaux). Une affectation % est dite

« méritoire » si et seulement si pour tout noeud (C,-, E ]) du graphe l'une des 
pro--
positions suivantes est vraie :

Ml (C,,Ej)eM

M2 3,)

l'accolade dans M3 signifiant que les 3 propriétés sont vraies simultanément.

I.D.1) Que signifie en langage courant la définition d'une affectation
méritoire ?

I.D.2) Une affectation méritoire est--elle nécessairement totale ?

I.E - Noeuds inutiles pour les écoles

Dans cette section on cherche un algorithme conduisant à une affectation méri-
toire privilégiant les voeux des candidats en donnant à chaque candidat son

choix préféré.
On appelle « noeud inutile pour les écoles » tout noeud (C,-, E ]) tel qu'il 
existe
N j noeuds distincts (C..., Ej) (CnN_, Ej) , avec nk =ei pour tout k , qui 
vérifient
les deux propriétés suivantes :

VkE[I,NJ-l,Pc((an»Ep>,)=>(P=j) » ' ' (l)

Vk E[1,le, Pe<,-->f(xl,x2, ...,x,--_1,1, x,--+1, 
,xn)
De même, on appelle résidu de f par rapport à 5,- (noté f --_ la fonction :

f; : (xl, ...x2, ...,x,_1,xi+l, ...,xn)l-->f(xl,x2, ...,x,_1,0,x,+1, ...,xn)
l

II.B.1) Démontrer que f = (x,-- A fxi) v (Sc--,-- A f;)
II.B.2) Démontrer que f = (x,-- v f?) A (aÎ, v fxi)
On définit la dérivée booléenne par rapport à x d'une fonction booléenne

f: (xlax2a°°°axi,---axn)Hf(xl,x2,....,x .. ,x n) par. %" -- fx ®f_

où le symbole (+) désigne le ou exclusif (XOR).
H. B. 3) Démontrer que la valeur de f est indépendante de la valeur de x,-- si

_â__f_

ôx,--

II.B.4) Démontrer que----- ôf-- -ô--f

ôx,-- _ôx,- .

-O et que la valeur de f dépend de la valeur de x si £-_f=1

Soient f et g deux fonctions booléennes des n variables x1,x2, x,, :

H. B. 5) Démontrer que :

"f.;g>= (fAâ--î>@® <î--£Aäî>

H. B. 6) Démontrer que:
...-- -@ <ï>-->

ôx,-- ôx,-- ôx ôx

00. FIN ooo

Extrait du corrigé obtenu par reconnaissance optique des caractères



Centrale Informatique MP 2004 -- Corrigé
Ce corrigé est proposé par Samuel Mimram (ENS Lyon) ; il a été relu par 
JeanBaptiste Rouquier (ENS Lyon) et Vincent Puyhaubert (Professeur en CPGE).

Le sujet est constitué de deux problèmes indépendants.
Le premier est un problème d'algorithmique qui propose d'étudier deux façons
d'affecter des candidats à des écoles en privilégiant soit les candidats, soit 
les écoles.
Les listes des choix des candidats peuvent être représentées par des graphes. 
L'énoncé
est en grande partie constitué de définitions et de notations et ne requiert 
pratiquement aucune connaissance préalable sur les graphes pour pouvoir être 
traité
­ en contrepartie, il ne fait pas réviser beaucoup de notions du programme. Il 
est
demandé au candidat de proposer des algorithmes pour trouver des affectations 
méritoires (c'est-à-dire « justes » d'un certain point de vue) puis de les 
exécuter sur un
exemple. Les parties I.E et I.F sont très similaires. Les questions demandent 
de la
rigueur et sont parfois un peu techniques, mais elles restent conceptuellement 
simples.
Le second problème introduit les notions de résidu et de dérivée d'une formule
booléenne, cette dernière étant une généralisation aux formules booléennes de
la notion habituelle de dérivée d'une fonction. Le sujet amène à manipuler des 
tables
de vérité et quelques identités classiques (lois de De Morgan), faisant 
intervenir des
opérateurs booléens usuels, pour montrer des propriétés de la dérivée booléenne.
La difficulté des questions est variable, et le choix de la méthode à employer 
est parfois délicat. Cette épreuve constitue une bonne révision des outils 
disponibles pour
traiter les problèmes de logique booléenne.

Indications
I.D.2 Trouver un contre-exemple avec deux élèves et deux écoles.
I.E.1 Montrer qu'un noeud inutile pour les écoles ne fait jamais partie d'une
affectation méritoire en raisonnant par l'absurde.
I.E.2 Itérer une procédure qui « enlève des noeuds inutiles pour les écoles » 
jusqu'à
atteindre un point fixe.
I.F.1 Formaliser l'idée intuitive suivante : si un candidat est classé parmi 
les Nj
premiers dans une école Ej alors il est sûr d'être pris dans cette école, ou 
dans
une école qu'il préfère à Ej .
I.F.2 Raisonner par l'absurde sur le même modèle qu'à la question I.E.1.
I.F.3 Trouver un algorithme fondé sur le même principe qu'à la question I.E.2.
I.G.1 Même indication que pour la question I.F.3.
II.A.1 Dresser la table de vérité de s1 en fonction de x3 , x2 , x1 et x0 .
II.A.2 Dresser la table de vérité de s0 en fonction de x3 , x2 , x1 et x0 .
II.B.1 Démontrer que l'égalité est vraie pour tout n-uplet (x1 , . . . , xn ) 
en distinguant
les cas xi = 0 et xi = 1.
II.B.3 Utiliser la table de vérité de l'opérateur  ; a  b = 0 si et seulement 
si a = b.
II.B.4 Utiliser l'identité a  b = a  b.
II.B.5 Distinguer suivant les valeurs possibles de fxi , fxi , gxi et gxi en un 
point
de {0, 1}n-1 donné.
II.B.6 Utiliser l'identité a  b = a  b pour se ramener à la question précédente.

I.

Algorithmique

La propriété (A2) de l'énoncé, qui rend compte du fait que sur chaque
ligne le nombre de noeuds appartenant à l'affectation est au plus égal au
nombre de postes ouverts par l'école correspondante, ne correspond pas
à l'explication de l'énoncé. En outre, elle est syntaxiquement incorrecte.
Intuitivement, c'est l'ensemble de la propriété qui dépend de l'entier j
(pour chaque j, il faut que l'école Ej ne prenne pas plus de candidats qu'elle
n'offre de postes) et non pas seulement l'hypothèse (on n'a pas besoin de
supposer que pour chaque école Ej il y a plus de Nj candidats ­ non 
nécessairement distincts ­ affectés à cette école). On pourrait donc penser 
qu'il
suffirait de sortir la quantification universelle sur j de la parenthèse pour
corriger cela :

p 6= q
j (n > Nj k  [1; n] hCik , Ej i  A ) = p, q  [1; n]
ip = iq
Mais c'est insuffisant car la formule reste alors syntaxiquement incorrecte :
à gauche de l'implication, la définition de l'entier n par la quantification
existentielle n'est valable qu'à l'intérieur de la parenthèse. On dit que la
quantification existentielle est un lieur car elle définit une variable (n dans
notre cas) et cette définition n'est valable que dans une « portion » limitée de
la formule, sa portée. La formule est en effet de la forme j P(j) = Q(j),
où P et Q sont des formules qui ne peuvent dépendre que de j car c'est la seule
variable qui a été préalablement définie. Des variables peuvent être définies
à l'intérieur de ces formules (c'est le cas par exemple de n à l'intérieur de P)
mais elles ne peuvent que rester internes à ces formules. De plus, il serait
préférable de définir explicitement les indices ik (et il faut les définir 
après n
car ils dépendent de cette variable). Une formulation correcte serait :
j

n > Nj

i1 , . . . , in

(k  [1; n], hCik , Ej i  A )

=

p, q  [1; n]

p 6= q
ip = iq

I.D.1 Une affectation est dite méritoire si et seulement si, lorsqu'un candidat 
C
qui a demandé une école E n'a pas été affecté à cette école, c'est que :
· soit il a été affecté à une école qu'il préfère (M2) ;
· soit l'école E a déjà affecté tous les postes qu'elle avait ouverts à des 
candidats
qu'elle préfèrait à C (M3).
I.D.2 Considérons le graphe dans lequel il y a deux candidats (C1 et C2 ),
deux écoles (E1 et E2 telles que N1 = 1 et N2 = 1), ayant pour sommets hC1 , E1 
i
et hC2 , E1 i et pour seul arc Pe (hC1 , E1 i, hC2 , E1 i).
E1

E2
C1

C2

En français : les deux candidats postulent pour la même école E1 mais pas
pour l'école E2 et l'école E1 , qui n'offre qu'une place, préfère le candidat 1.
Considérons l'affectation A = {hC1 , E1 i}. L'ensemble A est clairement une
affectation (chaque candidat est affecté au plus une fois et chaque école ne 
prend
pas plus de candidats qu'il n'y a de postes ouverts). De plus, elle est 
méritoire.
En effet, hC1 , E1 i appartient à A et vérifie donc (M1) et hC2 , E1 i vérifie 
(M3)
car C1 remplit à lui seul tous les postes ouverts de E1 , il est préféré à C2 
par
l'école E1 . Le candidat C2 n'a pas postulé pour d'autre école que E1 . 
L'affectation A
n'est pas totale car E2 n'a pas attribué tous ses postes ouverts et C2 n'a pas 
obtenu
de poste. Ainsi,
Une affectation méritoire n'est pas nécessairement totale.

Si le candidat avait également postulé à l'école E2 par sécurité, il n'y aurait
pas eu une place « gâchée ».
I.E.1 Un noeud hCi , Ej i est dit « inutile pour les écoles » lorsqu'il existe 
Nj candidats dont Ej est l'école préférée (1) et qui sont préférés à Ci par 
cette école (2).
La démonstration est un peu longue à rédiger mais sa structure est simple.
Si un noeud hCi , Ej i est inutile pour les écoles, alors il existe Nj autres 
candidatures qui sont à la fois la candidature préférée des candidats et que
les écoles préfèrent à hCi , Ej i (ces candidatures sont donc « meilleures de
tout point de vue » que hCi , Ej i). Ainsi, une affectation méritoire ne 
contient
pas hCi , Ej i.
Montrons qu'une affectation méritoire ne contient jamais de noeud inutile pour
les écoles. Soit hCi , Ej i un noeud inutile pour les écoles. Il existe Nj 
noeuds distincts
hCn1 , Ej i, . . ., hCnNj , Ej i, avec nk 6= i pour tout k, vérifiant les 
propriétés (1) et (2).
Soit A une affectation dont hCi , Ej i fait partie.
Nécessairement, comme hCi , Ej i, hCn1 , Ej i, . . ., hCnNj , Ej i sont des 
noeuds
distincts, ils ne peuvent simultanément être dans A car (A2) ne serait pas
vérifiée et A ne serait pas une affectation. Comme on a supposé que le noeud 
hCi , Ej i
appartient à A , il existe nécessairement un entier k, tel que 1 6 k 6 Nj , et 
tel que
le noeud hCnk , Ej i n'appartienne pas à A (ie ne vérifie pas (M1)).
Ce noeud vérifie par hypothèse (1) donc il ne vérifie pas non plus (M2)
(Ej étant l'école préférée du candidat Cnk , celui-ci ne peut pas être affecté 
à une école
qu'il préfère).
Supposons que hCnk , Ej i vérifie (M3). Alors il existe Nj élèves préférés à Cnk
par l'école Ej affectés à des postes de Ej . Or, l'école Ej préfère Cnk à Ci 
donc
Ci ne fait pas partie de ces Nj élèves. De plus, Ci est supposé lui aussi être 
affecté à un poste de Ej . L'école Ej aurait donc affecté au moins Nj + 1 
candidats à
des postes alors qu'elle n'en offre que Nj . Il y a contradiction avec 
l'hypothèse (A2).
Par conséquent, le noeud hCnk , Ej i ne vérifie ni (M1), ni (M2), ni (M3) et
l'affectation A n'est pas méritoire. Finalement,
Une affectation méritoire ne contient jamais de noeud inutile pour les écoles.