Aller au contenu
Encyclopédie informatique Édition 2026

L'algorithmique

Partie 3 sur 3

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

6Raisonner sur un algorithme

6.1La récursivitéApprofondir

Une fonction est récursive lorsqu’elle s’appelle elle-même, sur un problème plus petit. L’algorithme d’Euclide s’écrit ainsi très naturellement : le PGCD de a et b vaut a si b est nul, et sinon celui de b et de a mod b.

fonction PGCD(a, b)
    si b = 0 alors renvoyer a             // cas de base : la réponse est immédiate
    sinon renvoyer PGCD(b, a mod b)       // appel récursif sur un problème plus petit
fin fonction

Toute fonction récursive a besoin d’un cas de base, résolu sans nouvel appel, et chaque appel doit s’en rapprocher. Sans cela, la fonction s’appelle à l’infini. Chaque appel en attente occupe une place dans une zone de mémoire appelée la pile d’appels ; quand elle est pleine, le programme s’arrête sur une erreur de débordement de pile (stack overflow). Python limite par défaut la profondeur à 1 000 appels. La récursivité est l’outil naturel des méthodes « diviser pour régner », comme le tri fusion ou le tri rapide, et du parcours des structures arborescentes, comme les dossiers d’un disque.

6.2Prouver qu’un algorithme est justeApprofondir

Tester un algorithme sur des exemples montre qu’il marche sur ces exemples, pas qu’il marche toujours. Pour le prouver, on établit deux propriétés.

  • La terminaison : l’algorithme s’arrête. On la démontre souvent avec une quantité entière positive qui diminue strictement à chaque tour. Dans l’algorithme d’Euclide, b diminue toujours, puisque le reste d’une division par b est plus petit que b ; un entier positif ne peut pas diminuer indéfiniment.
  • La correction : le résultat est le bon. On utilise un invariant de boucle, une propriété vraie avant la boucle et préservée par chaque tour. Pour Euclide, l’invariant est « le PGCD de a et b ne change pas ». Quand la boucle s’arrête, b vaut 0, et le PGCD de a et 0 est a : le résultat est juste.

Pour la recherche dichotomique, l’invariant est : « si la valeur cherchée est dans la liste, elle se trouve entre les positions début et fin ». En 1844, le mathématicien français Gabriel Lamé a même démontré que l’algorithme d’Euclide demande au plus cinq fois plus d’étapes que le nombre de chiffres du plus petit nombre : un des premiers résultats de complexité de l’histoire. Ces raisonnements, longtemps réservés aux mathématiciens, sont aujourd’hui outillés : des logiciels de preuve formelle vérifient mécaniquement les programmes les plus critiques, ceux des métros automatiques ou de l’aéronautique.

Pour s’exercer

Exercice 4 : une récursivité qui ne s’arrête pas

On écrit : Factorielle(n) = n × Factorielle(n − 1), avec Factorielle(0) = 1. Que se passe-t-il si l’on appelle Factorielle(−1) ? Comment corriger ?

Voir la réponse

L’appel produit Factorielle(−2), puis Factorielle(−3), et ainsi de suite : le cas de base, 0, n’est jamais atteint. Le programme s’arrête sur un débordement de pile. Il faut vérifier l’entrée et refuser les nombres négatifs, par exemple en levant une exception. La terminaison n’est garantie que si chaque appel se rapproche réellement du cas de base.

Exercice 5 : prouver l’algorithme du maximum

Quel invariant de boucle permet de prouver que l’algorithme de la Figure 2 renvoie bien le plus grand élément ?

Voir la réponse

« max est le plus grand des éléments déjà examinés. » Il est vrai au départ, puisque max vaut le premier élément. Chaque tour le préserve : si le nouvel élément x est plus grand, max prend sa valeur ; sinon, max reste le plus grand. À la fin de la boucle, tous les éléments ont été examinés : max est donc le plus grand de la liste. La boucle se termine, car la liste est finie.

7De l’algorithme au programme

La réalisation d’un logiciel suit plusieurs étapes, qui s’enchaînent et se répètent.

  1. L’analyse : comprendre le problème, en cerner les limites, préciser les données d’entrée et le résultat attendu. Le résultat de l’analyse s’écrit dans un langage de description : c’est l’algorithme.
  2. La conception de l’algorithme : choisir une méthode, l’écrire en pseudo-code, vérifier sur des exemples qu’elle est juste, y compris dans les cas limites (liste vide, valeur absente, très grands nombres).
  3. La programmation : traduire l’algorithme dans un langage de programmation. Ce langage sert d’intermédiaire entre l’humain et la machine : assez proche de la machine pour être traduit sans ambiguïté, mais lisible par un humain. Il impose donc une syntaxe stricte.
  4. La compilation ou l’interprétation : un autre programme, le compilateur, transforme le code en langage machine, les instructions que le processeur sait exécuter ; un interpréteur les exécute au fur et à mesure (voir compilation et interprétation).
  5. L’édition de liens : un programme utilise presque toujours des éléments qu’il n’a pas écrits lui-même, rangés dans des bibliothèques (en anglais libraries, d’où le faux ami « librairies ») : affichage, calcul, accès au réseau. L’éditeur de liens relie le code compilé à ces éléments externes pour produire un programme exécutable. Les liens peuvent être faits une fois pour toutes (liaison statique) ou au lancement du programme (liaison dynamique, avec les fichiers .dll de Windows ou .so de Linux).
  6. Les tests et la maintenance : vérifier le comportement réel, corriger, faire évoluer.

Voici l’algorithme de recherche dichotomique traduit en Python. La structure est la même ; seuls les mots changent.

def recherche_dichotomique(liste, valeur):
    debut, fin = 0, len(liste) - 1       # en Python, on numérote à partir de 0
    while debut <= fin:
        milieu = (debut + fin) // 2
        if liste[milieu] == valeur:
            return milieu
        elif liste[milieu] < valeur:
            debut = milieu + 1
        else:
            fin = milieu - 1
    return None

On remarque que le calcul du milieu diffère du pseudo-code. En Python, les nombres entiers n’ont pas de limite de taille, et (debut + fin) // 2 ne pose aucun problème. Dans un langage où les entiers ont une taille fixe, cette addition peut déborder sur de très grandes listes : c’est l’objet d’une anecdote célèbre, racontée dans l’encart À côté.

8Écrire pour être lu : les règles de style

Un programme est lu bien plus souvent qu’il n’est écrit. On parle de maintenabilité pour désigner la facilité avec laquelle on peut le comprendre et le modifier après coup, et elle se joue dès l’écriture. Dès qu’un programme s’étoffe, il devient impossible de garder en tête tous ses détails : le programmeur qui se replonge dans son propre code après plusieurs mois a tout à réapprendre, comme s’il le découvrait. D’où l’importance de la forme : commenter, indenter, et surtout bien structurer, sans chercher à être trop astucieux.

Des programmeurs expérimentés ont résumé ces principes en maximes, qui valent dans tous les langages :

  • être clair pour être rigoureux : soyez clair plutôt qu’astucieux, rigoureux avant d’optimiser, et restez simple pour optimiser ;
  • écrire pour être lu : soignez la forme pour aider le lecteur, écrivez pour être lu de haut en bas, commentez le code sans le trahir, évitez l’excès de commentaires, donnez à chaque variable un nom parlant et une valeur initiale ;
  • être méthodique : écrivez d’abord une version simple, décomposez-la en blocs, cantonnez chaque bloc à une seule tâche bien faite, rendez visibles les liens entre les blocs et indentez pour montrer la structure logique.

Pour la présentation elle-même, des normes de fait se sont imposées par l’expérience. Chacun garde ses préférences, et le style de présentation d’un débutant évolue avec la pratique ; mais dans une équipe, tout le monde doit suivre la même convention.

  • Une seule instruction par ligne, et un retour à la ligne après une condition, sauf si l’instruction reste très courte.
  • L’indentation : décaler vers la droite le contenu de chaque bloc, de quatre espaces le plus souvent. En Python, elle fait partie de la syntaxe ; dans les autres langages, elle n’est que visuelle, mais tout aussi indispensable.
  • Les noms : ni trop courts ni trop longs. Pour le numéro de la couleur maximale d’un tableau, NumeroDeLaCouleurMaximum est trop long, n trop vague ; NumCouleurMax est un bon compromis. Les majuscules aident à lire les noms composés : FindItem, MustExist (notation dite « en chameau », à cause des bosses) ; d’autres langages préfèrent les tirets bas, comme recherche_dichotomique en Python.
  • Les commentaires, à bon escient : ils expliquent pourquoi le code fait quelque chose, pas ce qu’il fait, que le code dit déjà. Un en-tête explicatif en début de fichier rappelle le projet, l’auteur et la version.
  • La coloration syntaxique de l’éditeur, ou de l’environnement de développement, met en valeur les mots-clés, les commentaires et les chaînes de caractères ; ses couleurs se règlent selon ses goûts.
{ À éviter : deux instructions sur une ligne, structure invisible }
if not Updated then Update; I := IndexOf(Name);

{ Préférable : une instruction par ligne, blocs indentés }
function FindItem(const Name: string; MustExist: Boolean): TItem;
var
  I: Integer;
begin
  if not Updated then
    Update;
  I := IndexOf(Name);
  if I >= 0 then
    Result := Items[I]
  else
  begin
    if MustExist then
      raise EItemNotFound.Create(Name);   { lever une exception }
    Result := nil;
  end;
end; { FindItem }
Figure 5. Une même fonction, en langage Pascal, mal puis bien présentée. Elle cherche un objet par son nom dans une liste et, s’il est absent, renvoie nil (« rien ») ou lève une exception selon le paramètre MustExist. Les mots begin et end délimitent les blocs ; rappeler le nom de la fonction après le dernier end aide à se repérer dans un long fichier.

Pour s’exercer

Exercice 6 : doubler les données

Un traitement prend 1 seconde pour 100 000 données. Combien de temps prendra-t-il pour 200 000 données s’il est en O(log n), O(n), O(n log n) ou O(n2) ?

Voir la réponse

En O(log n), à peine plus : une seule étape de plus. En O(n), 2 secondes. En O(n log n), un peu plus de 2 secondes (environ 2,1). En O(n2), 4 secondes. Pour un million de données, l’écart devient énorme : 10 secondes en O(n), 100 en O(n2).

Exercice 7 : remettre en forme

Réécrivez lisiblement la ligne Pascal if not Updated then Update; I := IndexOf(Name); et expliquez le piège qu’elle cache.

Voir la réponse

Écrite sur une ligne, elle laisse croire que les deux instructions dépendent de la condition. En réalité, seule Update en dépend ; I := IndexOf(Name) s’exécute toujours. Une instruction par ligne, avec indentation, rend la structure évidente (voir la Figure 5). De nombreuses failles de sécurité sont nées de ce type de confusion entre ce que l’on croit lire et ce que la machine exécute.

Sécurité de l’information

Le coin cyber

Les algorithmes sont au cœur de la sécurité informatique : ils chiffrent les données, vérifient les mots de passe, signent les documents. Ils peuvent aussi être retournés contre ceux qui les utilisent, quand leur conception ou leur mise en œuvre laisse une prise.

C.1Ce qu’aucun algorithme ne peut faire

« Un bon antivirus détecte tous les virus. » C’est mathématiquement impossible. Dès 1984, le chercheur Fred Cohen a démontré, en s’appuyant sur les travaux de Turing, qu’aucun programme ne peut décider à coup sûr si un programme quelconque est malveillant ; son article est paru en 1987. Les antivirus combinent donc signatures, analyse du comportement et heuristiques, qui laissent passer des menaces ou déclenchent de fausses alertes. C’est l’une des raisons d’être de la défense en profondeur, qui superpose plusieurs protections indépendantes.

C.2Ce que dit le droit

Les algorithmes servent aussi à prendre des décisions sur des personnes. En France, depuis la loi pour une République numérique du 7 octobre 2016, une décision administrative individuelle prise sur le fondement d’un traitement algorithmique doit le mentionner explicitement, et l’administration doit en communiquer les règles et les principales caractéristiques à la personne qui le demande (article L311-3-1 du code des relations entre le public et l’administration). Dans toute l’Union européenne, l’article 22 du RGPD (règlement général sur la protection des données) donne à chacun le droit, sauf exceptions, de ne pas faire l’objet d’une décision fondée exclusivement sur un traitement automatisé qui l’affecte de manière significative.

C.3Bonnes pratiques

Particulier

  • Se méfier des produits qui vantent un chiffrement « secret », « exclusif » ou « inviolable » : un bon produit s’appuie sur des standards publics.
  • Préférer les outils reconnus, régulièrement mis à jour, dont la sécurité a été évaluée par des tiers.

Organisation

  • Ne jamais concevoir son propre algorithme de chiffrement : utiliser des bibliothèques éprouvées, avec les paramètres recommandés.
  • Limiter la taille des entrées et la durée des traitements ; tester les pires cas, notamment avec des données aléatoires en masse.
  • Comparer les secrets en temps constant.
  • Imposer des règles de style et des relectures de code : un code lisible cache moins bien ses erreurs.
  • Dresser l’inventaire des algorithmes cryptographiques utilisés et préparer la migration post-quantique.

Référentiels : ANSSI, Guide de sélection d’algorithmes cryptographiques · ANSSI, avis sur la migration vers la cryptographie post-quantique · NIST FIPS 197 (AES), FIPS 203, 204 et 205 · MITRE, CWE-327 (algorithme cryptographique cassé ou risqué), CWE-407 (complexité algorithmique inefficace), CWE-1333 (expression régulière inefficace), CWE-208 (écart de temps observable) et CWE-674 (récursivité non contrôlée).

Références

  1. Knuth D. E., The Art of Computer Programming, vol. 1, Fundamental Algorithms, Addison-Wesley, 1968 ; vol. 3, Sorting and Searching, 1973.
  2. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., Algorithmique, 3e édition, Dunod, 2010 (traduction d’Introduction to Algorithms).
  3. Kernighan B. W., Plauger P. J., The Elements of Programming Style, McGraw-Hill, 1974 (source de nombreuses maximes de style).
  4. Menabrea L. F., « Sketch of the Analytical Engine Invented by Charles Babbage », traduction et notes d’A. A. Lovelace, Scientific Memoirs, vol. 3, 1843.
  5. Turing A. M., « On Computable Numbers, with an Application to the Entscheidungsproblem », Proceedings of the London Mathematical Society, 1936.
  6. Hoare C. A. R., « Quicksort », The Computer Journal, vol. 5, 1962.
  7. Lamé G., « Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers », Comptes rendus de l’Académie des sciences, 1844.
  8. Dijkstra E. W., « A note on two problems in connexion with graphs », Numerische Mathematik, vol. 1, 1959.
  9. Kerckhoffs A., « La cryptographie militaire », Journal des sciences militaires, vol. IX, janvier et février 1883.
  10. Cohen F., « Computer Viruses: Theory and Experiments », Computers & Security, vol. 6, 1987.
  11. oCERT, avis oCERT-2011-003, déni de service par collisions dans les tables de hachage, 28 décembre 2011.
  12. Bloch J., « Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken », Google Research, 2006.
  13. NIST, FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) et FIPS 205 (SLH-DSA), 13 août 2024.
  14. Loi n° 2016-1321 du 7 octobre 2016 pour une République numérique ; code des relations entre le public et l’administration, article L311-3-1 ; règlement (UE) 2016/679 (RGPD), article 22.

Voir aussi

Citer cet article

« L'algorithmique », Encyclopédie informatique, révision du 22 octobre 2026.