To jest stara wersja strony!
LAB: Reprezentacja wiedzy w Prologu, szukanie rozwiązań
Przemyśleć całość i poprawić cut.
1. Reprezentacja wiedzy
Temat: 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: Rodzina - reprezentacja bazy danych
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 poprzednim laboratorium, proszę policzyć zarobki wszystkich osób:
?- bagof(X,istnieje(X),L),zarobki(L,Z).
Dopisać kolejne 2 rodziny.
Powtórzyć pytania, kreatywnie…
Temat: 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 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: Planowanie lotów
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)
.
2. 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|...]
3. Sterowanie wnioskowaniem
Temat: Cut
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
Ćwiczenie: Cut
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).
4. Powtarzanie i nie tylko
Temat: Użycie repeat i not
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.
Ćwiczenie: Użycie repeat i not
Sprawdzić działanie:
?- write('b'), repeat, write('u'), fail.
Sprawdzić działanie:
?- true.
?- fail.
?- not(true).
?- not(fail).
?- \+ true.
?- \+ fail.
5. Ciekawe problemy
Proszę przeanalizować poniższe problemy, w miarę czasu i możliwości.
Temat: Zaawansowana Mapa
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ą.
Ćwiczenie: Zaawansowana Mapa
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
.
Temat: Zagadka Einsteina
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?
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: Zagadka Einsteina
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.
Temat: Sortowanie
Ćwiczenie: 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)
Komentarze, propozycje, wątpliwości
ciężko zdażyć zrealizować całe laboratorium: rodzina + flight planner zajmuje 70 min —
Igor Wojnicki 2008/11/05 15:41