Algorithmen (algorithm2e/algpseudocode)

Die Suche nach „latex algorithm package“ liefert vier fast identische Namen – algorithm, algorithmic, algorithmicx, algorithm2e –, und die Präambel, die gerade repariert werden soll, lädt mit einiger Wahrscheinlichkeit zwei davon, die sich im selben Dokument nicht vertragen. Genau dieses Durcheinander ist das Thema dieser Seite, denn einmal entwirrt, ist Pseudocode in LaTeX unkompliziert. Festzuhalten ist vor allem: Pseudocode ist kein eingefügter Quelltext. Anders als die Code-Listings auf der Schwesterseite wird ein Algorithmus wie Mathematik gesetzt – kursive Variablen, ein Pfeil für die Zuweisung, fette Schlüsselwörter – und zwar in einem nummerierten Gleitobjekt, auf das \ref verweisen kann. Im Folgenden: welches Paketpaar tatsächlich geladen wird, welche Fehlermeldungen das falsche Paar erzeugt und beide Dialekte vollständig ausgeschrieben.

Pseudocode und listings: eingefügter Code oder gesetzter Text

In einem Satz: listings bewahrt Zeichen, Pseudocode setzt Bedeutung. Was an listings oder minted übergeben wird, behandelt LaTeX wörtlich – jedes Leerzeichen und jedes Sonderzeichen überlebt bis aufs Papier –, und genau das braucht echter Quelltext; diese Abwägung gehört auf die Schwesterseite. Pseudocode dreht das um. Aus $y \gets 1$ wird y als kursive Variable und \gets als Pfeil ←: der Körper lebt im Mathematikmodus, nicht in einer Verbatim-Umgebung. Nur die Schlüsselwörter erscheinen in fetter Antiqua und heben sich damit von den Variablen ab. Diese Übereinkunft – kursiv für Variablen, fett für Schlüsselwörter – ist die Lehrbuchkonvention, die bis zu Knuths The Art of Computer Programming zurückreicht. Auch der Name \gets stammt aus dieser Tradition: Er kommt aus der Informatik und liest sich in x \gets 1 als „x gets 1“.

Der zweite Unterschied ist der Ort. Ein lstlisting bleibt im Textfluss stehen, Pseudocode wandert dagegen üblicherweise in ein Gleitobjekt, genau wie figure oder table. LaTeX schiebt es dann an einem ungünstigen Seitenumbruch vorbei, versieht es mit der nummerierten Überschrift „Algorithm 1“ und nimmt es in \listofalgorithms auf. Sobald die eine strukturelle Tatsache sitzt – Behälter (das Gleitobjekt) und Inhalt (der Pseudocode) stammen aus verschiedenen Paketen –, ordnen sich die vier verwirrenden Namen von selbst.

Welches Paket wird tatsächlich per \usepackage geladen?

Für ein neues Dokument ist die Antwort zwei Zeilen lang. Entweder stehen \usepackage{algorithm} und \usepackage{algpseudocode} nebeneinander, oder es wird \usepackage{algorithm2e} allein geladen. Fast jede andere Kombination geht schief. Verwirrend ist das, weil CTAN-Paketnamen und Style-Dateinamen nicht zusammenpassen. algorithm.sty stammt nicht aus einem Paket namens algorithm, sondern aus dem Bündel algorithms – im Plural. Und algpseudocode.sty stammt aus algorithmicx. Man tippt also zwei Dateinamen in die Präambel und installiert dabei zwei völlig anders benannte Bündel.

% Camp 1 -- two packages, two jobs. This is the usual choice.
\usepackage{algorithm}      % the float: \begin{algorithm}, \caption, \listofalgorithms
\usepackage{algpseudocode}  % the body:  \begin{algorithmic}, \State, \If, \For

% Camp 2 -- one package does everything. Do NOT also load algorithm.
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}

Wie streng diese Arbeitsteilung ist, zeigt ein Blick in algorithm.sty: keine hundert Zeilen, und keine davon handelt von Pseudocode. Das Paket lädt float, deklariert mit \newfloat{algorithm}{htbp}{loa} genau einen neuen Gleitobjekttyp, benennt ihn „Algorithm“ und definiert \listofalgorithms – mehr ist es nicht (die Fassung in TeX Live 2024 ist v0.1 vom 24. August 2009). Ein hübscher Nebeneffekt: Jede Option, die das Paket nicht kennt, wird als Name des Gleitobjekts gedeutet. Nach \usepackage[Procedure]{algorithm} lauten sämtliche Beschriftungen „Procedure 1“, „Procedure 2“.

Wenn Command \algorithm already defined. erscheint

Diese Meldung bedeutet genau eines: es werden algorithm und algorithm2e gleichzeitig geladen. Beide wollen eine Umgebung namens algorithm anlegen, und das zweitgenannte läuft ins erste hinein. Eines der beiden aus der Präambel entfernen, und der Fehler ist weg. Aus demselben Grund ändert sich der Wortlaut mit der Ladereihenfolge: steht algorithm2e zuerst und algorithm danach, erscheint stattdessen ! LaTeX Error: Command \listofalgorithms already defined. – gleiche Ursache. Die zweite häufige Variante lautet ! LaTeX Error: Command \algorithmic already defined. und tritt auf, wenn das alte algorithmic und das neuere algpseudocode zusammen geladen werden. Die algorithmicx-Familie ist der Nachfolger von algorithmic; beide zugleich braucht niemand.

% Each of these three preambles stops the compile.
\usepackage{algorithm}\usepackage{algorithm2e}
%   ! LaTeX Error: Command \algorithm already defined.

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

\usepackage{algorithmic}\usepackage{algpseudocode}
%   ! LaTeX Error: Command \algorithmic already defined.

% If a class or a co-author really forces algorithm2e into a document that
% already owns the algorithm float, this option renames the environment to
% algorithm2e and \listofalgorithms to \listofalgorithmes, so nothing collides.
\usepackage[algo2e]{algorithm2e}

Die unangenehmste Kombination wirft allerdings gar keinen Fehler. algorithm2e und algpseudocode nebeneinander geladen, und das Dokument übersetzt klaglos. Der Grund: Wenn algorithmicx einen Anwendernamen wie \For oder \If definiert, prüft es zuerst, ob dieser Name bereits existiert – und verzichtet stillschweigend, falls ja. Die Bedeutungen aus algorithm2e überleben also, und schiefgehen tut zunächst nichts. Erst beim Schreiben eines algorithmic-Körpers bricht in der Zeile mit \EndWhile etwas scheinbar Fremdes hervor, etwa ! Missing number, treated as zero.. So weit wie möglich von der Ursache entfernt zu zerbrechen ist wohl schlimmer als ein klarer Fehler. Genau gegen solche Kollisionen führt algorithm2e die Option algo2e; mit ihr heißt \listofalgorithms dann anders geschrieben \listofalgorithmes – eine Spur der französischsprachigen Herkunft des Pakets.

\begin{algorithm} ist ein Gleitobjekt: \caption, \label, [H]

algorithm ist ein echtes Gleitobjekt, genau in dem Sinn, in dem es figure und table sind. Die Standardplatzierung lautet htbp – hier, oben, unten, dann eine eigene Seite –, und die Verzeichnisdatei trägt die Endung .loa. Alles von Abbildungen Vertraute überträgt sich damit: \caption{…} erzeugt die nummerierte Überschrift „Algorithm 1“, und ein unmittelbar danach gesetztes \label{alg:…} erlaubt es, im Text die Nummer mit \ref{alg:power} und die Seite mit \pageref{alg:power} abzurufen. Steht \label vor \caption, stimmt die Nummer nicht mehr – um eins verschoben oder die Abschnittsnummer –, deshalb ist die Reihenfolge einzuhalten. Ein \listofalgorithms am Dokumentanfang – das Geschwister von \listoffigures und \listoftables – liefert ein „List of Algorithms“, das jede Nummer mit ihrem Beschriftungstext zusammenführt. Wie immer stabilisieren sich Nummern, Verweise und Verzeichnis erst nach zwei Läufen. Und wenn gerade nicht gleiten soll: \begin{algorithm}[H] fixiert den Kasten an Ort und Stelle – [H] ist sofort verfügbar, weil algorithm das Paket float ohnehin lädt.

Den Körper schreiben: \State, \If, \For, \While, \Function

Die innere Umgebung heißt algorithmic – die letzte Falle der Namensgebung: das Paket heißt algpseudocode, die Umgebung nicht. Alle Befehle beginnen mit einem Großbuchstaben: \State eröffnet eine Anweisungszeile, Blöcke werden ausdrücklich mit \If … \EndIf, \For … \EndFor und so weiter geschlossen. Das optionale Argument am Anfang legt den Abstand der Zeilennummern fest: [1] nummeriert jede Zeile, [5] jede fünfte, ohne Argument gibt es keine Nummern. Das folgende Beispiel ist eine binäre Suche und führt Verzweigungen, eine Schleife, eine Funktion, eine Vorbedingung und einen Zeilenendkommentar vor.

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

\begin{algorithm}
  \caption{Binary search}\label{alg:bsearch}
  \begin{algorithmic}[1]
    \Require sorted array $a[1..n]$, key $k$
    \Ensure index of $k$, or $0$
    \Function{Search}{$a,k$}
      \State $lo \gets 1$;\ $hi \gets n$ \label{ln:init}
      \While{$lo \le hi$}
        \State $m \gets \lfloor (lo+hi)/2 \rfloor$ \Comment{midpoint}
        \If{$a[m] = k$}
          \State \Return $m$
        \ElsIf{$a[m] < k$}
          \State $lo \gets m+1$
        \Else
          \State $hi \gets m-1$
        \EndIf
      \EndWhile
      \State \Return $0$
    \EndFunction
  \end{algorithmic}
\end{algorithm}

Algorithm~\ref{alg:bsearch} halves the interval; the bounds are set on
line~\ref{ln:init}, page~\pageref{alg:bsearch}.

\end{document}

Das Ergebnis sieht so aus: Ein oben und unten von Linien begrenzter Kasten gleitet auf die Seite, überschrieben mit „Algorithm 1 Binary search“. Darin erzeugen \Require und \Ensure die fetten Marken Require: und Ensure:, die außerhalb der Nummerierung stehen. Die Nummern beginnen bei der \Function-Zeile und laufen links mit 1, 2, 3 … weiter; \Comment{midpoint} setzt am Zeilenende ein kleines Dreieck: ▷ midpoint. Der Name in \Function{Search}{$a,k$} erscheint in Kapitälchen, und aufgerufen wird er aus einer anderen Zeile mit \Call{Search}{$a,k$}. Weil viele andere Marken wünschen: Die Zeichenketten Require: und Ensure: stecken in \algorithmicrequire und \algorithmicensure; \renewcommand{\algorithmicrequire}{\textbf{Input:}} macht daraus Input:.

Der häufigste Unfall in diesem Lager ist ein vergessenes \State – und er erzeugt keinen Fehler. Folgt auf \State $x \gets 1$ ein nacktes $y \gets 2$, steht in der Ausgabe „1: x ← 1 y ← 2“: zwei Anweisungen in einer Zeile und eine Nummer zu wenig. Stimmt die Zeilenzahl nicht, ist hier zuerst zu suchen. Und wer in einer alten Konferenzvorlage Großbuchstabenbefehle wie \STATE, \WHILE, \ENDWHILE findet, hat den algorithmic-Dialekt von 1994 vor sich. Um ein solches Manuskript unverändert weiterzuverwenden, lädt man statt algpseudocode einfach \usepackage{algcompatible}: Die Großbuchstabenbefehle laufen dann auf dem Unterbau von algorithmicx weiter.

Zeilen nummerieren und auf „Zeile 3“ verweisen

Zeilennummern lassen sich referenzieren. Die Umgebung algorithmic mit [1] öffnen, ans Ende der gewünschten Zeile ein \label{ln:init} setzen – und \ref{ln:init} im Text expandiert zur Nummer dieser Zeile. Im obigen Beispiel trägt die \Function-Zeile die 1, also ergibt \ref{ln:init} die 2. Das wiegt schwerer, als es klingt: Wer „die Bedingung in Zeile 3“ von Hand schreibt, macht seinen Text mit der nächsten eingefügten Anweisung zur Unwahrheit. In algorithm2e funktioniert es genauso – linesnumbered aktivieren und \label{…} hinter das abschließende \; der Zeile setzen. Ein Vorbehalt: Eine unnummerierte Zeile zu beschriften ist sinnlos, denn ohne [1] oder linesnumbered existiert gar keine Nummer.

algorithm2e schreiben: geschweifte Klammern statt \End… und das unverzichtbare \;

Das andere Lager schließt einen Block nicht mit einem Befehl wie \EndFor. Es übergibt den Körper als Klammerargument – \For{Bedingung}{Körper}, \While{Bedingung}{Körper}, und für if–then–else \eIf{cond}{then}{else} (\uIf ohne else, \lIf für eine einzige Zeile). Ein- und Ausgabe haben eigene Befehle, \KwIn{…} und \KwOut{…}, gesetzt als fettes Input: und Output: (wer die Wörter Data: und Result: vorzieht, nimmt \KwData{…} und \KwResult{…}). Die große Falle: Jede Anweisung muss mit \; enden. Fehlt es, gibt es keinen Fehler – die nächste Anweisung läuft schlicht in dieselbe Zeile. Wer das „;“ im Druck nicht sehen möchte, blendet es mit \DontPrintSemicolon aus (das \; selbst bleibt nötig). Das gesamte Erscheinungsbild wird beim Laden gewählt: ruled (Linien oben und unten), boxed (Kasten um alles), vlined und lined (zwei Arten, senkrechte Blocklinien zu ziehen), plain (Standard), dazu linesnumbered für Zeilennummern. Diese drei Linienoptionen sind buchstäblich die Dokumentbefehle \SetAlgoVlined, \SetAlgoLined und \SetAlgoNoLine, nur vorab ausgeführt. TeX Live 2024 liefert v5.2 vom 18. Juli 2017.

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

\begin{algorithm}
  \DontPrintSemicolon
  \KwIn{an array $a[1..n]$}
  \KwOut{the sum $s$ of its positive entries}
  $s \gets 0$\;\label{ln:zero}
  \For{$i \gets 1$ \KwTo $n$}{
    \eIf{$a[i] > 0$}{
      $s \gets s + a[i]$\;
    }{
      \tcp{negative or zero: skip}
    }
  }
  \Return $s$\;
  \caption{Sum of positive entries}\label{alg:sum}
\end{algorithm}

Algorithm~\ref{alg:sum} accumulates into $s$, initialised on line~\ref{ln:zero}.

\end{document}

Die Überschrift lautet „Algorithm 1: Sum of positive entries“ – der Doppelpunkt nach der Nummer ist der sichtbare Unterschied zum algorithm-Gleitobjekt. Darüber stehen Input: und Output:; der Körper liest sich als for i ← 1 to n do und if … then … else, mit einer senkrechten Linie links neben jedem Block, weil vlined angefordert wurde. \tcp{…} ist ein Kommentar in der Zeile und erscheint als // negative or zero: skip. Zu beachten: \caption steht am Ende der Umgebung – das ist die Konvention von algorithm2e, und mit ruled erscheint die Überschrift trotzdem oben am Kasten. Derselbe Text wandert in \listofalgorithms. Da auch die algorithm2e-Umgebung standardmäßig gleitet, steht \begin{algorithm}[H] bereit, wenn sie stehen bleiben soll.

Schlüsselwörter auf Deutsch: die Option onelanguage

algorithm2e kann die Schlüsselwörter des Pseudocodes selbst übersetzen. Nur dieses Lager bietet das; in algpseudocode gibt es nichts Vergleichbares. Zur Wahl stehen french, german, ngerman, spanish, italiano, portuguese, czech, slovak, croatian und english. Im Verhalten steckt allerdings eine Stufe. \usepackage[german]{algorithm2e} allein benennt das Gleitobjekt in „Algorithmus 1:“ um, lässt \For und \eIf aber weiterhin englisch drucken – deutsche Ausgabe erhält man über die deutschsprachigen Befehlsnamen, im Französischen etwa \Pour{…}{…} und \Si{…}{…}. Wer die Befehlsnamen eines bestehenden Manuskripts nicht umschreiben möchte, ergänzt onelanguage: Mit \usepackage[german,onelanguage]{algorithm2e} liefern dieselben \For und \eIf für i ← 1 bis n tue sowie wenn … dann … sonst … Ende. Im Französischen ergibt [french,onelanguage] entsprechend pour i ← 1 à n faire und si … alors … sinon … fin, unter der Überschrift „Algorithme 1 :“.

% Keep the English command names, print French keywords.
\usepackage[french,onelanguage,ruled,linesnumbered]{algorithm2e}
%   \For{...}{...}  ->  pour i <- 1 a n faire ... fin

% Without onelanguage, only the float name is translated; use the
% French command names for a French body.
\usepackage[french,ruled]{algorithm2e}
%   \Pour{...}{...}, \Si{...}{...}, \KwA

Welches also nehmen: algpseudocode oder algorithm2e

Nennt die Vorlage des Verlags oder der Konferenz eines der beiden, gilt diese Vorgabe – viele Konferenzklassen stimmen Ränder und Schriften auf eine bestimmte Wahl ab. Andernfalls: algpseudocode, wenn der Pseudocode wie mathematischer Text lesbar sein soll, und algorithm2e, wenn ausdrückliche Ein-/Ausgabedeklarationen, Blocklinien oder übersetzte Schlüsselwörter gebraucht werden. Den Rest klärt die Tabelle.

Welches auch gewählt wird, die Präsentationsebene ist identisch: \caption liefert die nummerierte Überschrift, \label und \ref lassen den Text darauf zeigen, \listofalgorithms baut das Verzeichnis, und zwei Läufe fixieren die Nummern. Und noch einmal, denn darin besteht die ganze Lehre dieser Seite: pro Dokument genau ein Körperpaket. Mit algorithm2e niemals algorithm laden. Mit algpseudocode niemals algorithmic laden. Diese eine Zeile Disziplin verhindert nahezu jeden Unfall rund um die vier verwechselbaren Namen vom Anfang. Wer statt Pseudocode echten Quelltext mit Syntaxfärbung und Zeilennummern zeigen will, ist auf der Schwesterseite zu listings und minted richtig.