Qu’est ce qu’un algorithme ?

Aujourd’hui, je réponds à la question de la petite Solène, qui se demande ce que peut bien être un algorithme. Ce mot parait un peu compliqué, mais il désigne en fait quelque-chose de très simple : un algorithme est une suite d’instructions. C’est tout 🙂 Ces instructions sont souvent très simples, on essaie même de les rendre les plus simples possibles. Elles servent généralement à faire quelque-chose, mais on peut aussi faire des algorithmes qui ne servent à rien.

Ce qui rend les algorithmes un peu compliqués, c’est qu’ils sont souvent écrits dans un langage particulier, pour être compris par des machines. Pour expliquer tout cela, nous allons prendre l’exemple d’une recette de cuisine.

La recette de la pâte à crêpes  est en effet un algorithme : c’est une suite d’opérations simples qui te permettent de préparer … de la pâte à crêpes. Logique.

Des ingrédients aux crêpes, images honteusement chipées sur le blog de hoptoys

La recette est souvent décomposée en étapes, que tu dois réaliser dans l’ordre. Les algorithmes sont représentés de la même façon ou presque : on décompose les étapes en les reliant par des flèches, un peu comme ci-dessous :

Pour faire des crêpes, il suffit de suivre les instructions dans l’ordre. Les recettes sont des algorithmes destinés aux humains et sont donc écrites dans un langage compréhensible par des humains. Comme on suppose que les humains sont raisonnablement intelligents, il y a plein de choses qu’on n’a pas besoin de préciser dans la recette, par exemple qu’ il faut retirer la coquille des œufs ou ne pas utiliser du lait de raton-laveur. Pour les machines, c’est un peu différent : il faut absolument tout préciser !

De manière générale, un algorithme sert à traiter ce qu’on appelle des « entrées » pour donner un résultat. Ici, les entrées sont les ingrédients et le matériel de cuisine, et le résultat est la pâte à crêpes.

Les instructions décrites dans l’algorithme doivent être très simples et ne pas porter à confusion. Pour obtenir le même résultat, il existe une infinité d’algorithmes possibles. Dans la recette des crêpes, on pourrait rajouter une étape consistant à faire tourner la bouteille de lait cinq fois sur elle même avant de s’en servir. Cela ne changerait rien au résultat : c’est donc une étape inutile. Un bon algorithme est une recette facile à suivre, qui ne fait pas perdre de temps inutilement et qui ne provoque pas d’erreurs. Un bon algorithme doit aussi avoir un début et surtout .. une fin ! Tous les informaticiens du monde se sont un jour retrouvés confrontés à l’horreur absolue d’une boucle infinie : comme si tu étais condamné(e) à faire des crêpes pour toujours !

 

Les conditions dans les algorithmes

L’algorithme de la recette des crêpes est très simple car il n’y a qu’un seul choix possible à chaque étape. Pour aborder cette notion de choix, nous allons considérer un autre algorithme : celui qui permet de déterminer si on peut faire des crêpes ou non, en fonction de ce qu’il y a dans le frigo et les placards.

Avant de se lancer dans la confection des crêpes, on vérifie d’ordinaire qu’on a bien tout ce qu’il faut. C’est quelque-chose de facile pour un humain, mais supposons que tu aies la chance d’avoir un robot pour t’aider en cuisine. Pour s’assurer qu’il dispose de suffisamment d’ingrédients, voici un des algorithmes qu’il pourrait utiliser, sachant qu’il lui faudra des œufs, du lait, de la farine, du sucre et du beurre.

Dans ce schéma, le robot va vérifier une à une toutes les conditions nécessaires au bon déroulement de la préparation des crêpes. Les questions qu’il doit se poser sont affichées dans des losanges et les instructions dans des rectangles. À chaque étape, en fonction des réponses, les instructions peuvent changer :

Les algorithmes en langage informatique

Aujourd’hui, toutes les machines avec des composants électroniques utilisent des algorithmes, qui peuvent être plus ou moins compliqués. Ces algorithmes sont généralement conçus par des humains, qui réalisent des schémas qui ressemblent à ceux que nous avons vus précédemment. Mais pour être compris par des machines, ces schémas doivent être traduits en langage informatique. Considérons par exemple un algorithme très simple, toujours dans la cuisine : celui qui permet au four de maintenir la température demandée. Appelons le « algorithme bonne température ». Voici à quoi il pourrait ressembler (dans une version très simple) :

Pour que le four comprenne cet algorithme et puisse suivre les instructions, il faut le traduire en langage informatique. Et pour cela, il faut identifier ce qu’on appelle les variables : ce sont les données que la machine doit connaitre pour suivre les instructions de l’algorithme. Ici, le four doit connaitre la température demandée par l’utilisateur du four (que l’on peut noter Tu) et la température actuelle du four (que l’on peut noter Tf).

Dans le schéma, on fait aussi intervenir un laps de temps pendant lequel le four accomplit une instruction. On peut y associer une variable t. On peut alors réécrire l’algorithme de chauffage de façon un peu plus « brute ». L’algorithme devient :

Algorithme bonne température
étape 1 Lire et Mémoriser Tu

étape 2 Mesurer Tf

Si Tf est inférieure à Tu : chauffer fortement le four pendant un temps t = 60 secondes puis revenir à l‘étape 2

Si Tf est égale à Tu : chauffer modérément le four pendant un temps t = 60 secondes puis revenir à l‘étape 2

Si Tf est supérieure à Tu : interrompre le chauffage pendant un temps t = 60 secondes puis revenir à l‘étape 2

Mais cela n’est pas suffisant, il faut donc encore simplifier les phrases en utilisant un vocabulaire très basique qui correspond à des opérations élémentaires déjà connues par la machine. Dans l’algorithme simplifié ci-dessous, Les mots en verts sont des fonctions : des instructions qui lancent une action ou un autre algorithme, défini ailleurs. Par exemple, la fonction compteur effectue un compte à rebours à partir de la valeur t.

Algorithme bonne température

Début
étape 1 Lire Tu
étape 2 Lire Tf
t = 60

Si Tf inférieur à Tu
Alors
exécuter compteur (t)
tant que t supérieur à 0
exécuter chauffage fort
fin tant que

aller à étape 2

fin Si

Si Tf = Tu
Alors
exécuter compteur (t)

tant que t supérieur à 0
exécuter chauffage doux
fin tant que

aller à étape 2

fin Si

Sinon
exécuter compteur (t)
tant que t supérieur à 0
exécuter chauffage stop
fin tant que

aller à étape 2

fin Si

fin

On pourrait encore simplifier l’algorithme en remplaçant les mots par des symboles, mais tu as compris le principe !

Les algorithmes dans la vie quotidienne

Tu t’en doutes, la grande majorité des algorithmes sont beaucoup plus compliqués que cela ! Mais ce qui est cool, pour les gens qui les inventent, c’est qu’ils sont tous écrits avec un vocabulaire simple et restreint, même lorsqu’ils sont issus de théories mathématiques assez pointues. C’est le cas par exemple de l’algorithme de Dijkstra, qui sert à trouver un chemin optimal dans les applications GPS. On retrouve les algorithmes, avec leur double mathématique maléfique, un peu partout aujourd’hui. Dans les jeux vidéos par exemple : tout ce qui se passe sur l’écran dépend d’algorithmes, et tu fournis toi même certaines variables en appuyant sur des boutons. Tous les programmes installés sur ton ordinateur utilisent des algorithmes. Les moteurs de recherche, la confidentialité des transactions en ligne, la gestion des bonus dans Candy Crush et celle des stocks d’Ikea dépendent d’algorithmes. Leur qualité dépend essentiellement du temps qu’ils mettent pour résoudre un problème et fournir un résultat correct ainsi que des ressources qu’ils vont utiliser sur les ordinateurs. Des gens sont payés très chers pour trouver les algorithmes les plus performants, ceux qui iront le plus vite et qui nécessiteront le moins de mémoire ! Et Si tu ne sais pas quoi faire plus tard, ça peut être une bonne piste 🙂

Texte : Karim de Sweet Random Science

Illustrations : Kam et Karim.