Composition d’algorithmes

Les paquets LaTeX qui composent du pseudocode portent des noms d’une similarité déroutante — algorithm, algorithmic, algorithmicx (en pratique on emploie algpseudocode) et algorithm2e — et le premier obstacle consiste à savoir lesquels se querellent. Or la combinaison vraiment dangereuse n’est pas celle qui lève une erreur. En essayant tous les appariements sous TeX Live 2024, il apparaît que charger algorithm2e avec algpseudocode ne produit aucune erreur au chargement et corrompt silencieusement la sortie dès qu’on écrit \For. Cette page pose l’architecture en deux couches (contenant et contenu), donne un tableau des conflits avec les messages d’erreur réellement reproduits, traite l’écriture de \State et \Procedure, montre comment redéclarer soi-même les mots-clés, et se termine par une recommandation pour qui débute aujourd’hui.

Deux couches : le paquet qui fait le cadre et celui qui écrit le corps

La composition du pseudocode se scinde en deux couches aux rôles distincts. La première est le contenant : une boîte qui flotte sur la page comme une figure ou une table, porte une légende numérotée « Algorithm 1 », se référence, et peut même être rassemblée dans une liste. Elle vient de algorithm, qui construit en interne un nouveau flottant en appelant \newfloat du paquet float (algorithm.sty ligne 31 : \RequirePackage{float} ; lignes 82 à 94 : \newfloat{algorithm}{htbp}{loa}). Son aspect par défaut est \floatstyle{ruled} — les filets bien connus au-dessus et au-dessous.

La seconde couche est le contenu — des commandes comme \State (une ligne), \While (une boucle) et \If (une branche) qui composent le pseudocode lui-même, avec indentation et numéros de ligne. Ici le choix se divise en trois : l’ancien algorithmic, son successeur plus souple algorithmicx (en pratique on charge la mise en page bâtie dessus, algpseudocode), et le monde séparé et autonome d’algorithm2e. Ce ne sont pas seulement les noms qui égarent : même après avoir chargé algpseudocode, l’environnement s’appelle algorithmic. Le nom du paquet et celui de l’environnement diffèrent.

Quelles combinaisons cassent : tous les appariements essayés sous TeX Live 2024

En bref : une seule paire est sûre, algorithm + algpseudocode. Les autres cassent de trois manières différentes. Voici les messages tels qu’ils sont sortis d’une exécution réelle.

% SAFE — the intended pairing, compiles cleanly
\usepackage{algorithm}\usepackage{algpseudocode}

% two body packages: the environment name collides
\usepackage{algorithmic}\usepackage{algpseudocode}
! LaTeX Error: Command \algorithmic already defined.

% algorithm2e already owns a container — order changes only which name trips first
\usepackage{algorithm2e}\usepackage{algorithm}
! LaTeX Error: Command \listofalgorithms already defined.

\usepackage{algorithm}\usepackage{algorithm2e}
! LaTeX Error: Command \algorithm already defined.
! LaTeX Error: Command \algorithm* already defined.

Ce sont là des échecs faciles à lire : LaTeX s’arrête dès que les noms se heurtent, et la première ligne du journal désigne la cause. Le problème vient de la quatrième combinaison — algorithm2e avec algpseudocode. Essayée dans les deux ordres, elle donne zéro erreur au chargement. Pire, si l’on se contente d’utiliser chaque environnement séparément, les deux semblent fonctionner. Tout s’effondre à l’instant où l’on écrit \For dans un environnement algorithmic, car les deux paquets définissent les mêmes noms, \For et \If, d’une manière qui ne lève aucune erreur.

\usepackage{algorithm2e}
\usepackage{algpseudocode}   % loads fine. no error. no warning.
...
\begin{algorithmic}[1]
  \State $x \gets 0$
  \For{$i=1$ to $n$} \State $x \gets x+i$ \EndFor
\end{algorithmic}

% output is scrambled — lines merge and reorder — and only then:
! Missing number, treated as zero.
<to be read again> \ALG@b@2@EndFor@0
l.9 \EndFor

L’erreur remonte à la ligne du \EndFor, formulée en « missing number » — difficile d’être plus éloigné de la cause réelle. Rien ne désigne les deux lignes \usepackage du préambule. C’est ce qui en fait la pire des quatre combinaisons. Notons aussi qu’il s’agit d’un échec distinct du conflit d’options que provoquent deux appels \usepackage en désaccord sur les options. Un conflit d’options se déclenche sur un test d’inclusion — le second chargement demande une option absente du premier — et s’annonce par le message dédié Option clash for package. Ici, il ne s’agit que d’un nom de commande en double : deux paquets ont défini le même \For.

Écrire un corps algpseudocode : de \State à \Procedure

Le pseudocode s’écrit entre \begin{algorithmic} et \end{algorithmic}, et son argument optionnel règle la numérotation des lignes : [0] aucune, [1] toutes, [n] une sur n. La pièce maîtresse est \State, posée une fois par instruction — affectation, appel de procédure. On ne met pas de \State devant une commande ouvrant un bloc comme \While ou \If : elles entament une ligne d’elles-mêmes. Le contenu des blocs est indenté automatiquement et les espaces de la source n’ont aucun effet sur la sortie. La casse de titre des commandes (\State) est l’indice le plus rapide pour distinguer ceci de l’ancien algorithmic tout en majuscules (\STATE, \WHILE).

• \State — le début d’une instruction (une ligne) ; s’emploie comme \State $x \gets 1$.
• \For{cond} … \EndFor — une boucle ; la sortie s’ouvre sur « for … do » et se ferme par « end for ». \ForAll{cond} existe aussi.
• \While{cond} … \EndWhile — « while … do » / « end while ». \Repeat … \Until{cond} est également disponible.
• \If{cond} … \ElsIf{cond} … \Else … \EndIf — une branche ; « if … then », « else if … then », « else », « end if ». \ElsIf et \Else sont facultatifs.
• \Procedure{name}{args} … \EndProcedure — une procédure ; « procedure name(args) » / « end procedure ». La forme fonction \Function{name}{args} … \EndFunction a la même structure.
• \Return — une valeur de retour, composée en « return » gras suivi de la valeur.
• \Comment{...} — un commentaire de fin de ligne, placé après un triangle pointant à droite ▷.
• \Require / \Ensure — pré- et post-conditions, précédées chacune d’un « Require: » / « Ensure: » en gras.

\documentclass{article}
\usepackage{algorithm}
\usepackage{algpseudocode}

% declare your own keywords: Require/Ensure become Input/Output
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

\begin{document}
\listofalgorithms

\begin{algorithm}
  \caption{Power}\label{alg:p}
  \begin{algorithmic}[1]
    \Require $n \ge 0$
    \Ensure  $y = x^n$
    \Procedure{Power}{$x, n$}
      \State $y \gets 1$
      \While{$n \neq 0$}
        \State $y \gets y \times x$ \Comment{one step}
        \State $n \gets n - 1$
      \EndWhile
      \State \Return $y$
    \EndProcedure
  \end{algorithmic}
\end{algorithm}

See Algorithm~\ref{alg:p}.
\end{document}

Compilez-le deux fois et vous obtenez une boîte flottante filetée en haut et en bas, coiffée de « Algorithm 1 Power ». Les numéros de ligne 1 à 8 descendent le long du bord gauche, et les lignes \Require/\Ensure sortent en « Input: » et « Output: » exactement comme redéfini — les mots-clés ne sont pas un ornement mais des déclarations remplaçables. Réécrivez de même \algorithmicwhile, \algorithmicdo, \algorithmicend et les autres, et les mots des boucles et des branches changent avec eux. Le \listofalgorithms du début produit une « List of Algorithms » (algorithm.sty tient un fichier de table avec l’extension loa), et \ref{alg:p} dans le texte se résout en « See Algorithm 1. ». Compilez toujours deux fois pour que numéros et renvois se stabilisent.

Un point sur le contenant est largement mal compris ; corrigeons-le ici. Quand on écrit \begin{algorithm}[H] pour fixer la boîte sur place, il n’est pas nécessaire de charger soi-même le paquet float. La ligne 31 de algorithm.sty est \RequirePackage{float} : float est donc déjà là dès que l’on charge algorithm. Sous TeX Live 2024, un document ne comportant que \usepackage{algorithm} et un [H] a bien gardé la boîte fixée entre les paragraphes voisins. Au passage : algorithm accepte les options plain, ruled et boxed pour choisir le style du cadre (par défaut ruled).

algorithm2e : des blocs passés entre accolades et le \\; à ne pas oublier

L’autre grande option est algorithm2e. Autonome, elle fournit contenant et contenu dans un seul paquet et se charge dans le préambule par \usepackage[…]{algorithm2e}. Son environnement algorithm est le flottant : aucun environnement interne à imbriquer. La syntaxe s’écarte aussi nettement de algpseudocode sur trois points. D’abord, entrée et sortie passent par les commandes dédiées \KwIn{…} et \KwOut{…} (ou \KwData{…} et \KwResult{…}). Ensuite, branches et boucles reçoivent leur corps en argument entre accolades : \eIf{cond}{partie then}{partie else} (le e signifie « avec else »), \For{cond}{body}, \While{cond}{body}. Enfin, chaque instruction doit finir par \\; — l’oublier fait glisser l’instruction suivante sur la même ligne.

\documentclass{article}
\usepackage[ruled, vlined, linesnumbered]{algorithm2e}
\SetKwInOut{Param}{Parameters}   % declare a keyword of your own
\DontPrintSemicolon              % hide the line-ending \;

\begin{document}
\begin{algorithm}[H]
  \caption{Sum of positive entries}\label{alg:s}
  \KwIn{an array $a[1..n]$}
  \Param{tolerance $\epsilon$}
  \KwOut{the sum $s$ of its positive entries}
  $s \gets 0$\;
  \For{$i \gets 1$ \KwTo $n$}{
    \eIf{$a[i] > 0$}{
      $s \gets s + a[i]$\tcp{keep it}
    }{
      \tcc{skip}
    }
  }
  \Return $s$\;
\end{algorithm}
See Algorithm~\ref{alg:s}.
\end{document}

ruled trace des filets en haut et en bas avec une ligne de légende, vlined ajoute les traits verticaux qui marquent la structure des blocs (la commande équivalente depuis le corps est \SetAlgoLined, anciennement \SetLine), et linesnumbered numérote chaque ligne. \DontPrintSemicolon masque dans la sortie le \\; de fin de ligne, utile quand on ne veut pas que le pseudocode ressemble à un langage de programmation. Les commentaires prennent deux formes : \tcp{…} (style //, en fin de ligne) et \tcc{…} (style /* … */, sur une ligne à part). Et \SetKwInOut{Param}{Parameters} est précisément le sujet de cette page : \KwIn et \KwOut n’ont rien d’exceptionnel — ils sont fabriqués par le même mécanisme de déclaration, et l’on peut en ajouter un soi-même. \SetKw, \SetKwFunction et \SetKwData font de même pour d’autres sortes de mots-clés, et les mots derrière \KwTo et \Return se remplacent aussi. [H] est implémenté par algorithm2e lui-même : là encore, inutile de charger float explicitement.

Lequel choisir si vous commencez aujourd’hui

La recommandation est algorithm + algpseudocode, non par goût mais pour trois raisons pratiques. D’abord, c’est la seule paire qui compile sans conflit sous TeX Live 2024. Ensuite, le contenant étant un flottant ordinaire bâti sur float, \caption, \label, \ref et \listofalgorithms se comportent exactement comme pour les figures et les tableaux : rien de nouveau à apprendre. Enfin, le style « une instruction par \State » est celui que présupposent la plupart des modèles de revues et de conférences.

Les raisons de choisir algorithm2e sont tout aussi nettes : vous voulez déclarer explicitement entrées et sorties, vous aimez passer les blocs entre accolades et la mise en page à traits verticaux, ou vous comptez inventer beaucoup de mots-clés. Si l’un de ces points s’applique, c’est le choix le plus naturel. Quel que soit votre choix, une règle demeure : s’en tenir à un seul paquet de corps pour tout le document, et si vous employez algorithm2e, ne pas charger algorithm. Pour essayer les deux, comparez-les dans des fichiers séparés plutôt que de les mêler : deux lignes du préambule vous reviendraient sous forme d’erreur incompréhensible sur la ligne du \EndFor.