Tutorium 9¶
Gruppen 5 und 7
Samuel Teuber
propa@teuber.dev
https://teuber.dev/propa
Übungsblätter¶
- Fragen?
- Probleme?
- Zu schwierig?
Aufgabe 1 - Tester¶
even(0).
even(X) :- X>0, X1 is X-1, odd(X1).
odd(1).
odd(X) :- X>1, X1 is X-1, even(X1).
Was passiert, wenn man hier ?even(X) aufruft?
Aufgabe 1 - Generator¶
even(0).
even(X) :- odd(Y), X is Y+1, X>0.
odd(1).
odd(X) :- even(Y), X is Y+1, X>1.
Was passiert, wenn man hier ?odd(7) aufruft?
Wie unterscheidet sich das zu ?odd(8)?
Aufgabe 1 - Teil 2¶
Was passiert, wenn bei den Generatoren die Teilziele X>0 und X>1 weggelassen werden?
even(0).
even(X) :- odd(Y), X is Y+1, X>0.
odd(1).
odd(X) :- even(Y), X is Y+1, X>1.
X>1: Reerfüllung vonodd(1)übereven(0), damit auchevenreerfüllbarX>0: Überflüssig
Aufgabe 1 - Ausführungsbaum¶
Aufgabe 2¶
del1([],_,[]).
del1([X|T1],X,L2) :- !, del1(T1,X,L2).
del1([Y|T1],X,[Y|T2]) :- del1(T1,X,T2).
del2([],_,[]).
del2([X|T1],X,L2) :- del2(T1,X,L2).
del2([Y|T1],X,[Y|T2]) :- del2(T1,X,T2), not(X=Y).
del3([X|L],X,L).
del3([Y|T1],X,[Y|T2]) :- del3(T1,X,T2).
Anfrage: deli([1,2,1],X,L).
del1bricht nach erster erfüllbaren Belegung ab:X=1,L=[2]del2ist fürXreerfüllbar:X=1,L=[2]; X=2,L=[1,1]del3ist reerfüllbar und löscht nur ein Vorkommen:X=1,L=[2,1]; X=2,L=[1,1]; X=1,L[1,2]
Aufgabe 2 - Teil 2¶
del1([],_,[]).
del1([X|T1],X,L2) :- !, del1(T1,X,L2).
del1([Y|T1],X,[Y|T2]) :- del1(T1,X,T2).
del2([],_,[]).
del2([X|T1],X,L2) :- del2(T1,X,L2).
del2([Y|T1],X,[Y|T2]) :- del2(T1,X,T2), not(X=Y).
del3([X|L],X,L).
del3([Y|T1],X,[Y|T2]) :- del3(T1,X,T2).
deli(L, 2, [1, 3]).: Nur 3
deli([1, 2, 3], X, [1, 3]).: Nur 2 und 3 (wegen Cut)
deli([1, 2, 3, 2], X, [1, 3]).: Nur 2
deli([1, 2, 3, 2], X, [1, 2, 3]).: Nur 3
deli([1|L], 1, X).: Alle
Aufgabe 2 - Freie Variablen¶
?fv(app(abs(x, abs(y, app(app(x,z), 17))), u), F).
F = [z,u]
Wir brauchen Regeln für jede mögliche Komponente:
- Zahl
- Atom
- Abstraktion
- Applikation
fv(X,[]) :- integer(X).
fv(X,[X]):- atom(X).
fv(abs(X,Y),R) :- fv(Y,L), del2(L,X,R).
fv(app(X,Y),R) :- fv(X,L1), fv(Y,L2), append(L1, L2, R).
Eine Substitution wird überall, einmal, gleichzeitig durchgeführt!
Gleichungssysteme¶
$$ X_1 = X_2\\ X_2 = X_3\\ X_3 = X_4 $$Welche Substitution $\sigma$, damit das Gleichungssystem gültig ist? (1 min)
- Mit $X=Z$ $$ f(A,B,C)=f(X_1,X_2,X_3) $$
- Kann nur garantiert werden, wenn: $$ A=X_1\\ B=X_2\\ C=X_3 $$
- Unifikator: $$ \{X_1⇨A, X_2⇨B, X_3⇨C\}\circ \{X⇨f\left(A,B,C\right), Z⇨f\left(X_1,X_2,X_3\right)\} $$
- Zusammengefasst ergibt das: $$ \{X_1⇨A, X_2⇨B, X_3⇨C, X⇨f\left(A,B,C\right), Z⇨f\left(A,B,C\right)\} $$
ABER: $$ \gamma = \{B⇨A, C⇨A\} \circ \sigma $$
$\sigma$ ist allgemeiner als $\gamma$
Wir nennen $\sigma$ den most general unifier (mgu), wenn für alle Unifikatoren $\gamma$ gilt es gibt einen zugehörigen Unifikator $\theta$, sodass: $$ \gamma = \theta \circ \sigma $$
Wie finden wir den mgu?
Algorithmische Lösung: Robinson¶
function unify(C) {
if (C.empty()) {
return []
} else {
(T1 = T2) := C.pop()
if (T1 == T2)
{ return unify(C) }
else if (T1.isVar() && !T2.isFree(T1))
{ return compose( unify([T1->T2]C), [T1->T2]) }
else if (T2.isVar() && !T1.isFree(T2))
{ return compose( unify([T2->T1]C), [T2->T1]) }
else {
f(X1,...,XN) := T1
g(Y1,...,YN) := T2
if (g != f) { fail(); }
else { return unify( C+[X1=Y1,...,XN=YN]) }
}
}
}
Übung zu manueller Ausführung von Robinson
Geldwechselmaschine¶
Aufgabe und Lösung: https://pp.info.uni-karlsruhe.de/lehre/WS201819/paradigmen/uebung/blaetter/blatt8-zusatz-solutions.pdf
remove([(C,N)|Coins],C,[(C,N1)|Coins]) :- N > 0, N1 is N - 1.
remove([(C,N)|Coins],C1,[(C,N)|CoinsNew]) :- remove(Coins,C1,CoinsNew).
put([],X,[(X,1)]).
put([(W,A)|T],W,[(W,A1)|T]) :- !, A1 is A+1.
put([(W,A)|T],X,[(W,A)|T1]) :- put(T,X,T1).
change(0,_,[]).
change(X, Coins, ChangeNew) :-
remove(Coins, C, CoinsNew),
X>=C, Xnew is X-C,
change(Xnew, CoinsNew, Change),
put(Change, C, ChangeNew).
QUERYSTART
change(100, [(50,2),(20,2),(10,1),(5,3)], R)
QUERYEND