Centrale Option Informatique MP 2004Sujet, corrigé et rapport du jury

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

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

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 candidats et des écoles peuvent être représentés par un graphe dans lequel chaque nœud représente une candidature : les nœuds 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.

On note ⟨C_i, E_j⟩ la candidature du candidat C_i à un poste ouvert par l'école E_j. On note P_c la relation de préférence des candidats pour les écoles, et P_e la relation de préférence des écoles pour les candidats. Ainsi P_c(⟨C_i, E_j⟩, ⟨C_i, E_k⟩), indique que le candidat C_i préfère l'école E_j à l'école E_k, et P_e(⟨C_j, E_i⟩, ⟨C_k, E_i⟩) indique que l'école E_i préfère le candidat C_j au candidat C_k. On note N_i le nombre de postes ouverts par l'école E_i.
Dans toute cette partie [ 1, n ] désigne l'ensemble {1, …, n}.

Considérons le graphe ayant pour sommets :

pour arcs «verticaux»:

et pour arcs «horizontaux»:

avec, comme nombres de postes ouverts, N_1 = 1, N_2 = 2 et N_3 = 1.
Ce graphe peut être représenté comme suit :
Ce graphe indique que le candidat C_1 postule pour les écoles E_2 et E_3, et qu'il préfère E_3 à E_2. De même, le candidat C_2 postule pour les 3 écoles et préfère E_3 à E_2 et E_2 à E_1 et donc, par transitivité, il préfère E_3 à E_1. Le candidat C_3 postule pour E_2 et

E_3, dans cet ordre de préférence décroissante, et C_4 postule pour E_1 et E_2 dans cet ordre. L'école E_1 ouvre un seul poste, et elle préfère la candidature de C_2 à celle de C_4. L' école E_2 ouvre 2 postes, elle préfère C_4 à C_3, C_3 à C_1 et C_1 à C_2; par transitivité, elle préfère donc C_4 à C_1, C_4 à C_2 et C_3 à C_2. Enfin E_3 n'ouvre qu'un poste et préfère C_1 à C_2 qu'elle préfère à C_3.

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

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 nœud ⟨C_i, E_j⟩ du graphe l'une des propositions suivantes est vraie :

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?

Dans cette section on cherche un algorithme conduisant à une affectation méritoire privilégiant les vœux des candidats en donnant à chaque candidat son choix préféré.
On appelle «nœud inutile pour les écoles» tout nœud ⟨C_i, E_j⟩ tel qu'il existe N_j nœuds distincts ⟨C_(n_1), E_j⟩…⟨C_(n_(N_j)), E_j⟩, avec n_k ≠ i pour tout k, qui vérifient les deux propriétés suivantes :

I.E.1) Montrer que les affectations méritoires d'un graphe sont exactement celles du graphe obtenu en supprimant les nœuds inutiles pour les écoles du graphe initial, à condition que, lors de la suppression des nœuds inutiles, on prenne garde de maintenir les chaînes des préférences concernant les noeuds restants.
I.E.2) Déduire de la question précédente un algorithme pour trouver une affectation méritoire.
I.E.3) Appliquer cet algorithme (pas à pas) au graphe donné en exemple.

On va maintenant s'intéresser à l'affectation qui privilégie les vœux des écoles.

I.F.1) Donner la définition d'un «nœud inutile pour les candidats».
I.F.2) Montrer que les nœuds inutiles pour les candidats peuvent eux-aussi être supprimés du graphe sans que cela change les affectations méritoires.
I.F.3) En déduire un algorithme pour obtenir l'affectation méritoire qui privilégie le choix des écoles.
I.F.4) Appliquer cet algorithme au graphe donné en exemple.

I.G.1) Donner un algorithme permettant de supprimer tous les nœuds inutiles (aussi bien pour les écoles que pour les candidats) d'un graphe.
I.G.2) Appliquer cet algorithme au graphe donné en exemple, et en déduire toutes les affectations méritoires de ce graphe.

Un nombre entier X (avec 0 ≤ X ≤ 15 ), représenté sur 4 chiffres binaires x_3, x_2, x_1, x_0, est appliqué à l'entrée d'un circuit logique ( x_3 est le chiffre de fort poids). Ce circuit a deux sorties s_1 et s_0 qui représentent la partie entière de la racine carrée de X ( s_1 est le chiffre de fort poids).
II.A.1) En utilisant les connecteurs NOT, AND, et OR, donner une expression de s_1 en fonction de x_3, x_2, x_1 et x_0.
II.A.2) En utilisant les mêmes connecteurs, donner une expression de s_0 en fonction de x_3, x_2, x_1 et x_0.

Soit une fonction booléenne f(x_1, x_2, …, x_i, …, x_n) des n variables x_1, x_2, …, x_n. On appelle résidu de f par rapport à x_i (noté f_(x_i) ) la fonction des n − 1 variables x_1, …x_2, …, x_(i − 1), x_(i + 1), …, x_n qui correspond à une expression logique de f dans laquelle on a remplacé x_i par 1:

De même, on appelle résidu de f par rapport à x¯_i (noté f_(x_i^–) la fonction :

II.B.1) Démontrer que f = (x_i ∧ f_(x_i)) ∨ (x_i^– ∧ f_(x_i^–))
II.B.2) Démontrer que f = (x_i ∨ f_(x_i^–)) ∧ (x_i^– ∨ f_(x_i))

On définit la dérivée booléenne par rapport à x_i d'une fonction booléenne

où le symbole ⊕ désigne le ou exclusif (XOR).
II.B.3) Démontrer que la valeur de f est indépendante de la valeur de x_i si (∂f)/(∂x_i) = 0 et que la valeur de f dépend de la valeur de x_i si (∂f)/(∂x_i) = 1.
II.B.4) Démontrer que (∂f)/(∂x_i) = (∂f¯)/(∂x_i).

Soient f et g deux fonctions booléennes des n variables x_1, x_2, …, x_n :
II.B.5) Démontrer que :

II.B.6) Démontrer que :