P1-WS04-MusterLoesung05.txt: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
fsrwiki_>Oddmuse Import K (link fix) |
K (2 Versionen) |
(kein Unterschied)
|
Aktuelle Version vom 5. November 2007, 07:50 Uhr
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.