Übung 4.4 a) b)

Benutzeravatar
plane
Computerversteher
Computerversteher
Beiträge: 337
Registriert: 21. Okt 2005 00:18

Übung 4.4 a) b)

Beitrag von plane »

Hi,

bei Aufgabe 4.4.
b)
muss es hier nicht
(m1,m2) relationssymbol (n1,n2)
statt
(n1,n2) relationssymbol (m1,m2)

oder muss es bei a) vielleicht
n relationssymbol m heissen
statt
m relationssymbol n...

bin gerade verwirrt...
viele grüße

xAx
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 157
Registriert: 6. Mär 2008 17:20

Re: Übung 4.4 a) b)

Beitrag von xAx »

4.4a) ist quatsch, denn die angegebene relation ist nicht fundiert. wahrsch. ein tippfehler.
Nichts ist wie es scheint!
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Zuletzt geändert von xAx am 14. Mär 2009 16:17, insgesamt 99-mal geändert.

Benutzeravatar
plane
Computerversteher
Computerversteher
Beiträge: 337
Registriert: 21. Okt 2005 00:18

Re: Übung 4.4 a) b)

Beitrag von plane »

Alles klar, habs beim Assistenten abgeklärt.
Muss n >(relationssymbol) m heissen
:D

Simon Siegler
Computerversteher
Computerversteher
Beiträge: 369
Registriert: 16. Apr 2007 09:12

Re: Übung 4.4 a) b)

Beitrag von Simon Siegler »

In a) muss \(n \succ m\) heißen, analog zu b).

Benutzeravatar
itportal2
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 236
Registriert: 25. Jan 2008 15:34
Wohnort: Darmstadt

Re: Übung 4.4 a) b)

Beitrag von itportal2 »

Beweisen Sie, dass die Prozedur total ist.
Wie beweißt man allgemein, dass eine Prozedur total ist? Muss man nicht erstmal beweißen, dass die Funktion für alle minimale Elemente definiert ist, und dann für alle nicht-minimale?

Benutzeravatar
Tigger
Kernelcompilierer
Kernelcompilierer
Beiträge: 404
Registriert: 26. Okt 2007 17:35
Wohnort: Hofheim
Kontaktdaten:

Re: Übung 4.4 a) b)

Beitrag von Tigger »

Naja erstmal musst du eine Relation angeben, auf die sich der Beweis stützt. Dann bildest du die Relationsbeschreibung. Bei einer terminierenden, rekursiven Prozedur muss die mindestens 2 atomare Relationsbeschreibungen haben. Eine hat keine Induktionshypothesen (also keine Vorgänger => minimale Elemente), und eine hat Induktionshypothesen (Menge der Vorgänger des Elements). Wenn beides vorhanden ist, ist die Funktion total (oder fehlt noch was?).

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

Re: Übung 4.4 a) b)

Beitrag von Christoph Walther »

itportal2 hat geschrieben: Wie beweißt man allgemein, dass eine Prozedur total ist? Muss man nicht erstmal beweißen, dass die Funktion für alle minimale Elemente definiert ist, und dann für alle nicht-minimale?
Mal zur begriffsbildung:
1. Eine Funktion kann total (oder auch nicht total ) sein.
2. Eine Prozedur (und allgemein ein Algorithmus) kann terminieren (oder auch nicht terminieren).

D.h., es gibt keine terminierenden funktionen und keine totalen prozeduren !

Und jetzt der zusammenhang zwischen Funktionen & Prozeduren:
1. Eine Prozedur P berechnet eine Funktion f_P.
2. Eine prozedur P terminiert genau dann, wenn die funktion f_P total ist.

Wie zeigt man, daß eine prozedur terminiert?
Das steht in Kapitel 8.

Wie zeigt man, daß eine funktion f total ist ?
Kommt darauf an wie f definiert ist. Falls f durch eine prozedur P berechnet wird, dann kann man das mit dem terminierungsbeweis für P beweisen. Das geht aber nicht immer, denn es gibt auch funktionen, die durch keine prozedur berechnet werden (=> Vorlesung Berechenbarkeit).

Antworten

Zurück zu „Archiv“