Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:prolog:prolog_lab:prolog_lab_reprezentacja [2008/10/30 12:57] 127.0.0.1 (old revision restored) |
— (aktualna) | ||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | {{header>1}} | ||
| - | |||
| - | ====== - #4 LAB: Reprezentacja wiedzy w Prologu, sterowanie szukaniem rozwiązań i typowe problemy ====== | ||
| - | |||
| - | ===== - 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? | ||
| - | * 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... | ||
| - | |||
| - | ==== 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> | ||
| - | |||
| - | |||
| - | ==== Ć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)''. | ||
| - | |||
| - | |||
| - | ===== - 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 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. | ||
| - | |||
| - | ==== Ć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 predykaci not/0, równoważnym operatorowi | ||
| - | +, który z logicznegu 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. | ||
| - | |||
| - | 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 program o rodzinie z lab. 4, można teraz policzyć zarobki wszystkich osób: | ||
| - | |||
| - | ?- bagof(X,istnieje(X),L),zarobki(L,Z). | ||
| - | |||
| - | |||
| - | ===== - Typowe problemy ===== | ||
| - | ==== 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]] | ||
| - | |||
| - | ==== Ć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. | ||
| - | |||
| - | ==== 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> | ||
| - | |||
| - | ==== Ćwiczenie: Wieże Hanoi ==== | ||
| - | Pobrać program {{hanoi-2.pl}} | ||
| - | |||
| - | Przetestować i przemyśleć. | ||
| - | |||
| - | ==== 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> | ||
| - | 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. | ||
| - | |||
| - | <code> | ||
| - | 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. | ||
| - | </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> | ||
| - | 1 ?- rozwiazanie(Hodowca_rybek). | ||
| - | Hodowca_rybek = dunczyk ; | ||
| - | Hodowca_rybek = niemiec ; | ||
| - | fail. | ||
| - | </code> | ||
| - | |||
| - | ===== - Dla Zainteresowanych ===== | ||
| - | ==== 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 | ||
| - | |||
| - | ==== Ć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> | ||
| - | |||
| - | ===== SPOOL ===== | ||
| - | Propozycja: przeniesc Silnię do lab2. | ||
| - | - razem z rownaniem kw. sa to zad. dotyczace problemow arytmetycznych | ||
| - | - wprowadzenie do rekurencji w prologu (przed jej uzyciem w listach) | ||
| - | |||
| - | Ponadto (watpliwosci, propozycje): | ||
| - | * Zagadka Einsteina: ew. przeniesc do ''typowych problemow'' lub ''dla zainteresowanych'' | ||
| - | * Planer lotow -przeniesc do ''dla zainteresowanych''? | ||
| - | |||
| - | ==== 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> | ||
| - | |||
| - | ==== Ćwiczenie: Silnia ==== | ||
| - | Wpisać, przetestować i przemyśleć program. | ||
| - | |||
