====== LAB: Reprezentacja wiedzy w Prologu, szukanie rozwiązań ======

===== -. Reprezentacja wiedzy =====
==== Rodzina - reprezentacja bazy danych ====

Program prezentuje realizację prostej bazy danych.

Baza jest opisywana przy pomocy predykatu ''rodzina/3''. Osoby w rodzinie są opisywane przy pomocy termu ''osoba/4''.

Rekord:

<code prolog>
rodzina(
	osoba(jan,  kowalski, data(5,kwiecien,1946), pracuje(tpsa,3000)),
	osoba(anna, kowalski, data(8,luty,1949),     pracuje(szkola,1500)), 
	[
	 osoba(maria, kowalski, data(20,maj,1973), pracuje(argo_turist,4000)),
	 osoba(pawel, kowalski, data(15,listopad,1979), zasilek)],
	 ).
</code>

Do bazy dostarczony jest interfejs, pozwalający na wyszukiwanie osób o pewnych własnościach. Przykładowe własności - elementy interfejsu:

<code prolog>
zona(X) :-
	rodzina(_,X,_).

dziecko(X) :-
	rodzina(_,_,Dzieci),
	nalezy(X,Dzieci).
</code>

Pełny program {{repr-fam.pl}}


**Ćwiczenie**

Pobrać program {{repr-fam.pl}}

Przeglądnąć całość.

Zadać pytania:

  * jakie są osoby w bazie?
  * jakie są dzieci w bazie?
  * pokazać pensje wszystkich osób,
  * jakie dzieci urodziły się w 1979r.?
  * znaleźć wszystkie żony, które pracują,
  * znaleźć osoby urodzone przed 1950 r, których pensja jest mniejsza niż 3000,
  * itd.

Korzystając z wiedzy zdobytej na [[listy2#przechwytywanie_wynikow|poprzednim laboratorium]], proszę policzyć zarobki wszystkich osób:

  ?- bagof(X,istnieje(X),L),zarobki(L,Z).


Dopisać kolejne 2 rodziny.

Powtórzyć pytania, kreatywnie...


==== Planowanie lotów ====
Program {{flight_planner-1.pl}} pozwala na znalezienie trasy przelotu.

Uwaga: w kodzie powyżej znajduje się ciekawe użycie operatora / /2. Proszę zwrócić uwagę na poniższy kod.
Prolog nie wylicza wyniku działania [[http://gollem.science.uva.nl/SWI-Prolog/Manual/operators.html#tab:operators|operatora]] (nie ma nigdzie ''is'') ale uzgadnia jego argumenty, gdyż operator po prawej i po lewej stronie ''='' jest taki sam.

<code prolog>
?- a/b = X/Y.

X = a
Y = b

?- a/b = Z.

Z = a/b
</code>

**Ćwiczenie**

Pobrać program {{flight_planner-1.pl}}

Przetestować, np.:
<code prolog>
?- flight(ljubljana,london,Dzien,_,Wylot:_,_),Wylot >=18.

Dzien = mo
Wylot = 20 ;

Dzien = we
Wylot = 20 ;

Dzien = th
Wylot = 20 ;

Dzien = sa
Wylot = 20 ;
</code>
Czyli w które dni tygodnia mamy bezpośredni lot z Ljubljany do Londynu, po 18.

Albo: jak można dostać się z Ljubljany do Edynburga w czwartek?
<code prolog>
?- route(ljubljana,edinburgh,th,R).

R = [ljubljana/zurich/jp322/11:30, zurich/london/sr806/16:10, london/edinburgh/ba4822/18:40]
</code>

Rozbudować - dodać własne trasy.

Uwaga: wyrażenie

  :-  op( 50, xfy, :).

definiuje nowy operator (omówione na [[prolog_lab_metaprog#tematdefiniowanie_operatorow|kolejnym laboratorium]]). 
W uproszczeniu: chcemy móc pisać ''g:m,'' zamiast '':(g,m)''.

===== -. Wewnętrzna reprezentacja =====

Predykaty ''display'', ''write_canonical'' wypisują Prologową reprezentację termów.

Np.
<code prolog>
?- A=1, display(A).
1

?- A=[1], display(A).
.(1, [])

?- A=[1,a], display(A).
.(1, .(a, []))

?- A=[1,a,[ala,ma,[kota]]], display(A).
.(1, .(a, .(.(ala, .(ma, .(.(kota, []), []))), [])))
</code>

W przypadku długich list może przydać się ''print/1''.
<code prolog>
?- X=[1,2,3,45,6,7,8,9,32,4,6,ff,7,d],print(X).
[1, 2, 3, 45, 6, 7, 8, 9, 32, 4, 6, ff, 7, d]

X = [1, 2, 3, 45, 6, 7, 8, 9, 32|...]
</code>

===== -. Sterowanie wnioskowaniem =====

Operator cut, pisany przy pomocy ''!'' pozwala na zablokowanie procesu nawrotu w wybranym miejscu. Te zmienne logiczne, które zostały zunifikowane przed napotkaniem ''!'', nie mogą ulec zmianie. 
W efekcie można uniknąć wyszukiwania niechcianych, zbędnych, a czasem wręcz niepoprawnych rozwiązań.

__Przykład 1__:\\
Baza wiedzy:
<code prolog>
c(1).
c(2).

a(X) :- c(X), !.
</code>

Proszę zadać cel:
<code prolog>
?- a(X), write(X), fail.
</code>

X zostaje zunifikowany z 1 - c(1). Cut uniemożliwia dalsze nawroty.

__Przykład 2__:\\
Baza wiedzy:
<code prolog>
c(1).
c(2).
d(2).

a(X) :- c(X), !, d(X).
</code>

Proszę zadać cel:
<code prolog>
?- a(1).
?- a(2).
?- a(X).
</code>

Dla celu a(X) X nie zostanie zunifikowany! (odp. interpretera: No.) Reguła jest prawdziwa dla X=2, ale Prolog nie znajdzie takiego rozwiązania, bo uniemożliwiony został nawrót. d(1) przy takiej bazie wiedzy nie jest prawdziwe.

__Przykład 3__:\\
Baza wiedzy:
<code prolog>
c(1).
c(2).
c(3).
d(1).
d(2).
d(3).

a(X,Y) :- c(X), !, d(Y).
</code>

Proszę zadać cel:
<code prolog>
?- a(X,Y), write('X = '), write(X), write(', Y = '), writeln(Y), fail.
</code>

Proszę zauważyć, że dla zmiennej logicznej Y, której unifikacja przebiega po wykonaniu odcięcia, nawroty są możliwe.


__Przykład 4__:\\
Baza wiedzy:
<code prolog>
b(1).
b(2).
c(2).
c(3).

a(X) :- b(X), !, c(X).
a(X) :- c(X).
</code>

Proszę zadać cel:
<code prolog>
?- a(X).
?- a(3).
</code>

Po napotkaniu cut odcinane są także pozostałe reguły predykatu. Dlaczego wobec tego a(3) jednak zwraca prawdę?

Przykłady inspirowane [[http://en.wikibooks.org/wiki/Prolog/Cuts_and_Negation|Prolog Cuts and Negation]]

**Ćwiczenie**

Proszę dopisać do bazy wiedzy znany już predykat ''należy/2'':

<code prolog>
nalezy1(X,[X|_]) :- write(X).
nalezy1(X,[_|O]) :-
	nalezy1(X,O).
</code>

Sprawdzić działanie dla list:

  ?- nalezy1(a,[a,b,c]),fail.

  ?- nalezy1(a,[a,b,a,c]),fail.

Zmodyfikować:

<code prolog>
nalezy2(X,[X|_]) :- !, write(X).
nalezy2(X,[_|O]) :-
	nalezy2(X,O).
</code>

Przetestować:

  ?- nalezy2(a,[a,b,c]),fail.

  ?- nalezy2(a,[a,b,a,c]),fail.

A nastęnie sprawdzić działanie predykatu once/1.

  ?- once((nalezy1(a,[a,b,a,c]))),fail.

Wpisać predykat:

<code prolog>
max1(X,Y,X) :- X >= Y.
max1(X,Y,Y) :- X < Y.
</code>

a następnie prześledzić jego działanie:

<code prolog>
?- spy(max1).
% Spy point on max1/3

[debug]  ?- trace.

[trace]  ?- max1(2,3,X).
</code>

Następnie dopisać:

<code prolog>
max2(X,Y,X) :- X >= Y, !.
max2(_,Y,Y).
</code>

i sprawdzić:

<code prolog>
?- spy(max2).
% Spy point on max2/3

[debug]  ?- trace.

[trace]  ?- max2(2,3,X).
</code>


===== -. Użycie predykatu not =====

Poza predykatem fail/0 mamy do dyspozycji predykat true/0.
Przy ich użyciu można skonstruować odpowiednik operatora \+ (negacja) - predykat not/0, który z logicznego punktu widzenia mógłby wyglądać tak:

<code prolog>
not(P) :- P,!,fail;true.
</code>

albo w nieco mniej zwartej, ale bardziej czytelnej postaci:

<code prolog>
not(P) :- P,!,fail.
not(_).
</code>


**Ćwiczenie**

<code prolog>
?- true.

?- fail.

?- not(true).

?- not(fail).

?- \+ true.

?- \+ fail.
</code>


===== -. Ciekawe problemy =====
Proszę przeanalizować poniższe problemy, w miarę czasu i możliwości.

==== Minecraft ====
Zastanówmy się nad próbą implementacji prostej gry typu [[http://pl.wikipedia.org/wiki/Minecraft|Minecraft]]. Kluczowym elementem gry jest silnik wokselowy, który odpowiada za renderowania ogromnego świata przy użyciu prostych klocków zwanych [[http://pl.wikipedia.org/wiki/Woksel|wokselami]]. Zaczniemy od rysowania przykładowego woksela. Proszę uruchomić program {{:pl:prolog:prolog_lab:cuboid.pl|}} (wymagane XPCE) i przeanalizować jego działanie.

<code prolog>
?- cuboid(2,2,2).
</code>

Następnie proszę zapoznać się z kodem odpowiadającym za animację {{:pl:prolog:prolog_lab:animation.pl|}}:

<code prolog>
?- sm.
</code>

Zadania:
  - Przerobić predykat ''cuboid'' tak, żeby można było sprecyzować jego pozycję w przestrzeni
  - Napisać predykat ''cuboids'', który przyjmuje listę współrzędnych i rysuje w nich sześciany o zadanej długości boku
  - Przy pomocy predykatu ''cuboids'' należy zamodelować [[http://i.ytimg.com/vi/u1bX8kEy0pg/maxresdefault.jpg?|złożony obiekt ze świata Minecraft]]
  - Bazując na kodzie z ''animation.pl'' należy wprawić krowę w ruch sinusoidalny, imitujący [[https://www.youtube.com/watch?v=QH2-TGUlwu4|kota z filmu]]
  - [Dla odważnych] dodać do animacji [[https://archive.org/details/nyannyannyan|dźwięk]] podobny do tego z [[https://www.youtube.com/watch?v=QH2-TGUlwu4|filmu]]

Pytania:
  - Czy rozsądne jest rysowanie wszystkich klocków? Jak wykryć, które klocki są widoczne z perspektywy gracza? Pomocny może okazać się [[http://et1337.com/2015/02/18/the-poor-mans-voxel-engine/#|link]]
  - Czy możliwe jest zrobienie w podobny sposób imitacji poniższego [[http://goo.gl/YroZm|filmu]]?

==== Zaawansowana Mapa ====

Rozważmy problem [[programy#kolorowanie_mapy|kolorowania mapy]].

W jaki sposób policzyć ile jest rozwiązań problemu? 

Napisz odpowiednie zapytanie albo predykat. 
Podpowiedź: utwórz listę rozwiązań, policz elementy listy.

Powyższy problem można przedstawić w sposób ogólny definiując predykaty: ''panstwo/1'', ''kolor/1'', ''sasiad/2'' określające odpowiednio: nazwy państw, kolory, oraz państwa sąsiadujące ze sobą.

**Ćwiczenie**

Zaimplementuj powyższą bazę wiedzy korzystając z tematu Kolorowanie Mapy.
Napisz klauzule predykatu ''koloruj/1'', który znajduje odpowiednie pokolorowanie w formie listy: ''[ [panstwo1,kolor1], [panstwo2,kolor2], ... ]''.

Podpowiedź: 
  - wygeneruj listę państw,
  - wygeneruj: ''[panstwo1,kolor1]'' dla każdego państwa, rekurencyjnie przegladajac listę państw, w rezultacie otrzymując kandydata na rozwiązanie: ''[ [panstwo1,kolor1], [panstwo2,kolor2], ... ]''
  - sprawdź czy w wygenerowanym kandydacie na rozwiązanie sąsiadujące państwa nie mają tego samego koloru; uwaga: przydatne będzie użycie ''forall/2''. 

==== Zagadka Einsteina ====
Jedna z możliwych postaci zagadki Einstein'a (patrz [[http://en.wikipedia.org/wiki/Einstein_puzzle]], [[http://pl.wikipedia.org/wiki/Zagadka_Einsteina]]).

5 ludzi różnych narodowości zamieszkuje 5 domów w 5 różnych kolorach. Wszyscy palą papierosy 5 różnych marek i piją 5 różnych napojów. Hodują zwierzęta 5 różnych gatunków. Który z nich hoduje rybki?

  - Norweg zamieszkuje pierwszy dom.
  - Anglik mieszka w czerwonym domu.
  - Zielony dom znajduje się bezpośrednio po lewej stronie domu białego.
  - Duńczyk pije herbatkę.
  - Palacz Rothmansów mieszka obok hodowcy kotów.
  - Mieszkaniec żółtego domu pali Dunhille.
  - Niemiec pali Marlboro.
  - Mieszkaniec środkowego domu pija mleko.
  - Palacz Rothmansów ma sąsiada, który pija wodę.
  - Palacz Pall Malli hoduje ptaki.
  - Szwed hoduje psy.
  - Norweg mieszka obok niebieskiego domu.
  - Hodowca koni mieszka obok żółtego domu.
  - Palacz Philip Morris pija piwo.
  - W zielonym domu pija się kawę.


**Ćwiczenie**

Proszę pobrać kod {{einstein2.pl}} i zastanowić się na jego działaniem.

Uzyskanie poprawnego rozwiązania:
<code prolog>
1 ?- rozwiazanie(Hodowca_rybek).
Hodowca_rybek = niemiec ;
fail.
</code>

W przytoczonej wyżej wersji zagadki pytamy o hodowcę rybek.
Proszę wykonać odpowiednią modyfikację, aby dowiedzieć się, jakie papierosy palą mieszkańcy poszczególnych narodowości.

Uzyskanie poprawnego rozwiązania:
<code prolog>
1 ?- rozwiazanie(S).
S = [norweg, dunhill] ;
S = [dunczyk, rothmans] ;
S = [anglik, pall_mall] ;
S = [niemiec, marlboro] ;
S = [szwed, phillip_morris] ;
fail.
</code>

Proszę wrócić do oryginalnej wersji i sprawdzić, jak usunięcie któregoś z ograniczeń (ze wskazówek zagadki) wpływa na rozwiązanie. Proszę usunąć np. ograniczenie nr 13.

Pojawia się alternatywne rozwiązanie.

<code prolog>
1 ?- rozwiazanie(Hodowca_rybek).
Hodowca_rybek = dunczyk ;
Hodowca_rybek = niemiec ;
fail.
</code>


==== Sortowanie ====
Pliki poniżej zawierają niektóre klasyczne algorytmy sortowania w Prologu. Patrz również: http://en.wikipedia.org/wiki/Sorting_algorithm oraz po polsku: http://pl.wikipedia.org/wiki/Sortowanie

**Ćwiczenie**

Pobrać kod algorytmów i prześledzić ich działanie:

  * {{bubblesort.pl}}
  * {{insertsort.pl}}
  * {{mergesort.pl}}
  * {{quicksort.pl}}

Przypomnienie z podstaw informatyki: jaką złożoność obliczeniową mają te algorytmy?

Porównać ich wydajność, sortując losową listę liczb (np. z zakresu od 0 do 100) o zadanej długości (np. 30), wygenerowaną przy pomocy {{mkrandom.pl}}

<code prolog>
?- mkrandom(100,30,X), time(bubblesort(X,B)), time(quicksort(X,Q)).
% 19,749 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
% 701 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
</code>

===== Komentarze ====