Zum Inhalt springen
Zurück zur Themenübersicht

Algorithmen

Vom Algorithmus zum Programm: implementieren, testen, Fehler finden

Die drei Fehlerarten, was eine Fehlermeldung wirklich sagt und wie man einen Fehler systematisch einkreist statt zu raten.

Benötigte Grundlagen

Dieses Vorwissen brauchst du für das Kapitel. Schau kurz nach, wenn dir etwas davon nicht mehr präsent ist, sonst leg direkt los.

Einführung

Ein ist ein Plan. Ein Programm ist derselbe Plan in einer Sprache, die eine Maschine ausführen kann.

Zwischen beiden liegt ein Schritt, den fast alle unterschätzen: das Fehlersuchen. Berufsprogrammierer verbringen damit mehr Zeit als mit dem Schreiben. Das ist kein Zeichen von Unfähigkeit, sondern normal, denn eine Maschine tut genau das, was dasteht, und nicht das, was gemeint war.

Gute : Fehlersuche ist erlernbar. Es gibt genau drei Fehlerarten, und für jede gibt es ein Vorgehen. Wer sie unterscheiden kann, hört auf zu raten.

Das kannst du nach diesem Kapitel

  • die drei Phasen Entwerfen, Implementieren, Reflektieren benennen und ihren Zweck erklären.

  • , Laufzeitfehler und logische Fehler unterscheiden und je ein Beispiel nennen.

  • eine Fehlermeldung lesen und daraus ableiten, wo zu suchen ist.

  • einen Fehler durch Einkreisen systematisch finden statt durch Raten.

  • sinnvolle Testfälle angeben, insbesondere Randfälle.

Die drei Phasen des Problemlösens

Entwerfen. Zuerst wird das Problem verstanden und ein entwickelt, auf Papier, als oder als Pseudocode. In dieser Phase wird noch nicht getippt. Wer sofort tippt, entwirft am Bildschirm, und das ist der teuerste Ort dafür.

Implementieren. Der Algorithmus wird in einer Programmiersprache aufgeschrieben. Hier geht es um Genauigkeit in der Form, nicht mehr um die Idee.

Reflektieren. Das Programm wird getestet, verbessert und schließlich beurteilt: Löst es das Problem? Ist es verständlich? Funktioniert es auch in ungewöhnlichen Fällen?

Die Reihenfolge ist kein Ritual. Ein Denkfehler im Entwurf kostet Minuten; derselbe Denkfehler, erst nach hundert getippten Zeilen bemerkt, kostet einen Nachmittag.

Vom Problem zum geprüften Programm

1Problem verstehenWas ist gegeben, was istgesucht?2Algorithmus entwerfenDer Weg: noch ohneProgrammiersprache.3Programm schreibenDenselben Weg in einer Spracheaufschreiben.4TestenAn Beispielen prüfen, ob erwirklich stimmt.

Die häufigste Abkürzung ist, Schritt 2 zu überspringen und gleich zu tippen. Sie kostet fast immer mehr Zeit, als sie spart: Ein Fehler im Weg sieht im Programm wie ein Tippfehler aus und wird an der falschen Stelle gesucht. Und Schritt 4 ist kein Anhängsel, ein ungetestetes Programm ist ein Programm, von dem man nicht weiß, ob es funktioniert.

Die drei Fehlerarten

. Das Programm ist nach den Regeln der Sprache nicht richtig gebaut: eine fehlende Klammer, ein falsch geschriebenes Schlüsselwort, ein vergessenes Semikolon. Das System meldet ihn und führt gar nichts aus. Das ist die freundlichste Fehlerart, denn sie ist sofort sichtbar.

Laufzeitfehler. Das Programm startet und bricht mittendrin ab: Division durch null, Zugriff auf ein nicht vorhandenes Element, nicht gefunden. Der Fehler zeigt sich erst bei bestimmten Eingaben, deshalb kann er lange unbemerkt bleiben.

Logischer Fehler. Das Programm läuft vollständig durch und liefert ein falsches Ergebnis. Niemand meldet etwas. Das ist die gefährlichste Art, weil das Programm zufrieden aussieht.

ArtWann bemerktWer bemerkt es
Syntaxfehlervor dem Startdas System
Laufzeitfehlerwährend der Ausführungdas System
logischer Fehlervielleicht nienur ein Mensch mit einem Testfall

Drei Fehlerarten

Syntax-fehlerLaufzeit-fehlerLogik-fehlerWann fällt er auf?vor demStartmitten imLaufoft garnichtWas passiert?Programmläuft garnicht anProgrammbricht abErgebnisisteinfachfalschEin BeispielKlammervergessendurch nullgeteiltPlus stattMinusDer gefährlichste ist der letzte:Er meldet sich nicht von selbst.

Lies die erste Zeile von links nach rechts. Sie ordnet die drei Fehlerarten danach, wann man sie bemerkt. Und genau in dieser Reihenfolge werden sie schlimmer: Ein hält dich auf, ein Laufzeitfehler macht sich bemerkbar, ein Logikfehler liefert brav eine Zahl, die falsch ist. Deshalb testet man, statt sich auf Fehlermeldungen zu verlassen.

Fehlermeldungen lesen statt wegklicken

Eine Fehlermeldung ist keine Beschimpfung, sondern ein Hinweis mit drei Angaben:

  1. Wo: und Zeilennummer.
  2. Was: die Art des Problems.
  3. Manchmal warum: ein Vorschlag.

Zwei Dinge muss man dabei wissen. Erstens ist die genannte Zeile die Stelle, an der das System stolpert, nicht immer die Stelle, an der die Ursache liegt. Fehlt in Zeile 12 eine Klammer, wird der Fehler vielleicht erst in Zeile 15 gemeldet. Sieh deshalb auch oberhalb der genannten Zeile nach.

Zweitens: Bearbeite immer nur den ersten Fehler und lasse das Programm dann erneut prüfen. Ein einziger bringt das System aus dem Tritt und erzeugt oft eine ganze Kaskade von Folgemeldungen, die sich mit dem ersten Fix von selbst erledigen.

Fehler einkreisen statt raten

Für logische Fehler gibt es ein Verfahren, das immer funktioniert:

  1. Fehler zuverlässig auslösen. Welche Eingabe erzeugt ihn? Ein Fehler, den man nicht wiederholen kann, lässt sich nicht untersuchen.
  2. Erwartung aufschreiben. Was müsste bei dieser Eingabe herauskommen? Ohne diese Zahl weiß man nicht einmal sicher, dass ein Fehler vorliegt.
  3. Zwischenstände sichtbar machen. An mehreren Stellen die Werte ausgeben lassen. So sieht man, ab welcher Stelle sie von der Erwartung abweichen.
  4. Halbieren. Stimmt es in der Mitte des Programms noch? Wenn ja, liegt der Fehler dahinter, sonst davor. Damit halbiert sich der zu prüfende Bereich bei jedem Schritt.
  5. Ändern, prüfen, weitergehen. Immer nur eine Sache ändern und danach erneut testen. Wer drei Dinge gleichzeitig ändert, weiß hinterher nicht, welche geholfen hat.

Punkt 4 ist mehr als ein Kniff: Bei 64 Zeilen führen sechs Halbierungsschritte zur genauen Zeile. Genau dieses Prinzip lernst du später als binäre Suche wieder.

Halbieren statt raten

wiederholenFehlerirgendwo imProgrammBereich =ganzesProgrammBereichgrößerals eineZeile?janeinFehlergefundenin der Mitteprüfen, diefalscheHälftebehalten

Jeder Durchgang halbiert den Bereich, in dem der Fehler noch stecken kann. Das klingt bescheiden, ist es aber nicht: Bei 100100 Zeilen bleiben nach dem ersten Durchgang 5050 übrig, dann 2525, dann 1313, nach sieben Durchgängen ist es eine einzige Zeile, denn 27=1282^7 = 128 ist bereits größer als 100100. Raten braucht im schlechtesten Fall hundert Versuche.

Testfälle: normale und Randfälle

Ein Programm mit einem einzigen Beispiel zu prüfen genügt nicht. Man braucht mindestens:

  • einen Normalfall, der typisch ist,
  • Randfälle an den Grenzen: 0, 1, der größte erlaubte Wert, eine leere Eingabe,
  • Sonderfälle, die verboten sein sollten: negative Werte, Buchstaben statt Zahlen.

Die meisten Fehler sitzen an den Rändern. Eine , die für 5 Werte richtig arbeitet, macht bei 0 Werten oder bei genau 1 Wert oft etwas Unerwartetes. Wer nur den Normalfall prüft, findet genau die Fehler nicht, die in der Praxis auffallen.

Eine Testtabelle

EingabeerwartettatsächlichUrteil3 und477✓0 und000✓−2 und533✓127und 1128−128✗Die ersten drei sind normale Fälle,der letzte ein Randfall: 127 istdie größte Zahl, die in einen8-Bit-Zahlentyp mit Vorzeichenpasst.

Drei Häkchen und ein Kreuz, und das Kreuz steht genau dort, wo man nicht von selbst hinschaut. In einem 8-Bit-Zahlentyp mit Vorzeichen ist 127127 die größte darstellbare Zahl; 127+1127 + 1 passt nicht mehr und kippt auf −128-128, den kleinsten Wert. Die ersten drei Zeilen hätten dich in Sicherheit gewiegt. Deshalb gehören zu jedem Test nicht nur Beispiele, die man sich ausdenkt, sondern die Ränder des erlaubten Bereichs.

Eine Fehlermeldung auswerten

Ein Programm meldet: „Zeile 15: unerwartetes Symbol“. In Zeile 15 steht eine ganz gewöhnliche Ausgabeanweisung. Wie gehst du vor?

  1. 1

    Zuerst festhalten, was die Meldung wirklich sagt: Beim Lesen von Zeile 15 passte etwas nicht zu dem, was das System dort erwartet hat.

  2. 2

    Weil Zeile 15 für sich genommen korrekt aussieht, muss die Erwartung falsch sein, und die entsteht aus dem, was davor stand.

  3. 3

    Also die Zeilen 14, 13, 12 rückwärts prüfen, und zwar gezielt auf: fehlende schließende Klammer, nicht geschlossenes Anführungszeichen, fehlendes Semikolon, nicht beendeter Block.

  4. 4

    Häufiger Fund: In Zeile 12 fehlt eine schließende Klammer. Das System liest deshalb die folgenden Zeilen noch als Teil des Ausdrucks aus Zeile 12 und stolpert erst in Zeile 15 über etwas, das dort nicht hineinpasst.

  5. 5

    Nach dem Beheben einmal neu prüfen lassen, bevor man weitersucht. Oft verschwinden mit dieser einen Klammer alle Folgemeldungen.

Die gemeldete Zeile ist der Stolperpunkt, nicht zwingend die Ursache. Rückwärts nach unabgeschlossenen Konstrukten suchen.

Einen logischen Fehler einkreisen

Ein Programm soll den Durchschnitt von vier Noten berechnen. Bei 2, 3, 1, 2 gibt es 1,5 aus statt 2,0. Finde den Fehler systematisch.

  1. 1

    Erwartung notieren: (2+3+1+2):4=8:4=2,0(2+3+1+2) : 4 = 8 : 4 = 2{,}0. Ausgegeben wird 1,5.

  2. 2

    Rückwärts rechnen: Welche Summe ergäbe 1,5 bei Division durch 4? Es wäre 6. Welcher Divisor ergäbe 1,5 bei Summe 8? Es wäre ungefähr 5,33, also keine glatte Zahl.

  3. 3

    Die glatte 6 ist der wahrscheinlichere Fall. Vermutung: Die Summe stimmt nicht, es fehlt eine 2.

  4. 4

    Zwischenstand ausgeben lassen: Nach der wird die Summe angezeigt. Sie beträgt tatsächlich 6.

  5. 5

    Ursache prüfen: Die Schleife läuft offenbar nur dreimal statt viermal. Typischer Grund ist eine Bedingung wie i < 4\texttt{i < 4} bei Start mit i := 1\texttt{i := 1}; dann sind es die Durchläufe 1, 2, 3. Richtig wäre i <= 4\texttt{i <= 4} oder Start bei 0.

  6. 6

    Eine Sache ändern, erneut testen: Jetzt kommt 2,0 heraus. Zusätzlich mit anderen Werten gegenprüfen, damit die Korrektur nicht nur zufällig passt.

Ein Durchlauf zu wenig, verursacht von der Vergleichsbedingung. Gefunden durch Rückwärtsrechnen und einen ausgegebenen Zwischenstand.

Typischer Fehler

„Es läuft ohne Fehlermeldung, also stimmt mein Programm.“

Eine ausbleibende Meldung sagt nur: Es wurde keine Regel der Sprache verletzt und es ist nichts abgestürzt. Über die Richtigkeit des Ergebnisses sagt sie nichts, denn das System kennt deine Absicht nicht.

Das ist derselbe Umkehrschluss wie bei der Prüfziffer im Kapitel zur Nachrichtenübertragung: Aus „keine Fehlermeldung“ folgt nicht „richtig“. Ein Programm, das statt der Fläche den Umfang berechnet, läuft tadellos.

Der einzige Beleg für Richtigkeit ist ein Testfall mit unabhängig bekanntem Ergebnis. Rechne von Hand vor, was herauskommen muss, und vergleiche. Und prüfe dabei nicht nur den Normalfall: Die Fehler sitzen an den Rändern, also bei 0 Werten, bei genau einem Wert, bei leerer Eingabe und beim größten erlaubten Wert.

Übung 1

leicht

Welche Fehlerart liegt vor?

a) Eine Klammer wurde nicht geschlossen. b) Das Programm teilt bei bestimmten Eingaben durch null und bricht ab. c) Die berechnete Fläche eines Rechtecks ist immer doppelt so groß wie erwartet. d) Ein Schlüsselwort wurde falsch geschrieben.

Tipp anzeigen

Frage: Wird etwas gemeldet, und wenn ja, wann?

Lösung anzeigen

a) (vor dem Start gemeldet) b) Laufzeitfehler (Abbruch während der Ausführung) c) Logischer Fehler (läuft durch, Ergebnis falsch) d) Syntaxfehler

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    Nach dem Zeitpunkt ordnen, nicht nach der Schwere

    Die drei Fehlerarten unterscheiden sich darin, wann sie auffallen. Syntaxfehler: schon vor dem Start, das System meldet sie. Laufzeitfehler: während der Ausführung, das Programm bricht ab. Logischer Fehler: gar nicht, das Programm läuft durch und liefert ein falsches Ergebnis.

  2. 2

    a) und d): Verstöße gegen die Sprachregeln

    Eine nicht geschlossene Klammer und ein falsch geschriebenes Schlüsselwort verstoßen beide gegen die Form der Sprache. Das System kann den Text gar nicht erst deuten und meldet den Fehler vor dem Start: Syntaxfehler.

  3. 3

    b) Der Abbruch während der Ausführung

    Die Division durch null ist im Programmtext einwandfrei geschrieben, der Fehler entsteht erst, wenn eine bestimmte Eingabe den Nenner auf null bringt. Das Programm läuft an und bricht dann ab: Laufzeitfehler.

  4. 4

    c) Der stille Fehler: richtig gerechnet, falsch gedacht

    Die berechnete Fläche ist immer doppelt so groß wie erwartet. Nichts wird gemeldet, das Programm läuft vollständig durch und liefert eine schön aussehende Zahl. Nur die Zahl stimmt nicht: logischer Fehler.

Übung 2

mittel

Ein Programm soll die Zahlen von 1 bis nn aufsummieren, gibt aber für n=5n = 5 den Wert 10 statt 15 aus.

summe := 0
i := 1
SOLANGE i < n WIEDERHOLE
  summe := summe + i
  i := i + 1
ENDE SOLANGE
SCHREIBE summe

a) Finde den Fehler durch eine Wertetabelle. b) Benenne die Fehlerart. c) Korrigiere den Fehler auf zwei verschiedene Arten. d) Nenne zwei Testfälle, mit denen du die Korrektur prüfst.

Tipp anzeigen

Zähle in der Tabelle mit, wie oft der Rumpf tatsächlich läuft.

Lösung anzeigen

a) Wertetabelle für n=5n = 5:

Durchlaufi vorherBedingung i<5i < 5summe nachheri nachher
11wahr12
22wahr33
33wahr64
44wahr105
55falschAbbruch

Der Rumpf läuft nur viermal; die 5 wird nie addiert.

b) Ein logischer Fehler. Das Programm ist formal einwandfrei, läuft vollständig durch und liefert eine falsche Zahl.

c) Erste Möglichkeit: Bedingung zu i≤ni \le n ändern. Zweite Möglichkeit: Bedingung zu i<n+1i < n + 1 ändern. Beide bewirken denselben zusätzlichen Durchlauf.

d) Erster Test: n=5n = 5 muss 15 ergeben. Zweiter Test als Randfall: n=1n = 1 muss 1 ergeben; die alte Fassung hätte hier 0 geliefert. Sinnvoll ist zusätzlich n=0n = 0 mit dem Ergebnis 0.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    Erwartung und Beobachtung gegenüberstellen

    Bevor man sucht, schreibt man auf, was herauskommen müsste. Ohne diese Zahl kann man nicht einmal sicher sagen, dass ein Fehler vorliegt.

    1+2+3+4+5 = 15 \quad\text{erhalten: } 10

    Zwischenergebnis

    Es fehlen genau 5, also vermutlich der letzte Summand.

    Die Differenz ist oft schon der Hinweis: Fehlt genau der größte Wert, deutet das auf einen Durchlauf zu wenig.

  2. 2

    Den Ablauf sichtbar machen

    Statt zu raten, wird der Ablauf in einer Tabelle mitgeschrieben: für jeden Durchlauf der Wert von ii, das Ergebnis der Bedingung und die neuen Werte. Entscheidend ist die Spalte mit der Bedingung.

    Zwischenergebnis

    Beim fünften Anlauf ist i=5i = 5 und die Bedingung 5<55 < 5 ist falsch. Der Rumpf läuft also nur viermal.

  3. 3

    Die Ursache benennen

    Der Fehler steckt im Vergleichsoperator. Mit << wird der letzte Wert ausgeschlossen, gebraucht wird aber ein Vergleich, der ihn einschließt. Solche Abweichungen um genau eins sind der häufigste Schleifenfehler überhaupt.

    Zwischenergebnis

    i < n\texttt{i < n} muss zu i <= n\texttt{i <= n} werden.

  4. 4

    Korrektur absichern

    Eine Korrektur ist erst dann belegt, wenn sie an mehreren Fällen hält, besonders an den Rändern. Ein Randfall ist hier n=1n = 1: Es darf genau ein Durchlauf stattfinden.

    n = 1 \Rightarrow \text{summe} = 1 \qquad n = 0 \Rightarrow \text{summe} = 0

    Zwischenergebnis

    Beide Randfälle stimmen, also war die Änderung richtig und nicht nur zufällig passend.

Übung 3

schwer

Ein Programm berechnet den Notendurchschnitt einer Klasse. Es funktioniert bei den Tests der Entwicklerin einwandfrei, stürzt im Schulalltag aber gelegentlich ab.

a) Nenne drei mögliche Ursachen und ordne jeweils die Fehlerart zu. b) Welche Testfälle hätte die Entwicklerin zusätzlich prüfen müssen? c) Erkläre, warum „es lief bei mir“ kein Nachweis für Fehlerfreiheit ist. d) Beschreibe, wie du bei einem Absturz, den du nicht nachstellen kannst, überhaupt anfängst.

Tipp anzeigen

Zu a): Was passiert an dem Tag, an dem noch keine Note eingetragen ist?

Lösung anzeigen

a) Erstens: Die Klasse hat noch keine Noten, die Summe wird durch 0 geteilt. Laufzeitfehler. Zweitens: Eine Note wurde als Text eingetragen, etwa „krank“, und lässt sich nicht in eine Zahl umwandeln. Laufzeitfehler. Drittens: Eine ungültige Note wie 7 wird mitgerechnet, das Programm läuft durch und liefert einen unsinnigen Durchschnitt. Logischer Fehler.

b) Mindestens: leere Notenliste, genau eine Note, ungültige Werte (0, 7, negativ), nicht numerische Einträge, sehr viele Noten und alle Noten gleich.

c) Weil ein einzelner erfolgreicher Durchlauf nur zeigt, dass dieser eine Fall funktioniert. Aus „kein Fehler bei meinen Eingaben“ folgt nicht „kein Fehler bei allen Eingaben“; das ist derselbe unzulässige Umkehrschluss wie bei einer bestandenen Prüfziffer. Ein Test kann Fehler nachweisen, ihre Abwesenheit aber nicht beweisen.

d) Zuerst sammeln, statt am Quelltext zu ändern: Was genau war eingegeben worden, wann trat es auf, welche Meldung erschien? Dann versuchen, den Fehler mit diesen Angaben nachzustellen, denn was man nicht auslösen kann, kann man nicht prüfen. Hilft das nicht, baut man an kritischen Stellen Ausgaben oder ein Protokoll ein und wartet auf das nächste Auftreten. Erst wenn der Fehler zuverlässig auslösbar ist, beginnt das Einkreisen durch Halbieren.

Detaillierte Schritterklärung anzeigen

Hier wird jeder Schritt einzeln erklärt, vor allem, warum er gemacht wird.

Erklärungstiefe

✦ Empfohlen: Standard – Die normale Erklärungstiefe passt zum Einstieg.

  1. 1

    a) Ursachen an den Randfällen suchen, nicht im Normalbetrieb

    Drei Ursachen mit ihrer Fehlerart: Erstens, die Klasse hat noch keine Noten, es wird durch 0 geteilt: Laufzeitfehler. Zweitens, eine Note wurde als Text eingetragen, etwa „krank“, und lässt sich nicht umwandeln: Laufzeitfehler. Drittens, eine ungültige Note wie 7 wird mitgerechnet, das Programm läuft durch und liefert einen unsinnigen Durchschnitt: logischer Fehler.

  2. 2

    b) Testfälle systematisch statt nach Gefühl wählen

    Zu prüfen wären mindestens: leere Notenliste, genau eine Note, ungültige Werte (0, 7, negativ), nicht numerische Einträge, sehr viele Noten und alle Noten gleich. Das sind keine ausgedachten Beispiele, sondern die Ränder des Wertebereichs.

  3. 3

    c) Warum „es lief bei mir“ nichts beweist

    Weil ein einzelner erfolgreicher Durchlauf nur zeigt, dass dieser eine Fall funktioniert. Aus „kein Fehler bei meinen Eingaben“ folgt nicht „kein Fehler bei allen Eingaben“. Ein Test kann Fehler nachweisen, ihre Abwesenheit aber nicht beweisen.

  4. 4

    d) Vorgehen bei einem Absturz, den man nicht nachstellen kann

    Zuerst Informationen sammeln, statt am Quelltext zu ändern: Was war eingegeben worden, wann trat es auf, welche Meldung erschien? Dann versuchen, den Fehler damit nachzustellen, was man nicht auslösen kann, kann man nicht prüfen. Hilft das nicht, baut man an kritischen Stellen ein Protokoll ein und wartet auf das nächste Auftreten. Erst wenn der Fehler zuverlässig auslösbar ist, beginnt das Einkreisen durch Halbieren.

Zusammenfassung

Der Weg vom Plan zum lauffähigen Programm führt über drei Phasen: Entwerfen, Implementieren, Reflektieren. Fehler treten in drei Arten auf. verletzen die Formregeln und werden vor dem Start gemeldet, Laufzeitfehler brechen die Ausführung bei bestimmten Eingaben ab, logische Fehler lassen das Programm durchlaufen und liefern falsche Ergebnisse, ohne dass jemand etwas meldet. Eine Fehlermeldung nennt Ort und Art, wobei die Ursache oberhalb der genannten Zeile liegen kann; man behebt immer nur den ersten Fehler und prüft dann erneut. Logische Fehler findet man durch Einkreisen: zuverlässig auslösen, Erwartung aufschreiben, Zwischenstände ausgeben, den Bereich halbieren und immer nur eine Sache ändern. Getestet wird mit Normalfall und Randfällen, denn ein fehlerfreier Lauf ist kein Beweis für Richtigkeit.