Logik:Klausuren/04.11.2004/2. Aufgabe
Inhaltsverzeichnis
1. Aufgabenstellung[Bearbeiten]
Ein Einbahnstra�ennetz zwischen Plätzen a, b, c, ... werde durch Fakten
$ von\_nach\ /2 $ beschrieben,
wobei $ von\_nach(\,P1,P2). $ besagt, dass eine Einbahnstraße von $ P1\, $ nach $ P2\, $ existiert.
$ von\_nach(a\,,b).\qquad \qquad von\_nach(a\,,c).\qquad \qquad von\_nach(b\,,d).\qquad \qquad von\_nach(b\,,e). $
$ von\_nach(b\,,f).\qquad \qquad von\_nach(k\,,e).\qquad \qquad von\_nach(c\,,g).\qquad \qquad von\_nach(c\,,e). $
$ von\_nach(e\,,h).\qquad \qquad von\_nach(e\,,i).\qquad \qquad von\_nach(h\,,j).\qquad \qquad von\_nach(l\,,k). $
das folgende Einbahnstra�ßnnetz beschrieben:
grafik
a)
Schreiben Sie ein auch auf andere Beispieldaten als die obigen anwendbares Prologprogramm
$ verbindung\ /2 $,
mit dem ermittelt werden kann, zwischen welchen Plaetzen es Verbindungen gibt.
Im oben angegebenen Beispiel sollte der Aufruf
$ ?-verbindung(\,a,j). $ die Antwort $ Yes\, $ liefern,
der Aufruf
$ ?-verbindung(\,j,a). $ dagegen $ No\, $.
b)
Natuerliche Zahlen koennen als iterierte Nachfolger der Zahl $ 0\, $ dargestellt werden,
$ d.h.\qquad 1=s(0)\,,\ 2=s(s(0))\,,\ 3=s(s(s(0)))\, $ usw.
Erweitern Sie Ihr unter a) angegebenes Programm dahingegehend, dass es zusaetzlich noch ermittelt, wieviele Plaetze auf der gesuchten Verbindung liegen, wobei die Anzahl in iterierter Zahlendarstellung anzugeben ist. Z.B. sollte der Aufruf
$ ?-knoten(\,a,j,A). $ das Ergebnis
$ A\,=s(s(s(s(s(0))))) $ liefern.
2. Lösung[Bearbeiten]
a)
$ verbindung\,(X,X). $
$ verbindung\,(X,Z):-von\_nach\,(X,Y)\,,verbindung\,(Y,Z).\, $
b)
$ knoten(X,X,s(0)).\ $
$ knoten(X,Y,Erg):-von\_nach\,(X,Z)\,,knoten(Z,Y,s(Erg)). $
3. Lösungsweg[Bearbeiten]
4. Alternativen/Diskussion/Hinweise etc.[Bearbeiten]
Im HnH-Forum wurde diskutiert, ob aufgrund der gegebenen Daten davon ausgegangen werden kann, ob es auch eine direkte Verbindung (z.B. ? verbindung(a,a)) gibt: Thread
Die offizielle Lösung sieht das nicht vor, demnach ist o.g. Lösung falsch.
Offizielle Lösung:
a)
$ verbindung\,(X,Y):-von\_nach\,(X,Y). $
$ verbindung\,(X,Z):-von\_nach\,(X,Y)\,,verbindung\,(Y,Z).\, $
