Prolog: Listen

Listen

Bisher sprach ich stets über Prädikate mit einzelnen Variablen. Zur Verwaltung einer Vielzahl von Variablen ist es in Prolog möglich Listen zu nutzen. Ich werde diese anhand von Sortieralgorithmen einführen.

Rekursion

Rekursionen sind den Schleifen gleichzusetzen. Sie haben lediglich den kleinen Unterschied inne, ein großes Problem in viele kleine zu zerlegen, und schließlich ein kleinstes Teilproblem zu finden, welches lösbar ist. Dieses kleinste Problem stellt den Rekursionsabbruch dar.

Übungen

Übung 3

Gegeben sei folgende Prolog-Datenbasis:

ist_Nachbar_von(schneider, schmidt).
ist_Nachbar_von(schmidt, schneider).
ist_Nachbar_von(meier, schmidt).
ist_Nachbar_von(schmidt, meier).
ist_Nachbar_von(meier, mueller).    
ist_Nachbar_von(mueller, meier).
ist_Nachbar_von(mueller, petram).
ist_Nachbar_von(petram, mueller).
ist_Nachbar_von(petram, kringel).
ist_Nachbar_von(kringel, petram).
wohnt_in(schneider, hauptstrasse).
wohnt_in(schmidt, hauptstrasse).
wohnt_in(meier, hauptstrasse).
wohnt_in(mueller, dorfstrasse).
wohnt_in(petram, dorfstrasse).
wohnt_in(kringel, bahnhofstrasse).
wohnt_in(fischer, bahnhofstrasse).

und das Prädikat

sind_bekannt(X,Y) :- wohnt_in(X, _strasse), wohnt_in(Y, _strasse).
sind_bekannt(X,Y) :- ist_Nachbar_von(X,Y).

Es sei die folgende Anfrage gegeben:

?- sind_bekannt(kringel, fischer).

a) Gib zu dieser Anfrage den vollständigen Prolog-Abarbeitungsbaum inklusive aller erfolgreichen und fehlschlagenden Pfade an.

b) Markiere in a) alle Pfade, die zum Beweisbaum der Anfrage gehören, also alle Pfade, die zur Erfüllung der Anfrage führen.