Terminierungsfunktionsdefinition (Algorithmen)

Question

Eine Frage zur Definition von Terminierungsfunktionen.

Wir haben eine relativ einfache Funktion zur Berechnung ⌊log₂ n⌋ eines Eingangs.

LOG2 
Configuration: {[r, n] | Integers r ≥ 0 and n ≥ 1} 
[r, n] -> [r + 1, n/2] if n > 1 ∧ n even 
[r, n] -> [r, n − 1] if n > 1 ∧ n odd 

Und wir gefragt werden, ob einige Terminierungsfunktionen μ (r, n) korrekt sind.

• μ (r, n) = n korrekt ist: die Endbedingung der Funktion ist, wenn n = 1 , wie an diesem Punkt r = ⌊log₂ n₀⌋.

• Jedoch ist μ (r, n) = 2n + r anscheinend auch richtig.

• Weiterhin μ (r, n) = n + r ist falsch

Es war mein Verständnis, dass die Terminierungsfunktion μ (r, n) war einfach die Variable, die die Funktionen Beendigung war abhängig von, (in diesem Fall n erreichen 1,) also warum ist 2n + r eine Terminierungsfunktion?

Was ist die genaue Definition der Abschlussfunktion μ (r, n) in diesem Zusammenhang?

Answer 1

Die Abschlussfunktion μ muss für die Zustände, in denen die Schleife eingegeben wird, positiv sein und bei jeder Iteration streng abnehmen. Das, plus die wohlgeordnete Natur der natürlichen Zahlen stellt sicher, dass Ihre Schleife immer beendet wird. (Beachten Sie, dass es nicht erforderlich ist, dass μ (s) = 1 für s, die die Schleife beendet wird, nur, dass es immer pro Iteration abnimmt.)

Das Problem bei der Auswahl μ (r, n) = n + r ist, daß für n = 2 , haben wir

• n sogar
• n> 1

und so ist der Übergang [r, n] -> [r + 1, n/2] gültig. in diesem Fall würden wir

verringern müssen jedoch nicht

μ(r',n') =   Definition of r' and n' 
μ(r+1,n/2) =  Definition of μ 
r + 1 + n/2 =  Rearrange via n = 2 
r + 2 = 
r + n =   Definition of μ 
μ(r, n) 

so μ nicht streng.