Algorithmes de Parcoursup

Projet de programmation fonctionnelle 2021

Le but de ce projet est d’explorer divers algorithmes de mariages stables, puis le fameux algorithme de Parcoursup, dans une version très simplifiée (pas d’internats, pas de boursiers, etc).

Une excellente introduction à l’algorithme des mariages stables de Gale et Shapley est la vidéo de vulgarisation scientifique du vidéaste David Louapre (dont je vous recommande au passage toute la chaîne, en particulier les vidéos sur l’informatique). Prenez le temps de regarder cette vidéo et de lire le billet de blog avant de vous lancer dans le projet, cela vous donnera une très bonne idée de ce sur quoi vous allez travailler. Les curieux qui veulent voir à quoi ressemble un article scientifique pourront aussi consulter l’article original de Gale et Shapley, mais la vidéo résume très bien l’article et il n’est pas nécessaire de le lire.

Quelques points importants avant de commencer

Travailler en équipe

Vous pouvez faire ce projet seul ou en binôme. L’utilisation de git ou d’un autre gestionnaire de versions vous facilitera la tâche, mais si vous ne voulez pas apprendre git pour le moment (vous aurez l’occasion de le faire en projet de L3), vous pouvez bien sûr échanger vos fichiers entre vous par mail. Je rappelle aussi la règle suivante: vous ne devez pas échanger de fichiers avec d’autres personnes que votre binôme. Les discussions sur moodle ou discord sont encouragées, c’est très bien si vous posez des questions, et c’est très bien si vous aidez quelqu’un qui a posé une question à la place de l’enseignant (si ce que vous dites n’est pas correct, on corrigera). Mais restez au niveau de la langue française (ou d’un dessin), ne montrez pas de code (occasionnellement, 1 ou 2 lignes de codes peuvent être divulguées si votre question ou votre réponse n’a pas été comprise, mais évitez autant que possible). Enfin, si vous utilisez un dépot dans le cloud (bitbucket, github, etc) paramétrez votre dépot pour qu’il ne soit pas public et que seul votre binôme y ait accès. J’utilise un logiciel de détection de plagiat et j’enleverai des points aux plagieurs mais aussi aux plagiés (sans chercher à faire de distinction) en cas de plagiat détecté, même partiel.

Découpage du projet, prise en main de dune

Comme vous pouvez vous en rendre compte si vous avez téléchargé l’archive du projet, le projet contient de nombreux fichiers dans divers répertoires. Il n’y a pas un exécutable “final”, mais de nombreux tests qui permettent d’évaluer ce que fait le code. Le projet est prévu pour être compilé et testé avec le gestionnaire de projet OCaml dune. Il vous faut donc installer dune avec la commande opam install dune. Pour me permettre d’évaluer vos projets, veuillez ne pas changer l’arborescence des répertoires ni les noms de fichiers. Il y a deux répertoires principaux :

Chaque sous-répertoire de src correspond à une librairie qui définit un ou plusieurs modules. Les fichiers nommés dune dans les répertoires précisent les dépendances avec les autres librairies et quels modules sont définis par la librairie. De même, chaque sous-répertoire de test contient des tests. Lisez les fichiers dune fournis et consultez la documentation de dune pour plus de précisions.

Pour une première prise en main, exécutez depuis la racine du projet la commande dune runtest test/hello. Vous allez voir que le test échoue. Pour que le test passe, il faut que l’affichage généré par test/hello/test_hello.ml corresponde à ce qui est spécificé dans le fichier test/hello/test_hello.expected. Ne touchez pas le fichier test/hello/test_hello.ml ni le fichier test/hello/test_hello.expected (de manière générale, ne modifiez pas les tests qui vous sont fournis), mais corrigez plutôt le fichier src/hello/hello.ml. Ré-exécutez la commande dune runtest test/hello et vérifiez que cette fois-ci le test passe.

Travail à rendre

Vous aurez à rendre tous les fichiers qui constituent votre projet:

Créez une archive avec tous ces fichiers et mettez-la dans la boite de dépôt Moodle. Date limite de dépôt des projets: 5 décembre minuit. 2 points de pénalité seront appliqués par jour de retard.

Évaluation du projet

Le projet sera évalué sur la base de tests. Certains tests ne vous seront communiqués que le 6 décembre. Chaque test rapportera des points selon un barème qui sera défini en fonction de l’ensemble des projets rendus. Durant la semaine du 6 décembre vous pourrez retoucher légèrement votre code pour faire passer des tests qui échouent. Les modifications ne devront pas dépasser les 2-3 lignes à chaque fois, et je devrai approuver ces modifications pour que vous obteniez les points.

Barème prévisionnel (à titre indicatif uniquement):

Partie 1 : mariages stables

Dans cette première partie, nous allons donner différentes implémentations de l’algorithme (ou plutôt des algorithmes) des mariages stables.

Algorithme de Knuth

Nous n’allons pas commencer par l’algorithme de la vidéo, qui est aussi celui décrit très informellement dans l’article de Gale et Shapley, mais plutôt par l’algorithme proposé par Donald Knuth dans ses notes de cours de 1976. Prenez le temps de lire ces notes de cours au moins jusqu’aux pages 21-22 (la suite est aussi très intéressante et contient des exemples qui peuvent vous être utiles). Pages 21-22 est défini l’algorithme, que l’on retranscrit ci-dessous pour une meilleure lisibilité.

constante n : nombre d'hommes = nombre de femmes
variable k : nombre de couples fiancés
variable X : prétendant
variable x : femme à qui le prétendant fait une avance
constante Ω : homme très indésirable

k := 0;
fiancer toutes les femmes à Ω;
tant que k < n faire début
    X := k+1 ième homme;
    tant que X ≠ Ω faire début
        x := meilleur choix restant sur la liste de X
        si x préfère X à son fiancé
        alors début
            fiancer x et X
            X := fiancé précédent de x
        fin
        si X ≠ Ω alors retirer x de la liste de X
        // si demandé, afficher la configuration courante
    fin
    k := k + 1
fin
célébrer n mariages

Votre première mission dans ce projet va consister à implémenter cet algorithme en OCaml. Avant de commencer, il nous faut poser quelques définitions. Consultez le fichier src/mariages_stables/definitions.mli qui définit les notions d’entrée (les données du problème), de sortie (ce que doit renvoyer l’algorithme), et de configuration intermédiaire (l’ensemble des données mises à jour durant l’exécution de l’algorithme). Il vous faut digérer ces définitions (vous n’avez pas le droit de modifier le fichier definitions.mli) et comprendre comment elles sont reliées à ce qui apparait dans les notes de cours de Knuth. Une fois que c’est fait, complétez le fichier src/mariages_stables/knuth.ml et implémentez l’algorithme de Knuth. Notez le paramètre optionnel affiche_config: lorsque ce paramètre vaut true, votre algorithme doit afficher la configuration à chaque changement de configuration en appelant la fonction prédéfinie print_configuration du module Definitions. Vous pouvez tester votre code en tapant dune runtest test/mariages_stables/knuth depuis la racine du projet et vérifier d’une part que le résultat de l’algorithme est correct, d’autre part que toutes les configurations intermédiaires s’affichent correctement. Pour simplement voir ce qui est attendu comme sortie, lisez le fichier test/mariages_stables/knuth/test_knuth.expected.

Algorithme de Gale-Shapley

Nous allons maintenant nous intéresser à l’algorithme de Gale et Shapley tel que présenté dans la vidéo et dans l’article. Décrivons à nouveau cet algorithme informellement (il peut être plus simple et plus efficace de ne pas tout faire exactement comme suggéré par cette description informelle de l’algorithme).

tant qu'il reste des célibataires, faire début
    pour tout homme célibataire X faire début
        x := prochaine femme sur la liste d'appel de X
        ajouter X aux prétendants de x
    fin
    pour toute femme x ayant reçu au moins une nouvelle proposition,
    faire début
        X := prétendant que x préfère
        si x préfère X à son fiancé actuel, ou si x est célibataire, faire début
            fiancer x et X (X n'est plus célibataire, l'éventuel ancien fiançé de x le devient)
            avancer le rang d'appel de l'éventuel ancien fiancé 
        fin
        pour tout prétendant Y de x différent de son fiancé actuel,
            avancer le rang d'appel de Y (et laisser Y parmi les célibataires)
        remettre à ø l'ensemble des prétendants de x
    fin
    // si demandé, afficher la configuration courante
fin
célébrer les mariages

Complétez le fichier src/mariages_stables/gale_shapley.ml. Vous devez utiliser les mêmes définitions du fichier src/mariages_stables/definitions.mli que précédemment concernant l’entrée, la sortie, et les configurations intermédiaires à afficher. Testez votre code avec dune runtest test/mariages_stables/gale_shapley.

Algorithme abstrait

Vous aurez remarqué que l’algorithme de Knuth et celui de Gale-Shapley, bien que différents, conduisent au même résultat. On peut en fait généraliser cela et donner toute une famille d’algorithmes qui permettent de calculer le même mariage stable (si vous avez retenu la vidéo et les notes de cours de Knuth, vous avez sans doute noté que c’est LE mariage stable optimal pour les hommes). De plus, non seulement tous ces algorithmes calculent le même résultat, mais ils conduisent à faire toujours le même nombre de propositions (mais pas dans le même ordre), et sont donc d’efficacités comparables tant qu’on ne les parallélise pas.

On va appeler “pioche” une structure de données qui comporte deux opérations: défausser un objet (l’ajouter à la pioche) et piocher un objet (le retirer de la pioche). Peu importe comment la pioche se comporte, ça peut être une pile, une file, une pioche aléatoire, une file de priorité (si on ajoute l’hypothèse que l’on peut comparer les objets de la pioche entre eux), etc. La seule chose qui compte pour cet algorithme, c’est que ce soit une pioche.

ALGORITHME ABSTRAIT

pioche <- tous les hommes
tant que la pioche n'est pas vide faire
   on pioche un homme X
   soit x la prochaine femme à qui X doit faire une proposition
   si x n'est pas fiancée, x et X se fiancent
   sinon faire 
        x choisit un gagnant et un perdant entre X et son fiancé actuel
        le gagnant devient le fiancé de x
        le perdant avance son rang d'appel
        on defausse le perdant
    fin faire
fin tant que

Vous pourrez vous convaincre que l’algorithme de Knuth correspond à cet algorithme dans lequel la pioche est une pile, tandis que l’algorithme de Gale-Shapley correspond au cas où la pioche est une file. Vous pourrez aussi vous convaincre que le résultat de l’algorithme ne dépend pas de la stratégie de pioche. Pour les plus curieux, j’ai rédigé une “idée de démonstration” de ce fait, mais qui demande pour être tout à fait formelle d’avoir quelques notions de réécriture que malheureusement je ne suis pas sûr que vous ayez l’occasion de voir dans vos autres cours d’informatique. Mais peu importe, si vous avez l’intuition de pourquoi le résultat ne dépend pas de la stratégie de pioche, tant mieux, sinon ce n’est pas essentiel pour la suite. Votre but à ne pas perdre de vue dans ce projet, c’est programmer. Vous allez donc programmer cet algorithme abstrait. Comme c’est un algorithme qui prend en paramètre une structure de données, la façon naturelle de le représenter en Caml, c’est d’utiliser un foncteur.

Allons-y. Regardez les fichiers

src/mariages_stables/algo_abstrait.mli

et

src/mariages_stables/algo_abstrait.ml.

Vous avez pas mal de choses à compléter:

Partie 2 : Parcoursup

Dans cette partie il vous est demandé d’écrire une librairie de fonctions qui permettent de simuler le déroulement d’une session de Parcoursup. Si vous ne connaissez pas le fonctionnement de Parcoursup, vous pourrez consulter le document de présentation des algorithmes de Parcoursup très complet qui présente de nombreux détails qui ne seront pas abordés (notamment les internats et les quotas d’étudiants boursiers et d’étudiants locaux). Seule l’option “répondeur automatique” sera simulée. Les commentaires dans le fichier src/parcoursup/api.mli viennent préciser la spécification de ce qu’on appelle “une session Parcoursup”. Si la spécification ne vous semble pas assez précise, posez une question sur le forum (si c’est une bonne question vous aurez un bonus).

Pour cette partie vous devez choisir vos structures de données, aucune proposition ne vous est faite, à vous de voir ce qui vous convient le mieux. Quelques tests vous sont fournis (cf test/parcoursup), mais ils sont très insuffisants et vous aurez à écrire vos propres tests, que vous rangerez dans le répertoire tests_perso ou un sous-répertoire de ce répertoire. Inspirez-vous des tests fournis pour écrire des fichiers dune déclarant ces tests.

Bon codage!

Liens