Algorithme : définition, types et exemples concrets

Définition et historique

Un algorithme est une suite finie, ordonnée et non ambiguë d’instructions permettant de résoudre un problème donné ou d’accomplir une tâche précise. En informatique, cette définition prend une résonance particulière : chaque étape doit être assez claire pour qu’une machine puisse l’exécuter sans la moindre ambiguïté, sans avoir à “deviner” l’intention du concepteur. On part d’un état initial, on applique des opérations dans un ordre défini, et on obtient un résultat attendu. C’est aussi simple que cela, du moins dans le principe.

Le terme lui-même vient de loin. Il est une latinisation du nom du mathématicien perse Muhammad ibn Musa al-Khwarizmi, qui vécut au IXe siècle à Bagdad et dont les travaux sur les opérations arithmétiques ont posé les fondements de ce qu’on appellera bien plus tard l’algèbre. Le mot “algèbre”, d’ailleurs, vient lui aussi de son traité le plus célèbre. Pendant des siècles, la notion d’algorithme est restée dans le domaine des mathématiques pures, utilisée pour décrire des procédures de calcul sans qu’on lui donne forcément ce nom. C’est au XXe siècle, avec les travaux d’Alan Turing et d’Alonzo Church dans les années 1930, que la notion prend une forme rigoureuse et universelle. Turing, notamment, formalisera la notion de machine capable d’exécuter n’importe quelle procédure calculable, posant ainsi les bases théoriques de toute l’informatique moderne.

Un algorithme correct possède trois propriétés fondamentales. D’abord la finitude : il doit se terminer en un nombre fini d’étapes, quelles que soient les données d’entrée. Un processus qui tournerait indéfiniment ne serait pas un algorithme au sens strict. Ensuite le déterminisme : à chaque étape, l’instruction à exécuter est unique et sans ambiguïté. Pour des données identiques, un algorithme déterministe produira toujours le même résultat. Enfin l’efficacité, dans le sens où chaque opération doit être réalisable concrètement, avec les ressources disponibles, et mener effectivement vers la solution.
 

Fonctionnement d’un algorithme (schéma)

Types d’algorithmes

Algorithmes de recherche et tri

Parmi les algorithmes les plus fondamentaux, ceux de recherche et de tri occupent une place centrale. Ils apparaissent dans presque tous les logiciels, des bases de données aux moteurs de recherche, en passant par les applications mobiles les plus ordinaires.

La recherche binaire est un exemple classique d’élégance algorithmique. Plutôt que de parcourir une liste élément par élément depuis le début, elle tire parti du fait que la liste est triée pour diviser l’espace de recherche en deux à chaque étape. On compare la valeur cherchée avec l’élément central : si elle est inférieure, on ne regarde que la moitié gauche ; si elle est supérieure, que la moitié droite. Et on recommence. Une liste de mille éléments sera ainsi parcourue en dix étapes au maximum. C’est là toute la puissance de cette approche.

Le tri rapide, ou quicksort, fonctionne selon une logique différente. On choisit un élément pivot dans la liste, on place tous les éléments plus petits d’un côté et tous les plus grands de l’autre, puis on répète l’opération récursivement sur chaque sous-liste. En pratique, c’est l’un des algorithmes de tri les plus performants qui existe, malgré un comportement parfois capricieux dans les cas défavorables. D’autres algorithmes de tri comme le tri par fusion ou le tri par insertion répondent à des contraintes différentes, selon que l’on privilégie la stabilité, la mémoire utilisée ou la simplicité d’implémentation.

Algorithmes gloutons et récursifs

Les algorithmes gloutons adoptent une stratégie intuitive : à chaque étape, ils font le choix qui semble localement le meilleur, sans jamais remettre en question les décisions passées. L’idée est qu’une succession de bons choix immédiats devrait mener à une bonne solution globale. C’est vrai dans certains cas, comme pour le problème du rendu de monnaie avec certains systèmes monétaires, ou pour la construction d’arbres couvrants de poids minimal avec l’algorithme de Kruskal. Mais ce n’est pas toujours le cas. Un algorithme glouton peut passer à côté de la solution optimale globale en s’engageant trop tôt dans une direction qui semblait prometteuse. C’est son talon d’Achille.

Les algorithmes récursifs, eux, se définissent par leur capacité à s’appeler eux-mêmes. Un problème est décomposé en sous-problèmes de même nature, mais plus petits, jusqu’à atteindre un cas de base suffisamment simple pour être résolu directement. La récursivité est puissante et élégante, mais elle exige de gérer avec soin les conditions d’arrêt, sous peine de provoquer une récursion infinie. Elle consomme aussi de la mémoire à chaque appel, ce qui peut devenir un problème sur des données volumineuses.

Apprentissage supervisé et non supervisé

L’intelligence artificielle moderne repose en grande partie sur des algorithmes d’apprentissage automatique, qu’on classe généralement en deux grandes familles.

Dans l’apprentissage supervisé, l’algorithme est entraîné sur des données étiquetées, c’est-à-dire des exemples pour lesquels la réponse correcte est connue. Il apprend à associer des entrées à des sorties en minimisant l’écart entre ses prédictions et les réponses attendues. Les réseaux de neurones, les forêts aléatoires ou les machines à vecteurs de support appartiennent à cette catégorie.

L’apprentissage non supervisé fonctionne sans étiquettes. L’algorithme doit lui-même trouver une structure dans les données, identifier des regroupements ou des patterns sans indication externe. K-Means est l’exemple le plus connu : il cherche à partitionner un ensemble de données en K groupes en minimisant la distance entre chaque point et le centre de son groupe. Le Q-Learning, quant à lui, appartient au domaine de l’apprentissage par renforcement, une troisième voie où un agent apprend en interagissant avec un environnement et en recevant des récompenses ou des pénalités. Il s’entraîne à prendre de meilleures décisions au fil du temps sans qu’on lui dise explicitement quoi faire.

Caractéristiques et analyse

Complexité temporelle et spatiale

Savoir qu’un algorithme fonctionne ne suffit pas. En pratique, on veut aussi savoir à quelle vitesse il fonctionne et combien de mémoire il consomme. C’est là qu’intervient la notion de complexité.

La complexité temporelle mesure le nombre d’opérations élémentaires effectuées en fonction de la taille des données d’entrée. On l’exprime généralement en notation Big O, qui décrit le comportement dans le pire des cas ou en moyenne. Un algorithme en O(n) effectue un nombre d’opérations proportionnel à la taille n de l’entrée. Un algorithme en O(n²) effectue un nombre d’opérations proportionnel au carré de cette taille, ce qui devient vite problématique à grande échelle. La recherche binaire, avec sa division par deux à chaque étape, est en O(log n), ce qui la rend extrêmement efficace.

La complexité spatiale, elle, mesure la quantité de mémoire nécessaire à l’exécution. Certains algorithmes sont très rapides mais consomment beaucoup d’espace, d’autres font le choix inverse. Le bon équilibre dépend du contexte, des contraintes matérielles et des priorités du projet.

Différence avec un programme

La distinction entre algorithme et programme est subtile mais fondamentale. Un algorithme est une description abstraite d’une procédure de résolution, indépendante de tout langage de programmation et de tout environnement d’exécution. On peut l’écrire en français, en pseudocode, sous forme d’organigramme. C’est la logique pure.

Un programme, en revanche, est la traduction concrète de cet algorithme dans un langage que la machine peut exécuter. Python, Java, C, Rust : le même algorithme peut être implémenté dans des dizaines de langages différents, avec des performances légèrement différentes selon les cas, mais la logique sous-jacente reste identique. Confondre les deux, c’est un peu comme confondre une recette de cuisine avec le plat lui-même.

Exemples simples

Prenons le calcul de la factorielle d’un entier n, noté n!. Il s’agit du produit de tous les entiers de 1 à n. Par exemple, 5! vaut 5 x 4 x 3 x 2 x 1, soit 120. En pseudocode, une version itérative de cet algorithme pourrait s’écrire ainsi : on initialise une variable résultat à 1, puis on multiplie résultat par chaque entier de 2 à n, et on retourne la valeur finale. Une version récursive définirait factorielle(n) comme n multiplié par factorielle(n-1), avec factorielle(0) égale à 1 comme cas de base.

La recherche linéaire est encore plus simple. On parcourt une liste du début à la fin, on compare chaque élément à la valeur cherchée, et on s’arrête dès qu’on la trouve ou quand on a tout parcouru sans succès. En pseudocode : pour chaque élément de la liste, si cet élément est égal à la cible, retourner sa position. Si la liste est entièrement parcourue sans résultat, retourner une valeur indiquant l’absence. C’est l’algorithme le plus naturel qui soit, et malgré sa simplicité, il reste pertinent pour les listes non triées ou de petite taille.

FAQ

Qu’est-ce qu’un algorithme ?

Un algorithme est une suite d’instructions finie et non ambiguë permettant de résoudre un problème ou d’accomplir une tâche. À partir de données d’entrée, il produit un résultat déterminé en suivant des étapes précises et ordonnées.

Quels sont les types d’algorithmes ?

On distingue principalement les algorithmes séquentiels, qui exécutent les instructions dans l’ordre, les algorithmes à branchement, qui incluent des conditions, les algorithmes récursifs, qui s’appellent eux-mêmes, et les algorithmes gloutons, qui font à chaque étape le meilleur choix local disponible. À cela s’ajoutent les algorithmes d’apprentissage automatique, supervisés ou non.

Quelle est la complexité d’un algorithme ?

La complexité d’un algorithme mesure ses ressources nécessaires en fonction de la taille des données traitées. La complexité temporelle, exprimée en notation Big O, indique le nombre d’opérations effectuées. La complexité spatiale mesure la mémoire consommée.

Donnez un exemple d’algorithme.

La recherche binaire dans une liste triée est un exemple classique. On compare l’élément central de la liste avec la valeur cherchée, on élimine la moitié non pertinente, et on répète jusqu’à trouver la valeur ou épuiser la liste. Sa complexité temporelle est de O(log n).

Quelle est la différence entre un algorithme et un programme ?

L’algorithme est la description logique et abstraite d’une procédure de résolution, indépendante de tout langage. Le programme est sa traduction concrète dans un langage de programmation exécutable par une machine. Un même algorithme peut donner lieu à des programmes très différents selon le langage utilisé.