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 faisant à 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

  • Avoir terminé au moins une des implémentations du problème du voyageur de commerce (cf séance 4).

Articles à étudier

  • 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

  • Lors de la séance précédente, vous avez vu qu'aucun algorithme exact ne permet d'attraper en un temps raisonnable les 21 morceaux de fromage d'une partie par défaut.

    2h30

Après le cours

Terminer l’activité pratique

  • Si besoin, révisez les articles de cette séance.
  • Terminez les parties obligatoires de l’activité pratique.
  • Préparez le livrable mentionné ci-dessous.

Évaluation

Ce qui est évalué

Cette séance clôt la seconde partie du projet, qui vise à attraper plusieurs morceaux de fromage dans le labyrinthe. Avant le début de la présentation finale, vous devrez rendre un livrable contenant les codes que vous aurez produits jusque là pour répondre à cet objectif (séance 5 incluse).

Information

Vous pouvez laisser les fichiers du livrable précédent sur votre GitLab. Attention toutefois à bien rédiger votre README pour rendre explicite ce que vous réutilisez de vos anciens codes, et ce qui est spécifique à ce nouveau livrable.

La modalité d’évaluation est décrite sur la page principale du projet.

Comment rendre le livrable

La modalité de rendu de ce livrable est exactement la même qu’en séance 3. Référez-vous à la page correspondante pour obtenir toutes les informations.

Pensez à bien mettre à jour votre README (notamment vos rôles !). Vous pouvez renommer l’ancien README.md en README.md.old et en créer un nouveau pour vous faciliter la vie.

Prenez également le temps de relire les remarques données dans les consignes du premier livrable, et tenez compte des remarques de votre enseignant(e) sur votre précédent livrable pour améliorer la qualité de votre code, documentation et tests unitaires.

Grille d’évaluation

Partie globale (G) Points
Le livrable respecte la forme demandée / 2
Les remarques sur le livrable précédent ont été prises en compte / 1
L’enseignant(e) peut exécuter les codes sans intervention
autre que le téléchargement et l’installation des dépendances 		/ 3
Le fichier README.md est succinct et va droit au but / 1
L’historique du dépôt Git montre un travail partagé et régulier / 3
Pénalité de retard
-1 par jour entamé		 -1 / jour
Total (G) / 10
Partie code (C) Points
L’algorithme exhaustif (et ses améliorations) fonctionne et est correct / 5
L’algorithme glouton (et ses améliorations) fonctionne et est correct / 5
Le code existant est réutilisé plutôt que recopié / 3
Des études pertinentes sont faites pour comparer les différentes approches / 2
Le code est cohérent avec l’architecture imposée
hérite de Player, méthodes turn, preprocessing/postprocessing si pertinent 		/ 2
Le découpage en méthodes est pertinent et facilite la lecture/test du code / 3
Des éléments des sections “Pour aller (encore) plus loin” sont présents
incluant ceux de la séance 1 		/ 5
Total (C) / 25
Partie documentation (D) Points
Le fichier README.md est clair, concis, et complet
il fournit toutes les informations nécessaires pour utiliser/tester/comprendre le code 		/ 10
Chaque fonction est documentée
entrées, sorties, description, exceptions 		/ 5
Des type hints sont utilisés pour les entrées et sorties de toutes les fonctions / 3
Les blocs de code sont commentés, et le code respecte les conventions
nommage correct, pas de constantes en dur, commentaires utiles, etc. 		/ 5
Le code est en anglais
noms de variables, fonctions, classes, commentaires 		/ 2
Total (D) / 25
Partie tests (T) Points
Chaque méthode est testée / 5
Les tests couvrent les cas nominaux, avec exemples fixés ou aléatoires pour vérifier des propriétés / 5
Les tests couvrent aussi les cas d’erreur
entrées invalides, conditions aux limites 		/ 5
Tous les tests passent correctement / 5
Les tests sont bien structurés
utilisation de unittest, des méthodes setUpClass, setUp et tearDown notamment 		/ 5
Total (T) / 25

Préparer la prochaine séance

  • Consultez la section « Avant le cours » de la prochaine séance, et vérifiez 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.