Centrale Informatique MP 2004

 

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