Comment écrire des algorithmes en pseudocode?

En programmation, le pseudocode est une façon de décrire un algorithme d'une façon proche du langage naturel, sans référence à un langage de programmation en particulier.

Le pseudocode diffère des listings de programmes réels en ce qu'il n'a pas de syntaxe et de sémantique strictes. De plus, comme le pseudocode est censé exprimer un algorithme de manière claire, il peut avoir besoin d'incorporer des notations mathématiques, des figures, des tableaux et d'autres éléments LaTeX qui n'apparaissent normalement pas dans les langages de programmation conventionnels. La mise en forme des programmes est décrite ailleurs.

Il n'y a pas une unique façon de mettre en forme du pseudocode, mais de nombreuses. Il existe par conséquent de nombreuses extensions LaTeX pour mettre en forme des algorithmes de façon lisible et jolie.

On pourrait certainement créer son propre environnement de composition de pseudocode en utilisant, par exemple, les environnements tabbing (décrits ici) ou list (décrits ici) — ce ne serait pas très difficile pour commencer, mais on arriverait vite à un niveau de complexité rédhibitoire. Cela vaut donc la peine d'essayer les extensions suivantes, toutes conçues spécifiquement pour la mise en forme de pseudocodes.

Le package algorithms (qui contient les extensions algorithm et algorithmic, toutes deux nécessaires pour une utilisation normale) a une interface simple et produit des résultats plutôt jolis. Il fournit des primitives pour les déclarations, qui peuvent contenir des commandes LaTeX arbitraires, des commentaires, et diverses structures itératives et conditionnelles. Ces primitives peuvent facilement être redéfinies pour produire une sortie différente. Cependant, il n'y a pas de support pour ajouter de nouvelles primitives. La mise en forme du pseudocode lui-même est effectuée par l'extension algorithmic ; l'extension algorithms utilise, elle, les fonctionnalités de l'extension float pour numéroter les algorithmes de manière séquentielle, permettre aux algorithmes de flotter comme des figures ou des tableaux, et produire « Liste des algorithmes » en début de document.

Les extensions fournies par le package algorithmicx sont similaires à algorithmic, tant par leurs principes de base que par leur résultat final, mais elles permettent d'ajouter de nouveaux mots-clefs et de modifier la mise en forme. Il y a notamment l'extension algpseudocode qui est (presque) un remplacement direct d'algorithmic. Une autre extension du package, algpascal, utilise des mots-clefs de type Pascal, indente le code différemment de algpseudocode et formatte les arguments des commandes en mode mathématique plutôt qu'en mode texte. Il n'y a pas d'environnement flottant mais algorithmicx, comme algorithmic, est compatible avec algorithm

L'extension frpseudocode, d'Oliver Irwin, s'appuie sur algorithmicx (équivalent récent des extensions présentées ci-dessus) en la françisant. Son but est avant tout de fournir une traduction en français de termes utilisés dans les algorithmes, pour permettre leur intégration dans un document en français. Il suffit de charger frpseudocode, puis d'utiliser les commandes habituelles de algorithmicx, puisque leur nom est conservé.

L'extension algpseudocodex, de Christian Matt, est elle aussi basée sur algorithmicx, dont elle reprend la syntaxe, mais elle lui ajoute de nombreuses fonctionnalités.

L'extension algorithm2e est très ancienne, mais encore largement utilisée et recommandée. Elle charge l'extension float pour fournir formatter les algorithmes comme des flottants, mais vous pouvez toujours utiliser l'option H de float pour que l'algorithme apparaisse « là où vous l'avez écrit ».

Le package algorithm2e permet comme son nom l'indique d'écrire des algorithmes. Il a l'avantage d'avoir une présentation souple et d'être facilement extensible. En effet, les petites instructions conditionnelles peuvent être présentées sur une ligne et l'on peut facilement ajouter un filet sur le côté. Il dispose également de commandes telles que \SetKw qui permettent de rajouter facilement des mots-clés.

Voici un algorithme écrit avec algorithm2e:

\documentclass[french]{article}
  \usepackage[ruled,lined]{algorithm2e}
  \usepackage{babel}
 
\begin{document}
\begin{algorithm}
  \caption{Comment utiliser \LaTeX{} ?}
  \Entree{un utilisateur quelconque}
  \Sortie{un utilisateur connaissant \LaTeX{}}
 
  initialisation \;
  \Tq{pas à la fin de la FAQ}{
    l'utilisateur lit la section courante \;
    \eSi{comprise}{
      aller à la section suivante \;
      la section courante devient cette dernière \;
    }{
      revenir au début de cette section \;
    }
  }
\end{algorithm}
\end{document}

L'extension alg offre, comme algorithms, un environnement d'algorithmes flottants avec toutes les subtilités qui en découlent. Cependant, alg peut légender ses flottants dans diverses langues, dont le français. En outre, alg, contrairement à l'extension algorithms, permet d'ajouter facilement de nouvelles structures.

L'extension newalg a une interface assez similaire à celle dealgorithms, mais sa sortie vise à imiter la mise en forme plutôt agréable utilisée dans le livre “Introduction to Algorithms” de Corman, Leiserson, Rivest et Stein (le livre est consultable ici, en anglais). Malheureusement, newalg ne propose pas d'environnement flottant ni d'options de personnalisation de la sortie.

Le package newalg propose un environnement algorithm qui, par défaut, utilise le mode mathématique et l'environnement array pour les alignements. La commande \text est également disponible. Le package gère les instructions : if-then-else, for, while, repeat, switch et propose un certain nombre de macros telles que call, error, algkey, return, nil.

Exemple d'utilisation de newalg:

\documentclass{article}
  \usepackage{newalg}
 
\begin{document}
\begin{algorithm}{StrictSup}{x, y}
  \begin{IF}{x > y}
    \RETURN x
  \ELSE
    \ERROR{x leq y}
  \end{IF}
\end{algorithm}
\end{document}

Si vous vous méfiez des imitations, l'extension LaTeX développée pour “Introduction to Algorithms” a été publiée par Thomas Cormen:

• clrscode pour la deuxième édition de l'ouvrage,
• clrscode3e pour la troisième édition.

De même, le style utilisé dans “Combinatorial Algorithms: Generation, Enumeration and Search” est fourni par l'extension pseudocode, écrite par les auteurs du livre. Elle offre un style courant « de type Pascal », et quelques structures intéressantes supllémentaires pour ce qui ressemblerait à des blocs en Pascal.

L'utilisation de l'extension program est un peu différente de celle des autres. Elle compose les programmes en mode mathématique plutôt qu'en mode texte, et les sauts de ligne sont significatifs. Program ne propose pas d'environnement de flottant, mais elle peut numéroter les algorithmes, alg et algorithms. Il n'y a pas vraiment de possibilité de personnalisation ou d'ajout de fonctionnalités. La documentation de “program” est très succincte, mais un fichier d'exemple, program-demo.tex, est fourni avec l'extension et présente de nombreux cas d'usage.

Le package program permet de mettre en relief des mots clés, d'utiliser des mathématiques dans des algorithmes, etc.

\documentclass{article}
  \usepackage{program}
 
\begin{document}
\begin{program}
\mbox{Exponentiation rapide :} \\
\BEGIN
  \FOR i:=1 \TO 10 \STEP 1 \DO
     |afficher|(|exp|(2,i)); \\ |newline|() \OD
\WHERE
\FUNCT |exp|(x,n) \BODY
          \EXP z:=1;
               \WHILE n \ne 0 \DO 
                  \WHILE |pair|(n) \DO
                     n:=n/2; x:=x*x \OD;
                  n:=n-1; z:=z*x \OD;
               z \ENDEXP \ENDFUNCT
\END\label{fin}
\end{program}
\end{document}

Les packages algorithm et algorithmic disponibles dans algorithms, ont été spécifiquement conçus pour mettre en forme des algorithmes. Algorithmic sert à décrire les algorithmes et algorithm fournit un environnement flottant semblable à figure ou table (voir les pages à propos des flottants). Voici un exemple d'utilisation:

\documentclass{article}
  \usepackage{algorithm,algorithmic}
 
\begin{document}
\begin{algorithm}
\caption{Un joli algorithme}
\begin{algorithmic}
\REQUIRE{habiter près des montagnes}
\REPEAT
 \IF{il fait beau}
  \STATE faire une randonnée
 \ELSE[il fait moche]
  \STATE résoudre P $\neq$ NP
 \ENDIF
\UNTIL{foulure de cheville}
\ENSURE{bobo}
\end{algorithmic}
\end{algorithm}
\end{document}

Le style programs.sty du package progkeys permet lui aussi d'utiliser des mathématiques et de mettre des mots-clefs en gras.

Sources:

• Typesetting pseudocode in LaTeX,
• Écrire des algorithmes en LaTeX,
• Présenter des algorithmes, morceaux de programmes avec LaTeX.