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’on ne connaît aucun algorithme permettant 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

• Ayez un Dijkstra fonctionnel (cf séance 3), ou à défaut un BFS fonctionnel (cf séance 2).
• N’oubliez pas, vous devez soumettre votre livrable de séance 3 avant le début de cette séance !

Articles à étudier

• Complexité des algorithmes

  Dans cet article, vous allez découvrir une notion théorique importante pour comparer les algorithmes : la complexité.

  15 min de lecture

• Complexité des problèmes & NP-complétude

  Jusqu'à présent, nous avons étudié la complexité des algorithmes, comme moyen d'estimer le temps nécessaire à leur exécution en fonction de leurs entrées.

  10 min de lecture

• Le problème du voyageur de commerce

  Dans cet article, vous découvrirez un problème célèbre en informatique, appelé le « problème du voyageur de commerce » (ou « Traveling Salesperson Problem », TSP).

  10 min de lecture

• Bruteforce & backtracking pour résoudre des problèmes NP-complets

  Dans cet article, nous vous présentons une approche pour résoudre le problème du voyageur de commerce (TSP), ou plus généralement des problèmes NP-complets.

  30 min de lecture

• Quiz d’auto-évaluation

  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

• Activité pratique

  Dans cette activité, vous allez programmer un joueur qui attrape plusieurs morceaux de fromage en un minimum de tours.

  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é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.