Eigenschaften von Algorithmen und Pseudocode
Lena backt mit ihrer Oma Waffeln für das Schützenfest in Neuss. Auf dem Rezept steht: „Rühre den Teig, bis er gut ist, und backe ihn dann eine Weile.“ Kann man danach wirklich immer dasselbe Ergebnis erwarten? Und ein Computer? Der könnte mit „gut“ und „eine Weile“ gar nichts anfangen. Warum nicht, und wie schreibt man Vorschriften so auf, dass eine Maschine sie ausführen kann? Das klären wir in diesem Abschnitt.
Was ist ein Algorithmus?
Ein Algorithmus ist eine Handlungsvorschrift zur Lösung eines Problems. Damit ein Computer sie ausführen kann, muss sie bestimmte Eigenschaften haben.
Zur Unterscheidung: Die Endlichkeit betrifft den Text der Vorschrift. Die Terminierung betrifft die Ausführung. Ein kurzer Text kann eine Ausführung haben, die nie endet.
Nenne die algorithmischen Eigenschaften Endlichkeit, Eindeutigkeit und Terminierung und erkläre jede in einem Satz.
Nenne die algorithmischen Eigenschaften Endlichkeit, Eindeutigkeit und Terminierung und erkläre jede in einem Satz.
Eine Handlungsvorschrift lautet: „Rühre den Teig, bis er gut ist, und backe ihn dann eine Weile.“ a) Welche Eigenschaft eines Algorithmus ist verletzt? b) Formuliere die…
Eine Handlungsvorschrift lautet: „Rühre den Teig, bis er gut ist, und backe ihn dann eine Weile.“
- a) Welche Eigenschaft eines Algorithmus ist verletzt?
- b) Formuliere die Vorschrift so um, dass sie eindeutig ist.
Pseudocode lesen und schreiben
Pseudocode ist eine Beschreibung in Umgangssprache, die sich an Programmiersprachen anlehnt. Man schreibt Algorithmen damit auf, ohne an die Syntax einer bestimmten Sprache gebunden zu sein. Wir verwenden diese Bausteine:
| Baustein | Pseudocode |
|---|---|
| Eingabe | lies n |
| Ausgabe | gib zahl aus |
| Zuweisung | setze x auf x + 1 |
| Verzweigung | wenn x > 5: … sonst: … |
| Schleife mit Bedingung | solange x > 0: … |
| Rest der Division | a mod b |
Was eingerückt ist, gehört zur Schleife oder zur Verzweigung.
Eine Variable ist wie ein beschrifteter Behälter: setze zahl auf zahl - 2 heißt „nimm den alten Wert von zahl, ziehe 2 ab und speichere das Ergebnis wieder in zahl“. Es ist keine Gleichung.
Um zu verstehen, was ein Algorithmus tut, führt man ihn von Hand aus und notiert die Werte in einer Wertetabelle (auch Trace-Tabelle oder Schreibtischtest).
Gegeben ist der Pseudocode: a) Welche Zahlen werden ausgegeben? b) Terminiert der Algorithmus? Begründe.
Gegeben ist der Pseudocode:
setze zahl auf 10
solange zahl > 0:
gib zahl aus
setze zahl auf zahl - 2
- a) Welche Zahlen werden ausgegeben?
- b) Terminiert der Algorithmus? Begründe.
Schreibe in Pseudocode einen Algorithmus, der eine Zahl n einliest und die Summe aller Zahlen von 1 bis n ausgibt. Berechne die Ausgabe für n = 6 und begründe, dass der…
Schreibe in Pseudocode einen Algorithmus, der eine Zahl n einliest und die Summe aller Zahlen von 1 bis n ausgibt. Berechne die Ausgabe für n = 6 und begründe, dass der Algorithmus endlich ist.
Terminierung begründen
Eine solange-Schleife terminiert, wenn sich ihre Bedingung irgendwann sicher ändert. Drei Fragen helfen dir bei der Begründung:
-
Welche Größe ändert sich in jedem Durchlauf (zum Beispiel
zahlwird um 2 kleiner)? -
Verändert sie sich immer in dieselbe Richtung?
-
Erreicht oder überschreitet sie sicher den Wert, bei dem die Bedingung falsch wird?
Auch Alltagsvorschriften können das Problem haben, etwa am Geldautomaten.
Gegeben ist der Pseudocode: a) Verfolge die Werte von zahl in einer Tabelle für die ersten fünf Schritte. b) Terminiert der Algorithmus? Begründe. c) Ändere die…
Gegeben ist der Pseudocode:
setze zahl auf 7
solange zahl ungleich 0:
setze zahl auf zahl - 2
- a) Verfolge die Werte von zahl in einer Tabelle für die ersten fünf Schritte.
- b) Terminiert der Algorithmus? Begründe.
- c) Ändere die Bedingung so, dass er für jeden positiven Startwert terminiert.
Eine Anweisung für einen Bankautomaten lautet: „Wiederhole die PIN-Eingabe, bis sie richtig ist.“ a) Warum ist die Terminierung nicht garantiert? b) Ergänze eine Regel,…
Eine Anweisung für einen Bankautomaten lautet: „Wiederhole die PIN-Eingabe, bis sie richtig ist.“
- a) Warum ist die Terminierung nicht garantiert?
- b) Ergänze eine Regel, die Terminierung sicherstellt, und formuliere sie in Pseudocode.
Algorithmen entwerfen und prüfen
Zum Entwerfen eines Algorithmus gehören drei Schritte: Idee überlegen, in Pseudocode aufschreiben, mit einer Wertetabelle an einem Beispiel prüfen. Danach begründest du die drei Eigenschaften.
Ein berühmtes Beispiel ist der euklidische Algorithmus. Er bestimmt den größten gemeinsamen Teiler zweier Zahlen.
Gegeben ist: a) Führe den Algorithmus für a = 48 und b = 18 aus und gib alle Zwischenwerte an. b) Welche Aufgabe löst der Algorithmus? c) Begründe, warum er für…
Gegeben ist:
lies a
lies b
solange b ungleich 0:
setze r auf a mod b
setze a auf b
setze b auf r
gib a aus
- a) Führe den Algorithmus für a = 48 und b = 18 aus und gib alle Zwischenwerte an.
- b) Welche Aufgabe löst der Algorithmus?
- c) Begründe, warum er für natürliche Zahlen terminiert.
Entwirf in Pseudocode einen Algorithmus, der in einer Liste von n Zahlen das Maximum bestimmt. a) Schreibe den Algorithmus auf. b) Prüfe ihn an der Liste (4, 9, 2, 9, 5)…
Entwirf in Pseudocode einen Algorithmus, der in einer Liste von n Zahlen das Maximum bestimmt.
- a) Schreibe den Algorithmus auf.
- b) Prüfe ihn an der Liste (4, 9, 2, 9, 5) mit Wertetabelle.
- c) Begründe Eindeutigkeit, Endlichkeit und Terminierung für deinen Algorithmus.
Muss ein Algorithmus immer enden?
Klassisch gilt: Ein Algorithmus terminiert. Manche Programme sind aber absichtlich endlos, zum Beispiel ein Betriebssystem oder die loop()-Funktion eines Arduino. Sie warten ständig auf neue Eingaben.
setze x auf 1
solange wahr:
setze x auf x * 2
Der Text ist endlich und eindeutig, aber die Ausführung hält nie an. Wer streng nach der Definition urteilt, sagt: Das ist kein Algorithmus im engeren Sinn. Bei Steuerungen und Betriebssystemen betrachtet man stattdessen jeden einzelnen Durchlauf, und der terminiert.
Ein Kollege behauptet: „Der folgende Algorithmus ist ein gültiger Algorithmus, obwohl er nie hält.“ a) Erkläre, welche Eigenschaften ein Algorithmus nach der Definition…
Ein Kollege behauptet: „Der folgende Algorithmus ist ein gültiger Algorithmus, obwohl er nie hält.“
setze x auf 1
solange wahr:
setze x auf x * 2
- a) Erkläre, welche Eigenschaften ein Algorithmus nach der Definition erfüllen muss.
- b) Beurteile die Behauptung. Gibt es Algorithmen, bei denen Nichtterminierung beabsichtigt ist (z. B. ein Betriebssystem)?
- c) Wie unterscheidet man dann Endlichkeit der Beschreibung und Terminierung der Ausführung?
Zurück zum Anfang: Lenas Rezept war unbrauchbar, weil „gut“ und „eine Weile“ nicht eindeutig sind. Mit festen Zeiten und Temperaturen wird es zu einem Algorithmus.