Hausübung 4, Aufgabe 2

PaddyG
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 9. Okt 2009 10:29

Hausübung 4, Aufgabe 2

Beitrag 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ß

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: Hausübung 4, Aufgabe 2

Beitrag 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.

PaddyG
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 9. Okt 2009 10:29

Re: Hausübung 4, Aufgabe 2

Beitrag 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ß

Christoph Walther
Dozentin/Dozent
Beiträge: 86
Registriert: 1. Nov 2005 18:51

Re: Hausübung 4, Aufgabe 2

Beitrag 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".

PaddyG
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 9. Okt 2009 10:29

Re: Hausübung 4, Aufgabe 2

Beitrag 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ß

Nathan Wasser
Kernelcompilierer
Kernelcompilierer
Beiträge: 430
Registriert: 16. Okt 2009 09:48

Re: Hausübung 4, Aufgabe 2

Beitrag 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.

Christoph Walther
Dozentin/Dozent
Beiträge: 86
Registriert: 1. Nov 2005 18:51

Re: Hausübung 4, Aufgabe 2

Beitrag 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.

PaddyG
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 9. Okt 2009 10:29

Re: Hausübung 4, Aufgabe 2

Beitrag 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ß

Antworten

Zurück zu „Archiv“