Mit Google fortfahren
Eigenschaften von Algorithmen einfach erklärt
Ein Algorithmus ist eine präzise Verarbeitungsvorschrift: Er führt von einer Eingabe über ausführbare Einzelschritte zu einer Ausgabe. Einen problemlösenden Algorithmus prüfst du vor allem auf Ausführbarkeit, Eindeutigkeit, Endlichkeit und Terminierung. Dabei musst du besonders Endlichkeit und Terminierung sowie Determinismus und Determiniertheit auseinanderhalten.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Die Eigenschaften gemeinsam prüfen
Stell dir mehrere Schachteln und eine Waage vor. Gesucht ist eine Schachtel mit größtem Gewicht. Eine mögliche Vorschrift lautet:
- Lege eine Schachtel auf eine Waagschale.
- Nimm eine weitere Schachtel und vergleiche beide.
- Lege die leichtere Schachtel beiseite. Sind beide gleich schwer, lege die neu hinzugekommene Schachtel beiseite.
- Wiederhole die Schritte 2 und 3, solange noch Schachteln vorhanden sind.
- Gib die verbliebene Schachtel als Ergebnis aus.
Nach jedem Vergleich bleibt eine Schachtel auf der Waage, die mindestens so schwer ist wie alle bereits geprüften Schachteln. Eine leichtere Schachtel kann nicht mehr das gesuchte Maximum sein und darf ausscheiden. Nach dem letzten Vergleich bleibt deshalb eine Schachtel mit größtem Gewicht übrig.
An diesem Beispiel kannst du mehrere Eigenschaften prüfen:
- Ausführbarkeit: Der vorgesehene Ausführende kann jede Anweisung umsetzen. Mit der Waage lassen sich zwei Schachteln vergleichen. Die Anweisung „Sortiere sofort alle Schachteln“ wäre dagegen keine ausführbare Grundoperation dieses Ausführenden.
- Eindeutigkeit: Für jeden Vergleich ist festgelegt, wie es weitergeht. Die Zusatzregel für gleich schwere Schachteln verhindert eine offene Entscheidung.
- Endliche Beschreibung: Die Vorschrift besteht aus endlich vielen Anweisungen. Eine Schleife ersetzt dabei beliebig viele ausgeschriebene Wiederholungen.
- Terminierung: Bei einer endlichen, nicht leeren Menge von Schachteln wird in jeder Runde eine Schachtel beiseitegelegt. Daher endet das Verfahren.
- Allgemeinheit: Die Vorschrift funktioniert nicht nur für genau drei Schachteln, sondern für jede endliche, nicht leere Schachtelmenge. Allgemeinheit ist typisch, kann aber entfallen, wenn ausdrücklich nur ein einzelner Fall gelöst werden soll.
Ob ein Schritt ausführbar ist, hängt vom Ausführenden ab. Eine Person besitzt anderes Vorwissen und andere Grundoperationen als eine einfache Maschine.
Weg und Ergebnis unterscheiden
Zwei ähnlich klingende Eigenschaften beschreiben verschiedene Fragen:
Determinismus
Ein Algorithmus ist deterministisch, wenn in jedem Zustand eindeutig feststeht, welcher Schritt als Nächstes ausgeführt wird.
Determiniertheit
Ein Algorithmus ist determiniert, wenn gleiche Eingaben und gleiche Startbedingungen bei jeder Ausführung dasselbe Ergebnis liefern.
Beim Determinismus untersuchst du also den Weg. Bei der Determiniertheit untersuchst du das Ergebnis.
Ein Sortierverfahren soll dieselben Zahlen immer aufsteigend ausgeben. Es darf zufällig auswählen, welches noch ungeprüfte Element es als Nächstes betrachtet. Dadurch kann der Bearbeitungsweg wechseln. Wenn die vollständig sortierte Ausgabe trotzdem stets gleich ist, ist das Verfahren determiniert, aber wegen der zufälligen Wahl nicht deterministisch.
Ein deterministischer Algorithmus liefert unter gleichen Voraussetzungen einen festgelegten Ablauf. Im hier verwendeten Begriffsverständnis ist er damit auch determiniert. Umgekehrt kann ein determiniertes Verfahren verschiedene Wege zum gleichen Ergebnis zulassen.
Endlichkeit und Terminierung trennen
Eine kurze Beschreibung kann eine Schleife enthalten, die niemals endet. Deshalb sind Endlichkeit und Terminierung nicht dasselbe.
Statische Finitheit
Die statische Finitheit bedeutet: Die Beschreibung des Algorithmus hat eine endliche Länge.
Dynamische Finitheit
Die dynamische Finitheit bedeutet: Während der Ausführung wird zu jedem einzelnen Zeitpunkt nur endlich viel Speicher benötigt.
Terminierung
Ein Algorithmus terminiert für eine Eingabe, wenn er nach endlich vielen Schritten anhält oder kontrolliert abbricht. Er terminiert überall, wenn dies für jede zulässige Eingabe gilt.
Die Vorschrift „Warte auf einen Befehl, verarbeite ihn und warte danach wieder“ lässt sich mit wenigen Anweisungen beschreiben. Sie ist also statisch endlich. Ohne Beenden-Befehl läuft sie jedoch unbegrenzt weiter und terminiert dann nicht.
Bei einem Algorithmus, der eine einzelne Aufgabe lösen und ein Ergebnis liefern soll, ist Terminierung normalerweise erforderlich. Betriebssysteme, Steuerungen und andere fortlaufende Systeme sollen dagegen absichtlich weiterlaufen, bis sie beendet werden. Ob man solche fortlaufenden Verfahren im engen Sinn als Algorithmen bezeichnet, hängt von der verwendeten Definition ab.
Effizienz ist eine zusätzliche Bewertung: Wie viel Zeit und Speicher benötigt ein Verfahren abhängig von der Eingabegröße? Ein schnelles Verfahren kann falsch sein, und ein korrektes Verfahren kann langsam sein. Deshalb prüfst du Korrektheit, Terminierung und Ressourcenbedarf getrennt.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Eigenschaften von Algorithmen
- Beschreibung
- statische Finitheit
- Eindeutigkeit
- Ausführung
- Ausführbarkeit
- dynamische Finitheit
- Terminierung
- Weg und Ergebnis
- Determinismus betrifft den nächsten Schritt
- Determiniertheit betrifft die Ausgabe
- Geltungsbereich
- Allgemeinheit für eine Problemklasse
- Beschreibung
Prüfe eine Verarbeitungsvorschrift in dieser Reihenfolge: Sind die Eingaben und die gewünschte Ausgabe klar? Kann der vorgesehene Ausführende jeden Schritt umsetzen? Ist die Fortsetzung eindeutig? Ist die Beschreibung endlich? Endet das Verfahren im verlangten Geltungsbereich? Liefert es das richtige Ergebnis? Erst danach vergleichst du bei Bedarf Zeit- und Speicherbedarf.