Rangfunktion (Informatik)

Unter einer Rangfunktion (englisch ranking function) versteht man in der Informatik eine Funktion mit Werten in den natürlichen Zahlen, die beim Lauf eines Algorithmus von Rechenschritt zu Rechenschritt monoton fällt. Diese Eigenschaft nutzt man aus, um die Terminierung des Algorithmus zu beweisen.

Einfaches Beispiel

Wir betrachten folgenden Algorithmus zur Addition zweier Zahlen:

sum (a, 0) = a
sum (a, b) = sum (incr (a), decr (b))

(hierbei bedeutet incr(a) die Erhöhung der Zahl a um 1 und decr(b) die Verminderung der Zahl b um 1).

In diesem Beispiel ist

• r = b

eine Rangfunktion, die in jedem Rechenschritt um 1 abnimmt.

Weiteres Beispiel

Eine Variante des klassischen euklidischen Algorithmus zur Berechnung des größten gemeinsamen Teilers ggT(a,b) ist diese rekursive Version: Wenn a > b ist, dann rufe ggT(a-b,b) auf. Wenn a < b ist, dann rufe ggT(a,b-a) auf. Mache dies solange, bis a und b gleich sind. a bzw. b sind dann der gemeinsame größte Teiler.

In diesem Beispiel ist

• r = | a − b |

eine Rangfunktion.