Algorithmen
Unter einem Algorithmus verstehen wir eine präzise,
endliche Verarbeitungsvorschrift ,
die auf endlich vielen wohldefinierten Grundoperationen von jeweils
endlicher Ausführungszeit aufbaut.
Er definiert eine Funktion von seiner Eingabe in seine Ausgabe,
und er beschreibt eine Realisierung dieser Funktion.
Nicht jede Verarbeitungsvorschrift betrachten wir als Algorithmus;
wir verlangen von einem Algorithmus:
-
er löst eine Klasse von Problemen;
die Klasse ist sein Definitionsbereich ;
-
die Länge seiner Beschreibung und der Platzbedarf während
der Ausführung sind endlich;
-
für jede Eingabe aus dem Definitionsbereich ergibt sich das Ergebnis
nach endlich vielen Schritten (der Algorithmus terminiert );
-
wir lassen zu, daß während der Ausführung
eines Algorithmus für den nächsten Schritt
noch Wahlmöglichkeiten bestehen;
dann nennen wir ihn nichtdeterministisch,
andernfalls deterministisch.
Manchmal betrachtet man auch nicht-terminierende Algorithmen,
etwa bei Steuerungsaufgaben oder im Bereich der Betriebssysteme.
Sie lösen eine von vornherein nicht beschränkte Folge
von Problemen gleicher Art nacheinander; jeder dieser Schritte
ist dann ein Algorithmus im obigen Sinne.
Eine reale oder gedachte Funktionseinheit,
welche die einzelnen Arbeitsschritte eines Algorithmus ausführt,
nennen wir eine Maschine.
Beispiele dafür sind etwa:
die endlichen Automaten,
die Kellerautomaten,
unsere Formularmaschine für Syntaxdiagramme,
die virtuelle Modula-Maschine, auf der unsere Modula-Programme ablaufen,
und die später besprochene
Turing-Maschine.
Auch unser Computer selbst gehört natürlich dazu!
zurück |
Inhalt | Index |
vor |
Vorlesung
Klaus Lagally, 22. Februar 2000, 19:35