PyRat est le module de programmation, algorithmique et théorie des graphes de tronc commun en première année à l’IMT Atlantique. L’objectif du module est de vous enseigner les algorithmes de parcours classiques en théorie des graphes, en Python, en s’appuyant sur un jeu de labyrinthe (présenté ici).
Déroulement du cours
Contrairement à la majorité des cours classiques, PyRat n’est pas divisé en créneaux de cours/TD/TP. A la place, vous suivrez sept cours de trois heures chaque, auxquels s’ajoutent un pré-cours (présentation du cours) et un tournoi de fin de module.
Chacun des six premiers cours est divisé en plusieurs phases :
- Evaluation écrite (~10mn) : Le début de chaque cours (sauf bien évidemment le premier) sera consacré à une évaluation écrite. Le but n’est pas de vous piéger, mais de bien vérifier que vous avez acquis les différentes notions étudiées lors des séances précédentes.
- Cours interactif (~1h10mn) : Durant le restant de la première heure, nous aborderons ensuite des nouvelles notions et les mettrons directement en application à l’aide de petits exercices.
- Pause (~10mn).
- TP (~1h30mn) : Vous aurez à atteindre plusieurs objectifs intermédiaires (présentés plus bas). Pour ce faire, le temps restant sera consacré à une séance de TP (en binômes), durant laquelle vous pourrez travailler sur votre code, et profiter de l’aide de l’enseignant(e) au besoin.
La septième séance est un peu particulière. L’objectif final du cours est de programmer une petite intelligence artificielle pour ramasser des morceaux de fromage dans un labyrinthe. Cette séance est l’occasion pour vous de présenter à la classe (dix minutes, avec des diapos, démos…) les choix que vous aurez pu faire, et de montrer en quoi votre stratégie est intéressante. Vous serez évalué sur la qualité de votre présentation, mais aussi sur l’originalité de votre programme et sur la pertinence des réponses aux questions qui vous seront posées après votre présentation.
Après le cours, nous organiserons un tournoi afin de faire s’affronter vos différentes IAs. La compétition n’est pas notée, mais l’équipe gagnante remportera une coupe, et son IA servira de boss final pour les étudiants de l’année suivante !
Etapes intermédiaires
Afin de vous aider à assimiler les notions vues en cours de manière progressive, vous aurez à réaliser au fur et à mesure des cours des codes en Python (les objectifs à atteindre sont détaillés dans les pages associées aux cours). Ces programmes serviront de base de discussion lors des évaluations orales. Pour cela, nous vous fournissons ici un logiciel qui servira de support au cours. Plus exactement, PyRat est un jeu dans lequel vous êtes placé dans un labyrinthe où se trouvent des morceaux de fromage, qu’il vous faudra ramasser en vous servant des notions vues en cours.
Les objectifs sont les suivants :
- Pour la séance 3 : Il n’y a qu’un morceau de fromage au centre du labyrinthe, que vous devez ramasser en un minimum de déplacements.
- Pour la séance 6 : Il y a plusieurs morceaux de fromages dans le labyrinthe, que vous devez ramasser en un minimum de déplacements.
- Pour le tournoi : Vous n’êtes plus tout seul dans le labyrinthe, et vous devez ramasser plus de morceaux de fromage que votre adversaire.
Le système d’évaluation
Le système de couleurs
En naviguant à travers les différents articles (ainsi que sur la fiche d’évaluation téléchargeable ici), vous pourrez remarquer l’utilisation de trois couleurs, servant à indiquer le niveau associé aux notions introduites :
- Vert : C’est le niveau essentiel, ce que tout étudiant doit comprendre/appliquer pour espérer valider le module. Les notions introduites dans les sections de niveau vert du blog seront régulièrement évaluées à l’écrit en cours, et leur mise en pratique sera évaluée lors d’entretiens oraux, présentés plus bas.
- Bleu : C’est le niveau approfondi, regroupant des notions plus avancées que le niveau vert, que tout étudiant suivant le cours devrait être capable d’assimiler. Les notions présentées sur le blog seront aussi évaluées à l’écrit, et vous permettront d’atteindre une note supérieure à la moyenne.
- Rouge : Le niveau rouge est le plus ouvert. Il contient principalement une liste de liens (Wikipédia, papiers de recherche…) qui vous permettront d’approfondir les notions proposées en autonomie. Contrairement aux niveaux vert et bleu, le niveau rouge n’est pas évalué à l’écrit. En revanche, lors des interrogations orales, nous tiendrons compte de l’effort d’approfondissement que vous aurez fourni.
Les évaluations écrites de début de cours
Comme nous l’expliquions plus haut, le but des évaluations écrites est de vous inciter à assimiler les notions que nous jugeons essentielles. L’enseignant(e) corrigera donc rapidement vos réponses durant la pause, et vous rendra votre copie directement après.
Chaque évaluation écrite comportera des questions de niveau vert et de niveau bleu. Si vous répondez parfaitement à toutes les questions vertes, les réponses aux questions bleues sont également comptabilisées dans la note. Dans le cas contraire, vous pourrez profiter de la partie TP du cours pour venir expliquer à l’enseignant(e) pourquoi vous vous êtes trompé(e), et corriger vos erreurs afin de valider les questions vertes. Entre temps, vous êtes libre de consulter tous les documents que vous voulez, ou de vous faire expliquer votre erreur par un(e) ami(e). Toutefois, vous devrez expliquer la correction à l’enseignant(e), pas juste donner la bonne réponse.
Attention ! Les bonnes réponses aux questions bleues ne seront comptabilisées que si vous validez les questions vertes du premier coup ! La seconde chance ne vous permet que de rattraper les questions vertes.
Quelques précisions sur les évaluations orales
A ces évaluations écrites s’ajoutent des évaluations orales, aux séances 3 et 6, qui se dérouleront sous la forme de courts entretiens de cinq minutes avec l’enseignant(e) pendant le créneau de TP. Ces entretiens sont pour vous des opportunités de présenter à l’enseignant(e) les approfondissements que vous aurez réalisés.
A noter que le système de couleurs s’applique aussi à ces évaluations orales. Le niveau vert est validé si vous êtes capable de présenter votre implémentation des algorithmes vus en cours, et le niveau bleu est validé si vous êtes capables d’en illustrer les forces et faiblesses à l’aide d’outils appropriés (statistiques, analyses…).
Le niveau rouge est atteint si vous avez fourni un travail considéré par l’enseignant(e) comme plus conséquent que le niveau bleu (étude approfondie, autre algorithme non vu en cours, utilisations d’autres structures de données…). Les parties rouges du blog donnent des pistes à explorer en autonomie afin de valider le niveau rouge, mais tout autre travail jugé au delà du niveau bleu sera gratifié.
Voici quelques pistes de réflexion pour préparer ces entretiens :
- Comparer vos algorithmes avec d’autres algorithmes glanés sur Internet ou ailleurs.
- Regarder l’impact des paramètres des labyrinthes (configuration, taille…) sur les performances ou la correction de vos algorithmes. Des courbes (moyennées si besoin) aident à illustrer les résultats.
- Utiliser des cas de test déterministes pour vérifier certaines propriétés.
- Valider expérimentalement des conjectures ou des intuitions sur certaines propriétés des algorithmes.
Attention ! Au premier cours, un certain nombre de règles de programmation vous seront présentées, afin de produire du code propre. Lors des évaluations orales, votre respect de ces règles sera aussi évalué (comme si c’était une question verte).