PatrickFey: 2 Versionen

2007-11-05T05:50:15Z

2 Versionen

← Nächstältere Version	Version vom 5. November 2007, 05:50 Uhr
(kein Unterschied)

fsrwiki_>Oddmuse Import: link fix

2007-11-05T05:49:25Z

link fix

← Nächstältere Version		Version vom 5. November 2007, 05:49 Uhr
Zeile 93:		Zeile 93:
	% sonst führen wir die Multiplikation auf die Addition zurück		% sonst führen wir die Multiplikation auf die Addition zurück
	% 5 Rekursion: xs(y)= (xy) + x, dazu führen wir den Zwischenwert		% 5 Rekursion: xs(y)= (xy) + x, dazu führen wir den Zwischenwert
	% im "IntermediateResult" mit.		% im "[[IntermediateResult]]" mit.
	mult(X,s(Y),R):- mult(X,Y,IR),add(X,IR,R).		mult(X,s(Y),R):- mult(X,Y,IR),add(X,IR,R).

fsrwiki_>1illig: antispam

2006-12-22T05:46:57Z

antispam

Neue Seite

<pre>
P1 WS2004/2005
Musterlösung zu Aufgabenblatt 5 - v0.3

Aufgabe 1
---------

a) Aufgabe: p(X,f) p(g,Y)
X=g, Y=f - Erfolgreich

b) Aufgabe: r(a(b(M),N)) r(a(b(K),m))
N=m, K=M - Erfolgreich

c) Aufgabe: h(A,c(C),C) h(B,B,a)
B=C(a), C=a, A=B=C(a) - Erfolgreich

d) Aufgabe: f(a(X),b,b(X)) f(a(Y),Y,b(a))
X=a, Y=b, aber X=Y ist nicht erfüllt - Nicht erfolgreich

e) Aufgabe: a(i(i(i(p))),i(P)) a(i(P),i(i(i(p))))
P=i(i(p)) - Erfolgreich

f) Aufgabe: t(T,t(T)) t(S,S)
S=T=t(T) - Erfolgreich, aber rekursiv

Aufgabe 2
---------
a)

% even(A). --ergibt yes, wenn A gerade ist.
% es werden immer genau zwei "Vorgänger" mit s(s(X)) gesucht
even(0).
even(s(s(X))):-even(X).

b)

% odd(A). --ergibt yes, wenn A ungerade ist.
% ähnlich wie bei even, werden auch hier immer zwei "Vorgänger"
% mit s(s(x)) gesucht, % aber der Rekursionsabschluss ist
% nicht 0, sondern s(0), es folgt also immer noch ein
% letzter, sozusagen "ungrader Schritt".
odd(s(0)).
odd(s(s(X))):-odd(X).

c)

% le(A,B). -- ergibt yes, wenn A kleiner gleich B ist.
le(X,X).
le(X,s(Y)):-le(X,Y).

%%% und gleich noch die Variante mit Typprüfung. Dazu wird
%%% zuerst der Typtest aus dem Script mit verwendet:

% peano(Term). -- Term ist ein Peano-Term.
peano(0).
peano(s(X)):-peano(X).

% le2(A,B) -- ergibt yes, wenn A kleiner gleich B ist und
% beides Peano-Terme sind.
le2(X,X):-peano(X).
le2(X,s(Y)):-le2(X,Y).

%%% Der Vergleich beider Varianten zeigt, dass le/2 den Vorteil
%%% hat, dass es schneller zu einem Ergebnis kommt, da der Fall,
%%% dass zwei gleiche Terme übergeben werden, sofort zu yes
%%% führt. In diesem Fall (der in der Rekursion immer auftritt,
%%% falls A <= B gilt), muss bei le2/2 noch die Rekursion von
%%% peano/1 durchgelaufen werden. Dadurch wird allerdings erreicht,
%%% dass nur Peano-Zahlen yes ergeben können, und nicht etwa auch
%%% le(s(muell),s(muell)).
%%% Interessant ist auch die Reaktion auf die vollständig
%%% uninstanziierte Anfrage: le/2 liefert nur teilinstanziierte
%%% Antworten, während le2/2 nur die vollständig instanziierten
%%% Fälle von Gleichheit erreicht.

d)

%%% Gefordert war eine Multiplikation, also sollte auch eine
%%% Multiplikation implementiert werden.

%add(Summand1,Summand2,Summe) aus dem Script:
add(0,X,X).
add(s(X),Y,s(R)):-add(X,Y,R).

%mult(A,B,C). -- multipliziert die Peanozahlen A und B, das
% Ergebnis ist C
% X*0=0
mult(X,0,0).
% Rekursionsabschluss: X*1=X
mult(X,s(0),X).
% sonst führen wir die Multiplikation auf die Addition zurück
% 5 Rekursion: x*s(y)= (x*y) + x, dazu führen wir den Zwischenwert
% im "IntermediateResult" mit.
mult(X,s(Y),R):- mult(X,Y,IR),add(X,IR,R).

%%% Nur für den Fall das jemand wissen will wie eine
%%% Subtraktion ginge: sub ist dann eigentlich dasselbe, wie
%%% add aus dem Script, nur die Argumentpositionen haben
%%% sich verändert. Man könnte schreiben: sub(X,Y,R):-add(Y,R,X).

%sub(A,B,C). -- subtrahiert die Peanozahlen A und B, das
% Ergebnis ist C oder 'no', wenn A-B<0.
sub(X,0,X).
sub(s(X),s(Y),R):-sub(X,Y,R).

Der Test ergab für Teilaufgabe a:
---------------------------------

?- even(0).
Yes
?- even(s(0)).
No
?- even(X).
X = 0 ;
X = s(s(0)) ;
X = s(s(s(s(0))))
Yes

Der Test ergab für Teilaufgabe b:
---------------------------------

?- odd(0).
No
?- odd(s(0)).
Yes
?- odd(X).
X = s(0) ;
X = s(s(s(0))) ;
X = s(s(s(s(s(0)))))
Yes

Der Test ergab für Teilaufgabe c:
---------------------------------

?- le(s(0),s(s(0))).
Yes
?- le(s(s(0)),s(s(0))).
Yes
?- le(s(s(s(0))),s(s(0))).
No
?- le(s(s(s(0))),s(s(s(0)))).
Yes
?- le(s(s(s(0))),s(s(s(s(0))))).
Yes
?- le(s(s(s(0))),s(s(s(s(s(0)))))).
Yes
?- le(0,0).
Yes
?- le(0,s(0)).
Yes
?- le(s(0),0).
No
?- le(s(s(0)),X).
X = s(s(0)) ;
X = s(s(s(0))) ;
X = s(s(s(s(0)))) ;
X = s(s(s(s(s(0))))) ;
X = s(s(s(s(s(s(0)))))) ;
X = s(s(s(s(s(s(s(0))))))) ;
X = s(s(s(s(s(s(s(s(0)))))))) ;
X = s(s(s(s(s(s(s(s(s(0))))))))) ;
X = s(s(s(s(s(s(s(s(s(s(...)))))))))) ;
Yes

?- le(X,s(s(s(0)))).
X = s(s(s(0))) ;
X = s(s(0)) ;
X = s(0) ;
X = 0 ;
No

?- le(s(muell),s(muell)).
Yes

Und nun le2:
------------
?- le2(0,0).
Yes
?- le2(s(0),s(s(0))).
Yes
?- le2(s(s(s(0))),s(s(0))).
No
?- le2(muell,s(muell)).
No
?- le2(s(muell),s(muell)).
No

Und nun noch der Trace:
-----------------------
?- trace(le2).
% le2/2: [call, redo, exit, fail]
Yes

[debug] ?- trace(peano).
% peano/1: [call, redo, exit, fail]
Yes

[debug] ?- le2(X,Y).
T Call: (7) le2(_G415, _G416)
T Call: (8) peano(_G415)
T Exit: (8) peano(0)
T Exit: (7) le2(0, 0)

X = 0
Y = 0 ;
T Redo: (8) peano(_G415)
T Call: (9) peano(_G480)
T Exit: (9) peano(0)
T Exit: (8) peano(s(0))
T Exit: (7) le2(s(0), s(0))

X = s(0)
Y = s(0) ;
T Redo: (9) peano(_G480)
T Call: (10) peano(_G482)
T Exit: (10) peano(0)
T Exit: (9) peano(s(0))
T Exit: (8) peano(s(s(0)))
T Exit: (7) le2(s(s(0)), s(s(0)))

X = s(s(0))
Y = s(s(0))

Yes

Der Test ergab für Teilaufgabe d:
--------------------------------

?- mult(s(s(s(s(0)))),s(s(s(s(0)))),X).
X = s(s(s(s(s(s(s(s(s(s(...))))))))))
Yes
?- mult(s(s(s(s(0)))),s(s(s(s(0)))),X),peano2int(X,N).
X = s(s(s(s(s(s(s(s(s(s(...))))))))))
N = 16
Yes
?- mult(s(s(s(s(0)))),s((0)),X),peano2int(X,N).
X = s(s(s(s(0))))
N = 4
Yes
?- mult(s(s(s(s(0)))),s(s(0)),X),peano2int(X,N).
X = s(s(s(s(s(s(s(s(0))))))))
N = 8
Yes
?- mult(s(s(s(s(0)))),0,X),peano2int(X,N).
X = 0
N = 0
Yes

Aufgabe 3
---------

peano2int(0,0).
peano2int(s(Peano),Number):-peano2int(Peano,Predecessor),Number is Predecessor+1.

Test:
(Peano -> Integer)
?- peano2int(s(s(s(s(0)))),X).

X = 4 ;

No

(Integer -> Peano)
?- peano2int(X,5).

X = s(s(s(s(s(0))))) ;
^C
Action (h for help) ? abort
% Execution Aborted

Es wird endlos weitergesucht. Das Prädikat ist also nicht
richtungsunabhängig.

Aufgabe 4
---------

In der Vorlesung und den Übungen sind u.a. die folgenden rekursiven
Bezugnahmen aufgetaucht:
- Mengen und deren rekursive Definition in EBNF
- Rekursive Datenstrukturen wie z.B. Peano-Zahlen
Diese beziehen sich nur auf die syntaktische Form.
- Rekursive Prädikate
Dieses sind rekursive Berechnungsvorschriften.
</pre>

P1-WS04-MusterLoesung05.txt - Versionsgeschichte

PatrickFey: 2 Versionen

fsrwiki_>Oddmuse Import: link fix

fsrwiki_>1illig: antispam