dudulle69 a écrit : ↑02 mai 2018 14:18
matmeca_mcf1 a écrit : ↑02 mai 2018 12:51
On ne s'affranchit d'aucune règle. La règle stricte est que l'appariement entre écoles et élèves soit stable, ie, doit vérifier la propriété suivante:
Si l'élève b n'est pas affecté à l'école A alors soit il n'a pas demandé A, soit b est affecté à une école qu'il préfère à A, soit tous les élèves affectés à A ont un meilleur classement que l'élève b sur l'école A.
Il se trouve qu'il existe toujours un appariement qui vérifie cette propriété mais qu'il n'est pas nécessairement unique. Il y a un algorithme qui calcule l'appariement stable qui favorise le classement des écoles, et un algorithme qui favorise les voeux des élèves. En fait c'est le même algorithme juste appliquée dans l'autre sens. Cet algorithme s'appelle Gale-Shapley. Il faut choisir un appariement stable. On ne déroge à aucune règle tant qu'on choisit un appariement stable. Et les deux appariements dont on parlait sont tous les deux stables.
Dans le cas que tu cites, la solution visant à faire permuter les élèves semble techniquement, de manière automatique et généralisée, difficile à mettre en place.
C'est au contraire très facile à réaliser une fois qu'on a étudié le problème. La solution est connue depuis 1962.
Je t'avoue que je n'ai pas compris ta réponse
on parle bien du cas où l'élève A est premier sur liste d'attente sur l'école B et pris à l'école A, et B premier sur liste d'attente sur l'école A et pris à l'école B, alors que A préfère B et B préfère A?
Dans ce cas l'élève B n' est pas affecté à l'école A car moins bien bien classé que l'élève A pour l'ecole A (3ème partie de la condition de la propriété). Si tu permutes l'élève A avec l'élève B sur le prétexte que B préfère A et A préfère B, cette 3ème partie de condition n'est plus respectée (c'est ce que je voulais dire par s'affranchir de la règle) ou alors je me trompe?
Désolé si ma question est absurde, je suis peut être un peu paumé dans le raisonnement.
Pour ce cas, si j'ai bien compris:
x est 1er sur liste d'attente sur l'école B et est pris à l'école A. x préfère l'école B.
y est 1er sur liste d'attente sur l'école A et est pris sur l'école B. y préfère l'école A.
Finalement, après choix avec les préférences des étudiants: x est pris dans l'école B et y est pris dans l'école A.
Vérifions qu'on a bien la condition respectée:
Si l'élève b n'est pas affecté à l'école A alors soit il n'a pas demandé A (possibilité 1), soit b est affecté à une école qu'il préfère à A (possibilité 2), soit tous les élèves affectés à A ont un meilleur classement que l'élève b sur l'école A (possibilité 3).
x n'est pas affecté à l'école A: c'est pour la seconde possibilité, il a été affecté à une école qu'il préférait (ici B).
La condition avec "soit blabla, soit truc", c'est comme des "ou" (l'une des possibilités doit être vérifiée, mais pas toutes).
Si on prend z qui voulait l'école A mais est 2nd sur liste d'attente (après x et y donc), il n'est pas pris car tous les élèves affectés à A ont un meilleur classement que lui (y compris y) (c'est-à-dire la 3ème possibilité).