Algorithmen entwerfen: vom Problem zum Struktogramm

„Schreibe ein Programm, das die Klassenarbeit auswertet.“ So lautet die Aufgabe. Und jetzt?

Der häufigste Anfängerfehler an dieser Stelle ist, sofort zu tippen. Man kommt ein Stück weit, merkt dann, dass etwas fehlt, baut um, merkt wieder etwas, und nach zwei Stunden ist der Quelltext ein Flickwerk, das man selbst nicht mehr versteht.

Es gibt ein Verfahren, das genau das verhindert, und es kommt ohne Rechner aus. Man zerlegt das große Problem so lange in kleinere, bis jedes Stück offensichtlich lösbar ist. Das dauert am Anfang länger und am Ende deutlich kürzer.

Vorausgesetzt werden die vier Eigenschaften eines Algorithmus und die drei Grundbausteine Folge, Auswahl und Wiederholung. Bei Unsicherheit lies Was ist ein Algorithmus? und Die drei Grundbausteine.

Neu ist hier die Frage, wie man auf einen Algorithmus kommt und wie man begründet, dass er stimmt.

Die Methode besteht darin, das Problem zunächst in groben Schritten zu beschreiben und jeden Schritt anschließend zu verfeinern, bis er unmittelbar umsetzbar ist.

Stufe 1, das ganze Problem in einem Satz:

Werte die Klassenarbeit aus.

Stufe 2, in drei Schritte zerlegt:

1. Punkte aller Schüler einlesen
2. Aus den Punkten Noten berechnen
3. Ergebnisse ausgeben

Stufe 3, Schritt 2 weiter verfeinert:

2.1 Für jeden Schüler:
2.2   Prozentsatz aus Punkten und Höchstpunktzahl berechnen
2.3   Aus dem Prozentsatz die Note bestimmen

Stufe 4, Schritt 2.3 weiter verfeinert:

2.3.1 Wenn Prozent >= 87 dann Note 1
2.3.2 sonst wenn Prozent >= 73 dann Note 2
2.3.3 sonst wenn Prozent >= 59 dann Note 3
2.3.4 ...

Jetzt ist jeder Schritt so einfach, dass man ihn ohne Nachdenken hinschreiben kann. Das ist das Abbruchkriterium: Verfeinert wird, bis ein Schritt offensichtlich umsetzbar ist.

🔴 Der Gewinn liegt nicht nur in der Übersicht. Auf jeder Stufe kann man prüfen, ob die Zerlegung vollständig ist, ohne sich um die tieferen Ebenen zu kümmern. Fehlt in Stufe 2 der Punkt „Ergebnisse ausgeben“, fällt das dort auf und nicht erst nach zweihundert Zeilen Quelltext.

Ein Struktogramm stellt einen Algorithmus als ineinandergeschachtelte Kästen dar. Sein Vorteil gegenüber Pfeildiagrammen: Man kann keine unstrukturierten Sprünge zeichnen, weil ein Kasten immer vollständig in einem anderen liegt.

Die drei Grundbausteine sehen so aus:

Folge:                    Auswahl:                  Wiederholung:
+------------------+      +------------------+      +--------------------+
| Anweisung 1      |      |  \  Bedingung  / |      | solange Bedingung  |
+------------------+      |   \          /   |      | +----------------+ |
| Anweisung 2      |      | ja  \      /  nein|     | | Anweisung      | |
+------------------+      +-------+----------+      | +----------------+ |
                          | dann  | sonst    |      +--------------------+
                          +-------+----------+

Verschachteln ist ausdrücklich vorgesehen: In einem Wiederholungsrahmen darf eine Auswahl stehen und darin wieder eine Wiederholung. Genau daraus entsteht die Ausdruckskraft.

Vom Struktogramm zum Pseudocode ist es dann nur noch eine Übersetzung: Jeder Kasten wird eine Zeile, jede Schachtelung eine Einrückung.

Ein Entwurf ist erst dann fertig, wenn man ihn geprüft hat, und geprüft heißt: mit konkreten Werten durchgespielt.

Das Werkzeug dafür kennst du, es ist die Wertetabelle: eine Spalte je Variable, eine Zeile je Durchlauf. Man wählt Beispielwerte, deren Ergebnis man unabhängig kennt, und vergleicht.

Wichtig ist die Auswahl der Beispiele. Ein einziger typischer Fall genügt nie, denn die Fehler sitzen an den Rändern.

Statt zu raten, geht man eine feste Liste durch. Für jede Größe im Algorithmus fragt man:

Besonders die Zeile „genau an der Grenze“ verdient Aufmerksamkeit. Bei einer Notengrenze von 87 Prozent muss festgelegt sein, ob 87,0 noch eine 1 ist oder schon eine 2. Diese Entscheidung trifft der Vergleichsoperator, und ein $>$ statt $\ge$ verschiebt sie.

Ein Durchspielen zeigt, dass der Algorithmus für diese Werte stimmt. Es zeigt nicht, dass er immer stimmt. Dafür braucht man ein Argument.

Das wichtigste Werkzeug dazu ist die Invariante: eine Aussage, die vor der Schleife gilt und die jeder Durchlauf erhält.

Beispiel, Summe der Zahlen von 1 bis $n$:

summe := 0
i := 1
solange i <= n:
    summe := summe + i
    i := i + 1

Invariante: „$\texttt{summe}$ enthält die Summe aller Zahlen von 1 bis $\texttt{i} - 1$.“

Prüfen wir sie in drei Schritten, und genau diese drei gehören zu jeder Begründung:

Vor der Schleife gilt sie: $\texttt{summe} = 0$ und $\texttt{i} = 1$, also die Summe von 1 bis 0, und die ist leer, also 0. Stimmt.

Jeder Durchlauf erhält sie: Galt sie vorher, so wird $\texttt{i}$ addiert und danach $\texttt{i}$ um eins erhöht. Danach enthält $\texttt{summe}$ die Summe bis zum neuen $\texttt{i} - 1$. Stimmt weiterhin.

Nach der Schleife ist die Bedingung falsch, also $\texttt{i} > n$, und da $\texttt{i}$ genau um eins wächst, ist $\texttt{i} = n + 1$. Die Invariante liefert dann: $\texttt{summe}$ ist die Summe von 1 bis $n$. Genau das war gesucht.

Damit ist die Richtigkeit für alle $n$ begründet und nicht nur für ausprobierte Werte. Das ist der Unterschied zwischen Testen und Begründen, und beides hat seinen Platz: Testen findet Fehler, Begründen zeigt ihre Abwesenheit.

Zur Richtigkeit kommt die Frage, ob die Schleife überhaupt endet. Dafür genügt der Hinweis auf eine Größe, die sich in eine Richtung bewegt und eine Schranke erreichen muss:

$\texttt{i}$ startet bei 1, wächst in jedem Durchlauf um genau 1 und wird nie verkleinert; $n$ ändert sich nicht. Eine streng wachsende ganze Zahl überschreitet jede feste Schranke nach endlich vielen Schritten. Also endet die Schleife nach höchstens $n$ Durchläufen.

Ein vollständiger Entwurf beantwortet damit drei Fragen: Tut er das Richtige? Hört er auf? Was passiert an den Rändern?