====== 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:
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)],
).
Do bazy dostarczony jest interfejs, pozwalający na wyszukiwanie osób o pewnych własnościach. Przykładowe własności - elementy interfejsu:
zona(X) :-
rodzina(_,X,_).
dziecko(X) :-
rodzina(_,_,Dzieci),
nalezy(X,Dzieci).
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.
?- a/b = X/Y.
X = a
Y = b
?- a/b = Z.
Z = a/b
**Ćwiczenie**
Pobrać program {{flight_planner-1.pl}}
Przetestować, np.:
?- flight(ljubljana,london,Dzien,_,Wylot:_,_),Wylot >=18.
Dzien = mo
Wylot = 20 ;
Dzien = we
Wylot = 20 ;
Dzien = th
Wylot = 20 ;
Dzien = sa
Wylot = 20 ;
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?
?- route(ljubljana,edinburgh,th,R).
R = [ljubljana/zurich/jp322/11:30, zurich/london/sr806/16:10, london/edinburgh/ba4822/18:40]
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.
?- 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, []), []))), [])))
W przypadku długich list może przydać się ''print/1''.
?- 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|...]
===== -. 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:
c(1).
c(2).
a(X) :- c(X), !.
Proszę zadać cel:
?- a(X), write(X), fail.
X zostaje zunifikowany z 1 - c(1). Cut uniemożliwia dalsze nawroty.
__Przykład 2__:\\
Baza wiedzy:
c(1).
c(2).
d(2).
a(X) :- c(X), !, d(X).
Proszę zadać cel:
?- a(1).
?- a(2).
?- a(X).
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:
c(1).
c(2).
c(3).
d(1).
d(2).
d(3).
a(X,Y) :- c(X), !, d(Y).
Proszę zadać cel:
?- a(X,Y), write('X = '), write(X), write(', Y = '), writeln(Y), fail.
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:
b(1).
b(2).
c(2).
c(3).
a(X) :- b(X), !, c(X).
a(X) :- c(X).
Proszę zadać cel:
?- a(X).
?- a(3).
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'':
nalezy1(X,[X|_]) :- write(X).
nalezy1(X,[_|O]) :-
nalezy1(X,O).
Sprawdzić działanie dla list:
?- nalezy1(a,[a,b,c]),fail.
?- nalezy1(a,[a,b,a,c]),fail.
Zmodyfikować:
nalezy2(X,[X|_]) :- !, write(X).
nalezy2(X,[_|O]) :-
nalezy2(X,O).
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:
max1(X,Y,X) :- X >= Y.
max1(X,Y,Y) :- X < Y.
a następnie prześledzić jego działanie:
?- spy(max1).
% Spy point on max1/3
[debug] ?- trace.
[trace] ?- max1(2,3,X).
Następnie dopisać:
max2(X,Y,X) :- X >= Y, !.
max2(_,Y,Y).
i sprawdzić:
?- spy(max2).
% Spy point on max2/3
[debug] ?- trace.
[trace] ?- max2(2,3,X).
===== -. 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:
not(P) :- P,!,fail;true.
albo w nieco mniej zwartej, ale bardziej czytelnej postaci:
not(P) :- P,!,fail.
not(_).
**Ćwiczenie**
?- true.
?- fail.
?- not(true).
?- not(fail).
?- \+ true.
?- \+ fail.
===== -. 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.
?- cuboid(2,2,2).
Następnie proszę zapoznać się z kodem odpowiadającym za animację {{:pl:prolog:prolog_lab:animation.pl|}}:
?- sm.
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:
1 ?- rozwiazanie(Hodowca_rybek).
Hodowca_rybek = niemiec ;
fail.
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:
1 ?- rozwiazanie(S).
S = [norweg, dunhill] ;
S = [dunczyk, rothmans] ;
S = [anglik, pall_mall] ;
S = [niemiec, marlboro] ;
S = [szwed, phillip_morris] ;
fail.
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.
1 ?- rozwiazanie(Hodowca_rybek).
Hodowca_rybek = dunczyk ;
Hodowca_rybek = niemiec ;
fail.
==== 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}}
?- 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)
===== Komentarze ====