Salut,

Pas de photo d'énoncé ici, il doit être tapé --> Sujet ancien- ne plus donner ce lien-merci

Bonjour,

Je voudrais de l'aide pour mon devoir maison.
Merci

Le problème des mariages stables désigne de façon imagée le problème d'affectation des ressources ou d'affectation de personnels.
  Par exemple : comment décider quel élève sera affecté dans quel établissement ? Nous utiliserons la métaphore du mariage pour examiner un problème de ce type. Le but est de réaliser des mariages stables dans le sens qu'on ne puisse trouver un homme
marié et une femme mariée qui se préfèrent l'un à l'autre plutôt qu'à leurs conjoints respectifs. L'algorithme de Gale et Schapley répond à cette problématique : pour construire une solution stable, Lloyd Schapley a proposé un algorithme fondé sur une idée traditionnelle: “ l'homme propose, la femme dispose ” . Cet algorithme est utilisé par exemple pour les affectations des étudiants en classe préparatoire et pour celles des professeurs des universités. Il applique ce principe en procédant par étapes successives :

• Étape 1 : chaque personne (hommes et femmes) rédige sa liste de préférence ;

• Étape 2 : chaque homme propose le mariage à la femme qu'il préfère sans tenir compte d'éventuels concurrents ;

• Étape 3 : chaque femme étudie alors les propositions qu'elle a reçues et accepte celle de l'homme le mieux placé dans son classement. Elle se fiance à celui-ci en rompant éventuellement ses fiançailles précédentes. Les femmes n'ayant reçu aucune proposition de mariage attendent l'étape suivante ;

• Étape 4 : les hommes déjà fiancés ne font rien, les autres recommencent à partir de l'étape 2 en faisant une proposition aux femmes qui ne les ont pas déjà refusés.
Le processus se poursuit ainsi d' étape en étape tant que cela est possible. L'algorithme produit des mariages stables car, si l'homme préfère une autre femme à son épouse, celle-ci l'a rejeté au cours de la procédure, et si une femme préfère un homme à son époux, c'est que celui-ci est déjà marié à une femme mieux classé dans sa liste de préférences.

Exemple.

•Étape 1 :
Considérons 5 hommes, nommés Adam (A) ; Baptiste (B) ; Charlie (C) ; David (D) et Édouard (E) - et 5 femmes, nommées Adeline (a) ; Béa (b) ; Charlotte (c) ; Dahlia (d) et Émelyne (e). Voici les tableaux classant les préférences de ces personnes :

PHOTO 1

Hommes Préférences des hommes
A---> c > b > e
B---> a > d > e
C--->d > a > b
D---> d > a > b
E---> a > d > b > c

Femmes Préférences des femmes
a---> B > E > A
b---> C > D > E
c---> A > C > B
d---> E > D > A
e---> D > E > B

•Étape 2 :
Les hommes font les propositions suivantes :
A demande c en mariage ;
B demande a en mariage ;
C demande d en mariage ;
D demande d en mariage ;
E demande a en mariage.

•Étape 3 :
Les femmes décident comme suit :
a accepte la demande de B ;
b n'a reçu aucune demande, elle doit patienter ;
c accepte la demande de A ;
d accepte la demande de D ;
e n'a reçu aucune demande, elle doit patienter.
À ce stade, a et B sont fiancés, ainsi que c et A ; et d et D.

•Étape 2 (hommes, session 2) :
Les hommes restants font les propositions suivantes :
C demande a en mariage ;
E demande d en mariage.
•Étape 3 (femmes, session 2) :
Les femmes décident comme suit :
a refuse la demande de C ;
d quitte D et accepte la demande de E.
À ce stade, a et B sont fiancés, ainsi que c et A ; et d et E.
•Étape 2 (hommes, session 3) :
Les hommes restants font les propositions suivantes :
C demande b en mariage ;
D demande a en mariage.
Étape 3 (femmes, session 3) :
Les femmes décident comme suit :
a refuse la demande de D ;
b accepte la demande de C ;
À ce stade, a et B sont fiancés, ainsi que c et A ; d et E ; et b et C.
•Étape 2 (hommes, session 4) :
Les hommes restants font les propositions suivantes :
D demande b en mariage.
•Étape 3 (femmes, session 4) :
Les femmes décident comme suit :
b refuse la proposition de D.
Plus aucune demande n'est possible, l'algorithme s'arrête. Les mariages sont : a − B ; b − C ; c − A et d − E. On remarque que
e et D ne sont pas mariés, car D n'avait pas classé e dans sa liste de préférences.

•Exercice.
Réaliser des mariages stables en utilisant l'algorithme décrit précédemment pour les
deux cas suivants (en justifiant) :

PHOTO 2

1. Cas 1 :
Hommes Préférences des hommes
A c > b > a > d
B e > d > b
C b > a > c > e
D d > c > e > b > a

Femmes Préférences des femmes
a A > B > C
b D > B
c C > A > D
d A > B > D > C
e A > D > C > B
2. Cas 2 :

Hommes Préférences des hommes
A e > b > c > a > d
B a > b > c > d
C d > e > c
D a > c > e
E b > a > d

Femmes Préférences des femmes
a A > B > C > D
b E > C > D
c B > D > A
d C > B > E
e A > C > B

Merci pour votre aide !





*** message déplacé ***

Mais reposter le même énoncé c'est un Multipost et c'est interdit.

Multipost

Ne pas repondre tant qu'un modérateur n'a pas réuni

*** message déplacé ***

Boniour,
Une personne m'a dit de le reecrire je ne savais pas désole

*** message déplacé ***

Cette personne a dû te demander de recopier ton énoncé dans le même sujet déjà posté pas dans un nouveau.

*** message déplacé ***

Bonne nuit,

à AlexSchv89 : Pouvez-vous préciser maintenant l'aide que vous attendez ?

J'aimerais avoir de l'aide sur le devoir car je n'ai absolument rien compris pouvez vous m'eclaircir ou meme m'avancezr un peu dans l'exercice Merci Bonne journee

Bonjour ,

Avez-vous suivi et compris l'exemple donné ?
Si non, qu'est-ce que vous ne comprenez pas dans cet exemple ?
Car les deux cas que vous avez à traiter suivent la démarche de cet exemple....

AlexSchv89 ne donne pas suite, je n'apporterai plus d'aide à cet exercice.