Różnice między wybraną wersją a wersją aktualną.
|
pl:prolog:prolog_lab:reprezentacja_wiedzy [2009/02/24 12:22] holownia |
pl:prolog:prolog_lab:reprezentacja_wiedzy [2019/06/27 15:50] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | {{header>1}} | ||
| - | ====== - #4 LAB: Reprezentacja wiedzy w Prologu, szukanie rozwiązań ====== | ||
| - | FIXME Do odchudzenia. | ||
| - | |||
| - | ===== - 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: | ||
| - | |||
| - | <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: 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 [[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... | ||
| - | |||
| - | |||
| - | ==== 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 [[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: Planowanie lotów ==== | ||
| - | 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 ===== | ||
| - | |||
| - | ==== 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: | ||
| - | |||
| - | <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> | ||
| - | |||
| - | ==== Ć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: | ||
| - | |||
| - | <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> | ||
| - | |||
| - | |||
| - | ===== - 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!). | ||
| - | |||
| - | <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 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: | ||
| - | |||
| - | <code prolog> | ||
| - | ?- true. | ||
| - | |||
| - | ?- fail. | ||
| - | |||
| - | ?- not(true). | ||
| - | |||
| - | ?- not(fail). | ||
| - | |||
| - | ?- \+ true. | ||
| - | |||
| - | ?- \+ fail. | ||
| - | </code> | ||
| - | |||
| - | ===== - Przechwytywanie wyników ===== | ||
| - | |||
| - | |||
| - | ==== Temat: Użycie predykatów bagof, setof i findall ==== | ||
| - | 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, np. zakładając istnienie bazy faktów zdefiniowanej za pomocą predykatu ''a/2'': | ||
| - | * ''bagof(X,Y^a(X,Y),L)'' spowoduje znalezienie listy L na ktorej beda znajdować się wartości X niezależnie od tego jaką wartość przyjmuje Y (dokładnie jedno rozwiązanie). | ||
| - | * ''bagof(X,a(X,Y),L)'' spowoduje znalezienie listy L na ktorej beda znajdować się wartości X dla konkretnej (znalezionej) wartości Y (wiele rozwiązań, lista dla każdej wartości Y). | ||
| - | |||
| - | |||
| - | Predykat //findall/3// wymusza wyszukanie wszystkich możliwych wyników. | ||
| - | |||
| - | |||
| - | |||
| - | |||
| - | ==== Ćwiczenie: Użycie predykatów bagof, setof i findall ==== | ||
| - | 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 [[prolog_lab_reprezentacja#reprezentacja_wiedzy|powyższy program o rodzinie]], można teraz policzyć zarobki wszystkich osób: | ||
| - | |||
| - | ?- bagof(X,istnieje(X),L),zarobki(L,Z). | ||
| - | |||
| - | |||
| - | |||
| - | ===== - Ciekawe problemy ===== | ||
| - | Proszę przeanalizować poniższe problemy, w miarę czasu i możliwości. | ||
| - | |||
| - | |||
| - | ==== Temat: Zaawansowana Mapa ==== | ||
| - | |||
| - | Rozważmy problem [[prolog_lab_2#tematkolorowanie_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: 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: | ||
| - | <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> | ||
| - | |||
| - | |||
| - | ==== Temat: 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: Sortowanie ==== | ||
| - | 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, propozycje, wątpliwości==== | ||
| - | |||
| - | * ciężko zdażyć zrealizować całe laboratorium: rodzina + flight planner zajmuje 70 min --- //[[wojnicki@agh.edu.pl|Igor Wojnicki]] 2008/11/05 15:41// | ||
