Programmierparadigmen Tutorium 2 & 5 - 8. Tutorium am 10...

LEHRSTUHL PROGRAMMIERPARADIGMEN

Programmierparadigmen Tutorium 2 & 58. Tutorium am 10./11.12.2018Roman Langrehr | 10./11.12.2018

KIT – Universität des Landes Baden-Württemberg und nationales Forschungszentrum in der Helmholtz-Gemeinschaft

www.kit.edu

Gleichheit in Prolog= bzw. \=: Unifizierbarkeit

X = Y gilt für uninstantiierte Variablen X, YX und Y sind dannach die selbe Variable.

== bzw. \==: Gleichheit der TermeX == Y gilt nicht für uninstantiierte Variablen X, YVerändert die Terme nicht: X \== Y, X = 5, Y = 5. isterfüllbar.

Ist not(not(X = Y)) äquivalent zu X = Y?Ist not(not(X == Y)) äquivalent zu X == Y?

not(not(X = Y)) ist nicht äquivalent zu X = Y.not(not(X = Y)) stellt nicht sicher, dass X und Y dannach dieselbe Variable sind.Beispiel:

not(not(X = Y)),X = 5 setzt X auf 5.X = Y,X = 5 setzt X und Y auf 5.

not(not(X == Y)) ist äquivalent zu X == Y.Die Prüfung X == Y verändert die Variablen nicht.

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 2

Gleichheit in Prolog= bzw. \=: Unifizierbarkeit

X = Y gilt für uninstantiierte Variablen X, YX und Y sind dannach die selbe Variable.

== bzw. \==: Gleichheit der TermeX == Y gilt nicht für uninstantiierte Variablen X, YVerändert die Terme nicht: X \== Y, X = 5, Y = 5. isterfüllbar.

Ist not(not(X = Y)) äquivalent zu X = Y?Ist not(not(X == Y)) äquivalent zu X == Y?

not(not(X = Y)) ist nicht äquivalent zu X = Y.not(not(X = Y)) stellt nicht sicher, dass X und Y dannach dieselbe Variable sind.Beispiel:

not(not(X = Y)),X = 5 setzt X auf 5.X = Y,X = 5 setzt X und Y auf 5.

not(not(X == Y)) ist äquivalent zu X == Y.Die Prüfung X == Y verändert die Variablen nicht.

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 2

Gleichheit in Prolog= bzw. \=: Unifizierbarkeit

X = Y gilt für uninstantiierte Variablen X, YX und Y sind dannach die selbe Variable.

== bzw. \==: Gleichheit der TermeX == Y gilt nicht für uninstantiierte Variablen X, YVerändert die Terme nicht: X \== Y, X = 5, Y = 5. isterfüllbar.

Ist not(not(X = Y)) äquivalent zu X = Y?Ist not(not(X == Y)) äquivalent zu X == Y?

not(not(X = Y)) ist nicht äquivalent zu X = Y.not(not(X = Y)) stellt nicht sicher, dass X und Y dannach dieselbe Variable sind.Beispiel:

not(not(X = Y)),X = 5 setzt X auf 5.X = Y,X = 5 setzt X und Y auf 5.

not(not(X == Y)) ist äquivalent zu X == Y.Die Prüfung X == Y verändert die Variablen nicht.

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 2

Gleichheit in Prolog= bzw. \=: Unifizierbarkeit

X = Y gilt für uninstantiierte Variablen X, YX und Y sind dannach die selbe Variable.

== bzw. \==: Gleichheit der TermeX == Y gilt nicht für uninstantiierte Variablen X, YVerändert die Terme nicht: X \== Y, X = 5, Y = 5. isterfüllbar.

Ist not(not(X = Y)) äquivalent zu X = Y?Ist not(not(X == Y)) äquivalent zu X == Y?

not(not(X = Y)) ist nicht äquivalent zu X = Y.not(not(X = Y)) stellt nicht sicher, dass X und Y dannach dieselbe Variable sind.Beispiel:

not(not(X = Y)),X = 5 setzt X auf 5.X = Y,X = 5 setzt X und Y auf 5.

not(not(X == Y)) ist äquivalent zu X == Y.Die Prüfung X == Y verändert die Variablen nicht.

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 2

Gleichheit in Prolog= bzw. \=: Unifizierbarkeit

X = Y gilt für uninstantiierte Variablen X, YX und Y sind dannach die selbe Variable.

== bzw. \==: Gleichheit der TermeX == Y gilt nicht für uninstantiierte Variablen X, YVerändert die Terme nicht: X \== Y, X = 5, Y = 5. isterfüllbar.

Ist not(not(X = Y)) äquivalent zu X = Y?Ist not(not(X == Y)) äquivalent zu X == Y?

not(not(X = Y)) ist nicht äquivalent zu X = Y.not(not(X = Y)) stellt nicht sicher, dass X und Y dannach dieselbe Variable sind.Beispiel:

not(not(X = Y)),X = 5 setzt X auf 5.X = Y,X = 5 setzt X und Y auf 5.

not(not(X == Y)) ist äquivalent zu X == Y.Die Prüfung X == Y verändert die Variablen nicht.

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 2

4-Färbbarkeit

farbe(blau).farbe(gelb).farbe(gruen).farbe(rot).

nachbar(X, Y) :- farbe(X), farbe(Y), X \= Y.

deutschland(VW02,VW03,VW04,VW05,VW06,VW07,VW08,VW09):- nachbar(VW04, VW05), nachbar(VW04, VW03), ...

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 3

Prolog Listen

[] – Leere Listen[X|XS] – Liste mit Listenkopf X und Restliste XS

Kurzschreibweise: [1,2,3]

Wichtige Funktionen:

member(X,[X|R]).member(X,[Y|R]) :- member(X,R).

append([],L,L).append([X|R],L,[X|T]) :- append(R,L,T).

reverse(X,Y) :- rev1(X,[],Y).rev1([],Y,Y).rev1([X|R],A,Y) :- rev1(R,[X|A],Y).

permutation([],[]).permutation([X|R],P) :- permutation(R,P1),

append(A,B,P1),append(A,[X|B],P).

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 4

Prolog Listen

[] – Leere Listen[X|XS] – Liste mit Listenkopf X und Restliste XS

Kurzschreibweise: [1,2,3]

Wichtige Funktionen:

member(X,[X|R]).member(X,[Y|R]) :- member(X,R).

append([],L,L).append([X|R],L,[X|T]) :- append(R,L,T).

reverse(X,Y) :- rev1(X,[],Y).rev1([],Y,Y).rev1([X|R],A,Y) :- rev1(R,[X|A],Y).

permutation([],[]).permutation([X|R],P) :- permutation(R,P1),

append(A,B,P1),append(A,[X|B],P).

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 4

Reguläre Ausdrücke

matches(epsilon,[]).

matches(C,[C]) :- atom(C), C \= epsilon.

matches(union(A,_),S) :- matches(A,S).matches(union(_,B),S) :- matches(B,S).

matches( ·(A,B),S) :- append(S1,S2,S), matches(A,S1),matches(B,S2).

matches(*(_),[]).matches(*(A),S) :- append(S1,S2,S), not(S1=[]),

matches(A,S1), matches(*(A),S2).

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 5

Wolf, Ziege, Kohl

gegenueber(links,rechts).gegenueber(rechts,links).

harmlos(_,X,Y) :- gegenueber(X,Y).harmlos(Ufer,Ufer,Ufer).

erlaubt((Mann,Ziege,Wolf,Kohl)) :-harmlos(Mann,Ziege,Wolf),harmlos(Mann,Ziege,Kohl).

fahrt((U,U,Wolf,Kohl), ’Ziege’, (UNeu,UNeu,Wolf,Kohl)):- gegenueber(U,UNeu).

fahrt((U,Ziege,U,Kohl), ’Wolf’, (UNeu,Ziege,UNeu,Kohl)):- gegenueber(U,UNeu).

fahrt((U,Ziege,Wolf,U), ’Kohl’, (UNeu,Ziege,Wolf,UNeu)):- gegenueber(U,UNeu).

fahrt((U,Ziege,Wolf,Kohl), ’leer’, (UNeu,Ziege,Wolf,Kohl)):- gegenueber(U,UNeu).

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 6

Wolf, Ziege, Kohl

erreichbar(S,_,[],S).erreichbar(S,Besucht,[Fahrt|Fahrten],Z) :-

fahrt(S,Fahrt,ZwischenS), erlaubt(ZwischenS),not(member(ZwischenS,Besucht)),erreichbar(ZwischenS,[ZwischenS|Besucht]Fahrten,Z).

lösung(Fahrten) :- start(S), ziel(Z),erreichbar(S,[],Fahrten,Z).

start((links,links,links,links)).ziel((rechts,rechts,rechts,rechts)).

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 7

Arithmetik in PrologArithmetische Funktionen sind wie Funktoren aber

werten zu einer Zahl auskönnen in Infix-Notation geschrieben werden

Vorsicht! Arithmetik in Prolog ist gewöhnungsbedürftig.

test(5).

?test(2+3) liefert false.(2+3) wird nicht automatisch ausgewertet.

is wertet rechtes Argument (arithmetischer Ausdruck) aus und vergleichtes mit dem linken.

Im rechten Term müssen alle Variablen instantiiert sein.

test(X) :- 5 is X.

?test(2+3) liefert true.

test(X) :- X is 5.

?test(2+3) liefert false.

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 8

Arithmetik in PrologArithmetische Funktionen sind wie Funktoren aber

werten zu einer Zahl auskönnen in Infix-Notation geschrieben werden

Vorsicht! Arithmetik in Prolog ist gewöhnungsbedürftig.

test(5).

?test(2+3) liefert false.(2+3) wird nicht automatisch ausgewertet.

is wertet rechtes Argument (arithmetischer Ausdruck) aus und vergleichtes mit dem linken.

Im rechten Term müssen alle Variablen instantiiert sein.

test(X) :- 5 is X.

?test(2+3) liefert true.

test(X) :- X is 5.

?test(2+3) liefert false.

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 8

Arithmetik in PrologArithmetische Funktionen sind wie Funktoren aber

werten zu einer Zahl auskönnen in Infix-Notation geschrieben werden

Vorsicht! Arithmetik in Prolog ist gewöhnungsbedürftig.

test(5).

?test(2+3) liefert false.(2+3) wird nicht automatisch ausgewertet.

is wertet rechtes Argument (arithmetischer Ausdruck) aus und vergleichtes mit dem linken.

Im rechten Term müssen alle Variablen instantiiert sein.

test(X) :- 5 is X.

?test(2+3) liefert true.

test(X) :- X is 5.

?test(2+3) liefert false.

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 8

Arithmetik in PrologArithmetische Funktionen sind wie Funktoren aber

werten zu einer Zahl auskönnen in Infix-Notation geschrieben werden

Vorsicht! Arithmetik in Prolog ist gewöhnungsbedürftig.

test(5).

?test(2+3) liefert false.(2+3) wird nicht automatisch ausgewertet.

is wertet rechtes Argument (arithmetischer Ausdruck) aus und vergleichtes mit dem linken.

Im rechten Term müssen alle Variablen instantiiert sein.

test(X) :- 5 is X.

?test(2+3) liefert true.

test(X) :- X is 5.

?test(2+3) liefert false.Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 8

Arithmetik in Prolog

=:= bzw. =\=: Arithmetische GleichheitBeide Seiten müssen vollständig instantiiert sein.

Tipp: is für Zuweisungen verwenden, =:= bzw. =\= für Überprüfungen.Analog funktionieren <, =<, > und >=.

Beispiel

powerof2(X) :- X =:= 1.powerof2(X) :- X > 1, 0 =:= X mod 2, Y is X div 2,

powerof2(Y).

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 9

Arithmetik in Prolog

=:= bzw. =\=: Arithmetische GleichheitBeide Seiten müssen vollständig instantiiert sein.

Tipp: is für Zuweisungen verwenden, =:= bzw. =\= für Überprüfungen.

Analog funktionieren <, =<, > und >=.

Beispiel

powerof2(X) :- X =:= 1.powerof2(X) :- X > 1, 0 =:= X mod 2, Y is X div 2,

powerof2(Y).

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 9

Arithmetik in Prolog

=:= bzw. =\=: Arithmetische GleichheitBeide Seiten müssen vollständig instantiiert sein.

Tipp: is für Zuweisungen verwenden, =:= bzw. =\= für Überprüfungen.Analog funktionieren <, =<, > und >=.

Beispiel

powerof2(X) :- X =:= 1.powerof2(X) :- X > 1, 0 =:= X mod 2, Y is X div 2,

powerof2(Y).

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 9

Arithmetik in Prolog

=:= bzw. =\=: Arithmetische GleichheitBeide Seiten müssen vollständig instantiiert sein.

Tipp: is für Zuweisungen verwenden, =:= bzw. =\= für Überprüfungen.Analog funktionieren <, =<, > und >=.

Beispiel

powerof2(X) :- X =:= 1.powerof2(X) :- X > 1, 0 =:= X mod 2, Y is X div 2,

powerof2(Y).

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 9

Cut

Spezielles Prädikat: !

Wertet zu wahr aus.

Bei jedem Reerfüllungsversuch wertet es zu falsch aus.

Diese Reerfüllungsversuch werden nicht durchgeführt.

Wurde ein Cut erreicht, wird keine weitere Regel für das aktuellePrädikat getestet.

Implementierung: Choicepoints löschen

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 10

Cut

Spezielles Prädikat: !

Wertet zu wahr aus.Bei jedem Reerfüllungsversuch wertet es zu falsch aus.

Diese Reerfüllungsversuch werden nicht durchgeführt.

Wurde ein Cut erreicht, wird keine weitere Regel für das aktuellePrädikat getestet.

Implementierung: Choicepoints löschen

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 10

Cut

Spezielles Prädikat: !

Wertet zu wahr aus.Bei jedem Reerfüllungsversuch wertet es zu falsch aus.

Diese Reerfüllungsversuch werden nicht durchgeführt.

Wurde ein Cut erreicht, wird keine weitere Regel für das aktuellePrädikat getestet.

Implementierung: Choicepoints löschen

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 10

Cut

Spezielles Prädikat: !

Wertet zu wahr aus.Bei jedem Reerfüllungsversuch wertet es zu falsch aus.

Diese Reerfüllungsversuch werden nicht durchgeführt.

Wurde ein Cut erreicht, wird keine weitere Regel für das aktuellePrädikat getestet.

Implementierung: Choicepoints löschen

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 10

Cut

Spezielles Prädikat: !

Wertet zu wahr aus.Bei jedem Reerfüllungsversuch wertet es zu falsch aus.

Diese Reerfüllungsversuch werden nicht durchgeführt.

Wurde ein Cut erreicht, wird keine weitere Regel für das aktuellePrädikat getestet.

Implementierung: Choicepoints löschen

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 10

not

Beispielimplementierung:

not(P) :- call(P), !, fail.not(P).

call(P) überprüft, ob P zu wahr auswertet.

fail ist ein unerfüllbares Prädikat.

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 11

Missionare und Kannibalen

Nachdem Wolf, Ziege und Kohl den Fluss unbeschadet überquert haben,sollen nun n Missionare und n Kannibalen den Fluss überqueren. Dabeigilt:

In dem Boot ist nach wie vor nur Platz für 2 Personen

Sowohl Missionare als auch Kannibalen können das Boot steuern,das Boot steuert sich aber nicht von alleine.

Sind zu einem Zeitpunkt auf einer Uferseite mehr Kannibalen alsMissionare, werden die Missionare (falls vorhanden) von denKannibalen gefressen. Das gilt es zu vermeiden.

Schreibe ein Prolog-Prädikat, das alle Lösungen des Problems (ohneZustandswiederholungen) berechnet.

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 12

Türme von Hanoi

Es gibt 3 Stapel.

Zu Beginn enthält der Linke die Zahlen [1, . . . , n] der Mittlere und derRechte sind leer.

In einem Zug darf man von einem Stapel das oberste Element aufeinen anderen Stapel verschieben.

Alle Stapel müssen zu jedem Zeitpunkt sortiert sein.

Schreibe ein Prolog-Prädikat, das alle Lösungen des Problems (ohneZustandswiederholungen) berechnet.

Roman Langrehr – Programmierparadigmen Tutorium 2 & 5 10./11.12.2018 13