Attraper 1 fromage
Durée2h30Objectifs de la séance
Dans cette séance, vous allez commencer à vous déplacer plus intelligemment. Vous découvrirez ce que sont les graphes, des structures de données pratiques pour modéliser un labyrinthe PyRat, ainsi que ce que l’on nomme des chemins dans des graphes. Vous étudierez deux algorithmes permettant de trouver de tels chemins : le parcours en largeur (Breadth-First Search, BFS) et le parcours en profondeur (Depth-First Search, DFS). Ces algorithmes produisent une table de routage, qui peut être utilisée pour trouver des chemins d’une source à une destination.
Les notions ci-dessus sont abordées dans quelques articles que vous devez étudier avant le cours. Dans l’activité pratique en classe, vous devrez programmer ces deux algorithmes, afin que votre personnage puisse se déplacer d’un endroit à un autre dans le labyrinthe en exploitant la connaissance de la carte.
Avant le cours
Pré-requis
Pour pouvoir commencer à travailler sur l’activité, vous devez remplir les conditions suivantes :
- Assurez-vous d’avoir bien installé PyRat et créé votre dépôt Git, comme décrit en séance 1.
- Sachez comment écrire un programme pour PyRat (également vu en séance 1) et l’exécuter.
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 apprendrez à passer d'un problème, décrit en langage naturel, à un algorithme, puis à un programme qui résout ce problème.
-
Dans cet article, vous apprendrez ce que sont les graphes et comment ils peuvent fournir un cadre mathématique unifié pour de nombreux problèmes.
-
Dans cet article, vous découvrirez des solutions pour représenter des graphes en mémoire dans un ordinateur.
-
Dans cet article, vous apprendrez à explorer un graphe en utilisant des algorithmes appelés parcours.
-
Dans cet article, vous apprendrez à stocker le résultat d'un parcours dans une structure de données appelée table de routage.
-
Dans cet article, vous découvrirez certaines structures de données courantes, et comment elles peuvent être utilisées pour façonner le comportement d'un algorithme de parcours.
-
Ces quiz sont là pour vous permettre de vérifier que vous avez compris les articles à étudier.
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.
Activité pratique
-
L'objectif de cette activité est d'écrire des programmes pour guider votre rat à travers le labyrinthe grâce à des algorithmes de parcours.
Après le cours
Terminer l’activité pratique
Avant la prochaine séance, vous devez :
- Si besoin, réviser les articles de cette séance.
- Terminer au moins les parties obligatoires de l’activité pratique.
Préparer la prochaine séance
De plus, vous devez :
- 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.