Korrektheit von Algorithmen

von itkramtyp

Eine Anforderung an eine Algorithmus ist die Korrektheit. Scheint selbstverständlich, ja.

„Mit dem Testen von Algorithmen und Computerprogrammen kann man das Vorhandensein von Fehlern beweisen, aber nicht die Abwesenheit von Fehlern.“ — Edsger Wybe Dijkstra

Weitgehend gilt ein Algorithmus als korrekt, wenn dieser die Eigenschaften der Endlichkeit und Determiniertheit erfüllt. Also mit dem aus der Eingabe resultierenden Ergebnis stoppt bzw. terminiert.

Genauer betrachtet wird dann noch zwischen „partieller Korrektheit“ und „totaler Korrektheit“ unterschieden.

Partiell korrekt gilt ein Algorithmus dann, wenn bei gültiger Eingabe das richtige Ergebnis berechnet wird. Von totaler Korrektheit wird dann gesprochen, wenn der Algorithmus dann auch noch terminiert.