http://www.net-tex.de

Algorithmendarstellung


Beschreibung resp. Darstellung von Algorithmen

Die einfache sprachliche Umschreibung eines Algorithmus kann aufwändig und
mißverständlich sein.
Daher gibt es standardisierte Verfahren um diese Informationen zu verbreiten.
Programmablaufpläne genannt PAP und/oder Nassi-Shneidermann-Diagramme (Struktogramm)
PAP und Struktogramm

Dies zeigt die Ein-/Ausgabe und das Darstellen interner Befehle sowohl im PAP als auch im Struktogramm

Dieses Modell zeigt den allgemeinen Beginn und das Ende, welche als Oval dargestellt werden.
Einzelne Befehle/Definitionen/Deklarationen o.ä. werden im PAP in einem Rechteck
dargestellt, wobei dieses mit der Anweisung in Klartext bzw. allgemeiner mathematischer
Form befüllt wird. Im Struktogramm werden Start und Ende des Algos als Kasten dargestellt,
in dem sich die untergeordneten Abläufe darstellen.

Dies zeigt eine Zählschleife, also eine Schleife, deren Häufigkeit schon vorher
festgelegt wird. Im oberen Kästchen erfolgt die Anweisung wie oft sie ausgeführt
werden soll und im unteren wird diese Bedingung überprüft.



Die Auswahl. In der Raute steht eine Bedingung die bei Erfüllung dem Ja-Pfeil
folgt, während bei Nichterfüllung der Nein-Pfeil den Weg weist.

Die Kopfgesteuerte Schleife. Vor Beginn des Aktionsblocks wird die Schleifenbedingung
auf Richtigkeit überprüft, d.h. es kann vorkommen, daß der Aktionsblock nie ausgeführt wird.

Die Fußgesteuerte Schleife. Hier wird erst einmal der Aktionsblock ausgeführt und
dann wird die Bedingung kontrolliert und befolgt.
Struktogramme und PAPs lassen sich auch in LaTeX setzen, hierzu jeweils ein Beispiel mit LaTeX-Quellen:

\usepackage{flow}
\begin{document}
\STRUCT{Beispiel}{zeigt Patterns}{%
  \PROC{Prozedurname}{Zweck}%
  \IF{Bedingung}%
  \THEN{%
    \ACTION{$then$-Befehl 1}%
    \ACTION{$then$-Befehl 2}%
  }%
  \ELSE{%
    \ACTION{$else$-Befehl}%
  }%
  \ENDIF%
  \REPEAT{%
    \ACTION{wiederhole}%
  }%
  \UNTIL{Abbruch}%
    \ACTION{Befehl}%
  \CASE{Auswahl}{%
    \WHEN{Bedingung $\alpha$}{%
      \ACTION{Befehl $\alpha$  }%
    }%
    \WHEN{Bedingung $\beta$}{%
      \ACTION{Befehl $\beta$}%
    }%
  }%
  \ENDCASE%
}%
\usepackage{nassi}

\begin{document}
 \STRUCT{Diagram}{Beispiel}{%
  \ACTION{Start}%
  \PROC{Prozedur $foo$}{Zeigt mögliche Patterns}%
  \ACCEPT{Einstiegsbedingung}{%
    \ACTION{kritischer Befehl}%
  }%
  \ENDACCEPT%
  \IF{If Bedingung}%
  \THEN{%
    \ACTION{$then$-Befehl 1}%
    \ACTION{$then$-Befehl 2}%
  }%
  \ELSE{%
    \ACTION{$else$-Befehl}%
  }%
  \ENDIF%
  \REPEAT{%
    \ACTION{Zu Wiederholen}%
  }%
  \UNTIL{$repeat$ Abbruchbedingung}%
  \WHILE{$while$ oder $for$ Startbedingung}{%
    \ACTION{Zu Wiederholen}%
  }%
  \ENDWHILE%
  \CASE{Entscheidung}{%
    \WHEN{Bedingung $\alpha$}{%
      \ACTION{$\alpha$-Befehl}%
    }%
    \WHEN{Bedingung $\beta$}{%
      \ACTION{$\beta$-Befehl 1}%
      \ACTION{$\beta$-Befehl 2}%
    }%
    \WHEN{Bedingung $\gamma$}{%
      \ACTION{$\gamma$-Befehl}%
    }%
  }%
  \ENDCASE%


Backus-Naur-Form

Die BNF ist eine standardisierte Form der Syntaxbeschreibung aus Variablen <v>, Konstanten k und Ersetzungsregeln :=
Beispiele:
<Buchstabe> ::= a|b|c|...|z|A|B|...|Z
<Zeichenkette> ::= <Buchstabe>|<Ziffer>|<Unterstrich>| <Buchstabe><Zeichenkette>|<Ziffer><Zeichenkette>| <Unterstrich><Zeichenkette>
<Variablenname> ::= <Buchstabe>|<Buchstabe><Zeichenkette>

$Id: ad.html,v 1.6 2006/04/30 21:30:26 stefan Exp $