To jest stara wersja strony!
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
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|...]
Problem: mamy mapę taką jak poniżej
|Bialorus |------------ Polska | ---------------| | | Ukraina Czechy| Slowacja|----------- -----------------
Należy ja pokolorować 3 kolorami, tak aby żadne sąsiadujące państwa nie miały takiego samego koloru: Four_color_theorem
Deklaratywne liczenie silni.
factorial(0,1). factorial(Number,Result) :- Number > 0, NewNumber is Number-1, factorial(NewNumber,NewResult), Result is Number*NewResult.
Problem http://pl.wikipedia.org/wiki/Wieże_Hanoi.
Problem Towers_of_hanoi
Program hanoi-2.pl
Przykład:
?- move(3,left,right,center). Move top disk from left to right Move top disk from left to center Move top disk from right to center Move top disk from left to right Move top disk from center to left Move top disk from center to right Move top disk from left to right
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.
<code prolog>
?- a/b = X/Y.
X = a
Y = b
?- a/b = Z.
Z = a/b
</code>
Pobrać program repr-fam.pl Przeglądnąć całość. Zadać pytania: * jakie są osoby w bazie? * jakie są dzieci w bazie? * jakie są dane o zarobkach? * 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. Dopisać kolejne 2 rodziny. Powtórzyć pytania, kreatywnie…
Definiujemy 3 kolory:
<code prolog>
kolor(czerwony).
kolor(zielony).
kolor(niebieski).
</code>
Należy zdefiniować predykat koloruj/5, tak aby zadając pytanie:
?- koloruj(Polska,Bialorus,Ukraina,Slowacja,Czechy).
dostać wszystkie możliwości pokolorowania tej konkretnej mapy.
Uwaga: w Prologu operator \= to nieidentyczność, czy też niemożliwość uzgodnienia termów.
Wpisać, przetestować i przemyśleć program.
Pobrać program hanoi-2.pl Przetestować i przemyśleć.
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 kolejnym laboratorium). W uproszczeniu: chcemy móc pisać g:m, zamiast :(g,m).
====== 5 LAB: Sterowanie szukaniem rozwiązań w Prologu ======
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 intecją autora kodu: <code prolog> nazwa1(1) :- write('Jeden'). nazwa1(2) :- write('Dwa'). nazwa1(3) :- write('Trzy'). nazwa1(_) :- write(' Nie wiem!'). </code> a następnie działaniem Prologu: <code prolog> ?- nazwa1(2). Dwa Yes ?- nazwa1(2), fail. Dwa Nie wiem! No ?- nazwa1(X), fail. JedenDwaTrzy Nie wiem! No </code> Przypomnienie: fail/0 wymusza nawrót. A teraz modyfikacja: <code prolog> nazwa2(1) :- !, write('Jeden'). nazwa2(2) :- !, write('Dwa'). nazwa2(3) :- !, write('Trzy'). nazwa2(_) :- write(' Nie wiem!'). </code> i efekt: <code prolog> ?- nazwa2(2). Dwa Yes ?- nazwa2(2), fail. Dwa No ?- nazwa2(X), fail. Jeden No </code> Zadania podane są dalej.
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!). <code prolog> repeat. repeat :- repeat. </code> 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 predykaci not/0, równoważnym operatorowi +, który z logicznegu punktu widzenia mógłby wyglądać tak: not(P) :- P,!,fail;true.
Z Prologiem dostarczonych jest kilka predykatów przydatnych przy obróbce wyników wyszukiwania.
Predykat bagof/3, użyty jako bagof(X,P,L) buduje listę L, złożoną z takich X, że spełnione jest P.
Podobnie działa setof/3, jednak powstała lista jest posortowana i nie zawiera ew. duplikatów.
Specjalny operator ^ pozwala na modyfikowanie zapytania i jest równoważny kwantyfikacji egzystencjalnej.
Predykat findall/3 wymusza wyszukanie wszystkich możliwych wyników.
Poniżej klasyczne niektóre algorytmy sortowania w Prologu. Patrz również: http://en.wikipedia.org/wiki/Sorting_algorithm oraz po polsku: http://pl.wikipedia.org/wiki/Sortowanie Sortowanie bąbelkowe, bubblesort <code prolog> bubblesort(List, Sorted) :- swap(List, List1), !, bubblesort(List1, Sorted). bubblesort(Sorted, Sorted). swap([X,Y|Rest], [Y,X|Rest]) :- gt(X, Y). swap([Z|Rest], [Z|Rest1]) :- swap(Rest, Rest1). gt(X,Y) :- X>Y. gt(X,Y) :- X@>Y. </code> Uwaga: operator @> porównuje termy leksykograficznie. W większości implementacji Prologu wystarczy samo: gt(X,Y) :- X@>Y. Sortowanie przez wstawianie, insertsort <code prolog> insertsort([], []). insertsort([Head|Tail], L2):- insertsort(Tail, L1), insert(Head, L1, L2). insert(Element, [Head|Tail], [Head|Rest]):- gt(Element,Head),!, insert(Element, Tail, Rest). insert(Element, List, [Element|List]). gt(X,Y) :- X>Y. gt(X,Y) :- X@>Y. </code> Sortowanie przez scalanie, mergesort <code prolog> mergesort([First,Second|Rest],Result) :- !, partition([First,Second|Rest],L1,L2), mergesort(L1,SL1), mergesort(L2,SL2), mergelist(SL1,SL2,Result). mergesort(List,List). mergelist([First1|Rest1],[First2|Rest2],[First1|Rest]) :- First1 @< First2, !, mergelist(Rest1,[First2|Rest2],Rest). mergelist([First1|Rest1],[First2|Rest2],[First2|Rest]) :- \+ First1 @< First2, !, mergelist([First1|Rest1],Rest2,Rest). mergelist(X,[],X). mergelist([],X,X). partition([First,Second|Rest],[First|F],[Second|S]) :- !, partition(Rest,F,S). partition(List,List,[]). </code> Sortowanie quicksort <code prolog> quicksort( [], []). quicksort( [X|Tail], Sorted) :- split( X, Tail, Small, Big), quicksort( Small, SortedSmall), quicksort( Big, SortedBig), conc( SortedSmall, [X|SortedBig], Sorted). split( X, [], [], []). split( X, [Y|Tail], [Y|Small], Big) :- gt( X, Y), !, split( X, Tail, Small, Big). split( X, [Y|Tail], Small, [Y|Big]) :- split( X, Tail, Small, Big). gt(X,Y) :- X>Y. gt(X,Y) :- X@>Y. conc([],L,L). conc([X|L1],L2,[X|L3]) :- conc(L1,L2,L3). </code>
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: <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. ?- once1)),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>
Sprawdzić działanie: ?- write('b'), repeat, write('u'), fail. Sprawdzić działanie: <code prolog> ?- true. ?- fail. ?- not(true). ?- not(fail). ?- \+ true. ?- \+ fail. </code>
Wczytać program z 1. zajęć rodzina1.pl Sprawdzić działanie: ?- rodzic(X,robert). ?- bagof(X,rodzic(X,robert),L). Sprawdzić działanie: ?- bagof(X,ojciec(tomek,X),L). ?- setof(X,ojciec(tomek,X),L). Następnie: ?- bagof(X,Y^ojciec(X,Y),L). ?- setof(X,Y^ojciec(X,Y),L). Oraz: ?- bagof(X,ojciec(X,Y),L). ?- findall(X,ojciec(X,Y),L). Mając program o rodzinie z lab. 4, można teraz policzyć zarobki wszystkich osób: ?- bagof(X,istnieje(X),L),zarobki(L,Z).
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ść obliczniową 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>
