Algorithmen
Unter der Spezifikation eines Algorithmus versteht man eine Aussage,
die möglichst genau beschreibt, was der Algorithmus leistet.
Zwei Algorithmen heißen wirkungsgleich (äquivalent),
wenn sie der gleichen Spezifikation genügen. |
Algorithmus:
Beschreibung zur Lösung eines Problemes, die
so formuliert ist, das sie von einer Maschine abgearbeitet werden kann
Eigenschaften von Algorithmen:
-
Jeder Algorithmus löst eine Klasse von Problemen.
-
endliche Beschreibung
-
endliche Abarbeitung
-
Determiniertheit (gleiche Eingabe --> gleiche Ausgabe)
-
Arten:
- deterministische
(Zu jedem Zeitpunkt seiner Ausführung besteht höchstens eine Möglichkeit der
Fortsetzung.)
- nichtdeterministische,
(An gewissen Stellen gibt es bei der Ausführung mehrere Möglichkeiten der Fortsetzung,
von denen man nach Belieben eine auswählen kann.)
- stochastische
(An gewissen Stellen gibt es bei der Ausführung mehrere Möglichkeiten der Fortsetzung,
für deren Auswahl man Wahrscheinlichkeiten zuordnen kann.)
Formulierung von Algorithmen:
-
verbale
-
Struktogramm
-
Programm (Quelltext)
