Eigenschaften von Algorithmen einfach erklärt
Du lernst, Schrittregeln zu prüfen: Sind sie machbar und klar? Stehen der Weg und das Ergebnis fest? Hören sie auf?
Kurz gesagt
Du prüfst, ob eine Schrittregel machbar und klar ist und ob sie endet. Auch ihr Text und ihr Platz zum Merken zählen dazu. Beim Wort Algorithmus fordern manche Erklärungen ein Ende des Ablaufs, andere nicht.
Ein Algorithmus ist eine Regel, die dir Schritte vorgibt. Eigenschaften sind Merkmale, an denen du diese Regel prüfst. Für unsere ausgedachten Aufgaben nutzen wir einen gedachten Helfer. Er kann sehen, zählen und Dinge umlegen und wird nicht müde.
Deine Lernziele
Ein Rezept gibt Schritte vor. Auch daran kannst du Eigenschaften prüfen.
Finitheit bedeutet Endlichkeit. Der Regeltext muss ein Ende haben. Dazu kommt der Speicherplatz: Das ist der Platz für alles, was sich der Helfer merkt. Zu jeder Zeit darf er nur endlich viel davon brauchen. Endlich heißt: Die Menge lässt sich zu Ende zählen. Der Speicherbedarf darf beim Weiterarbeiten wachsen.
Ausführbarkeit heißt: Der Helfer kann den geforderten Schritt tatsächlich machen. Dafür müssen auch die nötigen Dinge da sein.
Die Wirkung ist das, was ein Schritt verändert. Effektivität heißt hier: Diese Wirkung ist klar festgelegt. Das Wort meint hier nicht, dass der Helfer schnell arbeitet.
Terminierung heißt: Die Regel hält nach endlich vielen Schritten an. Das muss bei jedem erlaubten Start gelten. Der Start ist das, was vor dem ersten Schritt da ist und gilt.
Das Wort Algorithmus wird verschieden gebraucht. Manche Erklärungen verlangen, dass ein Algorithmus anhält. Andere nennen auch Regeln ohne Ende so. Darum prüfen wir das Anhalten extra.
Ausführbarkeit
Ein Schritt ist ausführbar, wenn der Helfer ihn mit seinen Fähigkeiten und den vorhandenen Dingen machen kann.
Beispiel: Ausgedachtes Rezept für einen Rosinenteller
- 1Vor dem Helfer liegen eine Rosine und ein leerer Teller.
- 2Die Regel lautet: Lege die Rosine auf den Teller. Halte an.
- 3Der Helfer kann beide Schritte machen. Das Ablegen bringt die Rosine auf den Teller.
- 4Der Text ist kurz. Der Helfer muss sich nur wenig merken. Nach dem Ablegen hält er an.
Merke: Machbar, klar und schnell sind verschiedene Dinge. Eine klar beschriebene Handlung kann zum Beispiel scheitern, weil etwas fehlt.
Teste dich
Wir betrachten hier Regeln, die anhalten. Das Ergebnis ist das, was am Ende herauskommt. Bei den Klötzen unten zählt: Welcher Klotz liegt auf welchem Feld?
Gleicher Start heißt: Am Anfang ist alles wieder gleich. Dieselben Dinge sind da. Sie liegen an denselben Stellen. Auch alles andere für den Anfang bleibt gleich.
Determinismus betrifft den nächsten Schritt. Die Regel legt ihn genau fest. Der Helfer darf nicht frei zwischen mehreren nächsten Schritten wählen. Eine solche Regel heißt deterministisch.
Determiniertheit betrifft das Ergebnis. Bei gleichem Start kommt dasselbe Ergebnis heraus. Eine solche Regel heißt determiniert.
Bei den Klötzen darf der Helfer die Reihenfolge wählen. Er kann mit Rot oder mit Blau anfangen. Am Ende liegt trotzdem jeder Klotz auf seinem Farbfeld. Das Ergebnis bleibt gleich.
Ein fester Weg führt bei gleichem Start zum gleichen Ergebnis. Aber auch zwei verschiedene Wege können gleich enden. Dann ist das Ergebnis fest, obwohl der nächste Schritt frei sein kann.
Auch bei freier Wahl kann jeder einzelne Schritt eine klare Wirkung haben. Lege den roten Klotz auf das rote Feld: Dieser Schritt ist klar. Offen bleibt, ob er zuerst kommt.
Beispiel: Zwei Klötze auf ihre Farbfelder legen
- 1Ein roter und ein blauer Klotz liegen neben zwei leeren Feldern: einem roten und einem blauen.
- 2Die Regel lautet: Lege jeden Klotz auf das Feld seiner Farbe. Du darfst wählen, welcher zuerst kommt. Halte danach an.
- 3Erster Weg: Lege zuerst Rot auf Rot. Lege dann Blau auf Blau.
- 4Zweiter Weg: Lege zuerst Blau auf Blau. Lege dann Rot auf Rot.
- 5Vor jedem neuen Versuch legst du die Klötze zurück neben die leeren Felder. So bleibt der Start gleich.
- 6Beide Wege enden gleich: Rot liegt auf Rot, Blau auf Blau. Die Regel ist determiniert.
- 7Der erste Klotz ist frei gewählt. Die Regel ist nicht deterministisch.
Merke: Determinismus: Der nächste Schritt steht fest. Determiniertheit: Bei gleichem Start steht das Ergebnis fest.
Teste dich
Der Regeltext beschreibt die Schritte. Der Ablauf ist das, was der Helfer danach tut. Text und Ablauf sind zwei verschiedene Dinge.
Finitheit der Beschreibung heißt: Der Text hat eine endliche Länge. Du kannst ihn zu Ende lesen. Trotzdem kann er sagen: Wiederhole diesen Schritt ohne Ende. Dann endet der Text, aber der Ablauf geht weiter.
Speicher ist der Platz zum Merken. Unser Helfer nutzt gedachten Speicher. Bei Bedarf darf neuer Platz dazukommen. So denken wir uns das für dieses Beispiel. Ein echtes Blatt Papier hat dagegen begrenzten Platz.
Dynamische Finitheit heißt: Zu jeder Zeit braucht der Helfer nur endlich viel Speicher. Beim Punktebeispiel unten kannst du die Punkte nach jedem Schritt zu Ende zählen. Der Platz darf trotzdem weiterwachsen. Es muss keine feste größte Zahl von Punkten geben.
Terminierung fragt nach dem Anhalten. Die Regel muss bei jedem erlaubten Start nach endlich vielen Schritten anhalten. Sind zwei Starts erlaubt, muss sie bei beiden anhalten.
Stell dir zwei erlaubte Starts vor: eine rote Karte oder eine blaue Karte. Bei Rot hält die Regel an. Bei Blau läuft sie ohne Ende weiter. Dann ist die Regel nicht terminierend. Das Ende bei Rot reicht nicht.
Eine Regel kann unterwegs etwas zeigen oder sagen und trotzdem weiterlaufen. Etwas zu zeigen bedeutet noch nicht, dass die Regel anhält.
Beispiel: Punkte im gedachten Speicher sammeln
- 1Am Anfang merkt sich der Helfer keinen Punkt. Sein gedachter Speicher darf neuen Platz bekommen.
- 2Die Regel lautet: Merke dir einen weiteren Punkt. Wiederhole diesen Schritt ohne Ende.
- 3Nach einem Schritt merkt er sich einen Punkt.
- 4Nach zwei Schritten sind es zwei Punkte. Nach drei Schritten sind es drei.
- 5Nach jedem Schritt kommt ein Punkt dazu. Die Menge bleibt zu jeder Zeit endlich, wächst aber weiter.
- 6Der Text hat ein Ende. Der Ablauf hält nicht an.
Merke: Prüfe getrennt: Endet der Text? Ist der nötige Platz zu jeder Zeit endlich? Hält der Ablauf bei jedem erlaubten Start an?
Teste dich
Eine Handlungsvorschrift ist eine Anleitung zum Handeln. Ein Rezept ist so eine Anleitung. Eindeutig heißt: Es ist klar festgelegt, was gemeint ist.
Suche zuerst die Stelle, an der du zwischen mehreren nächsten Schritten wählen darfst. Wenn ein Rezept zwei Zutaten anbietet und keine Wahl festlegt, bleibt der nächste Schritt offen.
Schreibe dann genau auf, welche Sache du nehmen sollst, wie viel davon und wohin sie kommt. Die neue Anweisung muss zum gewünschten Ergebnis passen.
Du kannst auch festlegen, wann welcher Schritt gilt. Für unser Beispiel darf eine Schale leer sein oder eine Nuss enthalten. Die Regel lautet: Ist die Schale leer, lege eine Nuss hinein. Liegt schon eine Nuss darin, halte an. So legt der Inhalt der Schale den nächsten Schritt fest.
Prüfe danach zwei Fragen getrennt: Ist der nächste Schritt festgelegt? Ist klar, was dieser Schritt bewirkt?
Beispiel: Ein ausgedachtes Rezept für ein belegtes Brot
- 1Bereit liegen eine Scheibe Brot, ein Stück Käse und eine Scheibe Gurke.
- 2Die Anweisung lautet: Lege den Käse oder die Gurke auf das Brot.
- 3Offen bleibt, welchen Belag der Helfer nehmen soll.
- 4Gewünscht ist Brot mit Käse. Die passende Anweisung lautet: Lege das Stück Käse auf die Scheibe Brot.
- 5Jetzt sind die gewählte Zutat und ihr Platz festgelegt.
Merke: Eine freie Wahl verschwindet, wenn die Anleitung den nächsten Schritt passend zum gewünschten Ergebnis festlegt.
Teste dich
Alles auf einen Blick
Eigenschaften von Algorithmen
Der Text hat ein Ende. Der nötige Platz zum Merken ist zu jeder Zeit endlich. Er darf weiterwachsen.
Der Helfer kann den Schritt machen. Die nötigen Dinge sind da.
Es steht klar fest, was der Schritt bewirkt. Das sagt nichts über sein Tempo.
Der Ablauf hält bei jedem erlaubten Start nach endlich vielen Schritten an.
Der nächste Schritt steht fest. Eine genaue Anweisung kann eine freie Wahl aufheben.
Bei gleichem Start kommt dasselbe Ergebnis heraus. Wir betrachten hier Regeln, die anhalten. Verschiedene Wege sind möglich.
Ein ausgedachtes Rezept mit Papierkreisen prüfen
- 1Erlaubt ist dieser Start: Ein großer und ein kleiner Papierkreis liegen neben einer leeren Schachtel.
- 2Der Helfer kann beide Kreise hineinlegen.
- 3Die Regel lautet: Lege den großen Kreis in die Schachtel. Lege danach den kleinen Kreis hinein. Halte an.
- 4Ausführbarkeit: Beide Kreise sind da. Der Helfer kann die geforderten Schritte machen.
- 5Effektivität: Jeder Legeschritt bringt den genannten Kreis in die Schachtel. Seine Wirkung ist klar.
- 6Finitheit: Der Text hat ein Ende. Der Helfer muss sich nur merken, welcher Schritt folgt.
- 7Terminierung: Nach den beiden Legeschritten hält der Helfer an. Damit endet die Regel beim erlaubten Start.
- 8Am Ende liegen beide Kreise in der Schachtel.
Fehler finden
Fehler in Zeile 3Die falsche Zeile verwechselt einen kurzen Text mit einem endenden Ablauf. Richtig: Der kurze Regeltext beschreibt einen Ablauf, der nicht anhält. Nach jedem Läuten beginnt der Helfer wieder von vorn.
Lückentext
Auf dem Tisch liegt kein Papier. Der Helfer soll ein Blatt vom Tisch nehmen. Dieser Schritt ist . Die ganze nächste Regel lautet: Winke und fange wieder von vorn an. Damit ist ihr Regeltext . Bei einer weiteren Regel darfst du zuerst das Herz oder zuerst den Mond in die Schachtel legen. Der nächste Schritt ist damit .