[[
✎ pl:prolog:prolog_lab:prolog_lab_reprezentacja
]]
aiWiki
Pokaż stronę
Ostatnie zmiany
Indeks
Zaloguj
Ta strona jest tylko do odczytu. Możesz wyświetlić źródła tej strony ale nie możesz ich zmienić.
====== 4 LAB: Reprezentacja wiedzy w Prologu, sterowanie szukaniem rozwiązań i typowe problemy ====== ===== - #4 Reprezentacja wiedzy ===== ==== - Temat: Przykład reprezentacji wiedzy ==== 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}} ==== - Temat: 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> ==== - Temat: Mapa ==== Problem: mamy mapę taką jak poniżej <code prolog> |Bialorus |------------ Polska | ---------------| | | Ukraina Czechy| Slowacja|----------- ----------------- </code> Należy ja pokolorować 3 kolorami, tak aby żadne sąsiadujące państwa nie miały takiego samego koloru: [[wp>Four_color_theorem]] ==== - Temat: Silnia ==== Deklaratywne liczenie silni. <code prolog> factorial(0,1). factorial(Number,Result) :- Number > 0, NewNumber is Number-1, factorial(NewNumber,NewResult), Result is Number*NewResult. </code> ==== - Temat: Wieże Hanoi ==== Problem [[http://pl.wikipedia.org/wiki/Wieże_Hanoi]]. Problem [[wp>Towers_of_hanoi]] Program {{hanoi-2.pl}} Przykład: <code> ?- 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 </code> ==== - 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. <code prolog> ?- a/b = X/Y. X = a Y = b ?- a/b = Z. Z = a/b </code> ===== - #4 ĆWICZENIA ===== ==== - Ćwiczenie: Reprezentacja wiedzy ==== 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... ==== - Ćwiczenie: Mapa ==== 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. ==== - Ćwiczenie: Silnia ==== Wpisać, przetestować i przemyśleć program. ==== - Ćwiczenie: Wieże Hanoi ==== Pobrać program {{hanoi-2.pl}} Przetestować i przemyśleć. ==== - Ć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 kolejnym laboratorium). W uproszczeniu: chcemy móc pisać ''g:m,'' zamiast '':(g,m)''. ====== 5 LAB: Sterowanie szukaniem rozwiązań w Prologu ====== ===== - #5 WPROWADZENIE ===== ==== - Temat: Cut i sterowanie wnioskowaniem ==== 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. ==== - Temat: Powtarzanie i nie tylko ==== 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. ==== - Temat: Przechwytywanie wyników ==== 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. ==== - Temat: Sortowanie ==== 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> ===== - #5 ĆWICZENIA ===== ==== - Ćwiczenie: Cut i sterowanie wnioskowaniem ==== 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> ==== - Ćwiczenie: Powtarzanie i nie tylko ==== Sprawdzić działanie: ?- write('b'), repeat, write('u'), fail. Sprawdzić działanie: <code prolog> ?- true. ?- fail. ?- not(true). ?- not(fail). ?- \+ true. ?- \+ fail. </code> ==== - Ćwiczenie: Przechwytywanie wyników ==== 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). ==== - Ć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ść 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>
pl/prolog/prolog_lab/prolog_lab_reprezentacja.1225289279.txt.gz
· ostatnio zmienione: 2019/06/27 15:59 (edycja zewnętrzna)
Pokaż stronę
Poprzednie wersje
Menadżer multimediów
Do góry