Prolog

Bachelor Grundlagen der Logik in der Informatik
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Prolog
Hallo,

ich habe das mit den Listen in Prolog noch nicht ganz verstanden:
Warum ergibt bei folgenden Regeln:

test([[A,N]|Rest]) :- test([Rest]), N = 0.
test([[]]).

die Anfrage

test([[1,0],[2,0]]).

false

wohingegen folgendes:

test([[1,0],2,0]).

true ergibt?

Vielen Dank :).

3 
test([[1,0],[2,0]) 
 -> A = 1
 -> N = 0
 -> Rest = [[2,0]]
test([Rest])
 -> test([[[2,0]]])

und das matcht dann keine der Regeln

[Head|Tail] gibt dir in Head das erste Element und in Tail die komplette letzte Liste

4

Tip: gib im Interpreter (zumindest in swipl geht das so) „trace.“ ein, dann teilt er dir die einzelnen Backtrackingschritte mit. Abschalten mit „nodebug.“

5

Dankeschön.

Ich hab noch eine Frage zur nächsten Hausaufgabe. Spielt die Effizienz meines Algorithmus eine Rolle? D.h. dass mein Programm true liefert, wenn die Anfrage korrekt war. Auf meinem betagten Rechner erhalte ich aber die Meldung: “ERROR: Out of local stack” ;), sobald ich eine Variable in die Anfrage mit einbaue. Oder geht es hier rein um die theoretische Berechenbarkeit des Programms?

6

Dein Algorithmus scheint in diesem Fall eine Laufzeit in „O(∞)“ zu haben :wink: Mit anderen Worten: du läufst anscheinend in eine Endlosrekursion … das ist nicht ineffizient, sondern nicht terminierend.
Was ist denn die „theoretische Berechenbarkeit des Programms“?

7

Ja, du hast recht. Ich hab meinen Fehler gefunden. Hab einfach viel zu kompliziert gedacht.

8

Bei Blatt 6 hatten wir diese Tiefensuche in Prolog.
Wenn ich z.B. so einen Fakt habe wie kante(erlangen, nuernberg), dann sollte eine Anfrage wie kante(nuernberg, erlangen) ja ebenfalls true zurückgeben.

kante(erlangen, nuernberg).
% Gibt es keine Kante von X nach Y, dann schau, ob eine von Y nach X existiert.
kante(X, Y) :- \+kante(X, Y), kante(Y, X).

Das läuft allerdings scheinbar auf eine Endlosrekursion hinaus.

?- kante(nuernberg, erlangen).
ERROR: Out of local stack

Wie kriegt man das in den Griff, ohne zusätzliche Paramter einzufügen?

9

Mir fällt leider kein Möglichkeit dir einen großartig Tipp zu geben, ohne zu spoilern.

Vielleicht hilft es dir wenn du versuchst nachzuvollziehen, wieso das in eine Endlosrekursion läuft. (Notfalls die Traces anschalten)
Ein Parameter wäre sicherlich eine Möglichkeit dem vorzubeugen, allerdings weder elegant, noch möglich ohne die Schnittstelle verändern zu müssen (bzw. ohne auch hier zu spoilern hint).
Also was machst du stattdessen? :wink:

10

Ja, ich versteh schon, warum das endlos läuft.
Am liebsten würde ich eine Turingmaschine M_Drumherum bauen, die das Prolog Programm schrittweise ausführt und die Rekusion kontrolliert abbricht. :smiley:
Darf man sich eigentlich Hilfsprädikate definieren?

11

noch ne andere Frage: dürfen wir Sachen für Fallunterscheidungen wie das hier verwenden, oder läuft das unter implizite Prologfunktionen?

min([X], X).
min([H|T], R) :-min(T, M),(H < M → R = H ; R = M).