Un algorithme!? Quoi? Comment? Qu'est-ce?

La plupart du temps, lorsque ce mot est évoqué par un(e) initie(e) à des personnes qui ne le sont pas, les réactions tendent à être au mieux du côté de la curiosité et du questionnement, au pire du côté de la peur et du rejet.

Ce n'est pourtant pas quelque chose dont on doit avoir peur. Si on prend la peine de savoir ce que c'est, on est aussitôt rassuré. Et croyez-moi, je sais de quoi je parle...

légotrip1

Ce n'est pas forcément la réciproque de la fonction exponentielle ou du sport qui va supplanter la Zumba.
C'est une méthode, une suite d'instructions qui permettent d'effectuer des tâches, des actions.

Il y en a partout en informatique : les suggestions sur les sites commerciaux ou les sites d'hébergement de vidéo (Daylimotion, Youtube, ...), ceux qui choisissent les publicités les mieux appropriées en fonction de nos recherches, les moteurs de recherches (de Google à votre assistant de recherche dans l'explorateur de fichier de votre ordinateur), ... etc.

Mais ce terme n'est pas propre à l'informatique, par exemple: Euclide et Archimède avaient l'usage d'un ou plusieurs algorithme(s) pour leurs théories et calculs.

Plus simple encore : les tutoriels et les recettes de cuisine sont des algorithmes.

La différence avec n'importe quelle suite de tâches à effectuer, c'est que l'algorithme doit être exécuté dans l'ordre, sans quoi , le résultat n'est pas garanti.

Il est donc nécessaire de créer un programme.

Voici un jeu de "programmation" simple à laquelle vous pouvez initier vos enfants/élèves curieux ou vos parents/grand-parents frileux du domaine informatique.

légotrip2

Avec vos briques de couleurs disposée en cercle par "maison" (représentées par les grandes briques), nous allons trier les plus petites briques par couleurs. Il n'y a qu'une brique jaune. Cet impair va nous permettre de faire se déplacer les pièces d'une maison à une autre car la règle du jeu consiste à déplacer les pièces que de proche en proche (ou de voisin en voisin) en remplaçant le trou laissé par la pièce manquante.

 

Ce jeu est simple pour le commun des mortels mais n'a pas d'ordre défini. On ne peut pas demander à un ordinateur de reproduire ce que l'on vient de faire.

Si on veut faire appliquer une méthode de résolution, le hasard n'est pas permis. Par exemple dans cette situation:


cercle1

 

4 coups sont possibles. Or, un ordinateur a besoin d'aller droit au but. Il faut restreindre les possibilités.
Nous allons donc imposer un sens de rotation. Le pièces ne pourront plus se déplacer autrement que dans le sens indiqué.
Pour ajouter une contrainte, nous allons imposer de prendre l'une des deux pièces qui aura le moins de chemin à parcourir jusqu'à sa maison en premier.

 cercle2

Cette méthode semble bonne. Mais regardons de plus prêt. Si je prends comme départ de jeu l'inversion d'une pièce blanche avec une pièce verte...

 cercle3

On peut noter qu'au bout d'un moment, on revient au même cas de figure avec d'autres pièces.

 

cercle4

Si on continue à jouer... Nous finissons par revenir au point de départ. Notre méthode fonctionne donc, mais pas dans tous les cas. Cet algorithme est donc faux.

cercle3

Pour résoudre le problème, nous allons changer la disposition de nos pièces. Au lieu de les mettre en cercle, nous allons les disposer en ligne et limiter le déplacement sur cette même ligne. Comme méthode, nous allons remplir chaque "maison" de ses briques, une à une, maison par maison.

 

ligne1

ligne2

ligne3

L'algorithme que nous avons appliqué existe sous le nom de "tri à bulles": Il consiste à comparer répétitivement les éléments consécutifs d'un tableau et à les permuter lorsqu'ils sont mal triés. Il doit son nom au fait qu'il déplace rapidement les plus grands éléments en fin de tableau, comme des bulles d'air qui remonteraient rapidement à la surface d'un liquide. Son principe est simple mais c'est le plus lent des algorithmes de tri communément enseignés.
Cet algorithme reste une bonne base pour faire comprendre la programmation à nos contemporains. :)

A la semaine prochaine. ;)