L'affectation des candidats doit respecter l'ordre d'admission déterminé par les formations d'accueil. Le résultat produit par Parcoursup est un couplage entre les formations et les candidats. Des couplages, il en existe un paquet pour un même jeu de données. On en cherche un qui possède certaines propriétés intéressantes (et même avec cela, il n'est pas unique).
Voici trois propriétés typiques :
couplage maximum : on affecte le plus grand nombre de candidats pour laisser le moins de gens sans rien à la rentrée (algo polynomial dans le graphe biparti des formations/candidats). Cela cherche juste à exhausser le maximum de vœux, peu importe les préférences des candidats ;
couplage de poids maximum : on donne un score à chaque affectation (1 si c'est le vœu préféré du candidat, 0 si c'est son pire vœu). On cherche un couplage qui maximise tous la somme des scores en se disant que ça satisfera les candidats. Effets pervers : l'algo peut préférer refuser un couplage de score 1 pour permettre deux autres couplages de scores 0.7 ;
couplage stable : on garantit que, pour chaque candidat, il est impossible de lui proposer un meilleur vœu de son point de vue que celui qu'il a déjà. (Un couplage non stable, c'est lorsque Alice et Bob sont mariés, Dave et Charlie aussi, mais qu'en fait les premiers des deux couples se préfèrent ainsi que les seconds.)
L'algorithme que tu donnes est un algorithme glouton qui produit un couplage qui n'est ni stable ni maximum.
Parcoursup produit un couplage stable. Ce n'est à priori pas un couplage maximum mais vu le nombre de formations et de candidats, et vu le fait que le graphe des vœux n'est pas très connexe, ça ne tombe pas très loin.
Quant aux morceaux de SQL, j'ai déjà dit plus loin qu'il y a, historiquement d'après ce qui avait été publié d'APB, de nombreux morceaux qui ont été codés en PL/SQL plutôt que dans un langage plus courant. Il faut aussi voir que les modèles de données sont gigantesques (état civil, liste des vœux, description de toutes les formations avec de nombreux paramètres pour chacune, réponse aux vœux, classements des candidats, résultats scolaires, dossier scolaire complet). J'aurais tellement aimé avoir accès au code pour en avoir le cœur net, mais ça fait un paquet de tables et dans chacune un paquet de colonnes pour tout décrire.
[^] # Re: Incompréhensible
Posté par Florian Hatat . En réponse à la dépêche Audit du code source de Parcoursup par la Cour des comptes. Évalué à 5.
L'affectation des candidats doit respecter l'ordre d'admission déterminé par les formations d'accueil. Le résultat produit par Parcoursup est un couplage entre les formations et les candidats. Des couplages, il en existe un paquet pour un même jeu de données. On en cherche un qui possède certaines propriétés intéressantes (et même avec cela, il n'est pas unique).
Voici trois propriétés typiques :
L'algorithme que tu donnes est un algorithme glouton qui produit un couplage qui n'est ni stable ni maximum.
Parcoursup produit un couplage stable. Ce n'est à priori pas un couplage maximum mais vu le nombre de formations et de candidats, et vu le fait que le graphe des vœux n'est pas très connexe, ça ne tombe pas très loin.
Quant aux morceaux de SQL, j'ai déjà dit plus loin qu'il y a, historiquement d'après ce qui avait été publié d'APB, de nombreux morceaux qui ont été codés en PL/SQL plutôt que dans un langage plus courant. Il faut aussi voir que les modèles de données sont gigantesques (état civil, liste des vœux, description de toutes les formations avec de nombreux paramètres pour chacune, réponse aux vœux, classements des candidats, résultats scolaires, dossier scolaire complet). J'aurais tellement aimé avoir accès au code pour en avoir le cœur net, mais ça fait un paquet de tables et dans chacune un paquet de colonnes pour tout décrire.