2.3 Wie formuliert man einen Algorithmus?

Ebenso wie es viele Sprachen gibt, in denen man ein Bier bestellen kann, oder mehrere Programmiersprachen um ein Programm zu erstellen, gibt es auch mehrere Möglichkeiten, einen Algorithmus zu formulieren.

Die wichtigsten sind:

Mehr oder weniger formalisierte textliche Beschreibung.

Als Beispiel hier der Euklidsche Algorithmus ^2.4 aus [Knuth 1], S. 2, mit dessen Hilfe der größte gemeinsame Teiler (ggT) zweier gegebener positiver ganzer Zahlen und bestimmt werden kann:

**Abbildung 2.1:** Euklidscher Algorithmus aus [Knuth 1]
$\begin{figure}{\center \parbox{12cm}{{\bf Algorithm E} ({\it Euclid's algorithm\... ...go back to step E1. \rule[-0.2em]{0.35em}{1em} \end{tabular}\\ } \end{figure}$

Grafische Darstellung als Flußdiagramm (Programmablaufplan)

Dabei wird jeder Schritt eines Algorithmus in einem Rahmen dargestellt, wobei der Rahmen je nach Art des Schritts (auszuführende Anweisung, Fallunterscheidung etc.) unterschiedliche Formen annehmen kann. Die einzelnen Schritte werden sinnvoll in einem Bild angeordnet und entsprechend ihrer Ausführungsreihenfolge mit Linien oder besser Pfeilen verbunden.

Das obige Beispiel des Euklidschen Algorithmus sieht bei [Knuth 1] so aus:

**Abbildung:** Flußdiagramm Euklidscher Algorithmus in Notation gem. Knuth
$\begin{figure}\mbox{ }\begin{picture}(130,30)(0,-9)\thinlines \put(20,17){\v... ...(110,9){\line(0,1){5}} \put(110,14){\vector(-1,0){90}} \end{picture}\end{figure}$

Mithilfe solcher Flußdiagramme (flow chart) lassen sich praktisch alle Algorithmen darstellen, weshalb sie aber auch inzwischen weitgehend verpönt sind; denn durch die freie Platzierung der einzelnen Elemente und die Möglichkeit, Pfeile beliebig zu ziehen, kann man einerseits sehr unübersichtliche Algorithmen darstellen, andererseits auch alleine die Darstellung eines vielleicht vernünftigen Algorithmus unübersichtlich gestalten (,,Spaghetticode``).

Welche Rahmen um die einzelnen Symbole gezeichnet werden, wird etwas uneinheitlich gehandhabt. Bei den Büchern von Knuth werden, wie in Abbildung 2.2 gezeigt, um die eigentlichen Anweisungen gerade Rechtecke gezeichnet, und Fallunterscheidungen stehen in einem zigarrenförmigen abgerundeten Rahmen.

Üblicher ist aber eine andere Kennzeichnung, nämlich ebenfalls Rechtecke um Anweisungen, aber auf einem Eck stehende Rauten für Fallunterscheidungen. Abgerundete Rahmen werden für den Start- und einen oder gegebenenfalls mehrere Endpunkte des Algorithmus verwendet. Der Euklidsche Algorithmus sieht dann so aus:

**Abbildung:** Flußdiagramm Euklidscher Algorithmus in Standardnotation
$\includegraphics[width=6cm]{flussplan_euklid.eps}$

Bei solchen Flußdiagrammen gibt es für Schleifen keine besonderen Symbole; man muß Initialisierung, Schleifenbedingung, Schleifenrumpf und gegebenenfalls Reinitialisierung (Weitersetzen des Schleifenzählers beispielsweise) aus den gezeigten einzelnen Elementen zusammensetzen. Alleine dadurch wird die Darstellung schnell unübersichtlich.

Die Symbole sind in DIN 66001 genormt (mit weiteren Symbolen, die hier nicht erwähnt werden, beispielsweise zur Ein- und Ausgabe).

Struktogramme (Nassi-Shneiderman-Diagramme) nach DIN 66261.

Hier werden rechteckige Grundelemente für jeweils eine Anweisung, eine Fallunterscheidung, eine Schleife etc. direkt so aneinandergefügt, daß sich für den dargestellten Algorithmus insgesamt ein rechteckiges Diagramm ergibt. Der Start eines Diagramms ist immer am oberen Rand; das Ende zumindest am unteren Rand (oder in einem besonderen Abbruchelement irgendwo innerhalb des Diagramms).

In einigen der Bauelemente kommen in der ,,normalen`` Darstellung schräge Linien vor. Da dies manchmal schlecht zu zeichnen ist (beispielsweise beim Zusammensetzen aus Buchstaben), gibt es jeweils eine Ersatzdarstellung ohne schräge Linien. Diese Ersatzdarstellung ist insbesondere auch geeignet, direkt im Quelltext als Kommentar angelegt zu werden!

Es gibt folgende Grundelemente (jeweils links in Normal- und rechts in Ersatzdarstellung):

Anweisung: Nach Ausführung der Anweisung A wird das darunterliegende Element bearbeitet.
$\includegraphics[width=6cm]{strukt_anweisung.eps}$
Anweisungsfolge: Es werden nacheinander die Anweisungen A1, A2 und so fort abgearbeitet.
$\includegraphics[width=6cm]{strukt_anweisungsfolge.eps}$

Eine Anweisungsfolge kann überall eingesetzt werden, wo auch eine einfache Anweisung erlaubt ist.
Fallunterscheidung: Die Bedingung B wird ausgewertet; je nach Ergebnis wird dann entweder die Anweisung (oder Anweisungsfolge) A1 oder die Anweisung A2 ausgeführt.
Falls vorhanden, wird anschließend die Anweisung A3 ausgeführt.
$\includegraphics[width=7cm]{strukt_fallunterscheidung.eps}$
Mehrfachentscheidung: Der Ausdruck E wird ausgewertet. Falls er den Wert W1 ergibt, wird die darunterliegende Anweisung(sfolge) A1 ausgeführt; analog falls der Ausdruck W ergibt, wird A ausgeführt. Trifft keiner der angegebenen Werte zu, wird As ausgeführt.
$\includegraphics[width=8cm]{strukt_mehrfachauswahl.eps}$
Abweisende Schleife : Es wird die Bedingung B geprüft. Falls B erfüllt ist, wird A ausgeführt, und anschließend B erneut geprüft, und so weiter.
$\includegraphics[width=8cm]{strukt_abweisendeschl.eps}$
Nichtabweisende Schleife: Zuerst wird A ausgeführt. Dann wird die Bedingung B geprüft. Falls B erfüllt ist, wird A erneut ausgeführt, und so weiter.
$\includegraphics[width=8cm]{strukt_nichtabweisendeschl.eps}$
Unbedingte Schleife: A wird wiederholt ausgeführt.
$\includegraphics[width=8cm]{strukt_unbedingteschl.eps}$
Abbruch: Der umgebende Block Name wird beendet.
$\includegraphics[width=8cm]{strukt_abbruch.eps}$

Nach der Abarbeitung eines Elements wird das darunterliegende, gleich breite Element verwendet. Eine Ausnahme davon sind die einfache Fallunterscheidung und die Mehrfachauswahl. Hier wird jeweils nur einer der darunterliegenden Teilblöcke weiterverfolgt.

**Abbildung 2.4:** Struktogramm Euklidscher Algorithmus
$\includegraphics[width=6cm]{strukto_euklid.eps}$

**Abbildung 2.5:** Struktogramm Euklidscher Algorithmus (Ersatzdarstellung)
$\begin{figure}\begin{verse} \begin{verbatim}Euklidscher Algorithmus: +------... ... +---------------------------------------+\end{verbatim} \end{verse}\end{figure}$

Mit einem Nassi-Shneiderman-Diagramm lassen sich nicht alle Algorithmen darstellen; es ist nämlich nicht möglich beliebige Sprünge von einer Stelle eines Algorithmus zu einer anderen Stelle auszudrücken.

Da dies aber ohnehin als sehr unelegant gilt, werden Struktogramme gerne verwendet: elegant formulierte Algorithmen (also solche ohne wilde Sprünge) lassen sich damit sehr gut lesbar darstellen. Zudem ist die Umsetzung einer solchen Darstellung in jede moderne Programmiersprache leicht und elegant.