Korrektheit und Terminierung von Algorithmen

Correctness and Termination of Algorithms

Informatik Klasse 11 14 Aufgaben
InformatikAlgorithmenKorrektheitKerncurriculum

Korrektheit heißt, für JEDE zulässige Eingabe das spezifizierte Ergebnis zu liefern — Tests können Fehler zeigen, aber nie Fehlerfreiheit belegen; „bei fünf Tests richtig = korrekt" ist ein Fehlschluss. Terminierung heißt, für jede Eingabe nach endlich vielen Schritten zu stoppen, begründet über eine Größe, die in jedem Durchlauf schrumpft und eine untere Grenze nicht unterschreiten kann. Beide sind Eigenschaften des Algorithmus jenseits seines Codes und getrennt von der Effizienz; auf ihnen ruht später das Halteproblem.

Voraussetzungen (1)

Programme Schritt für Schritt verfolgen
Klasse 9
›

Ermöglicht (1)

Grenzen der Berechenbarkeit — das Halteproblem
Klasse 12
›
Leicht
Multiple Choice #1 18s ▶ Testen

Wann heißt ein Algorithmus korrekt?

  • ● Wenn er für jede zulässige Eingabe das in der Aufgabenstellung geforderte Ergebnis liefert
  • ○ Wenn er bei allen bisher ausprobierten Eingaben richtig war
  • ○ Wenn er ohne Fehlermeldung durchläuft
Korrektheit ist eine Aussage über ALLE Eingaben, gemessen an der Spezifikation — nicht über die getesteten Fälle und nicht über das bloße Durchlaufen.
Wahr / Falsch #2 12s ▶ Testen

Ein Programm, das bei fünf Testfällen das richtige Ergebnis liefert, ist damit als korrekt nachgewiesen.

✓ Falsch
Falsch — Tests können die Anwesenheit von Fehlern zeigen, niemals ihre Abwesenheit. Schon die sechste Eingabe kann den Fehler treffen.
Multiple Choice #3 15s ▶ Testen

Was bedeutet es, dass ein Algorithmus terminiert?

  • ● Er stoppt für jede Eingabe nach endlich vielen Schritten
  • ○ Er läuft höchstens eine Sekunde
  • ○ Er gibt am Ende eine Meldung aus
Terminierung heißt nicht „schnell", sondern „überhaupt irgendwann fertig" — für jede Eingabe, nicht nur für manche.
Lückentext #4 15s ▶ Testen

Ein gängiges Terminierungsargument: In jedem Schleifendurchlauf wird eine Größe echt kleiner und kann eine feste Grenze nicht unterschreiten — also endet die Schleife nach ___ vielen Schritten.

✓ Antwort: endlich
Eine Größe, die pro Durchlauf schrumpft und nach unten beschränkt ist, kann nur endlich oft schrumpfen — das ist das Standardargument für Terminierung.
Multiple Choice #5 18s ▶ Testen

Ein Sortierverfahren ist blitzschnell, sortiert aber gelegentlich falsch. Ein zweites ist langsam, sortiert aber immer richtig. Welche Aussage passt?

  • ● Nur das zweite ist korrekt — Geschwindigkeit ersetzt keine Korrektheit
  • ○ Das erste ist besser, weil Effizienz wichtiger ist
  • ○ Beide sind korrekt, nur unterschiedlich effizient
Korrektheit und Effizienz sind getrennte Eigenschaften. Erst wenn ein Verfahren korrekt ist, lohnt der Vergleich der Laufzeiten.
Wahr / Falsch #6 12s ▶ Testen

Ein Algorithmus kann terminieren und trotzdem ein falsches Ergebnis liefern.

✓ Wahr
Richtig — Terminierung und Korrektheit sind unabhängig. Ein Verfahren kann sauber stoppen und dennoch das Falsche berechnet haben.
Lückentext #7 12s ▶ Testen

Tests können die Anwesenheit von Fehlern zeigen, aber niemals ihre ___.

✓ Antwort: Abwesenheit
Der klassische Satz von Dijkstra. Für Fehlerfreiheit bräuchte man ein Argument über alle Eingaben — etwa eine Begründung entlang der Fälle des Algorithmus.
Wahr / Falsch #8 15s ▶ Testen

Ob eine Schleife terminiert, kann man immer schon an ihrer Bedingung ablesen, ohne den Schleifenkörper anzusehen.

✓ Falsch
Falsch — es kommt darauf an, ob der KÖRPER die Größen der Bedingung Richtung Abbruch bewegt. Bedingung und Körper müssen zusammen betrachtet werden.
Multiple Choice #9 15s ▶ Testen

Spezifikation: „Gib den Durchschnitt der Liste aus.“ Ein Programm läuft für [2, 4, 9] ohne Fehlermeldung durch und gibt 4 aus. Was folgt?

  • ● Es ist für diese Eingabe falsch.
  • ○ Es ist korrekt, denn es lief ohne Fehler.
  • ○ Es ist für alle Eingaben falsch.
Der Durchschnitt von 2, 4 und 9 ist 15 : 3 = 5, nicht 4. Ein Programm kann fehlerfrei durchlaufen und trotzdem das Falsche berechnen: Der Maßstab für Korrektheit ist die Spezifikation, nicht die Abwesenheit von Abstürzen. Ob es auch bei anderen Eingaben falsch rechnet, zeigt dieser eine Test nicht — er widerlegt nur die Korrektheit.
Mittel
Multiple Choice #1 25s ▶ Testen

Schleife A: SOLANGE n > 0: n = n − 1. Schleife B: SOLANGE n > 0: m = m − 1. Welche terminiert für jede Startzahl n > 0 sicher?

  • ● Nur A — dort schrumpft die geprüfte Größe n in jedem Durchlauf
  • ○ Nur B — dort wird m kleiner
  • ○ Beide, denn irgendwann ist jede Zahl bei 0
Entscheidend ist, dass sich die Größe aus der BEDINGUNG in jedem Durchlauf der Grenze nähert. In B bleibt n unverändert — die Bedingung bleibt für immer wahr.
Wahr / Falsch #2 20s ▶ Testen

Die Schleife SOLANGE n ≠ 1: wenn n gerade, n = n / 2, sonst n = 3n + 1 terminiert nachweislich für jede Startzahl — das ist mathematisch bewiesen.

✓ Falsch
Falsch — das ist die berühmte Collatz-Vermutung. Für alle je getesteten Zahlen stoppt die Schleife, aber ein Beweis für ALLE Zahlen fehlt bis heute. Terminierung kann eine echt schwere Frage sein.
Multiple Choice #3 25s ▶ Testen

Ein Algorithmus soll das Maximum einer Liste liefern. Bei der leeren Liste stürzt er ab. Die Spezifikation sagt: „Eingabe: eine nichtleere Liste." Ist der Algorithmus korrekt?

  • ● Ja — Korrektheit wird nur für die zulässigen Eingaben verlangt
  • ○ Nein — ein Absturz ist immer ein Korrektheitsfehler
  • ○ Nur, wenn er zusätzlich eine Fehlermeldung ausgibt
Korrekt heißt „erfüllt die Spezifikation". Was für unzulässige Eingaben passiert, regelt die Spezifikation — deshalb ist präzises Festlegen der Eingaben Teil der Arbeit.
Multiple Choice #4 20s ▶ Testen

Welche Eingabe ist der beste „Härtetest" für einen Algorithmus, der die kleinste Zahl einer Liste sucht?

  • ● Randfälle wie eine einelementige Liste oder lauter gleiche Zahlen
  • ○ Eine möglichst lange Liste mit zufälligen Zahlen
  • ○ Eine Liste, die schon aufsteigend sortiert ist
Fehler verstecken sich an den Rändern der Spezifikation — dort, wo Schleifen null- oder einmal laufen oder Vergleiche gleichauf enden. Zufällige „mittlere" Fälle decken das selten auf.
Multiple Choice #5 25s ▶ Testen

Die Schleife SOLANGE x ≠ 10: x = x + 3 wird mit x = 4 gestartet. Was passiert?

  • ● Sie terminiert — x läuft 4, 7, 10 und trifft die Bedingung
  • ○ Sie läuft endlos, weil x die 10 überspringt
  • ○ Sie stoppt sofort, weil 4 kleiner als 10 ist
Hier trifft x die 10 exakt. Vorsicht aber: Mit x = 5 gestartet (5, 8, 11, 14, …) würde dieselbe Schleife die 10 überspringen und nie enden — Ungleichheits-Bedingungen sind fragil.