Seite 1 von 1

Hausübung 4, Aufgabe 2

Verfasst: 23. Jan 2012 17:26
von PaddyG
Hallo,

eine Frage zu Maßtermen bei Aufgabe 2:

Wenn ich mehrere Maßterme habe (z.B.: max(x, y) und min(x, y)), ist es dann zwingend notwendig, dass der erste Maßterm im (ersten) rekursiven Aufruf unter den gegebenen Bedingungen ein ">" liefert und genau im zweiten rekursiven Aufruf ein "=", sodass dann der zweite Maßterm greifen kann (wie in der Lösung zu Gruppenübung 05), der anschließend ">" liefert? Oder ist die Reihenfolge egal, sprich:

Der erste Maßterm könnte auch im ersten Fall direkt "=" liefern und im zweiten ">" oder sogar zweimal "=" ?

Gruß

Re: Hausübung 4, Aufgabe 2

Verfasst: 23. Jan 2012 17:58
von dschneid
Welcher Maßterm für welchen rekursiven Aufruf kleiner wird oder gleich bleibt, ist egal. Es muss nur die gesamte Maßtermliste bezüglich der lexikographischen Ordnung für jede Terminierungshyptohese kleiner werden.

Re: Hausübung 4, Aufgabe 2

Verfasst: 23. Jan 2012 18:34
von PaddyG
D.h. in jeder Terminierungshypothese muss jeder Maßterm mindestens einmal kleiner werden (bzw. ">" erwirken), damit die gesamte Maßtermliste pro Terminierungshypothese kleiner wird?

Gruß

Re: Hausübung 4, Aufgabe 2

Verfasst: 23. Jan 2012 20:56
von Christoph Walther
PaddyG hat geschrieben:Wenn ich mehrere Maßterme habe (z.B.: max(x, y) und min(x, y)), ist es dann zwingend notwendig, dass der erste Maßterm im (ersten) rekursiven Aufruf unter den gegebenen Bedingungen ein ">" liefert ...
Ja. Zum beispiel kann die terminierung von

function f(x : ℕ, y : ℕ) : ℕ <=
if x > y
then f(⁻(x), ⁺(y))
else if ?0(x) then 13 else f(x, ⁻(y)) end_if
end_if

mit der maßtermliste "x, y" gezeigt werden. Mit "y, x" klappt es nicht, also ist "Der erste Maßterm könnte auch im ersten Fall direkt "=" liefern und im zweiten ">" oder sogar zweimal "=" ?" falsch.
PaddyG hat geschrieben: ... und genau im zweiten rekursiven Aufruf ein "=", sodass dann der zweite Maßterm greifen kann (wie in der Lösung zu Gruppenübung 05), der anschließend ">" liefert?
Nein, auch im 2. rekursiven aufruf ist ">" ok, da muß kein "=" herauskommen. Zum beispiel

function g(x : ℕ, y : ℕ) : ℕ <=
if x > y
then g(⁻(x), ⁺(y))
else if ?0(x)
then 13
else if ?0(⁻(x)) then g(⁻(x), ⁺(y)) else g(x, ⁻(y)) end_if
end_if
end_if

mit maßtermliste "x, y".

Re: Hausübung 4, Aufgabe 2

Verfasst: 24. Jan 2012 10:26
von PaddyG
Hallo,

viele Dank erstmal für die ausführliche Antwort, 2 Fragen stellen sich mir dann aber noch:

1. Steht das nicht im Gegensatz zu der Antwort von dschneid? Oder habe ich diese falsch interpretiert?

2. Könnten sie nochmal Bezug zu meinem zweiten Post nehmen, was ist die genaue Bedingung damit die gesamte Maßtermliste bezüglich der lexikographischen Ordnung für jede Terminierungshyptohese kleiner wird?

Gruß

Re: Hausübung 4, Aufgabe 2

Verfasst: 24. Jan 2012 11:13
von Nathan Wasser
Die Reihenfolge der Maßterme hat nichts mit der Reihenfolge der rekursiven Aufrufe zu tun. (Das war die Aussage von dschneid.)

Wenn ich nur einen Maßterm habe, so muss dieser für jeden rekursiven Aufruf kleiner werden. Wenn ich mehrere Maßterme habe, bilden diese eine lexikografische Ordnung:

(x1, ..., xn) > (y1, ..., yn) <=> x1 > y1 ODER (x1 = y1 UND (x2 > y2 ODER (... ich hoffe es ist klar wie es weiter geht ...)))

Eine Maßtermliste der Form m1, m2, m3 ist also für den Terminierungsbeweis einer Prozedur sinnvoll, wenn für jeden rekursiven Aufruf gilt:

1. m1 wird kleiner oder bleibt gleich
2. in den Fällen wo m1 gleich bleibt: m2 wird kleiner oder bleibt gleich
3. in den Fällen wo m1 und m2 gleich bleiben: m3 wird kleiner

Die Reihenfolge der Maßterme ist somit wichtig, da sie die lexikografische Ordnung bestimmt, hat aber nichts mit der Reihenfolge der rekursiven Aufrufe oder der Terminierungshypothesen zu tun.

Re: Hausübung 4, Aufgabe 2

Verfasst: 24. Jan 2012 11:20
von Christoph Walther
PaddyG hat geschrieben:Hallo,

viele Dank erstmal für die ausführliche Antwort, 2 Fragen stellen sich mir dann aber noch:

1. Steht das nicht im Gegensatz zu der Antwort von dschneid? Oder habe ich diese falsch interpretiert?

2. Könnten sie nochmal Bezug zu meinem zweiten Post nehmen, was ist die genaue Bedingung damit die gesamte Maßtermliste bezüglich der lexikographischen Ordnung für jede Terminierungshyptohese kleiner wird?

Gruß
Die maßtermliste wird nicht kleiner. Mit maßtermen gibt man an, was genau "gemessen" wird. Bei einem binärbaum kann man z.B. die anzahl aller knoten messen, die anzahl aller inneren knoten, die anzahl aller blätter, die tiefe des baums usw. Will man terminierung einer prozedur zeigen, so muß man zunächst einmal herausbekommen, nach welchem "maß" die rekursiven aufrufe kleiner werden. Dieses "maß" formalisiert man dann durch einen maßterm bzw. eine maßtermliste.

Ich habe den eindruck, daß Sie noch nicht verstanden haben, was genau terminierung bedeutet und wie dies bewiesen werden kann. Sie sollten sich noch einmal genau die vorlesungsunterlagen & übungen anschauen, bevor Sie an die lösung der praktikumsaufgaben gehen.

Re: Hausübung 4, Aufgabe 2

Verfasst: 24. Jan 2012 11:45
von PaddyG
Alles klar, viele Dank dafür :)

Im Übrigen geht es nicht um das Praktikum, sondern um die Hausübung.
Und die Aussage, dass die Maßtermliste kleiner wird, kam initial auch nicht von mir, sondern von Ihrem Tutor:
dschneid hat geschrieben:Welcher Maßterm für welchen rekursiven Aufruf kleiner wird oder gleich bleibt, ist egal. Es muss nur die gesamte Maßtermliste bezüglich der lexikographischen Ordnung für jede Terminierungshyptohese kleiner werden.
Dass die Maßterme ansich einfach nur angeben, was genau bemessen wird, war mir schon klar. Mich hatte nur obige Formulierung verwirrt.
Da bin ich wohl nicht der Einzige, der sich das nochmal genauer anschauen muss ;)

Des Weiteren ging es auch nicht um die Reihenfolge der Maßterme an sich, wie glaube ich von Ihnen in Ihrem Post vermutet (z.B.: "x,y" oder "y,x"), entschuldigung falls das falsch rüberkam, sondern (wie von Nathan richtig erkannt) um einen von mir, aufgrund der (Beispiel)Lösung der Gruppenübung 5, falsch vermuteten Zusammenhang zwischen der lexikografischen Ordnung der Maßterme und der Reihenfolge der rekusiven Aufrufe bzw. der Terminierungshypothesen.

Die Formulierung "Es muss nur die gesamte Maßtermliste ... kleiner werden" hatte mich dann ein wenig verwirrt, da, wie schon von Ihnen angemerkt, die Maßtermliste an sich ja nicht kleiner wird, sondern anhand der lexikografischen Ordnung "abgearbeitet" wird.

Vielen Dank auf jeden Fall für die Antworten!

Gruß