Aller au contenu
Encyclopédie informatique Édition 2026

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
Niveau de lecture :

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 ?

Vidéo de cette partieenviron une minute et demie, avec voix et texte à l’écran

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
Figure 1. L’algorithme d’Euclide en pseudo-code. La flèche ← signifie « reçoit la valeur ». Avec a = 1 071 et b = 462, les restes successifs valent 147, 21 puis 0 : le PGCD est 21.

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
Début Lire la liste max ← premier élément Reste-t-il un élément x à examiner ? oui x > max ? oui max ← x non non Afficher max Fin LES FORMES NORMALISÉES début ou fin entrée ou sortie de données instruction test (deux sorties : oui, non)
Figure 2. L’algorithme du maximum, en pseudo-code puis en organigramme. La boucle apparaît dans l’organigramme comme un chemin qui revient en arrière : tant qu’il reste des éléments, on compare, on met éventuellement à jour, puis on recommence.

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.
Sécurité de l’information

Le coin cyber

C.1Le principe de Kerckhoffs : publier la méthode, garder la clé

En 1883, le linguiste et cryptologue Auguste Kerckhoffs énonce dans La Cryptographie militaire six règles pour les systèmes de chiffrement. La deuxième est restée la plus célèbre :

« Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi. »

Autrement dit, la sécurité doit reposer uniquement sur le secret de la clé, et non sur celui de l’algorithme. Un algorithme public peut être examiné par des milliers de chercheurs ; un algorithme secret finit toujours par être reconstitué, et ses défauts apparaissent alors au grand jour. Le système de protection des DVD, gardé secret, a ainsi été cassé en 1999. À l’inverse, l’AES (Advanced Encryption Standard), l’algorithme de chiffrement le plus utilisé au monde, a été choisi en 2000 au terme d’un concours public de plusieurs années (voir la cryptographie). On résume parfois l’erreur inverse d’une formule : la « sécurité par l’obscurité ».

C.2Un test oublié suffit à ouvrir une faille

Un algorithme correct sur le papier peut échouer sur un cas que l’on n’a pas prévu. En 2014, la faille Heartbleed venait d’un contrôle manquant : un programme de chiffrement renvoyait des données de sa mémoire sans vérifier la taille demandée. Le bon réflexe : traiter toute donnée reçue comme non fiable, vérifier sa taille et son format, et tester les cas limites.

C.3Un résultat « au hasard » doit l’être vraiment

Pour fabriquer une clé ou un jeton de connexion, un algorithme a besoin d’un hasard imprévisible. Un générateur ordinaire, conçu pour les jeux ou les simulations, suit une suite que l’on peut parfois deviner après quelques valeurs. Le bon réflexe : utiliser le générateur sécurisé fourni par le système ou par une bibliothèque reconnue, et ne jamais écrire le sien.