Composition d’algorithmes

Le pseudocode encadré et numéroté « Algorithm 1 » que l’on voit dans les articles et manuels n’est pas une fonctionnalité intégrée de LaTeX : il vient de paquets. Le premier obstacle est l’existence de plusieurs paquets aux noms proches. La clé est une division du travail : un paquet fournit le contenant, une boîte flottante numérotée, et un autre fournit le contenu, le pseudocode lui-même. Cette page ordonne ce paysage, puis présente l’association classique, le flottant algorithm enveloppant un corps algpseudocode, et son rival autonome algorithm2e, chacun avec du code réellement compilable. Comme il n’y a pas de rendu en direct ici, le texte décrit ce que chaque exemple produit.

Deux couches : contenant et contenu

La composition du pseudocode se divise en deux couches aux rôles distincts. La première est le contenant : une boîte qui flotte sur la page comme figure ou table, avec une légende « Algorithm 1 », un numéro courant, des renvois et même une liste des algorithmes si souhaité. Elle est fournie par le paquet algorithm (\usepackage{algorithm}), qui ajoute l’environnement \begin{algorithm} … \end{algorithm}.

La seconde couche est le contenu : des commandes comme \State (une ligne), \While (une boucle) et \If (une branche) composent le pseudocode lui-même, avec indentation et numéros de ligne. C’est là que les choix divergent : l’ancien paquet algorithmic, son successeur plus personnalisable algorithmicx (en pratique, on utilise la mise en page algpseudocode construite dessus), et l’écosystème séparé algorithm2e.

Le point crucial : pour le corps, choisissez exactement un paquet. algpseudocode et algorithm2e diffèrent entièrement par leur syntaxe et leur philosophie, et les mélanger provoque des conflits. Le contenant algorithm, en revanche, est destiné à être associé à algpseudocode; algorithm2e apporte son propre contenant et son propre corps, donc n’a pas besoin de algorithm (et les combiner est déconseillé). Le tableau ci-dessous donne la vue d’ensemble.

Notez que algorithm est fourni par le bundle algorithms, qui contient aussi algorithmic. algorithmicx est distribué séparément, mais charger algpseudocode l’appelle automatiquement; vous n’avez donc jamais besoin de faire vous-même \usepackage de algorithmicx.

Les commandes d’algpseudocode

Le pseudocode algpseudocode s’écrit dans l’environnement \begin{algorithmic} … \end{algorithmic}. Notez que le nom de l’environnement diffère du nom du paquet (algpseudocode) : l’environnement s’appelle simplement algorithmic. L’argument optionnel [1] règle les numéros de ligne : 0 pour aucun, 1 pour chaque ligne, n pour une ligne sur n. Toutes les commandes sont en casse titre (\State, \While, …), ce qui les distingue le plus facilement de l’ancien algorithmic tout en majuscules (\STATE, \WHILE).

Le pivot est \State, qui marque le début de chaque ligne de pseudocode : on met un \State par instruction, comme une affectation ou un appel de procédure. On ne met pas \State avant une commande ouvrant un bloc comme \While ou \If, car ces commandes commencent elles-mêmes une nouvelle ligne. Le contenu d’un bloc est indenté automatiquement, et l’indentation dans la source n’influe pas sur la sortie. Les principales commandes :

• \State — début d’une instruction (ligne); s’utilise comme \State $x \\gets 1$.
• \For{cond} … \EndFor — boucle for; la sortie commence par « for … do » et se ferme par « end for ». \ForAll{cond} existe aussi.
• \While{cond} … \EndWhile — boucle while; « while … do » / « end while ».
• \If{cond} … \ElsIf{cond} … \Else … \EndIf — branchement; « if … then », « else if … then », « else », « end if ». \ElsIf et \Else sont optionnels.
• \Function{name}{args} … \EndFunction — fonction; « function name(args) » / « end function ». La forme procédure \Procedure{name}{args} … \EndProcedure a la même forme.
• \Return — valeur de retour, composée comme « return … » avec un mot-clé droit et gras.
• \Comment{...} — commentaire de fin de ligne, placé après un triangle pointant à droite ▷.
• \Require / \Ensure — préconditions et postconditions, chacune précédée d’un libellé gras « Require: » / « Ensure: ».

Ces mots-clés peuvent être remplacés. Si vous préférez les libellés « Input: » et « Output: » à « Require: » et « Ensure: », redéfinissez-les dans le préambule : \renewcommand{\algorithmicrequire}{\textbf{Input:}} et \renewcommand{\algorithmicensure}{\textbf{Output:}}. De même, réécrire \algorithmicwhile, \algorithmicdo et leurs voisins permet de changer librement les mots des boucles et branches.

Exemple complet : algorithm + algpseudocode

En combinant les deux couches, on obtient ceci : l’extérieur est enveloppé dans un flottant algorithm, avec \caption{…} pour la légende et \label{…} pour les renvois, puis le pseudocode est écrit dans l’environnement interne algorithmic. Voici l’algorithme classique pour calculer la puissance y = xⁿ.

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

\begin{algorithm}
  \caption{Calculate $y = x^n$}\label{alg:power}
  \begin{algorithmic}[1]
    \Require $n \geq 0$
    \Ensure $y = x^n$
    \State $y \gets 1$
    \State $X \gets x$
    \State $N \gets n$
    \While{$N \neq 0$}
      \If{$N$ is even}
        \State $X \gets X \times X$
        \State $N \gets N / 2$ \Comment{even case}
      \Else
        \State $y \gets y \times X$
        \State $N \gets N - 1$
      \EndIf
    \EndWhile
    \State \Return $y$
  \end{algorithmic}
\end{algorithm}

アルゴリズム~\ref{alg:power} は累乗を計算する。

\end{document}

À la compilation, une boîte avec des règles en haut et en bas flotte sur la page, avec en tête « Algorithm 1 Calculate y = xⁿ » (numéro automatique). À l’intérieur, chaque ligne est numérotée 1, 2, 3 … sur la gauche, et les deux premières lignes donnent la précondition et le résultat après « Require: » et « Ensure: » en gras. La ligne \While est composée avec while en gras et un do final, puis son corps est indenté d’un niveau. La note \Comment se place en fin de ligne après un triangle pointant à droite, et la dernière ligne affiche return suivi de y. Dans le texte, \ref{alg:power} se résout au numéro de la boîte (ici 1), donc « Algorithm 1 is… ».

Les mathématiques dans le pseudocode ($N \\neq 0$, $y \\gets 1$) sont entourées de $…$ comme en mode mathématique ordinaire. \gets est une flèche vers la gauche (←), notation conventionnelle de l’affectation. Comme toujours, compilez deux fois un document utilisant algorithm pour stabiliser numéros et renvois.

Le rival : algorithm2e

L’autre grande option est algorithm2e. C’est un écosystème séparé, autonome dans un seul paquet, contenant à la fois le flottant et le corps, chargé par \usepackage[...]{algorithm2e} avant \begin{document}. Son environnement algorithm est lui-même le flottant, donc il n’y a pas d’environnement interne à imbriquer. Sa syntaxe diffère aussi fortement de celle d’algpseudocode.

Deux différences ressortent. D’abord, entrée et sortie utilisent des commandes dédiées \KwIn{…} et \KwOut{…} (ou \KwData{…} et \KwResult{…}), composées comme « Input: », « Output: », « Data: » ou « Result: » en gras. Ensuite, branches et boucles prennent leur corps comme argument entre accolades. Un if–then–else s’écrit \eIf{cond}{then part}{else part}, le contenu du bloc passant dans { } (e signifie « avec else »). \For{cond}{body} et \While{cond}{body} fonctionnent de même.

Autre règle à surveiller : chaque instruction doit se terminer par \\; (barre oblique inverse et point-virgule). Si vous l’oubliez, l’instruction suivante continue sur la même ligne. Voici un court exemple.

\documentclass{article}
\usepackage[ruled,linesnumbered]{algorithm2e}
\begin{document}

\begin{algorithm}[H]
  \caption{Sum of positive entries}
  \KwIn{an array $a[1..n]$}
  \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]$\;
    }{
      skip\;
    }
  }
  \Return $s$\;
\end{algorithm}

\end{document}

Ici, l’option ruled trace des règles en haut et en bas avec une ligne de légende en haut, et linesnumbered numérote chaque ligne. [H] est un spécificateur de placement comme pour les figures : il fixe l’algorithme sur place au lieu de le laisser flotter (h, t, b, p sont aussi disponibles). Notez qu’algorithm2e implémente [H] lui-même; vous n’avez donc pas besoin de charger le paquet float séparément (contrairement à l’ancien paquet algorithm, où [H] exige \usepackage{float}). La boîte commence par « Input: » et « Output: » en gras; la ligne \For se lit for i ← 1 to n do avec le corps indenté; \eIf place le bloc vrai if … then au-dessus du bloc faux else. Chaque \; provoque un saut de ligne, et la dernière ligne affiche return s.

Quelques commandes ajustent l’apparence. \SetAlgoLined (anciennement \SetLine) trace des lignes verticales marquant la structure des blocs, et \DontPrintSemicolon empêche le \\; de fin de ligne d’apparaître dans la sortie. \KwTo compose « to » et \Return compose « return » comme mots-clés intégrés; ils peuvent aussi être redéfinis, en japonais par exemple. Les commentaires s’insèrent avec \tcc{…} (forme /* … */) ou \tcp{…} (forme //).

Lequel utiliser ?

Les deux sont largement utilisés; c’est une question d’idiome plus que de supériorité. algorithm + algpseudocode offre un jeu de commandes direct fondé sur \State, adapté à ceux qui aiment l’apparence traditionnelle du pseudocode, avec mots-clés en début de ligne et encadrement par do, then, end …, ou aux modèles de conférence qui l’imposent. algorithm2e plaît à ceux qui veulent des déclarations entrée/sortie explicites, le style à blocs passés entre accolades, des lignes verticales, et beaucoup de mots-clés multilingues ou de personnalisation fine.

À répéter : la règle pratique est de s’en tenir à un seul paquet de corps. Charger algpseudocode et algorithm2e ensemble provoque des conflits sur des commandes partagées comme \For et \If. Uniformisez le document entier. Si vous utilisez algorithm2e, vous n’avez pas besoin du contenant algorithm : algorithm2e définit son propre environnement algorithm, donc charger les deux crée un conflit de nom d’environnement.