Vom Problem zum Algorithmus

Zusammenfassung

Diese Lektion enthält keinen Code, und das nicht aus Versehen: Der Algorithmus geht dem Programm voraus, und wer nicht genau beschreiben kann, was zu tun ist, wird es auch in C++ nicht sagen können. Zuerst lernt man, ein Problem zu spezifizieren, das heißt festzulegen, welche Daten es erhält, welches Ergebnis es liefern muss und welche Beziehung beide verbindet, und es wird gezeigt, dass ein und dieselbe Aufgabenstellung verschiedene Spezifikationen zulässt. Danach wird der Algorithmus als endliches, eindeutiges und allgemeines Verfahren definiert, und der Algorithmus der Division durch fortgesetzte Subtraktion wird in nummerierten Schritten aufgeschrieben. Man lernt, einen Algorithmus mit einer Ablauftabelle von Hand nachzuvollziehen; sie wird im ganzen Kurs das erste Werkzeug sein, um zu verstehen und um zu debuggen. Vorgestellt werden die drei Arten, Schritte zu kombinieren (Sequenz, Entscheidung und Wiederholung), mit denen sich jeder Algorithmus schreiben lässt, und man lernt zu begründen, dass eine Wiederholung terminiert, und zwar mit einer Größe, die in jedem Durchlauf fällt und nicht unbegrenzt sinken kann.

Lernziele

Ein einfaches Problem spezifizieren, indem man seine Eingaben, seine Ausgaben und die Bedingungen angibt, die sie erfüllen müssen.
Einen Algorithmus in nummerierten Schritten beschreiben, ohne Mehrdeutigkeit, mit ausdrücklichen Entscheidungen und Wiederholungen.
Einen Algorithmus mit einer Ablauftabelle von Hand nachvollziehen und sein Ergebnis für eine gegebene Eingabe bestimmen.
In einem gegebenen Verfahren Sequenz, Entscheidung und Wiederholung unterscheiden und begründen, dass eine Wiederholung terminiert.

Was ein Berechnungsproblem ist

Ein Berechnungsproblem ist eine Beziehung zwischen zwei Arten von Daten: denen, die man erhält und die Eingabe heißen, und denen, die geliefert werden müssen und die Ausgabe heißen. Es zu lösen bedeutet nicht, eine Antwort für einen Fall zu finden, sondern über ein Verfahren zu verfügen, das für jede zulässige Eingabe eine Ausgabe erzeugt, die die Beziehung erfüllt. „Wie viel ist 17 geteilt durch 5?“ ist eine Frage; „zu zwei ganzen Zahlen ihren Quotienten und ihren Rest bestimmen“ ist ein Problem, weil es von allen Paaren ganzer Zahlen zugleich spricht.

Nun ist die Umgangssprache ungenau, und dieselbe Aufgabenstellung kann auf mehrere Weisen verstanden werden. Deshalb wird vor dem Lösen spezifiziert: Man schreibt auf, was hineingeht, was herauskommt und welche Bedingungen jedes davon erfüllen muss. Die Spezifikation hat drei Teile. Die Eingabe zählt die Daten mit ihrer Art auf (ganze Zahlen, Dezimalzahlen, Wörter) und die Bedingungen, die an sie gestellt werden und die Vorbedingung heißen: Wer die Lösung benutzt, verpflichtet sich, sie einzuhalten. Die Ausgabe zählt die Ergebnisse auf. Die Beziehung, oder Nachbedingung, sagt, was die Ausgabe im Verhältnis zur Eingabe erfüllen muss: Wer die Lösung schreibt, verpflichtet sich, sie zu garantieren, sofern die Vorbedingung eingehalten wurde. Daraus folgt, dass die Spezifikation ein Vertrag zwischen dem ist, der das Problem stellt, und dem, der es löst, und dass die Lösung außerhalb der Vorbedingung nichts verspricht.

BeispielDas Maximum von drei Zahlen

Umgangssprachliche Aufgabenstellung: „die größte von drei Zahlen finden“. Spezifikation:

Eingabe: drei Zahlen $x$ , $y$ , $z$ (ganze Zahlen oder Dezimalzahlen, ohne weitere Bedingung).
Ausgabe: eine Zahl $m$ .
Beziehung: $m$ ist einer der drei Werte, und keiner von ihnen ist größer als $m$ ; das heißt $m \geq x$ , $m \geq y$ und $m \geq z$ .

Die Beziehung sagt nicht „die größte der drei“, denn genau das sollte ja präzisiert werden, sondern nennt zwei überprüfbare Bedingungen. Die erste verlangt, dass $m$ einer der gegebenen Werte ist (ohne sie würde die Zahl 1000 die zweite für fast jede Eingabe erfüllen); die zweite, dass keiner ihn übertrifft. Und die Spezifikation klärt nebenbei eine Frage, die die Aufgabenstellung offenließ: Wenn zwei Werte beim Maximum gleichauf liegen, wie in $(4, 9, 9)$ , ist die Ausgabe $9$ , und darin liegt kein Fehler.

Ein und dieselbe Aufgabenstellung lässt verschiedene Spezifikationen zu, und zwischen ihnen zu wählen ist eine Entscheidung, kein Versehen. Der lehrreichste Fall ist die ganzzahlige Division. Für ganze Zahlen $a \geq 0$ und $b > 0$ sind sich alle einig: Der Quotient $q$ und der Rest $r$ sind die einzigen ganzen Zahlen mit

a = b \cdot q + r, \quad 0 \leq r < b

So sind es für $a = 17$ und $b = 5$ die Werte $q = 3$ und $r = 2$ , denn $17 = 5 \cdot 3 + 2$ . Aber die Aufgabenstellung „zwei ganze Zahlen dividieren“ sagt nicht, was zu tun ist, wenn $a$ negativ ist, und die Frage ist nicht müßig: Für $a = -7$ und $b = 2$ gibt es zwei vernünftige Antworten.

BeispielZwei Spezifikationen der Division mit negativem Dividenden

Erste Spezifikation: Der Rest ist nie negativ, $0 \leq r < b$ . Dann gilt $-7 = 2 \cdot (-4) + 1$ , und die Ausgabe ist $q = -4$ , $r = 1$ . Diese wird in der Mathematik behandelt, in der Lektion „Teilbarkeit und Division mit Rest“ des Kurses Algebra und Geometrie I.

Zweite Spezifikation: Der Quotient ist das Ergebnis der Division mit Dezimalstellen, deren Nachkommateil verworfen wird, also zur Null hin gerundet; der Rest ist das, was fehlt, und hat das Vorzeichen des Dividenden. Dann wird $-7 / 2 = -3{,}5$ auf $-3$ abgeschnitten, und es gilt $-7 = 2 \cdot (-3) + (-1)$ : Die Ausgabe ist $q = -3$ , $r = -1$ .

Beide erfüllen $a = b \cdot q + r$ ; sie unterscheiden sich in der Bedingung, die dem Rest auferlegt wird. Keine ist ein Fehler, aber ein Programm, das die eine benutzt und glaubt, die andere zu benutzen, liefert bei negativen Zahlen falsche Ergebnisse. Vorweggenommen sei eine Tatsache: C++ übernimmt die zweite, wie die Lektion Arithmetik zeigen wird; wer die erste erwartet, wird eine Überraschung erleben.

Es gibt eine dritte Möglichkeit, die in der Praxis häufigste: den Fall durch die Vorbedingung auszuschließen. Verlangt die Spezifikation $a \geq 0$ , so verschwindet das Problem der negativen Zahlen, nicht weil es gelöst wäre, sondern weil, wer die Lösung benutzt, sich verpflichtet hat, es nicht zu stellen. Was man nicht tun darf, ist, die Frage unentschieden zu lassen. Und aus demselben Grund verlangt die Spezifikation $b > 0$ : Mit $b = 0$ gibt es keine $q$ und $r$ , die die Beziehung erfüllen, und der Vertrag muss das sagen.

Ein häufiger Fehler besteht darin, mit einem Beispiel zu spezifizieren: „die Ausgabe zu 17 und 5 ist 3 und 2“. Ein Beispiel veranschaulicht, aber es spezifiziert nicht, weil es nicht sagt, was mit den anderen Eingaben geschieht; unendlich viele verschiedene Beziehungen stimmen in einem Fall überein. Die Spezifikation wird als allgemeine Bedingung geschrieben, und die Beispiele dienen danach dazu, sie zu überprüfen.

Algorithmen

Ist das Problem spezifiziert, sucht man ein Verfahren, um es zu lösen. Ein Algorithmus ist eine Folge von Anweisungen, die, angewandt auf jede Eingabe, die die Vorbedingung erfüllt, in endlich vielen Schritten eine Ausgabe erzeugt, die die Nachbedingung erfüllt. Die Definition enthält drei Forderungen.

Endlichkeit. Der Algorithmus wird mit endlich vielen Anweisungen geschrieben und terminiert für jede zulässige Eingabe, nachdem er endlich viele davon ausgeführt hat. Ein Verfahren, das für irgendeine Eingabe endlos weiterläuft, ist für diese Eingabe kein Algorithmus.
Eindeutigkeit. Jede Anweisung hat eine einzige Bedeutung, und wer sie ausführt, weiß jederzeit, was zu tun ist und welche Anweisung als Nächstes kommt. Keine Entscheidung bleibt dem Ermessen dessen überlassen, der ausführt.
Allgemeinheit. Der Algorithmus löst das Problem für alle zulässigen Eingaben, nicht nur für einen Fall.

Mit einer gewissen Freiheit nennt man auch ein Verfahren einen Algorithmus, das eindeutig ist und terminiert, aber für irgendeine zulässige Eingabe die Nachbedingung nicht erfüllt: Streng genommen ist es ein Algorithmus für ein anderes Problem, und man wird sagen, dass es für das spezifizierte Problem inkorrekt ist. So sprechen die Aufgaben dieser Lektion, die inkorrekte Algorithmen mit einem Gegenbeispiel widerlegen.

Ein Kochrezept ähnelt einem Algorithmus, und deshalb ist es der übliche Vergleich; aber fast keines ist einer. „Eine Prise Salz hinzufügen“ ist nicht eindeutig, weil eine Prise keine Menge ist; „backen, bis es goldbraun ist“ hängt von einem Urteil ab, das zwei Menschen verschieden fällen würden; „mehrmals schlagen“ sagt nicht, wie oft. Ein Koch füllt diese Lücken mit Erfahrung; ein Computer hat keine. Daraus folgt die Forderung, die den ganzen Kurs bestimmt: Einem Algorithmus muss auch folgen können, wer das Problem nicht versteht, ohne etwas zu erraten. Wenn man wissen muss, wozu ein Schritt dient, um ihn auszuführen, ist der Schritt schlecht geschrieben.

Die Algorithmen dieses Kurses werden zuerst in nummerierten Schritten geschrieben, auf Deutsch, mit einigen Konventionen. Die Daten, die sich während des Algorithmus ändern, werden mit Buchstaben oder Wörtern benannt, etwa $q$ oder $r$ , und heißen Variablen. Man schreibt „ $r$ erhält den Wert $r - b$ “, um zu sagen, dass $r - b$ mit dem aktuellen Wert von $r$ berechnet wird und das Ergebnis zum neuen Wert von $r$ wird; der vorige Wert geht verloren. In der Kurzform, die man beim Notieren verwendet, schreibt man dieselbe Anweisung mit einem Pfeil nach links, der auf der Tastatur r <- r - b lautet. Die Anweisungen werden in der Reihenfolge ihrer Nummern ausgeführt, sofern nicht eine von ihnen etwas anderes sagt.

BeispielDie Division durch fortgesetzte Subtraktion

Das Problem ist das oben spezifizierte: Eingabe, zwei ganze Zahlen $a \geq 0$ und $b > 0$ ; Ausgabe, zwei ganze Zahlen $q$ und $r$ mit $a = b \cdot q + r$ und $0 \leq r < b$ . Die Idee ist die des Verteilens: Von $a$ nimmt man Gruppen zu $b$ weg, solange es geht, zählt die weggenommenen Gruppen, und was übrig bleibt, ist der Rest.

$q$ erhält den Wert $0$ , und $r$ erhält den Wert $a$ .
Solange $r \geq b$ gilt, wiederhole die Schritte 3 und 4; sobald es nicht mehr gilt, fahre mit Schritt 5 fort.
$r$ erhält den Wert $r - b$ .
$q$ erhält den Wert $q + 1$ ; kehre zu Schritt 2 zurück.
Liefere $q$ und $r$ und beende den Algorithmus.

Schritt 2 ist eine Frage, die jedes Mal gestellt wird: vor dem ersten Durchlauf und nach jedem weiteren. Die Schritte 3 und 4 bilden den Rumpf der Wiederholung, das, was wiederholt wird. Nichts bleibt dem Ermessen dessen überlassen, der ausführt: In jedem Moment gibt es eine einzige nächste Anweisung.

Der Algorithmus ist langsam (um eine Million durch drei zu teilen, braucht er mehr als dreihunderttausend Durchläufe), und das Schulverfahren der Division ist viel schneller; aber er ist korrekt, und seine Einfachheit macht ihn ideal, um das Nachdenken über Algorithmen zu lernen. Auf den Unterschied zwischen einem korrekten und einem effizienten Algorithmus kommt der Kurs in der Lektion Die Kosten eines Algorithmus zurück.

Schließlich empfiehlt es sich, den Algorithmus von seiner Niederschrift zu trennen. Der Algorithmus der Division durch Subtraktion ist derselbe, ob man ihn auf Deutsch, in einem Diagramm, in C++ oder in irgendeiner anderen Programmiersprache aufschreibt: Was ihn bestimmt, ist die Folge der Operationen, nicht die Wörter. Ein Programm ist die Niederschrift eines Algorithmus in einer Sprache, die eine Maschine ausführen kann, und die Lektion Programme, Compiler und C++ wird erklären, wie diese Ausführung geschieht. Wenn das so ist, kann ein Programm auf zwei sehr verschiedene Arten falsch sein: weil der Algorithmus inkorrekt ist, und dann rettet ihn keine Sprache, oder weil der Algorithmus korrekt ist, aber schlecht aufgeschrieben wurde. Beide Fälle zu unterscheiden ist die halbe Arbeit des Debuggens, und deshalb schreibt der Kurs immer zuerst den Algorithmus.

Einen Algorithmus von Hand nachvollziehen

Einen Algorithmus zu lesen genügt nicht, um zu wissen, was er tut; man muss ihn ausführen. Ihn von Hand nachzuvollziehen, wie es die Maschine täte, ohne Schritte zu überspringen oder Ergebnisse zu erraten, ist die nützlichste Fähigkeit eines Programmierers: Mit ihr prüft man einen Algorithmus, bevor man ihn schreibt, sagt die Ausgabe eines Programms voraus, bevor man es ausführt, und findet den Fehler in einem, das versagt.

Das Werkzeug ist die Ablauftabelle (Trace-Tabelle): eine Spalte für die Nummer des ausgeführten Schritts, eine Spalte je Variable und, falls nützlich, eine für die ausgewerteten Bedingungen; und eine Zeile für jeden ausgeführten Schritt. In jede Zeile trägt man den neuen Wert der Variable ein, die sich in diesem Schritt geändert hat, und lässt leer, was sich nicht geändert hat, sodass der aktuelle Wert einer Variable der letzte in ihrer Spalte eingetragene ist. Bedingungen werden mit ihrem Ergebnis eingetragen.

BeispielDie Ablaufverfolgung der Division von 17 durch 5

Wir verfolgen die Division durch fortgesetzte Subtraktion mit $a = 17$ und $b = 5$ . Der Pfeil der Figur zeigt auf den Schritt, der gerade ausgeführt wurde; die gepunktete Linie erinnert daran, dass Schritt 4 zu Schritt 2 zurückkehrt.

Beweis

$(q, r) = (0, 17)$
Schritt 1: Die Anfangswerte werden gesetzt. Die Eingabe erfüllt die Vorbedingung, denn es gilt $17 \geq 0$ und $5 > 0$ .
$(q, r) = (1, 12)$
Erster Durchlauf. In Schritt 2 wird geprüft, dass $17 \geq 5$ gilt, also wird der Rumpf ausgeführt: Schritt 3 nimmt eine Gruppe von fünf weg, und Schritt 4 zählt sie.
$(q, r) = (2, 7)$
Zweiter Durchlauf: $12 \geq 5$ , und der Rumpf wird erneut ausgeführt.
$(q, r) = (3, 2)$
Dritter Durchlauf: $7 \geq 5$ , und der Rumpf wird erneut ausgeführt.
$17 = 5 \cdot 3 + 2, \quad 0 \leq 2 < 5$
In Schritt 2 schlägt die Bedingung fehl, weil $2 < 5$ gilt: Der Algorithmus fährt mit Schritt 5 fort und liefert $q = 3$ und $r = 2$ . Die Ausgabe erfüllt die Nachbedingung.

Die vollständige Tabelle hat zwölf Zeilen: Schritt 1, drei Durchläufe zu je drei Zeilen (Schritte 2, 3 und 4), die fehlschlagende Prüfung und die Rückgabe.

Zwei Beobachtungen zur Tabelle. Erstens: Die Zahl der Durchläufe ist gleich dem Quotienten, $3$ , und Schritt 2 wurde einmal öfter ausgeführt als der Rumpf, nämlich $4$ -mal; das geschieht bei einer Wiederholung dieser Form immer, weil die letzte Prüfung diejenige ist, die fehlschlägt. Zweitens: Die Ablaufverfolgung zeigt etwas, das der Text des Algorithmus auf den ersten Blick nicht sagt; gilt $a < b$ , zum Beispiel $a = 3$ und $b = 5$ , so schlägt die Bedingung gleich beim ersten Mal fehl, der Rumpf wird kein einziges Mal ausgeführt, und die Ausgabe ist $q = 0$ , $r = 3$ , was korrekt ist, denn $3 = 5 \cdot 0 + 3$ . Den Fall zu vergessen, in dem die Wiederholung nicht ausgeführt wird, ist einer der häufigsten Fehler beim Entwurf von Algorithmen, und die Ablaufverfolgung mit kleinen Eingaben deckt ihn auf.

Die Ablaufverfolgung eines Falls beweist nicht, dass der Algorithmus korrekt ist: Sie prüft einen Fall. Aber eine gut gewählte Ablaufverfolgung (ein gewöhnlicher Fall, ein Grenzfall, der Fall, in dem die Wiederholung nicht ausgeführt wird) deckt die meisten Fehler auf, und die, die fehlschlägt, zeigt, wo sie liegen. Die Lektion Korrekte Schleifen entwerfen wird lehren, von den Fällen zu einem Beweis überzugehen.

Sequenz, Entscheidung und Wiederholung

Aus der Nähe betrachtet, sind Algorithmen aus sehr wenigen Bausteinen gebaut. Es gibt elementare Anweisungen (einer Variable einen Wert geben, ein Ergebnis liefern) und drei Arten, sie zu kombinieren.

Sequenz: eine Anweisung nach der anderen, der Reihe nach. Die Schritte 3 und 4 der Division sind eine Sequenz: Zuerst wird subtrahiert, dann gezählt.
Entscheidung: Je nachdem, ob eine Bedingung erfüllt ist oder nicht, wird der eine oder der andere Teil ausgeführt (oder ein Teil oder nichts). „Wenn $y > m$ , erhält $m$ den Wert $y$ “ ist eine Entscheidung.
Wiederholung: Solange eine Bedingung erfüllt ist, wird ein Teil immer wieder ausgeführt. Schritt 2 der Division ist mit seinem Rumpf eine Wiederholung.

Jede Form hat einen einzigen Eingang und einen einzigen Ausgang, und ihr Inneres kann seinerseits jede der drei sein: Der Rumpf einer Wiederholung kann Entscheidungen enthalten, ein Zweig einer Entscheidung kann eine Wiederholung enthalten, und so fort. Wenn das so ist, baut man mit den drei Formen Algorithmen jeder Komplexität, so wie man mit wenigen Bausteinen, die ineinandergreifen, jedes Gebäude errichtet. Dass sie genügen, um jeden Algorithmus auszudrücken, ist ein bekanntes Ergebnis der Theorie der Programmierung (Corrado Böhm und Giuseppe Jacopini haben es 1966 bewiesen); hier wird es nicht bewiesen, aber der ganze Kurs bestätigt es: Die Programme, die in ihm geschrieben werden, wie lang sie auch sein mögen, verwenden nichts anderes als diese drei Formen, in C++ als if für die Entscheidung und while oder for für die Wiederholung geschrieben, in den Lektionen Entscheidungen und Schleifen.

Eine nützliche Notation, um die Gestalt eines Algorithmus zu sehen, ist das Flussdiagramm (der Programmablaufplan): Jede Anweisung ist ein Rechteck, jede Bedingung eine Raute mit zwei Ausgängen (erfüllt, von der Figur mit $1$ beschriftet, und nicht erfüllt, $0$ ), und die Pfeile sagen, welcher Schritt als Nächstes kommt. Es ist eine Notation, kein Selbstzweck: Sie dient dazu, einen kleinen Algorithmus auf einen Blick zu erfassen, aber sie skaliert nicht, und niemand schreibt ein großes Programm, indem er es zeichnet.

BeispielDrei Formen und ihre Zusammensetzung

Die Figur zeichnet die drei Formen mit allgemeinen Anweisungen $A$ und $B$ und einer Bedingung $c$ und setzt sie danach im Diagramm der Division durch fortgesetzte Subtraktion zusammen.

Beweis

$A ; B$
Sequenz: Es wird $A$ ausgeführt und danach $B$ ; es gibt einen einzigen Eingang und einen einzigen Ausgang.
$c = 1 \Rightarrow A, \quad c = 0 \Rightarrow B$
Entscheidung: Ist $c$ erfüllt, wird $A$ ausgeführt; wenn nicht, $B$ . Beide Zweige laufen in einem einzigen Ausgang zusammen.
$c, A, c, A, \ldots, c$
Wiederholung: Es wird $c$ ausgewertet; ist sie erfüllt, wird $A$ ausgeführt und erneut $c$ ausgewertet; wenn nicht, wird die Wiederholung verlassen. Die Bedingung wird einmal öfter ausgewertet als der Rumpf.
$a = b \cdot q + r, \quad 0 \leq r < b$
Zusammensetzung: Die Division durch fortgesetzte Subtraktion ist eine Sequenz (die Anfangswerte, die Wiederholung, die Rückgabe), deren Wiederholung als Rumpf eine weitere Sequenz hat (subtrahieren, zählen).

Die drei Formen in einem umgangssprachlich geschriebenen Verfahren zu erkennen ist der erste Schritt, um es zu übersetzen. Das Zeichen einer Entscheidung ist ein „wenn“, ein „falls“ oder ein „je nachdem“; das einer Wiederholung ein „solange“, ein „bis“, ein „für jedes“ oder ein „so oft wie“. Ein Verfahren ohne eines dieser Wörter ist eine Sequenz, und wenn es Eingaben variabler Größe verarbeiten muss (eine Liste von Zahlen, einen Text), fehlt ihm eine Wiederholung.

Terminiert der Algorithmus?

Die Endlichkeit gehört zur Definition des Algorithmus, und eine Wiederholung ist der einzige Ort, an dem sie verloren gehen kann: Eine Sequenz von fünf Schritten führt fünf Schritte aus, und eine Entscheidung führt einen ihrer Zweige aus; aber eine Wiederholung führt ihren Rumpf so oft aus, wie die Bedingung erfüllt ist, und nichts garantiert im Voraus, dass sie irgendwann nicht mehr erfüllt ist.

Um zu begründen, dass eine Wiederholung terminiert, sucht man eine aus den Variablen berechnete Größe, die zwei Bedingungen erfüllt: Sie ist eine natürliche Zahl (ganz und nicht negativ), solange die Wiederholung weiterläuft, und sie fällt streng in jedem Durchlauf. Wenn das so ist, terminiert die Wiederholung: Eine streng fallende Folge natürlicher Zahlen kann nicht unendlich sein, weil jeder Durchlauf sie um mindestens eins senkt und es von einer natürlichen Zahl $n$ aus nicht mehr als $n$ Stufen bis zur Null gibt. Diese Größe heißt Variante oder Schrankenfunktion, und die Lektion Korrekte Schleifen entwerfen wird sie systematisch verwenden.

BeispielDie Variante der Division durch Subtraktion

Bei der Division durch fortgesetzte Subtraktion ist die Variante $r$ . Solange die Wiederholung weiterläuft, gilt $r \geq b > 0$ , also ist $r$ eine natürliche Zahl. In jedem Durchlauf erhält $r$ den Wert $r - b$ , und da $b > 0$ gilt (Vorbedingung), ist der neue Wert streng kleiner. Folglich terminiert die Wiederholung, und zwar nach höchstens $a$ Durchläufen (genau genommen nach genau $q$ Durchläufen, dem Quotienten).

Man beachte, wo die Vorbedingung $b > 0$ verwendet wurde. Führt man den Algorithmus mit $b = 0$ aus, so lässt Schritt 3 den Wert $r$ unverändert, die Bedingung $r \geq 0$ ist immer erfüllt, und die Wiederholung terminiert nie: Der Algorithmus ist nicht falsch, sondern hat eine Eingabe erhalten, die der Vertrag ausschloss. Und wäre $b$ negativ, so würde $r$ in jedem Durchlauf wachsen. Die Vorbedingung ist kein Schmuck: Sie ist genau das, was nötig ist, damit die Überlegung funktioniert.

Beide Bedingungen der Variante sind notwendig, und man kann sich leicht bei jeder von ihnen irren. Man betrachte dieses Verfahren, das entscheiden soll, ob eine natürliche Zahl $n$ gerade ist: „solange $n \neq 0$ , erhält $n$ den Wert $n - 2$ ; wird die Null erreicht, war $n$ gerade“. Die Größe $n$ fällt in jedem Durchlauf, und dennoch terminiert das Verfahren nicht, wenn $n$ ungerade ist: Mit $n = 5$ durchläuft es $3$ , $1$ , $-1$ , $-3$ , und die Bedingung $n \neq 0$ schlägt nie fehl. Was nicht erfüllt ist, ist die andere Bedingung: $n$ hört auf, eine natürliche Zahl zu sein, weil die Bedingung der Wiederholung nicht verhindert, dass es unter null sinkt. Die Korrektur besteht darin, zu wiederholen, solange $n \geq 2$ gilt, und am Ende nach dem verbleibenden Wert zu entscheiden, $0$ oder $1$ ; jetzt ist $n$ in jedem Durchlauf eine natürliche Zahl, weil nur subtrahiert wird, wenn $n \geq 2$ gilt, und es fällt: Das Verfahren terminiert.

Zu entscheiden, ob eine Wiederholung terminiert, ist nicht immer leicht. Ein berühmtes Beispiel: Ausgehend von einer natürlichen Zahl $n \geq 1$ wird, solange $n \neq 1$ gilt, $n$ halbiert, wenn es gerade ist, und durch $3n + 1$ ersetzt, wenn es ungerade ist. Mit $n = 6$ lautet die Folge $6, 3, 10, 5, 16, 8, 4, 2, 1$ , und sie endet. Niemand hat ein $n$ gefunden, für das sie nicht endet, und man hat es mit Computern für ungeheuer viele Werte überprüft; aber niemand hat beweisen können, dass sie immer endet: Das ist die Collatz-Vermutung, ein offenes Problem der Mathematik. Keine bekannte Größe fällt in jedem Durchlauf. Die Moral für alle, die programmieren, ist bescheiden und fest: Ein Algorithmus, dessen Terminierung man nicht zu begründen weiß, ist nicht fertig.

Häufige Fehler

Mehrdeutige Schritte. „Mehrmals wiederholen“, „bis es passt“, „eine geeignete Zahl nehmen“. Jeder Schritt muss ausführbar sein, ohne das Problem zu verstehen; sonst ist er schlecht geschrieben.
Den Fall vergessen, in dem die Wiederholung nicht ausgeführt wird. Jede Wiederholung mit der Bedingung am Anfang kann ihren Rumpf null Mal ausführen. Man muss sich immer fragen, was der Algorithmus in diesem Fall liefert, und die Ablaufverfolgung mit einer minimalen Eingabe beantwortet das.
Mit einem Beispiel spezifizieren. „Für 17 und 5 ergibt sich 3 und 2“ ist keine Spezifikation; die Beziehung wird als allgemeine Bedingung geschrieben, und das Beispiel veranschaulicht sie.
Den Algorithmus mit seinem Programm verwechseln. Bei einem Programm, das versagt, kann der Algorithmus falsch sein oder seine Niederschrift. Wer den Algorithmus nicht vorher geschrieben hat, weiß nicht, welches von beiden er suchen soll.
Die Terminierung als selbstverständlich voraussetzen. Dass eine Größe fällt, genügt nicht: Sie muss außerdem eine natürliche Zahl sein, solange wiederholt wird.

Gelöste Aufgaben

Gelöste Aufgabe 1Die größte von drei Zahlen, mit Gleichstand

Einen Algorithmus schreiben, der die Spezifikation des Maximums von drei Zahlen vom Anfang dieser Lektion erfüllt, und ihn für die Eingaben $(7, 2, 5)$ und $(4, 9, 9)$ von Hand nachvollziehen.

Lösung

$m = x$
Idee: Man geht die Eingabe durch und hält den bisher größten Wert in einer Variable $m$ fest. Erster Schritt: $m$ erhält den Wert $x$ . Danach ist $m$ das Maximum der gesehenen Werte, und das ist nur $x$ .
$m = \max(x, y, z)$
Zweiter Schritt: Wenn $y > m$ , erhält $m$ den Wert $y$ . Dritter Schritt: Wenn $z > m$ , erhält $m$ den Wert $z$ . Vierter Schritt: Liefere $m$ . Das sind drei Anweisungen in Sequenz, zwei davon Entscheidungen ohne alternativen Zweig.
$(x, y, z) = (7, 2, 5) \Rightarrow m = 7$
Ablaufverfolgung für $(7, 2, 5)$ : Nach dem ersten Schritt gilt $m = 7$ ; im zweiten ist $2 > 7$ falsch, und $m$ ändert sich nicht; im dritten ist $5 > 7$ falsch, und $m$ ändert sich nicht. Geliefert wird $7$ .
$(x, y, z) = (4, 9, 9) \Rightarrow m = 9$
Ablaufverfolgung für $(4, 9, 9)$ : Nach dem ersten Schritt gilt $m = 4$ ; im zweiten gilt $9 > 4$ , und $m$ erhält den Wert $9$ ; im dritten ist $9 > 9$ falsch, und $m$ ändert sich nicht. Geliefert wird $9$ , was korrekt ist: Der Gleichstand verlangt keine eigene Behandlung.
$m \geq x, \quad m \geq y, \quad m \geq z$
Begründung: Nach jedem Schritt ist $m$ einer der gesehenen Werte, und keiner von ihnen übertrifft ihn. Das stimmt nach dem ersten Schritt, und jede Entscheidung erhält es: Ist der neue Wert größer, wird er zu $m$ ; wenn nicht, übertrifft er $m$ nicht. Am Ende sind alle drei gesehen, und $m$ erfüllt die Nachbedingung.
$(x, y, z) = (4, 9, 9) \Rightarrow p \in \{2, 3\}$
Hätte man $y \geq m$ statt $y > m$ geschrieben, wäre das Ergebnis dasselbe, weil bei Gleichstand ein gleicher Wert zugewiesen wird. Die Wahl zwischen $>$ und $\geq$ wäre wichtig, wenn zusätzlich die Position des Maximums verlangt würde: Mit $>$ wird die erste der gleichauf liegenden Positionen geliefert, mit $\geq$ die letzte; die Formel nennt die Position $p$ .

Gelöste Aufgabe 2Das Schaltjahr, mit einem Gegenbeispiel korrigiert

Im gregorianischen Kalender ist ein Jahr ein Schaltjahr, wenn es durch $4$ teilbar ist, ausgenommen die durch $100$ teilbaren, die es nur sind, wenn sie außerdem durch $400$ teilbar sind. Jemand aus dem Kurs schlägt den Algorithmus vor: „Wenn das Jahr durch $4$ teilbar ist, liefere ja; sonst liefere nein.“ Ein Jahr finden, in dem er versagt, und einen korrekten Algorithmus mit seiner Spezifikation schreiben.

Lösung

$(4 \mid n \wedge \neg (100 \mid n)) \vee 400 \mid n$
Spezifikation. Eingabe: eine ganze Zahl $n \geq 1583$ (der gregorianische Kalender gilt seit Oktober 1582). Ausgabe: ja oder nein. Beziehung: Die Ausgabe ist genau dann ja, wenn $n$ durch $4$ und nicht durch $100$ teilbar ist oder durch $400$ teilbar ist.
$1900 = 4 \cdot 475, \quad 1900 = 400 \cdot 4 + 300$
Der vorgeschlagene Algorithmus trifft in den meisten Jahren das Richtige und wirkt deshalb korrekt. Um ihn zu widerlegen, genügt ein Jahr, das durch $100$ und nicht durch $400$ teilbar ist: $1900$ ist durch $4$ teilbar, und der Algorithmus sagt ja; aber $1900$ war kein Schaltjahr.
$400 \mid n, \quad 100 \mid n, \quad 4 \mid n$
Korrigierter Algorithmus, in drei verketteten Entscheidungen. Schritt 1: Wenn $n$ durch $400$ teilbar ist, liefere ja und beende. Schritt 2: Wenn $n$ durch $100$ teilbar ist, liefere nein und beende. Schritt 3: Wenn $n$ durch $4$ teilbar ist, liefere ja; sonst liefere nein.
$2000, \quad 1900, \quad 2024, \quad 2023$
Die Reihenfolge der Fragen ist wesentlich: Sie gehen von der besondersten Regel zur allgemeinsten. Fragte man zuerst nach der $4$ , bekäme das Jahr $1900$ ein ja, bevor die Ausnahme erreicht ist. Ablaufverfolgung für vier Jahre, eines je Fall: $2000$ (Schritt 1: ja), $1900$ (Schritt 2: nein), $2024$ (Schritt 3: ja), $2023$ (Schritt 3: nein).
$4 \mid 1900 \wedge \neg (400 \mid 1900)$
Die Lehre betrifft nicht nur Kalender: Ein Algorithmus wird mit einem einzigen Gegenbeispiel widerlegt, und Gegenbeispiele sucht man an den Grenzen der Regeln, nicht in den gewöhnlichen Fällen. Mit $2024$ , $2020$ und $2016$ zu testen hätte nichts aufgedeckt.

Gelöste Aufgabe 3Wie viele Durchläufe die Division durch Subtraktion macht

Die Division durch fortgesetzte Subtraktion mit $a = 20$ und $b = 5$ sowie mit $a = 0$ und $b = 7$ von Hand nachvollziehen. Danach begründen, dass der Algorithmus für jede zulässige Eingabe nach genau $q$ Durchläufen terminiert und dass seine Ausgabe die Nachbedingung erfüllt.

Lösung

$20 = 5 \cdot 4 + 0$
Ablaufverfolgung mit $a = 20$ , $b = 5$ : $r$ durchläuft $20$ , $15$ , $10$ , $5$ , $0$ , und $q$ durchläuft $0$ , $1$ , $2$ , $3$ , $4$ . Die fünfte Prüfung, $0 \geq 5$ , schlägt fehl. Ausgabe: $q = 4$ , $r = 0$ . Hier ist der Grenzfall die aufgehende Division: Der vierte Durchlauf findet statt, weil $5 \geq 5$ gilt, und deshalb muss die Bedingung $\geq$ lauten und nicht $>$ .
$0 = 7 \cdot 0 + 0$
Ablaufverfolgung mit $a = 0$ , $b = 7$ : Die erste Prüfung, $0 \geq 7$ , schlägt fehl; der Rumpf wird kein einziges Mal ausgeführt. Ausgabe: $q = 0$ , $r = 0$ , was korrekt ist.
$\dato{conserva}{b \cdot (q + 1) + (r - b) = b \cdot q + r = a}$
Eine Beziehung, die erhalten bleibt. Vor dem ersten Durchlauf gilt $b \cdot q + r = b \cdot 0 + a = a$ . In jedem Durchlauf sinkt $r$ um $b$ und steigt $q$ um $1$ , sodass sich $b \cdot q + r$ nicht ändert. Folglich gilt die Gleichung nach jedem Durchlauf.
$r_0 > r_1 > r_2 > \cdots \geq 0$
Terminierung. Solange wiederholt wird, gilt $r \geq b > 0$ , und $r$ ist eine natürliche Zahl; in jedem Durchlauf sinkt es um $b \geq 1$ . Eine streng fallende Folge natürlicher Zahlen ist endlich: Die Wiederholung terminiert.
$a = b \cdot q + r, \quad 0 \leq r < b$
Beim Terminieren ist die Bedingung fehlgeschlagen: $r < b$ . Außerdem gilt $r \geq 0$ , weil nur dann $b$ subtrahiert wird, wenn $r \geq b$ gilt. Zusammen mit der Beziehung, die erhalten bleibt, erfüllt die Ausgabe die Nachbedingung; und da $q$ die Durchläufe zählt, ist die Zahl der Durchläufe der Quotient.

Online-Übungen

Übung 1Die Durchläufe zählen

Den folgenden Algorithmus von Hand nachvollziehen und den Wert, den er liefert, in das Feld schreiben, nur die Zahl.

$n$ erhält den Wert $29$ , und $k$ erhält den Wert $0$ .
Solange $n > 1$ gilt, wiederhole die Schritte 3 und 4; sobald es nicht mehr gilt, fahre mit Schritt 5 fort.
Wenn $n$ gerade ist, erhält $n$ den Wert $n / 2$ ; wenn es ungerade ist, erhält $n$ den Wert $n + 1$ .
$k$ erhält den Wert $k + 1$ ; kehre zu Schritt 2 zurück.
Liefere $k$ .

Der Browser prüft deine Antwort sofort, ohne sie zu bewerten.

Schreibe hier deine Antwort

Hinweis

Lege die Tabelle an: $n$ geht im ersten Durchlauf von $29$ auf $30$ . Zähle einen Durchlauf für jede Änderung von $n$ , bis $n$ den Wert $1$ hat.

Übung 2Die fehlende Bedingung

Der folgende Algorithmus, in der Kurzform geschrieben, soll Quotient und Rest der Division durch fortgesetzte Subtraktion berechnen, aber ihm fehlt die Bedingung der Wiederholung. Die Unterstriche durch die richtige Bedingung ersetzen, ohne den Rest zu ändern.

Der Browser prüft deine Antwort sofort, ohne sie zu bewerten.

Schreibe hier deine Antwort

Hinweis

Vollziehe den Algorithmus mit $a = 10$ und $b = 5$ von Hand nach: Der zweite Durchlauf muss stattfinden, obwohl der Rest genau $5$ beträgt.

Übungsaufgaben

Jede Aufgabe hat einen Hinweis, den man erst nach einem eigenen Versuch öffnen sollte, und eine Lösung, die nach dem Öffnen des Hinweises erscheint.

Übungsaufgabe 1Die Ordnung von drei Zahlen spezifizieren

Die Spezifikation des Problems „drei Zahlen sortieren“ schreiben (Eingabe, Ausgabe und Beziehung) und angeben, welche Entscheidungen sie erzwingt, die die Aufgabenstellung nicht traf. Danach prüfen, dass die Spezifikation für die Eingabe $(5, 2, 5)$ diese beiden Ausgaben ausschließt, $(2, 5, 6)$ und $(2, 5, 5, 5)$ , und $(2, 5, 5)$ zulässt.

Hinweis

Eine „sortierte“ Ausgabe kann mit der Eingabe nichts zu tun haben. Welche Bedingung verbindet die Zahlen der Ausgabe mit denen der Eingabe, die wiederholten eingeschlossen? Aufsteigend oder absteigend? Streng oder nicht?

Lösung

Eingabe: drei Zahlen $x$ , $y$ , $z$ . Ausgabe: drei Zahlen $u$ , $v$ , $w$ . Beziehung: $u \leq v \leq w$ , und $(u, v, w)$ ist eine Umordnung von $(x, y, z)$ , das heißt, es enthält dieselben Werte mit denselben Wiederholungen. Entscheidungen, die die Aufgabenstellung nicht traf: die Richtung (hier vom kleinsten zum größten); dass die Ordnung nicht streng ist ( $\leq$ und nicht $<$ , weil bei wiederholten Werten eine strenge Ordnung unmöglich ist); und dass die Ausgabe eine Umordnung sein muss. $(2, 5, 6)$ ist sortiert, enthält aber eine $6$ , die nicht vorkam; $(2, 5, 5, 5)$ hat vier Werte; $(2, 5, 5)$ erfüllt beide Bedingungen. Ohne die Bedingung der Umordnung wäre $(0, 0, 0)$ für jede Eingabe eine korrekte Ausgabe.

Übungsaufgabe 2Die Ziffern einer Zahl, von rechts nach links

Einen Algorithmus in nummerierten Schritten schreiben, der eine natürliche Zahl $n$ erhält und ihre Ziffern von der letzten bis zur ersten liefert (für $4072$ liefert er $2$ , $7$ , $0$ , $4$ ), wobei nur Quotient und Rest der Division durch $10$ verwendet werden. Ihn für $4072$ und für $0$ von Hand nachvollziehen und begründen, dass er für jedes $n$ terminiert.

Hinweis

Der Rest der Division durch $10$ ist die letzte Ziffer, und der Quotient ist die Zahl ohne sie. Entscheide, ob die Bedingung vor oder nach dem Liefern einer Ziffer gefragt wird, und sieh nach, was bei $n = 0$ geschieht, einer Zahl mit einer Ziffer.

Lösung

Ein korrekter Algorithmus: (1) liefere den Rest der Division von $n$ durch $10$ ; (2) $n$ erhält den Wert des Quotienten der Division von $n$ durch $10$ ; (3) wenn $n > 0$ , kehre zu Schritt 1 zurück; sonst beende. Die Frage steht nach dem Rumpf, sodass der Rumpf mindestens einmal ausgeführt wird: Für $n = 0$ liefert er $0$ , seine einzige Ziffer. Fragte man am Anfang („solange $n > 0$ “), würde für $n = 0$ nichts geliefert; das ist der Fehler, den Fall zu vergessen, in dem die Wiederholung nicht ausgeführt wird. Ablaufverfolgung für $4072$ : Geliefert werden $2$ , $7$ , $0$ , $4$ , und $n$ durchläuft $407$ , $40$ , $4$ , $0$ . Terminierung: Die Variante ist $n$ , eine natürliche Zahl; wenn zu Schritt 1 zurückgekehrt wird, dann weil $n > 0$ gilt, und für $n \geq 1$ ist der Quotient durch $10$ streng kleiner als $n$ , sodass $n$ in jedem Durchlauf streng fällt.

Übungsaufgabe 3Wechselgeld in Münzen

Es gibt Münzen zu $50$ , $10$ und $1$ Einheiten, in unbegrenzter Anzahl. Spezifikation: Eingabe, eine natürliche Zahl $m$ ; Ausgabe, drei natürliche Zahlen $c_{50}$ , $c_{10}$ , $c_1$ mit $50 c_{50} + 10 c_{10} + c_1 = m$ und der kleinstmöglichen Anzahl von Münzen, $c_{50} + c_{10} + c_1$ . Jemand schlägt den folgenden Algorithmus vor. Eine Eingabe finden, bei der er versagt, jeden Mangel erklären und ihn beheben.

$c_{50}$ , $c_{10}$ und $c_1$ erhalten den Wert $0$ .
Wenn $m \geq 50$ , erhält $c_{50}$ den Wert $c_{50} + 1$ und $m$ den Wert $m - 50$ .
Solange $m > 10$ : $c_{10}$ erhält den Wert $c_{10} + 1$ und $m$ den Wert $m - 10$ .
Solange $m > 0$ : $c_1$ erhält den Wert $c_1 + 1$ und $m$ den Wert $m - 1$ .
Liefere $c_{50}$ , $c_{10}$ und $c_1$ .

Hinweis

Die Summe der Münzen ist immer $m$ ; was fehlschlagen kann, ist ihre Anzahl. Probiere ein genaues Vielfaches von $10$ und einen Betrag von mehr als $100$ , und frage dich, welche Art, Schritte zu kombinieren, Schritt 2 verwendet und welche er verwenden sollte.

Lösung

Es gibt zwei Mängel. Erstens verwendet Schritt 3 $m > 10$ : Mit $m = 10$ liefert er keine Münze zu $10$ und zehn zu $1$ statt einer. Zweitens ist Schritt 2 eine Entscheidung, wo eine Wiederholung nötig ist: Mit $m = 120$ liefert der Algorithmus, so wie er geschrieben ist, eine Münze zu $50$ , sechs zu $10$ und zehn zu $1$ (siebzehn Münzen), und selbst mit bereits korrigiertem Schritt 3 lieferte er eine zu $50$ und sieben zu $10$ (acht) statt zwei zu $50$ und zwei zu $10$ (vier). Die Eingabe $m = 100$ zeigt beide Mängel: Der Algorithmus liefert eine zu $50$ , vier zu $10$ und zehn zu $1$ , fünfzehn Münzen, statt zwei. Korrektur: Schritt 2, „solange $m \geq 50$ , …“; Schritt 3, „solange $m \geq 10$ , …“. So korrigiert, nimmt der Algorithmus immer die größte Münze, die passt, und mit diesen drei Münzen ergibt das die kleinste Anzahl: Die Einerziffer von $m$ kann nur mit Münzen zu $1$ bezahlt werden, und vom Rest zahlt man am besten so viel wie möglich mit Münzen zu $50$ , weil fünf zu $10$ so viel wert sind wie eine zu $50$ . Mit anderen Münzen, etwa zu $1$ , $3$ und $4$ für $m = 6$ , ergibt die Wahl der jeweils größten nicht mehr das Minimum ( $4 + 1 + 1$ gegenüber $3 + 3$ ).