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.