• 15 hours
  • Easy

Free online content available in this course.

course.header.alt.is_video

course.header.alt.is_certifying

Got it!

Last updated on 7/11/17

Comprenez l'explosion combinatoire avec le jeu de la ficelle

Log in or subscribe for free to enjoy all this course has to offer!

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. ;) 

 

Example of certificate of achievement
Example of certificate of achievement