Eigenschaften eines Algorithmus (nach Vorlesung Prof

Eigenschaften eines Algorithmus (nach Vorlesung Prof.Dr.R.Schiedermeier, FH München)

Nicht jede beliebige Berechnungsvorschrift in Einzelschritten taugt als Algorithmus;

Gegenbeispiel: "Algorithmus für perfektes Schachspiel"

Startaufstellung einnehmen
Wiederhole bis Spiel gewonnen...

2a. wähle besten Zug aus;
2b. führe diesen Zug aus;
2c. warte auf Zug des Gegners;

Happy happy joy joy...

Mit diesem "Algorithmus" stimmt offenkundig etwas nicht; Das Problem liegt in Schritt 2a.

Berechnungsvorschrift muß Anforderungen genügen, um als Algorithmus bezeichnet werden zu können;

Liste von Eigenschaften lt. [Knuth73]:

Definierte Eingaben und Ausgaben
Endlich
Exakt
Effektiv

Diese Eigenschaften lassen sich meist nicht (formal) nachweisen; Sollten als Leitlinien für den Entwurf eines Algorithmus betrachtet werden;

Definierte Eingaben und Ausgaben

Es muß genau festgelegt werden, mit welchen Vorgabedaten ("Eingaben") der Algorithmus arbeitet; Das ist normalerweise kein Problem;

Ebenso müssen die gelieferten Ergebnisse ("Ausgaben") abgegrenzt werden;

Exakt

Jeder Einzelschritt muß so genau beschrieben sein, daß es keine Mehrdeutigkeiten bzgl. seiner Abwicklung gibt;

Gegenbeispiel: Schritt "wähle besten Zug aus" im oben genannten Schach-Beispiel: Es ist unklar, wie der "beste" Zug definiert ist;

Endlich

Der Algorithmus muß irgendwann zu einem Ende kommen;

Anzahl der Einzelschritte oder Gesamtdauer der Abwicklung sind nicht festgelegt; Es muß aber eine vorhersagbare Obergrenze existieren;

Gegenbeispiel: "Algorithmus zum Nachweis der Fermat'schen Behauptung: Es gibt für positive, ganze Zahlen a, b, c und n keine Lösung der Gleichung aⁿ + bⁿ = cⁿ mit n > 2."

wiederhole für jede Kombination von positiven, ganzen Zahlen a, b, c und n (n > 2):

Falls a, b, c und n der Gleichung aⁿ + bⁿ = cⁿ genügen: gib aus "True" und breche ab;

gib aus "False: und breche ab;

Die Vorschrift ist nicht endlich, weil man keine (noch so große) Obergrenze für die Anzahl der insgesamt auszuführenden Einzelschritte angeben kann;

Effektiv

Jeder Schritt muß im Prinzip auch mit Bleistift und Papier ausführbar sein;

Unterschied zu "endlich": "Effektiv" bezieht sich auf einen einzelnen Schritt, "endlich" auf das ganze Verfahren;

Gegenbeispiel: "Algorithmus für perfektes Schachspiel"

Startaufstellung einnehmen
Wiederhole bis Spiel gewonnen...

2a. untersuche sämtliche möglichen Fortsetzungen des Spiels; wähle einen Zug aus, der zum sicheren Sieg führt;
2b. führe diesen Zug aus;
2c. warte auf Zug des Gegners;

Happy happy joy joy...

Schritt 2a. ist nicht effektiv (aber endlich: es gibt nur endlich viele Stellungen im Schachspiel), weil es mehr Spielstellungen gibt als Elektronen im Universum;