To jest stara wersja strony!
Przemyśleć całość i poprawić cut.
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
Pobrać program repr-fam.pl
Przeglądnąć całość.
Zadać pytania:
Korzystając z wiedzy zdobytej na poprzednim laboratorium, proszę policzyć zarobki wszystkich osób:
?- bagof(X,istnieje(X),L),zarobki(L,Z).
Dopisać kolejne 2 rodziny.
Powtórzyć pytania, kreatywnie…
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 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
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 kolejnym laboratorium).
W uproszczeniu: chcemy móc pisać g:m, zamiast :(g,m).
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|...]
Operator cut, pisany przy pomocy ! pozwala na zablokowanie procesu nawrotu w wybranym miejscu.
W efekcie można uniknąć wyszukiwania niechcianych, zbędnych, a czasem wręcz niepoprawnych rozwiązań.
Na przykład, proszę się zastanowić nad intencją autora kodu:
nazwa1(1) :- write('Jeden'). nazwa1(2) :- write('Dwa'). nazwa1(3) :- write('Trzy'). nazwa1(_) :- write(' Nie wiem!').
a następnie działaniem Prologu:
?- nazwa1(2). Dwa Yes ?- nazwa1(2), fail. Dwa Nie wiem! No ?- nazwa1(X), fail. JedenDwaTrzy Nie wiem! No
Przypomnienie: fail/0 wymusza nawrót.
A teraz modyfikacja:
nazwa2(1) :- !, write('Jeden'). nazwa2(2) :- !, write('Dwa'). nazwa2(3) :- !, write('Trzy'). nazwa2(_) :- write(' Nie wiem!').
i efekt:
?- nazwa2(2). Dwa Yes ?- nazwa2(2), fail. Dwa No ?- nazwa2(X), fail. Jeden No
Przepisać pokazane w opisie predykaty nazwa do pliku odciecia.pl i przetestować ich działanie w sposób analogiczny jak w opisie.
Dodać opisy dla kolejnych cyfr, sprawdzić działanie dla różnych wartości.
Zmienić kolejność klauzul predykatu i sprawdzić działanie.
Uwaga: aby zaobserwować działanie cut należy zawsze wymuszać nawrót na poziomie interpretera po tym, jak zostanie znalezione rozwiąznie, przez naciśnięcie znaku średnika!
Proszę dopisać znany już predykat należy:
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).
Predykat repeat/0 powoduje powtarzanie. Jeżeli dociera się do niego w czasie nawrotu, szukanie jest kontynuowane.
Definicja mogłaby wyglądać tak (ten predykat już jest zdefiniowany w Prologu!).
repeat. repeat :- repeat.
Uwaga: rekursja i nawroty to dwa podstawowe mechanizmy powtarzania/kontynuowania szukania w Prologu.
Oprócz fail/0, repeat/0 innym przydatnym predykatem jest true/0.
Poza tym należy pamiętać o predykacie not/0, równoważnym operatorowi \+, który z logicznego punktu widzenia mógłby wyglądać tak:
not(P) :- P,!,fail;true.
Sprawdzić działanie:
?- write('b'), repeat, write('u'), fail.
Sprawdzić działanie:
?- true. ?- fail. ?- not(true). ?- not(fail). ?- \+ true. ?- \+ fail.
Proszę przeanalizować poniższe problemy, w miarę czasu i możliwości.
Rozważmy problem 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ą.
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ź:
[panstwo1,kolor1] dla każdego państwa, rekurencyjnie przegladajac listę państw, w rezultacie otrzymując kandydata na rozwiązanie: [ [panstwo1,kolor1], [panstwo2,kolor2], … ]forall/2. Jedna z możliwych postaci zagadki Einstein'a:
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?
Proszę pobrać kod einstein.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.
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
Pobrać kod algorytmów i prześledzić ich działanie:
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)
