Un algorithme, qu’est-ce que c’est ?

Aujourd’hui, les algorithmes sont partout : dans nos fils d’actualités, dans nos résultats de recherche, dans nos suggestions d’achat, mais aussi dans des objets concrets comme les véhicules autonomes ou encore nos thermostats connectés. Mais alors, qu’est-ce que c’est ?

L’algorithme, une définition

Un algorithme est une suite d’instructions non équivoques, données dans un ordre précis, qui permettent de résoudre un problème. Eh oui, c’est aussi simple que ça — une recette de cuisine, ou encore une liste d’indications pour se rendre à un lieu sont des algorithmes. Sur un ordinateur, il en va de même : un algorithme informatique est une suite d’instructions qui guide un ordinateur vers l’exécution d’une tâche, en vue d’un but prédéfini — résoudre un problème, ou encore traiter une série d’entrées pour obtenir un résultat.

Bien qu’aujourd’hui massivement utilisés et compris dans le domaine de l’informatique, du code et du web, les algorithmes sont pourtant omniprésents. Par exemple, vous utilisez un algorithme (une suite d’instructions) pour préparer des crêpes (votre problème) :

• Mettre la farine dans un saladier
• Ajouter vos œufs, l’huile et le beurre
• Mélanger le lait
• Laisser reposer
• Cuire à la poêle

Dans cette préparation de crêpes, les ingrédients sont vos données en entrée, les crêpes votre résultat. Et l’ordre est indispensable à la résolution du problème : vous n’obtiendrez pas de bonnes crêpes en mettant la farine à la poêle pour ensuite lui ajouter du lait.

Et la non-ambiguïté, dans tout ça ? Vous avez raison de poser la question : les instructions ci-dessus peuvent être ambiguës (qu’est-ce que de la farine ? Combien d’œufs faut-il ? Mélanger, ça veut dire quoi ?). Ainsi, dans une suite algorithmique, le niveau de précision des instructions dépend-il du niveau d’informations présentes dans son environnement. Pour reprendre l’exemple des recettes de cuisine, une liste d’ingrédient est fournie en amont de la liste d’instruction, permettant ainsi de donner à l’opérateur le contexte suffisant à la bonne exécution de la recette.

Pourquoi utiliser l’ordinateur pour effectuer des algorithmes ? Parce que ce sont des machines capables d’exécuter des suites d’instructions beaucoup plus rapidement, et pendant beaucoup plus de temps qu’un être humain. Mais alors, sur quoi reposent ces listes d’instructions ?

AND, OR et NOT vs IF, THEN et ELSE : algorithmes et booléens

Ainsi donc, nous avons une situation de départ avec des données en entrée, puis une suite d’instructions, utilisées pour obtenir un résultat. Entre les deux, deux formes d’instructions — les premières analysant la situation et donnant des instructions en fonction du caractère vrai ou faux des conditions préétablies, les secondes donnant des règles de combinaisons entre les éléments.

If (x), then (y) et else (z) : les conditions

If, then et else sont les booléens (variable à deux états, typiquement vrai ou faux) qui permettent de guider l’algorithme depuis une entrée, vers l’exécution un résultat.

• If : si la condition x est vraie
• Then : il exécutera l’action y
• Else : sinon, il exécutera l’action z

And, or et not : les combinaisons

And, or et not permettent de donner les règles de combinaison des différents éléments :

• And : conjonction des éléments
• Or : disjonction des éléments
• Not : négation d’un élément

Pour reprendre l’exemple de nos crêpes, voici comment se décrit la recette :

1. IF (Farine AND Œufs AND Huile AND Beurre AND Sucre) THEN (Sortir le saladier) ELSE (Aller acheter les ingrédients OR se résigner à ne pas manger de crêpes)
2. IF (Le saladier est sorti) THEN (Mettre la farine NOT le lait) ELSE (pas de crêpes aujourd’hui)
3. … et ainsi de suite !

 

Mais en quoi ça nous intéresse, tout ça ?

Dans les faits, tout traitement de données passe par un algorithme, plus ou moins complexe. Prenons par exemple un corpus d’individus, que nous voudrions trier en fonction de leur langue (cela devrait vous rappeler quelque chose). Pour pouvoir nous aider visuellement, nous classerons ces individus en deux colonnes : la verte et la rouge. La réalité du traitement de données est bien plus complexe, mais nous schématisons afin de nous faire comprendre :

• Tous les individus parlant français en vert, sinon en rouge :
  IF (Fr) THEN (Vert) ELSE (Rouge)
• Tous les individus ne parlant pas français en vert :
  IF (NOT Fr) THEN (Vert) ELSE (Rouge)
• Tous les individus parlant français ou anglais en vert :
  IF (Fr OR Eng) THEN (Vert) ELSE (Rouge)
• Tous les individus parlant français et anglais en vert :
  IF (Fr AND Eng) THEN (Vert) ELSE (Rouge)
• Supprimer tous les individus en rouge :
  IF (Rouge) THEN (supprimer) ELSE (Garder)

La liste des combinaisons est longue, voire quasi infinie, tout comme l’est celle des possibilités de traitement d’une base de données. À vous de mettre la main à la pâte !

 

Lecture complémentaire :

• Algorithmique pour l’apprenti programmeur