Einf. in das Symbolische Programmieren Fr, 24.5.2002 Anwesenheitsaufgabe: Laenge von Wegen in (kreisfreien) Graphen --------------------------------------------------------------- Wir veraendern die Definition von weg/2 so, dass auch die Lange von Wegen beruecksichtigt wird. Dazu benutzen wir ein dreistelliges Praedikat, weg(X,Y,N), bei dem in N die Anzahl der durchlaufenen Kanten auf einem Weg von X nach Y steht. In Prolog kann man Zahlen (Zeichenfolgen aus Ziffern 0-9) durch N is M + K bzw. N is M - K vergleichen bzw. N berechnen, *wenn* M und K Ziffernfolgen sind oder die Variablen M und K durch Zahlen belegt sind. (Die Beweissuche ist so ausgebaut, dass sie die Zahlen M und K addiert und N mit dem Ergebnis belegt bzw. vergleicht.) Um die Laenge eines Weges zu beruecksichtigen, definieren wir nun: weg(X,X,0). % Wege der Laenge 0. (wurden in weg/2 nicht erlaubt) weg(X,Y,N) :- % Ein Weg von X nach Y hat Laenge N, wenn kante(X,Z), % es eine Kante von X nach einem Punkt Z und Weg(Z,Y,M), % einen Weg der Laenge M von Z nach Y gibt, N is M + 1. % so dass N = M + 1 ist. a) Kommentiere den Text aus, sichere die Datei und lade sie in Prolog. b) Prolog meldet einen Fehler. Versuche die Fehlermeldung zu verstehen und beseitige den Fehler. Teste das korrigierte Programm an weg(1,1,N) und weg(1,7,N). c) Benutze den tracer, um die Berechnung (Beweissuche) zu ?- weg(1,7,N). zu verstehen, d.h. selbst am Suchbaum nachvollziehen zu koennen. d) Man kann eine interaktive Sitzung auf auf eine Datei ausgeben. Rufe in Prolog apropos(protocol). auf, um herauszufinden, wie das geht. Oder benutze das SWI-Handbuch aus dem Web, vgl. die Kursseite http://www.cis.uni-muenchen.de/~leiss/symbolischesProgrammieren-01/ Erzeuge ein Protokoll der Beweissuche zu ?- weg(1,7,N). auf die Datei mit dem Namen wegProtokoll.