L'algorithmique
Un algorithme est une méthode décrite pas à pas pour résoudre un problème : une suite finie d’instructions précises qui, appliquées à des données, mènent à coup sûr à un résultat. L’algorithmique est la discipline qui conçoit ces méthodes, vérifie qu’elles sont justes et mesure leur efficacité. Tout programme informatique commence par là.
- Rubrique
- Fondamentaux
- Niveau
- Débutant à avancé
- Lecture
- 15 min (essentiel)
26 min (complet) - Révision
- 22 octobre 2026
En bref
- Un algorithme est une suite finie d’instructions sans ambiguïté qui transforme des données d’entrée en un résultat.
- Il s’écrit d’abord indépendamment de tout langage, en pseudo-code ou sous forme d’organigramme, puis il est traduit en programme.
- Quelques briques suffisent pour tout exprimer : des variables, la séquence, la condition, la boucle et l’appel de fonction.
- Deux algorithmes justes peuvent avoir des efficacités très différentes : chercher un nom parmi un million demande jusqu’à un million de comparaisons, ou 20 seulement si la liste est triée.
- En sécurité, un algorithme de chiffrement doit pouvoir être public : seule la clé doit rester secrète.
Prérequis conseillés : Qu'est-ce que l'informatique ?
1Définition
Le dictionnaire définit l’algorithme comme une « suite finie d’opérations élémentaires constituant un schéma de calcul ou de résolution d’un problème ». Plus simplement, c’est une suite d’opérations décrites sans ambiguïté, qu’elles soient écrites dans un programme ou griffonnées sur une feuille de papier, qui permet de résoudre un problème ou d’obtenir un résultat à partir de données. On peut dire qu’il s’agit de la description logique d’un programme. L’algorithmique est la discipline qui étudie ces méthodes : comment les concevoir, comment prouver qu’elles donnent le bon résultat, et combien de temps et de mémoire elles demandent.
On compare souvent un algorithme à une recette de cuisine : des ingrédients (les données d’entrée), une suite d’étapes, un plat (le résultat). L’image est utile, mais une recette tolère le flou (« salez à votre goût », « faites cuire jusqu’à ce que ce soit doré »), alors qu’un ordinateur n’interprète rien : chaque instruction doit pouvoir être exécutée mécaniquement, de la même façon à chaque fois. Le mathématicien Donald Knuth a résumé en 1968 les cinq propriétés qu’on attend d’un algorithme :
- la finitude : il se termine toujours après un nombre fini d’étapes ;
- la précision : chaque étape est définie sans ambiguïté ;
- des entrées : il reçoit zéro, une ou plusieurs données de départ ;
- des sorties : il produit au moins un résultat ;
- l’effectivité : chaque opération est assez simple pour être réalisée exactement, en un temps fini.
Un algorithme ne dépend d’aucun langage de programmation ni d’aucune machine. Le même algorithme peut être écrit en Python, en Java ou en C, exécuté par un ordinateur, ou même déroulé à la main avec un crayon : un même algorithme peut donc aboutir à plusieurs programmes. Il est l’idée ; le programme en est une traduction particulière. On écrit d’ailleurs « algorithme » avec un i : le mot n’a rien à voir avec le rythme.
1.1Un exemple vieux de 2 300 ans
L’un des plus anciens algorithmes connus figure dans les Éléments du mathématicien grec Euclide, vers 300 avant notre ère. Il calcule le plus grand commun diviseur (PGCD) de deux nombres entiers, c’est-à-dire le plus grand nombre qui les divise tous les deux. Son principe : le PGCD de a et b est le même que celui de b et du reste de la division de a par b. On recommence jusqu’à obtenir un reste nul.
fonction PGCD(a, b)
tant que b ≠ 0 faire
r ← a mod b // r reçoit le reste de la division de a par b
a ← b
b ← r
fin tant que
renvoyer a
fin fonction
Pour s’exercer
Exercice 1 : dérouler l’algorithme d’Euclide
Calculez le PGCD de 252 et 105 en notant la valeur de a, b et r à chaque tour de boucle.
Voir la réponse
Tour 1 : 252 mod 105 = 42, donc a = 105, b = 42. Tour 2 : 105 mod 42 = 21, donc a = 42, b = 21. Tour 3 : 42 mod 21 = 0, donc a = 21, b = 0. La boucle s’arrête : le PGCD vaut 21. Vérification : 252 = 21 × 12 et 105 = 21 × 5, et 12 et 5 n’ont aucun diviseur commun.
2D’où vient le mot
Le mot rend hommage au savant persan Muhammad ibn Mūsā al-Khwārizmī, qui travaillait au IXe siècle à la Maison de la sagesse, à Bagdad. Vers 825, il rédige un traité sur le calcul avec les chiffres indiens, ceux que nous appelons « arabes », dont le zéro. Le texte arabe est perdu, mais une traduction latine du XIIe siècle, connue sous le titre Algoritmi de numero Indorum (« Al-Khwārizmī sur les nombres des Indiens »), s’ouvre sur les mots Dixit Algorizmi : « Al-Khwārizmī a dit ». Son nom latinisé donne au Moyen Âge le mot « algorisme », qui désigne le calcul écrit avec ces chiffres. La graphie « algorithme » est sans doute influencée par le grec arithmos, « nombre ». Un autre ouvrage d’al-Khwārizmī, consacré à la résolution des équations, nous a laissé le mot « algèbre », tiré de l’arabe al-jabr.
En 1843, la mathématicienne britannique Ada Lovelace publie un algorithme destiné à la machine analytique de Charles Babbage : c’est le premier algorithme publié conçu pour être exécuté par une machine (voir l’encart À côté). En 1936, Alan Turing donne enfin une définition mathématique de ce qu’est un algorithme, à l’aide d’une machine abstraite qui porte aujourd’hui son nom (voir qu’est-ce que l’informatique ?).
3Les briques d’un algorithme
Tous les algorithmes, des plus simples aux plus complexes, se construisent avec un petit nombre de briques. Les langages de programmation les reprennent sous des noms différents (voir conditions et boucles et les fonctions).
- Une variable est une case de mémoire désignée par un nom, qui contient une valeur susceptible de changer. L’affectation range une valeur dans une variable :
max ← 12. - La séquence exécute les instructions les unes après les autres, dans l’ordre où elles sont écrites.
- La condition choisit entre deux chemins selon qu’un test est vrai ou faux :
si … alors … sinon …. - La boucle répète un bloc d’instructions, soit un nombre de fois connu à l’avance (
pour i de 1 à n), soit tant qu’une condition reste vraie (tant que …). - La fonction regroupe des instructions sous un nom, pour les réutiliser. Elle permet de découper un problème en sous-problèmes plus simples.
On écrit généralement un algorithme en pseudo-code, un français structuré et sans ambiguïté, ou sous forme d’organigramme (on dit aussi ordinogramme, algorigramme ou logigramme), un schéma dont les formes sont normalisées. Voici les deux représentations d’un même algorithme, qui cherche le plus grand nombre d’une liste.
fonction Maximum(liste)
max ← premier élément de liste
pour chaque élément x de liste faire
si x > max alors
max ← x
fin si
fin pour
renvoyer max
fin fonction
Un organigramme est utile pour un rapport ou pour expliquer une idée ; pour soi-même, une feuille de papier et un crayon suffisent. L’algorithme n’a d’ailleurs pas forcément d’existence matérielle : on ne l’écrit pas toujours, et un programme bien écrit et bien commenté se suffit à lui-même pour être compris (voir la section 7).
3.1Les qualités d’un bon algorithme
Un algorithme est aussi un moyen de communiquer une solution à d’autres personnes, et de se comprendre soi-même quelques mois plus tard. Il gagne donc à être :
- lisible, compréhensible par quelqu’un qui n’a pas participé à sa conception, même s’il n’est pas informaticien ;
- de haut niveau, c’est-à-dire indépendant du langage : il doit pouvoir être traduit dans n’importe quel langage de programmation, sans recours aux particularités d’un langage ou d’un système d’exploitation ;
- précis, sans aucune étape sujette à interprétation ;
- concis : si un algorithme dépasse une page, c’est souvent le signe qu’il faut le décomposer en sous-problèmes ;
- structuré, composé de parties facilement identifiables.