Per Potentialfunktion Terminierung zeigen

Question

(Potentialfunktion)

Zeigen Sie mithilfe einer geeigneten Potentialfunktion \( \phi \), dass der folgende rekursive Algorithmus für beliebige Eingaben \( a, b, c \in \mathbb{N} \) terminiert.

Algorithmus 1: UNKNOWN \( (a, b, c) \)
if \( a-b<c \) then
  return 1
if \( a \bmod 2=0 \) then
  return \( 1+\operatorname{UNKNOWN}(a / 2, b, c) \)
if \( b \bmod 2=0 \) then
  return \( 1+\operatorname{UnkNOWN}(a, b / 2, c) \)
return \( 1+\operatorname{UNKNOWN}(a, b, c+1) \)

Problem/Ansatz:

Ich finde keine potentialfunktion und weiß nicht wie ich die Terminierung zeigen kann. Ich bedanke mich schon im Voraus für die Hilfe :)

Comments

Beim 1 fall mit der rückgabe von 1 ist es klar, im zweiten fall wird a immer kleiner und im 3 fall wird b immer kleiner, also sollten auch diese terminieren.

Im letzten Fall wird jedoch c größer?!?

---

In Deinen Überlegungen sollte was mit ner Potentialfunktion vorkommen - was wurde dazu in der Vorlesung gesagt?

---

Die aufgabe gehört eher zur stacklounge!

Answer 1

Um die Terminierung des Algorithmus UNKNOWN\(a, b, c\) zu zeigen, verwenden wir eine Potentialfunktion, die sicherstellt, dass jeder rekursive Aufruf den "Fortschritt" des Algorithmus hin zur Terminierung misst. Die gewählte Potentialfunktion kombiniert die Reduktion der Eingabewerte \(a\) und \(b\) durch Division mit der schrittweisen Erhöhung von \(c\).

Potentialfunktion: \( \phi(a, b, c) = \lfloor \log_2(a) \rfloor + \lfloor \log_2(b) \rfloor + c \)

Analyse der Rekursionsfälle:

Terminierungsfall \((a - b < c)\):

Der Algorithmus terminiert sofort, da die Bedingung erfüllt ist.
Fall: \(a\) ist gerade:

Der Algorithmus ruft UNKNOWN\((a/2, b, c)\) auf.
Die Potentialfunktion verringert sich um mindestens 1: \( \lfloor \log_2(a/2) \rfloor = \lfloor \log_2(a) - 1 \rfloor \leq \lfloor \log_2(a) \rfloor - 1 \)
Somit gilt: \(\phi(a/2, b, c) < \phi(a, b, c)\).
Fall: \(b\) ist gerade:

Der Algorithmus ruft UNKNOWN\((a, b/2, c)\) auf.
Analog zu Fall 2 verringert sich die Potentialfunktion um mindestens 1: \( \lfloor \log_2(b/2) \rfloor = \lfloor \log_2(b) - 1 \rfloor \leq \lfloor \log_2(b) \rfloor - 1 \)
Somit gilt: \(\phi(a, b/2, c) < \phi(a, b, c)\).
Fall: \(a\) und \(b\) sind ungerade:

Der Algorithmus ruft UNKNOWN\((a, b, c + 1)\) auf.
Die Potentialfunktion erhöht sich um 1: \( \phi(a, b, c + 1) = \phi(a, b, c) + 1 \)
Jedoch wird \(c\) schrittweise erhöht, bis \(a - b < c\) gilt. Da \(a\) und \(b\) fest bleiben, terminiert dieser Fall nach endlich vielen Schritten.  
Begründung der Terminierung:

Die Potentialfunktion \(\phi(a, b, c)\) ist durch die endliche Anzahl der möglichen Divisionen von \(a\) und \(b\) durch 2 sowie die lineare Erhöhung von \(c\) nach unten beschränkt.
Jeder rekursive Aufruf reduziert entweder \(\phi(a, b, c)\) \(Fälle 2 und 3\) oder erhöht \(c\) kontrolliert \(Fall 4\), bis die Terminierungsbedingung erreicht wird.
Da \(\phi(a, b, c)\) in jedem Schritt entweder strikt abnimmt oder nur begrenzt ansteigt, terminiert der Algorithmus garantiert.
Fazit: Die Potentialfunktion \(\phi(a, b, c)\) zeigt, dass der Algorithmus für alle natürlichen Zahlen \(a, b, c\) terminiert. Jeder rekursive Aufruf verringert entweder die Größe von \(a\) oder \(b\) oder erhöht \(c\) schrittweise, bis die Bedingung \(a - b < c\) erfüllt ist.

\({Der Algorithmus terminiert für alle } a, b, c \in \mathbb{N}.\)