[Hilfeeee plz] Terminierungsbeweis Informatik

Lieber Besucher, herzlich willkommen bei: MastersForum. Falls dies Ihr erster Besuch auf dieser Seite ist, lesen Sie sich bitte die Hilfe durch. Dort wird Ihnen die Bedienung dieser Seite näher erläutert. Darüber hinaus sollten Sie sich registrieren, um alle Funktionen dieser Seite nutzen zu können. Benutzen Sie das Registrierungsformular, um sich zu registrieren oder informieren Sie sich ausführlich über den Registrierungsvorgang. Falls Sie sich bereits zu einem früheren Zeitpunkt registriert haben, können Sie sich hier anmelden.

OoK_Michi

Meister

Beiträge: 1 654

Wohnort: München

Beruf: GER

05.02.2008, 14:20

[Hilfeeee plz] Terminierungsbeweis Informatik

fun f (x, y) = if (x + y) < 0 then ~1 else 1 + f(x + 2, y - 3)

Beweisen Sie, dass die Berechnung von f(x, y) für alle Werte
(x, y) 2 Z × Z terminiert.

Dies soll mit Induktion bewiesen werden. Ich vermute mit Hilfe einer Abstiegsfunktion, aber genau davon habe ich keine Ahnung. Wie sucht man so eine Funktion und mit welchen Kriterien?

p.s der Code ist in SML NJ geschrieben aber betrachtet den ruhig als Pseudo-Code^^

Zum Seitenanfang

Sheep

Erleuchteter

Beiträge: 4 172

Beruf: GER

05.02.2008, 14:36

Du kannst die Induktion ganz normal über n laufen lassen. Nimm an, dass bei der n-ten Ausführung x + y < 0 ist (dort terminiert die Funktion ja), und zeige es für die n+1-ste Ausführung.

n-te Ausführung: x_n + y_n = x_0 + 2n + y_0 - 3n = x_0 + y_0 - n

Das n startet hier bei 0, x_0 und y_0 sind die Startargumente.

EDIT: Hoffe jetzt ist es auch einigermassen sauber.

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Sheep« (05.02.2008, 14:52)

Zum Seitenanfang

OoK_Michi

Meister

Beiträge: 1 654

Wohnort: München

Beruf: GER

05.02.2008, 15:10

Ich seh da irgendwo einen Sinn darin aber ich kann das nicht bis zum Schluss ausführen.

Hast du vll kurz Zeit mir das über ICQ oder ähnliches zu zeigen ?

Zum Seitenanfang