Wann heißt ein Algorithmus korrekt?

Erklärung: Korrektheit ist eine Aussage über ALLE Eingaben, gemessen an der Spezifikation — nicht über die getesteten Fälle und nicht über das bloße Durchlaufen.

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

Erklärung: Falsch — Tests können die Anwesenheit von Fehlern zeigen, niemals ihre Abwesenheit. Schon die sechste Eingabe kann den Fehler treffen.

Was bedeutet es, dass ein Algorithmus terminiert?

Erklärung: Terminierung heißt nicht „schnell", sondern „überhaupt irgendwann fertig" — für jede Eingabe, nicht nur für manche.

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?

Erklärung: 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.

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.

Erklärung: 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.

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.

Erklärung: 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.

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

Erklärung: Korrektheit und Effizienz sind getrennte Eigenschaften. Erst wenn ein Verfahren korrekt ist, lohnt der Vergleich der Laufzeiten.

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?

Erklärung: 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.

Ein Algorithmus kann terminieren und trotzdem ein falsches Ergebnis liefern.

Erklärung: Richtig — Terminierung und Korrektheit sind unabhängig. Ein Verfahren kann sauber stoppen und dennoch das Falsche berechnet haben.

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

Erklärung: 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.

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

Erklärung: 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.

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

Erklärung: 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.

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

Erklärung: 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.

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?

Erklärung: 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.

Aufgabe 1 von 14