Les algorithmes

Un algorithme, c'est une suite d'étapes précises pour résoudre un problème ou obtenir un résultat. Rien de magique ni de réservé aux génies : une recette de cuisine, un itinéraire, une division posée à la main sont des algorithmes. On en suit tous les jours sans y penser.

Le mot vient d'ailleurs du mathématicien perse Al-Khwarizmi (IXe siècle), bien avant les ordinateurs. En programmation, l'algorithme, c'est le raisonnement que tu poses avant d'écrire la moindre ligne de code.

# Un algorithme, c'est quoi ?

Une bonne définition tient en trois propriétés. Un algorithme est :

• précis : chaque étape est claire, sans ambiguïté ;
• fini : il se termine (il ne tourne pas en rond pour toujours) ;
• indépendant du langage : c'est une idée, pas une syntaxe.

C'est exactement ce que la machine exécute, bêtement et à la lettre : si ton algorithme est bancal, le résultat le sera aussi.

# Les trois briques de tout algorithme

Toute la programmation tient sur trois structures. Combinées, elles suffisent à exprimer n'importe quel algorithme.

Séquence

Les instructions s'exécutent dans l'ordre, une par une, de haut en bas. C'est le comportement par défaut.

faire A
puis B
puis C

faire A

puis B

puis C

Condition (le branchement)

On choisit un chemin selon une situation : si telle chose est vraie, faire ceci, sinon faire cela.

si solde < 0 :
    refuser le paiement
sinon :
    accepter

si solde < 0 :

    refuser le paiement

sinon :

    accepter

Boucle (la répétition)

On répète une action, soit un nombre de fois donné, soit **tant qu'**une condition tient.

pour chaque article du panier :
    ajouter son prix au total

pour chaque article du panier :

    ajouter son prix au total

# Un exemple complet

Mettons les trois briques bout à bout. Objectif : trouver le plus grand nombre d'une liste.

plus_grand = premier élément de la liste     # séquence
pour chaque nombre de la liste :             # boucle
    si nombre > plus_grand :                 # condition
        plus_grand = nombre
afficher plus_grand

plus_grand = premier élément de la liste     # séquence

pour chaque nombre de la liste :             # boucle

    si nombre > plus_grand :                 # condition

        plus_grand = nombre

afficher plus_grand

On part d'un premier candidat, on parcourt la liste, et on garde le plus grand qu'on croise. Séquence + boucle + condition, rien de plus.

# L'algorithme n'est pas le code

L'algorithme est le raisonnement ; le code n'en est que la traduction dans un langage. Le même algo « trouver le plus grand » s'écrit en C#, en Python ou même en français.

On le décrit d'abord en pseudocode (comme ci-dessus) ou en schéma, puis on le traduit. Poser l'algorithme avant de coder, c'est bien plus efficace que d'écrire du code au hasard en espérant que ça marche.

# Plusieurs chemins, pas tous égaux

Un même problème a plein d'algorithmes possibles, et ils ne se valent pas. Chercher un mot dans un dictionnaire page par page fonctionne, mais ouvrir au milieu et couper en deux à chaque fois (la recherche dichotomique) est infiniment plus rapide.

Deux algorithmes tous les deux justes peuvent donc être très différents en efficacité. Mesurer et comparer cette efficacité, c'est le rôle de la complexité (la fameuse notation « Big O »), un sujet à part entière.

# À retenir

• Un algorithme = une suite d'étapes précises pour résoudre un problème ; c'est le raisonnement, indépendant du langage.
• Tout algorithme se construit avec trois briques : séquence, condition, boucle.
• On le pose d'abord (pseudocode), on le code ensuite.
• Un même problème a plusieurs solutions, qui diffèrent en efficacité (voir la complexité / Big O).

Les algorithmes vont de pair avec les structures de données : c'est la bonne structure qui rend le bon algorithme possible.