Attraper N fromages

Objectifs de la séance

Dans cette séance, nous augmentons considérablement la difficulté en considérant des labyrinthes avec plusieurs morceaux de fromage. L’objectif sera de tous les attraper, en un minimum de tours. Pour ce faire, nous introduirons 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 qu’il est impossible de le faire en un temps acceptable pour de grands nombres de morceaux 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.

Avant le cours

Pré-requis

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

• Apportez votre propre ordinateur.
• Assurez-vous d’avoir une connexion réseau fonctionnelle.

Soumettez votre livrable

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

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 :

• Complexité des algorithmes.
• Complexité des problèmes & NP-complétude.
• Le problème du voyageur de commerce.
• Bruteforce & backtracking pour résoudre les problèmes NP-complets.

Voici un petit quiz d’auto-évaluation pour vérifier votre compréhension des articles :

• Quiz d’auto-évaluation.

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 enseignants dans votre classe.

Activité pratique

Le reste de la séance sera consacré à une activité pratique visant à programmer les algorithmes étudiés dans les articles ci-dessus. Cliquez sur le lien ci-dessous :

• Activité pratique.

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.