Catch multiple pieces of cheese

Duration2h30 + préparation

Présentation & objectifs

Dans cette séance, nous augmentons significativement la difficulté, en considérant des labyrinthes avec plusieurs morceaux de fromage. L’objectif sera de tous les attraper, en un nombre minimum de tours. Pour ce faire, nous allons introduire un problème appelé le “Problème du voyageur de commerce” (ou “Traveling Salesperson Problem”, TSP en abrégé). Nous verrons que ce problème est très complexe à résoudre, et que vous ne pouvez pas espérer le faire dans un temps acceptable pour de grandes quantités de fromage.

Les notions ci-dessus sont couvertes par quelques articles que vous devez étudier avant le cours. Dans l’activité pratique, vous devrez programmer une solution au TSP basée sur une recherche exhaustive. Cela vous permettra d’attraper tous les morceaux de fromage en un nombre minimum de tours.

Avant le cours

Exigences techniques

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

Soumettez votre livrable

N’oubliez pas, vous devez soumettre votre livrable pour la session 3 avant le début de cette séance !

Acquisition des connaissances préalables

Pour pouvoir commencer efficacement l’activité pratique, nous avons introduit certains concepts nécessaires à la fin de la séance précédente. Voici les diapositives utilisées en cours :

Ces diapositives couvrent uniquement les éléments principaux du cours, et beaucoup plus de détails sont donnés dans les articles associés. Ainsi, vous devez étudier les articles suivants chez vous avant la séance :

Vous pouvez vérifier votre compréhension de ces articles ici :

Pendant le cours

Quiz

Au tout début de la séance, nous commençons par un quiz évalué Wooclap pour vérifier votre compréhension des articles que vous avez dû étudier. Le lien sera donné par l’enseignant au début du cours. Assurez-vous d’être à l’heure !

Activité pratique

Le cours est dédié à une activité pratique. Lorsque le quiz est terminé, allez vous asseoir avec votre groupe, et cliquez sur le lien ci-dessous pour commencer :

Après le cours

Compléter la séance en cours

Avant la prochaine séance, vous devez :

  • Revoir le contenu des articles ci-dessus.
  • Compléter les parties non optionnelles de l’activité pratique.

Préparer la prochaine séance

De plus, vous devez :

  • Vérifier la section “Avant le cours” de la prochaine séance, et vous assurer de faire tout ce qui est nécessaire pour la préparer.
  • La prochaine séance commencera par un quiz évalué pour vérifier que vous avez compris les articles.