Qu'est ce qu'un algorithme ? Explication avec la recette des crêpes

Aujourd’hui, je réponds à la question de la petite Solène, qui se demande ce que peut bien être un algorithme.

J'ai récemment adapté ce petit billet en vidéo avec mes comparses de Big Bang Science, en version un peu simplifiée. N'hésitez pas à me dire ce que vous en pensez, ça me permettra de corriger certaines problèmes et d'adapter le niveau de vulgarisation pour d'éventuelles autres vidéos :)

Algorithme : ce mot ne cache rien de bien méchant : un algorithme est simplement une suite d'instructions permettant de faire quelque-chose. Une recette de cuisine, par exemple, est un algorithme : une suite d'opérations simples permettant de passer des ingrédients à un plat préparé.

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

On représente souvent l'algorithme de façon schématique, en décomposant les étapes et 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. En plus, 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.

Les conditions dans les algorithmes

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 :

De manière générale, un algorithme sert à traiter ce qu'on appelle des "entrées" (dans notre cas, les ingrédients et le matériel de cuisine) pour donner un résultat (les 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, condamnés à faire des crêpes ad vitam æternam.

Les algorithmes en langage informatique

Aujourd'hui, toutes les machines avec des composants électroniques ont recours à 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. 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 bonne température. Voici à quoi il pourrait ressembler (dans une version très simple) :

Pour transcrire cet algorithme an langage informatique, il faut d'abord identifier ce qu'on appelle les variables du problème. Ici les variables sont la température demandée par l'utilisateur du four (que l'on peut noter Tu) et la température du four (que l'on peut noter Tf). Dans le schéma, on fait aussi intervenir un laps de temps, auquel on peut associer une variable t. On peut alors réécrire une suite d'instructions un peu plus codifiées. L'algorithme devient :

é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

Enfin, pour traduire cela en langage informatique, on simplifie au maximum les phrases en utilisant un vocabulaire très basique qui correspond à des opérations élémentaires déjà connues par la machine. Les mots en verts sont des fonctions : des instructions qui lancent une action ou un autre algorithme, défini ailleurs. Dans l'algorithme ci-dessous 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

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 dérivés 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. 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. On arrive alors à des résultats spectaculaires, comme l'algorithme ci-dessous, qui permet de savoir si oui ou non tu es un cheval.

Comme l'indique joliment le joyeux Jojo dans son commentaire, l'algorithme ci-dessus ignore le cas de Hans le malin, cheval surdoué qui parvenait à compter, calculer et répondre à des questions simples. Plus fort que Christine Boutin donc, mais moins balèze que Paul le poulpe. L'étude de ce phénomène équin mit en lumière l'influence de l’observateur sur l'animal, le fameux "Clever Hans Effect".