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) |
pl:prolog:prolog_lab:prolog_lab_reprezentacja [2008/11/12 08:19] holownia usunięto |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| {{header>1}} | {{header>1}} | ||
| - | + | ====== - #4 LAB: Reprezentacja wiedzy w Prologu, szukanie rozwiązań ====== | |
| - | ====== - #4 LAB: Reprezentacja wiedzy w Prologu, sterowanie szukaniem rozwiązań i typowe problemy ====== | + | |
| ===== - Reprezentacja wiedzy ===== | ===== - Reprezentacja wiedzy ===== | ||
| Linia 46: | Linia 45: | ||
| * jakie są osoby w bazie? | * jakie są osoby w bazie? | ||
| * jakie są dzieci w bazie? | * jakie są dzieci w bazie? | ||
| - | * jakie są dane o zarobkach? | ||
| * pokazać pensje wszystkich osób, | * pokazać pensje wszystkich osób, | ||
| * jakie dzieci urodziły się w 1979r.? | * jakie dzieci urodziły się w 1979r.? | ||
| Linia 56: | Linia 54: | ||
| Powtórzyć pytania, kreatywnie... | Powtórzyć pytania, kreatywnie... | ||
| + | |||
| ==== Temat: Planowanie lotów ==== | ==== Temat: Planowanie lotów ==== | ||
| - | |||
| Program {{flight_planner-1.pl}} pozwala na znalezienie trasy przelotu. | 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. | + | 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. | + | 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> | <code prolog> | ||
| Linia 74: | Linia 72: | ||
| Z = a/b | Z = a/b | ||
| </code> | </code> | ||
| - | |||
| ==== Ćwiczenie: Planowanie lotów ==== | ==== Ćwiczenie: Planowanie lotów ==== | ||
| + | Pobrać program {{flight_planner-1.pl}} | ||
| - | Pobrać program {{flight_planner-1.pl}} | ||
| Przetestować, np.: | Przetestować, np.: | ||
| - | |||
| <code prolog> | <code prolog> | ||
| ?- flight(ljubljana,london,Dzien,_,Wylot:_,_),Wylot >=18. | ?- flight(ljubljana,london,Dzien,_,Wylot:_,_),Wylot >=18. | ||
| Linia 96: | Linia 92: | ||
| Wylot = 20 ; | Wylot = 20 ; | ||
| </code> | </code> | ||
| - | |||
| Czyli w które dni tygodnia mamy bezpośredni lot z Ljubljany do Londynu, po 18. | 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? | Albo: jak można dostać się z Ljubljany do Edynburga w czwartek? | ||
| - | |||
| <code prolog> | <code prolog> | ||
| ?- route(ljubljana,edinburgh,th,R). | ?- route(ljubljana,edinburgh,th,R). | ||
| Linia 113: | Linia 107: | ||
| :- op( 50, xfy, :). | :- op( 50, xfy, :). | ||
| - | definiuje nowy operator (omówione na kolejnym laboratorium). W uproszczeniu: chcemy móc pisać ''g:m,'' zamiast '':(g,m)''. | + | 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 ===== | ===== - Wewnętrzna reprezentacja ===== | ||
| Linia 121: | Linia 115: | ||
| Np. | Np. | ||
| - | |||
| <code prolog> | <code prolog> | ||
| ?- A=1, display(A). | ?- A=1, display(A). | ||
| Linia 137: | Linia 130: | ||
| W przypadku długich list może przydać się ''print/1''. | W przypadku długich list może przydać się ''print/1''. | ||
| - | |||
| <code prolog> | <code prolog> | ||
| ?- X=[1,2,3,45,6,7,8,9,32,4,6,ff,7,d],print(X). | ?- X=[1,2,3,45,6,7,8,9,32,4,6,ff,7,d],print(X). | ||
| Linia 144: | Linia 136: | ||
| X = [1, 2, 3, 45, 6, 7, 8, 9, 32|...] | X = [1, 2, 3, 45, 6, 7, 8, 9, 32|...] | ||
| </code> | </code> | ||
| - | |||
| ===== - Sterowanie wnioskowaniem ===== | ===== - Sterowanie wnioskowaniem ===== | ||
| + | |||
| ==== Temat: Cut ==== | ==== 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ń. | + | 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: | + | Na przykład, proszę się zastanowić nad intencją autora kodu: |
| <code prolog> | <code prolog> | ||
| Linia 204: | Linia 197: | ||
| No | No | ||
| </code> | </code> | ||
| - | |||
| - | Zadania podane są dalej. | ||
| ==== Ćwiczenie: Cut ==== | ==== Ćwiczenie: Cut ==== | ||
| - | Przepisać pokazane w opisie predykaty nazwa do pliku odciecia.pl i przetestować ich działanie w sposób analogiczny jak w opisie. | + | 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. | Dodać opisy dla kolejnych cyfr, sprawdzić działanie dla różnych wartości. | ||
| Linia 284: | Linia 275: | ||
| [trace] ?- max2(2,3,X). | [trace] ?- max2(2,3,X). | ||
| </code> | </code> | ||
| + | |||
| ===== - Powtarzanie i nie tylko ===== | ===== - Powtarzanie i nie tylko ===== | ||
| - | ==== Temat: Użycie //repeat// i //not// | + | ==== Temat: Użycie repeat i not ==== |
| - | Predykat repeat/0 powoduje powtarzanie. Jeżeli dociera się do niego w czasie nawrotu, szukanie jest kontynuowane. | + | 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!). | Definicja mogłaby wyglądać tak (ten predykat już jest zdefiniowany w Prologu!). | ||
| Linia 298: | Linia 290: | ||
| Uwaga: rekursja i nawroty to dwa podstawowe mechanizmy powtarzania/kontynuowania szukania w Prologu. | 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. | + | 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 | + | Poza tym należy pamiętać o predykacie not/0, równoważnym operatorowi |
| - | +, który z logicznegu punktu widzenia mógłby wyglądać tak: | + | \+, który z logicznego punktu widzenia mógłby wyglądać tak: |
| not(P) :- P,!,fail;true. | not(P) :- P,!,fail;true. | ||
| - | ==== Ćwiczenie: Użycie //repeat// i //not// ==== | + | |
| + | ==== Ćwiczenie: Użycie repeat i not ==== | ||
| Sprawdzić działanie: | Sprawdzić działanie: | ||
| Linia 327: | Linia 320: | ||
| ===== - Przechwytywanie wyników ===== | ===== - Przechwytywanie wyników ===== | ||
| - | ==== Temat: Użycie predykatów //bagof//, //setof// i //findall// ==== | + | |
| + | |||
| + | ==== Temat: Użycie predykatów bagof, setof i findall ==== | ||
| Z Prologiem dostarczonych jest kilka predykatów przydatnych przy obróbce wyników wyszukiwania. | Z Prologiem dostarczonych jest kilka predykatów przydatnych przy obróbce wyników wyszukiwania. | ||
| Linia 334: | Linia 329: | ||
| Podobnie działa //setof/3//, jednak powstała lista jest posortowana i nie zawiera ew. duplikatów. | 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. | + | 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. | Predykat //findall/3// wymusza wyszukanie wszystkich możliwych wyników. | ||
| - | ==== Ćwiczenie: Użycie predykatów //bagof//, //setof// i //findall// ==== | + | |
| + | |||
| + | |||
| + | ==== Ćwiczenie: Użycie predykatów bagof, setof i findall ==== | ||
| Wczytać program z 1. zajęć {{rodzina1.pl}} | Wczytać program z 1. zajęć {{rodzina1.pl}} | ||
| Linia 365: | Linia 366: | ||
| ?- findall(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: | + | 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). | ?- bagof(X,istnieje(X),L),zarobki(L,Z). | ||
| - | ===== - Typowe problemy ===== | + | ===== - Ciekawe problemy ===== |
| - | ==== Temat: Mapa ==== | + | Proszę przeanalizować poniższe problemy, w miarę czasu i możliwości. |
| - | Problem: mamy mapę taką jak poniżej | + | |
| - | <code prolog> | ||
| - | |Bialorus | + | ==== Temat: Zaawansowana Mapa ==== |
| - | |------------ | + | |
| - | 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: | + | Rozważmy problem [[prolog_lab_2#tematkolorowanie_mapy|kolorowania mapy]]. |
| - | [[wp>Four_color_theorem]] | + | |
| - | ==== Ćwiczenie: Mapa ==== | + | W jaki sposób policzyć ile jest rozwiązań problemu? |
| - | Definiujemy 3 kolory: | + | |
| - | <code prolog> | + | Napisz odpowiednie zapytanie albo predykat. |
| - | kolor(czerwony). | + | Podpowiedź: utwórz listę rozwiązań, policz elementy listy. |
| - | kolor(zielony). | + | |
| - | kolor(niebieski). | + | |
| - | </code> | + | |
| - | Należy zdefiniować predykat ''koloruj/5'', tak aby zadając pytanie: | + | 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ą. |
| - | ?- koloruj(Polska,Bialorus,Ukraina,Slowacja,Czechy). | + | ==== Ćwiczenie: Zaawansowana Mapa ==== |
| - | + | ||
| - | 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 ==== | + | Zaimplementuj powyższą bazę wiedzy korzystając z tematu Kolorowanie Mapy. |
| - | Pobrać program {{hanoi-2.pl}} | + | Napisz klauzule predykatu ''koloruj/1'', który znajduje odpowiednie pokolorowanie w formie listy: ''[ [panstwo1,kolor1], [panstwo2,kolor2], ... ]''. |
| - | Przetestować i przemyśleć. | + | 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 ==== | ==== Temat: Zagadka Einsteina ==== | ||
| Linia 450: | Linia 416: | ||
| - Palacz Philip Morris pija piwo. | - Palacz Philip Morris pija piwo. | ||
| - W zielonym domu pija się kawę. | - W zielonym domu pija się kawę. | ||
| - | |||
| - | |||
| ==== Ćwiczenie: Zagadka Einsteina ==== | ==== Ćwiczenie: Zagadka Einsteina ==== | ||
| Linia 457: | Linia 421: | ||
| Uzyskanie poprawnego rozwiązania: | Uzyskanie poprawnego rozwiązania: | ||
| - | <code> | + | <code prolog> |
| 1 ?- rozwiazanie(Hodowca_rybek). | 1 ?- rozwiazanie(Hodowca_rybek). | ||
| Hodowca_rybek = niemiec ; | Hodowca_rybek = niemiec ; | ||
| Linia 466: | Linia 430: | ||
| Proszę wykonać odpowiednią modyfikację, aby dowiedzieć się, jakie papierosy palą mieszkańcy poszczególnych narodowości. | Proszę wykonać odpowiednią modyfikację, aby dowiedzieć się, jakie papierosy palą mieszkańcy poszczególnych narodowości. | ||
| - | <code> | ||
| Uzyskanie poprawnego rozwiązania: | Uzyskanie poprawnego rozwiązania: | ||
| + | <code prolog> | ||
| 1 ?- rozwiazanie(S). | 1 ?- rozwiazanie(S). | ||
| S = [norweg, dunhill] ; | S = [norweg, dunhill] ; | ||
| Linia 481: | Linia 445: | ||
| Pojawia się alternatywne rozwiązanie. | Pojawia się alternatywne rozwiązanie. | ||
| - | <code> | + | <code prolog> |
| 1 ?- rozwiazanie(Hodowca_rybek). | 1 ?- rozwiazanie(Hodowca_rybek). | ||
| Hodowca_rybek = dunczyk ; | Hodowca_rybek = dunczyk ; | ||
| Linia 488: | Linia 452: | ||
| </code> | </code> | ||
| - | ===== - Dla Zainteresowanych ===== | + | |
| ==== Temat: Sortowanie ==== | ==== 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 | + | 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 ==== | ==== Ćwiczenie: Sortowanie ==== | ||
| Linia 500: | Linia 464: | ||
| * {{quicksort.pl}} | * {{quicksort.pl}} | ||
| - | Przypomnienie z podstaw informatyki: jaką złożoność obliczniową mają te algorytmy? | + | 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}} | 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}} | ||
| Linia 510: | Linia 474: | ||
| </code> | </code> | ||
| - | ===== SPOOL ===== | + | ===== Komentarze, propozycje, wątpliwości==== |
| - | 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. | + | |
| + | * 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// | ||
