Mis à jour le 11/07/2017
  • 15 heures
  • Facile

Ce cours est visible gratuitement en ligne.

Ce cours est en vidéo.

Vous pouvez obtenir un certificat de réussite à l'issue de ce cours.

J'ai tout compris !

Comprenez l'explosion combinatoire avec le jeu de la ficelle

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

A vous de jouer !

Pour illustrer le problème de l'explosion combinatoire, vous pouvez utiliser une activité qui consiste à faire passer une ficelle parmi des clous plantés dans une planche. Plantez une vingtaine de clous de manière aléatoire, puis essayer de trouver la manière de relier tous les clous qui consomme le moins de ficelle possible.

Reliez les clous avec le moins de ficelle possible
Reliez les clous avec le moins de ficelle possible

Si vous ne disposez pas du matériel nécessaire, vous pouvez aussi jouer à ce jeu en ligne, avec un programme Scratch qui reproduit cette activité.

L’heuristique au secours de l’algorithmicien(ne)

“Explosion combinatoire” vous dîtes ? Vous y allez un peu fort non ?

Eh bien peut-être pas encore assez fort. Quand on passe de quelques chemins possibles à plusieurs milliards de milliards… ça donne le vertige non ?

Ah yes ! Quelques sensations fortes !

Eh oui ! Alors allons jouer à se faire peur avec tous ces milliards de chemins... avant de remettre doucement les pieds sur terre pour ne plus jamais se perdre dans ce monde numérique... grâce à la science informatique !

Pour vous convaincre de l'explosion combinatoire du nombre de solutions possibles au problème du voyageur de commerce, vous pouvez faire quelques essais avec un second projet sur scratch.

Et puisqu’on parle de chemin… Est-ce que vous mesurez le chemin que vous avez parcouru jusqu’ici au sujet des algorithmes ? Vous avez commencé par la simple idée qu’un algorithme est une suite d’instructions. Vous avez découvert les 4 ingrédients qui les composent. Puis vous avez comparé des algorithmes, et vu que différentes méthodes pouvaient exister pour un même résultat. Vous avez comparé ces méthodes, et en particulier leur efficacité. Et, enfin, vous avez vu que tous les problèmes ne peuvent pas être résolus par un algorithme… en tout cas pas en un temps raisonnable. Alors moi je dis que vous aurez bientôt largement mérité de partir en week-end ! Mais prenez tout de même votre GPS... on ne sait jamais. ;) 

 

Exemple de certificat de réussite
Exemple de certificat de réussite