Attraper N fromages plus efficacement

Durée2h30 + préparation

Objectifs de la séance

Lors de la séance précédente, vous avez implémenté un joueur qui attrape N fromages en utilisant un algorithme optimal basé sur une recherche exhaustive. Cependant, cet algorithme devient rapidement inefficace lorsque N augmente, car le nombre de permutations possibles croît de manière factorielle.

Dans cette séance, on choisit de sacrifier cette optimalité pour améliorer les performances de l’algorithme. Pour cela, vous allez implémenter un algorithme glouton qui construit une solution en choisissant à chaque étape un choix localement optimal.

Important

Le contenu de cette séance sera évalué. Consultez les détails en bas de cette page.

Avant le cours

Pré-requis

Pour pouvoir commencer à travailler sur l’activité, vous devez remplir les conditions suivantes :

Articles à étudier

Pour pouvoir commencer à travailler efficacement sur l’activité pratique de cette séance, vous devez étudier les articles suivants avant d’arriver en classe :

  • Dans cet article, vous découvrirez les heuristiques.

    15 min de lecture

  • Comme mentionné dans les autres articles, les heuristiques fournissent des solutions approchées.

    25 min de lecture

Pendant le cours

Quiz Wooclap

Comme pour les autres cours en classes inversées, nous commencerons la séance par un petit quiz Wooclap pour vérifier votre compréhension des notions, et discuter de vos interrogations. Le lien sera fourni par les enseignant(e)s dans votre classe.

Attribuer les rôles

La séance 5 est évaluée. Comme mentionné sur la page principale du projet, chaque membre du groupe sera évalué sur des aspects différents du livrable. Votre rôle ne sera pas le même que lors du précédent rendu. Pour un trinôme, si vous étiez responsable du code pour le rendu précédent, vous devenez responsable de la documentation pour ce livrable. L’ancien(ne) responsable de la documentation devient responsable des tests unitaires, et l’ancien(ne) responsable des tests unitaires devient responsable du code.

Information

Si vous êtes un binôme ou quadrinôme, veuillez SVP contacter les enseignant(e)s pour une adaptation des rôles.

Activité pratique

  • Dans cette activité, vous allez développer un algorithme heuristique pour approximer une solution au TSP.

    2h30

Après le cours

Terminer l’activité pratique

Cette séance est évaluée. Vous devez rendre un livrable décrit ci-dessous avant le début de la séance 6. Ce livrable devra contenir vos productions pour cette séance, répondant aux consignes données dans l’activité pratique.

Information

Si vous avez été plus loin que le minimum requis, n’hésitez pas à inclure ces éléments supplémentaires dans votre rendu, qui seront pris en compte dans l’évaluation.

Toutefois, veuillez ne pas fournir de code ou de documentation hors sujet par rapport à cette séance, ni votre environnement virtuel ou des fichiers temporaires.

La modalité d’évaluation est décrite sur la page principale du projet. Avant la prochaine séance, vous devez donc :

  • Revoir le contenu des articles ci-dessus.

  • Compléter les parties non optionnelles de l’activité pratique.

  • Vérifier que votre enseignant(e) est bien membre de votre dépôt GitLab avec le rôle Maintainer, comme demandé lors de la séance 1. Sans cela, nous ne pourrons pas récupérer votre travail, et votre livrable ne pourra pas être évalué.

  • Vérifier que votre dépôt est organisé comme suit (c’est l’organisation de votre pyrat_workspace) :

    pyrat_workspace
|
|_ games
|  |_ # Placez vos scripts de jeu ici
|
|_ players
|  |_ # Placez vos joueurs ici
|
|_ tests
|  |_ # Placez vos tests unitaires ici
|
|_ utils
|  |_ # Placez vos codes supplémentaires ici (si nécessaire)
|
|_ data
|  |_ # Placez vos données ici (si nécessaire)
|
|_ ... # Tout autre répertoire que vous jugez pertinent à ajouter
|
|_ pyproject.toml # Le fichier qui déclare les bibliothèques dont votre code a besoin
|
|_ uv.lock        # Le fichier qui fixe les versions exactes de ces bibliothèques
|
|_ README.md
    Important

    Les fichiers pyproject.toml et uv.lock doivent être versionnés : sans eux, nous ne pourrons pas recréer l’environnement dans lequel votre code fonctionne. À l’inverse, le dossier .venv et les dossiers __pycache__ ne doivent jamais apparaître sur GitLab : le .gitignore fourni par PyRat s’en charge, ne le supprimez pas.

    Le fichier README.md, à la racine de votre dépôt, doit être formaté en Markdown, avec le contenu suivant (remplacez les parties <entre chevrons> par les informations appropriées, en enlevant les chevrons) :

    ​
    # Étudiants

- Responsable des codes : <votre nom ici>
- Responsable de la documentation : <votre nom ici>
- Responsable des tests unitaires : <votre nom ici>

# Instructions d'installation

*Précisez les dépendances nécessaires pour exécuter votre code.*
*Quelles consignes à suivre pour permettre l'exécution de vos scripts de jeu et de test ?*

<détaillez ça ici>

# Joueurs

*Quels sont les joueurs implémentés dans le répertoire `players` ?*
*Précisez quels choix vous avez faits, et pourquoi.*
*Si vous avez choisi de créer des fonctions, lesquelles et pourquoi ?*
*Quelle est la complexité de ces fonctions ?*
*Avez-vous utilisé la programmation défensive ? Si oui, où et comment ?*

<détaillez ça ici>

# Jeux

*Que font les scripts que vous avez fournis ?*
*Avez-vous modifié certains paramètres du jeu ? Si oui, lesquels et pourquoi ?*

<détaillez ça ici>

# Tests unitaires

*Quels tests unitaires avez-vous réalisés ?*
*Testez-vous certains cas d'erreur ?*
*Y a-t-il des tests manquants que vous auriez aimé réaliser ?*

<détaillez ça ici>

# Utilitaires

*Avez-vous fourni quelque chose dans le répertoire `utils` ?*
*Quels sont ces fichiers ? À quoi servent-ils ?*

<détaillez ça ici>

# Documentation

*Quelque chose à dire concernant la documentation ?*

<détaillez ça ici>

# Autres

*Avez-vous fait des analyses intéressantes ?*
*Comment avez-vous utilise les IA génératives (ChatGPT, etc.) dans ce projet ?*
*Autre chose à ajouter ?*

<détaillez ça ici>

  • Pousser votre travail sur GitLab avec git push, puis relever l’identifiant du commit qui correspond à votre livrable. Cet identifiant (ou hash) est la suite de caractères qui désigne de façon unique une version de votre dépôt. Vous l’obtenez avec la commande git log -1 depuis votre workspace, ou dans le menu Code > Commits de votre projet GitLab.

  • L’étudiant(e) responsable du code doit déposer sur Moodle, avant le début de la séance 6 :

    • l’URL de clonage de votre dépôt GitLab ;
    • l’identifiant du commit à évaluer.
    Important

    C’est exactement cette version de votre dépôt que nous évaluerons : les commits suivants ne seront pas pris en compte. Vérifiez donc que le commit annoncé est bien poussé sur GitLab (il doit être visible depuis la page du projet), et qu’il contient bien tout le travail que vous voulez nous montrer.

Important

En plus de la qualité du code, de la documentation et des tests unitaires, nous évaluerons également votre capacité à produire un livrable. En d’autres termes, faites attention aux éléments importants suivants :

  • Votre code doit fonctionner directement, c’est-à-dire qu’exécuter un script dans les répertoires games ou tests doit lancer une partie ou effectuer des tests sans aucune intervention de notre part. Pour cela, suivez les instructions suivantes (ce sont les mêmes que nous suivrons pour vous évaluer) :

    1. Créez un dossier livrable_2 vide sur votre ordinateur, ailleurs que dans votre workspace habituel.

    2. Depuis ce dossier, clonez votre dépôt et placez-vous sur la version annoncée sur Moodle :

      git clone <url de clonage du projet GitLab>
cd pyrat_workspace
git checkout <identifiant du commit>

    3. Dans un terminal, placez-vous dans le dossier pyrat_workspace ainsi obtenu, et lancez la commande uv sync. Cette commande recrée l’environnement virtuel, y installe PyRat ainsi que les bibliothèques déclarées dans votre pyproject.toml, et installe votre workspace lui-même, ce qui rend vos programmes importables entre eux. C’est votre pyproject.toml, qui est versionné, qui rend cette étape automatique : veillez donc à bien le pousser sur le dépôt.

    4. Si votre code a besoin d’autres bibliothèques, elles doivent avoir été ajoutées à votre projet avec uv add (elles apparaissent alors dans pyproject.toml) et être mentionnées dans votre README.md. Nous n’installerons rien à la main.

    5. Ouvrez ce dossier pyrat_workspace dans VSCode, et assurez vous que VSCode utilise l’environnement virtuel .venv de ce dossier.

    6. Lancez vos scripts de jeu et de test (par exemple uv run games/visualize_greedy.py et uv run tests/test_greedy.py depuis le dossier pyrat_workspace), et vérifiez que tout fonctionne correctement.

  • Nous évaluerons votre capacité à produire un livrable conforme aux directives données. Considérez que nous sommes un client à qui vous envoyez un logiciel que vous deviez produire. L’organisation de votre dépôt et le contenu du fichier README.md doivent correspondre à nos exigences listées ci-dessus.

Pensez à prendre en compte les remarques sur votre précédent livrable pour améliorer la qualité de votre code, documentation et tests unitaires.

Préparer la prochaine séance

  • Consulter la section « Avant le cours » de la prochaine séance, et vérifier que vous avez bien tout fait pour la préparer.
  • La prochaine séance commencera par un quiz afin de vérifier que vous avez compris les articles.