imported>Früchtebrot: Belege fehlen

2019-06-26T21:08:42Z

Belege fehlen

Neue Seite

{{Belege}}
Unter einer '''Rangfunktion''' (englisch ''ranking function'') versteht man in der [[Informatik]] eine Funktion mit Werten in den [[natürliche Zahl|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 [[euklidischer Algorithmus|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
* <math> r = |a -b| </math>
eine Rangfunktion.

[[Kategorie:Theoretische Informatik]]

Rangfunktion (Informatik) - Versionsgeschichte

imported>Früchtebrot: Belege fehlen