CM4-2

Question 1

Qu’est-ce qu’un algorithme d’affectation ?

Answer 1

Un algorithme qui applique un processus d’appariement à partir de voeux d’affectation et de critères de priorité

Question 2

Quels sont les critères d’évaluation d’un algorithme d’affectation ?

Answer 2

• Efficacité
• Équité
• Non-manipulabilité

Question 3

Qu’est-ce que le critère d’efficacité ?

Answer 3

C’est le critère de respect des préférences : il ne doit pas être possible de proposer un meilleur choix à un élève sans que cela n’affecte négativement un autre élève

Question 4

Qu’est-ce que le critère d’équité ?

Answer 4

C’est le critère de respect des priorités : aucun élève ne doit avoir d’envie justidiée, c’est-à-dire s’être vu refuser l’admission dans une école alors qu’il a une priorité plus élevée qu’un autre élève admis dans cette école

Question 5

Qu’est-ce que le critère de non-manipulabilité ?

Answer 5

On veut qu’il soit dans l’intérêt des élèves d’êtres sincères, c’est-à-dire de soumettre leurs vraies préférences

Question 6

Principe de l’algorithme de Boston

Answer 6

Satisfaire au maximum les premiers choix

Question 7

Évaluation de l’algorithme de Boston

Answer 7

Il ne satisfait aucun des trois critères

Question 8

Déroulement de l’algorithme de Boston

Answer 8

• On considère d’abord le premier voeur de chaque élève et on attribue définitivement les places en fonction des critères de priorité
• On considère ensuite les seconds voeux des élèves refusés pour leur premiers voeu, les places restantes sont définitivement attribuées en fonction des critères de priorité
• …

Question 9

Déroulement de l’algorithme d’affectations différées (mariages stables)

Answer 9

• On considère d’abord le premier voeur de chaque élève, et chaque école accepte temporairement les mieux classés dans la limite des places disponibles et rejette les autres
• …
• Les élèves rejetés à l’étape précédente candidatent pour leur voeu suivant, et chaque école compare les élèves qu’elle a déjà accepté avec les nouveaux candidats et accepte temporairement les plus hauts classés d’entre eux et rejette les autres
• L’algorithme se termine lorsque plus aucun élève n’est rejeté

Question 10

Évaluation de l’algorithme d’affectations différées (mariages stables)

Answer 10

Il est équitable et non-manipulable, et il peut être efficace : parmi les algorithmes qui respectent les priorités, c’est celui qui donne la satisfaction la plus élevée aux élèves