Universita ̈t Rostock Prof. Thomas Kirste Dr. Christian Rosenke Sophie Wallner
Sommersemester 2021 Logische Programmierung 3. Juli 2021
Hausaufgaben, Serie 6
• Es gibt drei Aufgaben und pro Aufgabe ko ̈nnen Sie maximal zehn Punkte erhalten.
• Die Bearbeitung dieser Hausaufgaben soll in Gruppen von mindestens drei bis ho ̈chs- tens fu ̈nf Teilnehmenden erfolgen und bis zum 15.07.2021, 23:59 Uhr elektronisch in Form von PDF- und Textdateien bei der StudIP-Veranstaltung 23189 ( ̈Ubung) Logische Programmierung eingereicht werden.
• Alle eingereichten Dateien mu ̈ssen alle Gruppenmitglieder auflisten. Der Upload soll jeweils nur durch ein Gruppenmitglied in dessen Hausaufgabenordner erfolgen. Wir fu ̈hren die Statistik u ̈ber erreichte Punkte intern fu ̈r alle Teilnehmenden unabha ̈ngig von der Gruppe. Uploads in eine andere Veranstaltung, das falsche Verzeichnis oder im falschen Format erhalten keine Beachtung.
• Handschriftliche und anschließend digitalisierte Ausarbeitungen mu ̈ssen mit blauem oder schwarzem Stift erfolgen. Die Arbeit mit einem Textsatzsystem, wie z. B. LATEX wird empfohlen. Abgaben, die gut lesbar und pra ̈zise formuliert sind, erhalten einen Zusatzpunkt.
• Die Ru ̈ckgabe bewerteter Hausaufgaben erfolgt u ̈ber den Feedback-Ordner der oder des einreichenden Gruppenteilnehmenden. Bitte organisieren Sie die Weitervertei- lung an alle anderen Teilnehmenden der Gruppe selbststa ̈ndig.
Aufgabe 1 (Differenzlisten, Operatoren)
In dieser Aufgabe ko ̈nnen Sie mit Differenzlisten eine weitere Technik zur Effizienzsteige- rung von Prolog-Programmen erproben. Differenzlisten stellen eine Mo ̈glichkeit dar, auf das Ende einer Liste in Prolog direkt zugreifen zu ko ̈nnen. Die append-Operation kann dadurch effizienter realisiert werden, wie es die Vorlesung anhand des append-dl/3-Pra ̈di- kats vorfu ̈hrt.
a) Nuzten Sie den Vorteil von Differenzlisten, indem Sie die folgende ineffiziente Imple- mentierung von umgekehrt/2 zu einem neuen Pra ̈dikat umgekehrt-dl/2 umschreiben, dessen zweites (Ergebnis-) Argument eine Differenzliste ist.
1 2
b) Die Implementierung von umgekehrt(L, R) in Teilaufgabe (a) erlaubt es auch, zu jeder umgekehrten Liste R, wie z.B. R = [c, b, a], die urspru ̈ngliche Liste L zu bestimmen, d. h., im Beispiel L = [a, b, c]. Verwenden Sie trace/0, um heraus- zufinden, warum Ihr Code mit der Anfrage
?- umgekehrt-dl(L, [c, b, a |E]-E).
kein sinnvolles Ergebnis L liefert. Erkla ̈ren Sie in ho ̈chstens zwei Sa ̈tzen, welchen Fehler Prolog hier begeht, der zu dem falschen Ergebnis fu ̈hrt.
3 Punkte
3 Punkte
umgekehrt([], []).
umgekehrt([H|T], R) :- umgekehrt(T, L), append(L, [H], R).
Bitte wenden!
c) Ko ̈nnen Sie einen Vorschlag machen, wie man das Problem aus Teilaufgabe (c) lo ̈sen ko ̈nnte?
d) Verwenden Sie op/3 zur Erweiterung Ihrer Lo ̈sung um einen nichtassoziativen Ope- rator spiegelt, bei dem X spiegelt Y gilt, wenn Y die umgekehrte Liste von X ist.
Aufgabe 2 (Dynamische Pr ̈adikate und Pr ̈adikate 2. Stufe)
Das folgende Pra ̈dikat dient der Berechnung von Fibonacci-Zahlen:
1 2 3 4 5 6
2 Punkte
2 Punkte
fibonacci(0, 0) :- !.
fibonacci(1, 1) :- !.
fibonacci(N, F) :- N > 1, P is N-1, PP is N-2,
fibonacci(P, PF),
fibonacci(PP, PPF),
F is PF + PPF.
a) Testen Sie auf Ihrem Computer, bis zu welcher Eingabe N die Anfrage ?- fibonacci(N, F).
innerhalb von einer Sekunde ein Ergebnis liefert.
b) Verwenden Sie trace/0 bei der Anfrage
?- fibonacci(5, F).,
um sich die Ursache fu ̈r die schwerfa ̈llige Berechnung des Pra ̈dikats fibonacci/2
zu erkla ̈ren. Beschreiben Sie Ihre Erkenntnisse kurz in maximal zwei Sa ̈tzen.
c) Es gibt mehrere Mo ̈glichkeiten, die Effizienz von fibonacci/2 deutlich zu verbes- sern. Hier sollen Sie die Systempra ̈dikate dynamic/1 und assert/1 benutzen, um das Problem zu beheben, das Sie in Teilaufgabe (b) identifiziert haben.
d) Erweitern Sie Ihr Fibonacci-Programm unter Verwendung von findall/3, einem Pra ̈dikat 2. Stufe, um ein Pra ̈dikat fibonacciSequenz(N, S), das jede gegebene Zahl N mit der Liste S der ersten N Fibonacci-Zahlen in Relation setzt.
1 Punkt
3 Punkte
4 Punkte
2 Punkte
Aufgabe 3 (Suchprobleme)
Die Gefahr bei ged ̈achnisloser Suche unter Verwendung des Prolog-Inferenzprozesses ist der Abstieg in einen sich unendlich wiederholenden Ast des SLD-Baums. Wir haben das in Serie 2 der Hausaufgaben beim 15-Puzzle beobachtet.
Um dieses Problem zu lo ̈sen, mu ̈ssen Prolog-Programme mit einem Ged ̈achnis ausgestattet werden, damit so eine unendliche Rekursion erkannt werden kann.
a) Erweitern Sie das Pra ̈dikat spiel/2 aus Teilaufgabe 3 (c) in Serie 2 der Hausaufga- ben mit Hilfe eines dynamischen Pra ̈dikats um ein Geda ̈chnis. Testen Sie spiel/2 anschließend auf eine korrekte Funktionsweise und dokumentieren Sie diese.
Hinweis: Weil das 15-Puzzle in der Gro ̈ßenordnung von 1013 Spielstellungen hat, sollen Sie Ihr Pra ̈dikat zug/2 fu ̈r den Test auf das 8-Puzzle beschra ̈nken, was weniger als 400000 Spielstellungen hat.
4 Punkte
b) Lo ̈sen Sie das folgende Ra ̈tsel mit einem Suchverfahren:
6 Punkte
Drei Missionare stehen mit drei Kannibalen am Nordufer eines Flusses. Um ihn zu u ̈berqueren, k ̈onnen sie ein Boot benutzen, das aber h ̈ochstens drei Personen zugleich tr ̈agt. Bei der U ̈berquerung du ̈rfen niemals Kanni- balen in der U ̈berzahl sein, weder im Boot, noch am einen oder am anderen Ufer. Sonst besteht die Gefahr, dass sie ihren alten Sitten folgen und ein Festmahl bereiten. Wie kommen die Missionare mit ihren G ̈asten heil ans andere Ufer?
Gehen Sie dabei wie in Serie 2 der Hausaufgaben vor, indem Sie ein Pra ̈dikat zug(X, Y) implementieren, das zwei direkt aufeinanderfolgende Zust ̈ande X und Y in Relation setzt. Anschließend sollen Sie dies zu einem Pra ̈dikat spiel(X, Y, Acc) erweitern, wobei der Accumulator Acc die Aufgabe des Geda ̈chnisses u ̈bernehmen soll.