Algorithmus/Korrektheit/Invarianzprinzip/Bemerkung

Von der Beschreibung eines Algorithmus, d.h. der präzisen Festlegung der einzelnen auszuführenden Rechenschritte, ist die Begründung für die Korrektheit des Algorithmus zu unterscheiden. Mit Korrektheit meint man, dass der Algorithmus wirklich das leistet, was er verspricht, also dass beispielsweise das schriftliche Additionsverfahren wirklich die beiden Zahlen addiert. Für diesen Nachweis braucht man einen mathematischen Beweis, der sowohl auf die zu berechnende mathematische Struktur (die Addition) als auch auf die Festlegungen des Algorithmus Bezug nimmt.

Ein wichtiger Aspekt bei vielen Algorithmen, der bei einem solchen Beweis hilft, ist ein Invarianzprinzip. Bei einem Algorithmus werden typischerweise mehrere Zwischenergebnisse berechnet und weiterverarbeitet. Insbesondere bei rekursiven Definitionen und bei der maschinellen Durchführung werden Zwischenergebnisse auch überschrieben. Dennoch ist zu jedem Zeitpunkt des Ablaufes die volle Information in einer bestimmten Weise in den Zwischenergebnissen repräsentiert. Wenn man beipielsweise zwei zehnstellige Zahlen schriftlich addiert, und die hinteren fünf Endziffern der Summe und den letzten Übertrag schon berechnet hat, so kann man die hinteren Endziffern der Summanden vergessen. Die Information, was berechnet werden soll, steckt vollständig (invariant) in den vorderen Ziffern der Summanden, den hinteren Ziffern der Summe und dem einen Übertrag drin.