Einf. in das symbolische Programmieren CIS, SS 2006, H.Leiss ================================================================= Abgabe: Donnerstag, Mi 24.5.06 bis 16.Uhr ----------------------------------------- Aufgabe 4 (Punkte 4) --------- Wir nehmen nochmal den endlichen, kreisfreien Graphen (G,kante) aus Aufgabe 2, wo G = {1,2,3,4,5,6,7} und kante(X,Y) angibt, daß X mit Y direkt Verbunden ist: kante(1,2). kante(1,3). kante(2,4). kante(2,5). kante(3,4). kante(4,7). kante(5,6). kante(6,7). Wir hatten die Definitionen von Wegen in einem Graphen durch weg(X,Y) :- kante(X,Y). weg(X,Y) :- kante(X,Z), weg(Z,Y). definiert und das in der Übungsstunde so zu weg/3 geändert, daß in der 3. Komponente die Länge des Wegs (= die Anzahl der durchlaufenen Kanten) ausgegeben wird: weg(X,Y,1) :- kante(X,Y). weg(X,Y,N) :- kante(X,Z), weg(Z,Y,K), N is K+1. Ändern Sie die Definition von weg/3 so zu weg/4, daß in einer 4. Komponente auch die Liste [xn,...,x1] der Punkte xi aus {1,2,...,7} ausgegeben wird, die auf dem jeweiligen Weg von x0 nach xn (in der Reihenfolge x1,x2,... ) besucht wurden (nach dem Startpunkt x0). Aufgabe 5 --------- Schreiben Sie ein Programm trenne(+Eingabeliste,-Zahlliste,-Liste von Termen, die keine Zahlen sind) das eine Eingabeliste in die Elemente, die Zahlen sind, und die, die keine Zahlen sind trennt. Um festzustellen, ob ein Term eine Zahl ist, benutze das Prädikat number(X) von Prolog. a) Einfach geht es so, daß die Elemente in den Ausgabelisten in der umgekehrten Reihenfolge wie in der Eingabeliste erscheinen, also z.B. Frage: ?- trenne([a,2,b,4,1,d,c],Zahlen,Nichtzahlen). Antwort: Zahlen = [1,4,2], Nichtzahlen = [c,d,b,a]) (Punkte 4) b) Könnes Sie es auch so, daß die Elemente in den Ausgabelisten in der gleichen Reihenfolge wie in der Eingabeliste erscheinen? Also wie bei Frage: ?- trenne([a,2,b,4,1,d,c],Zahlen,Nichtzahlen). Antwort: Zahlen = [2,4,1], Nichtzahlen = [a,b,d,c]) (Punkte 2) Aufgabe 6 --------- Verwenden Sie den eingebauten Tracer, um festzustellen, in welcher Reihenfolge Prolog welche Aufrufe von weg/4 und welche von kante/2 macht, wenn Sie mit Ihrem Programm zu Aufgabe 3 die Frage ?- weg(2,7,N,L). stellt. Genauer gesagt, machen Sie folgendes: a) Schauen Sie mit ?- apropos(trace). oder ?- help(trace)., wie man Prolog sagt, von welchen Prädikaten es Informationen über - Aufrufen (call) des Prädikats - Benutzen der nächsten passenden Klausel des Prädikats (redo) - Finden einer Lösung (exit) - Scheitern einer Beweissuche für den Aufruf (fail) ausgeben soll. b) Sagen Sie Prolog, es soll - für weg/4 die Aufrufe, das Benutzen den nächsten Klausel, und das Finden einer Lösung, - für kante/2 nur die Aufrufe und die gefundenen Lösungen melden. (Punkte 2) c) Geben Sie die Informationen an, die Prolog danach (nach c)) zur Frage ?- weg(2,7,N,L). ausgab. (Falls Ihr weg/4 nicht richtig funktioniert, nehmen Sie weg(1,4,N).) Verstehen Sie die Ausgabe des Tracers? (Punkte 2)