Paradygmaty programowania/Ćwiczenia 13: Programowanie w logice w Prologu I: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
(Nie pokazano 3 pośrednich wersji utworzonych przez tego samego użytkownika)
Linia 38: Linia 38:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Można niemal dosłownie przetłumaczyć algebraiczną definicję złożenia relacji:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Można niemal dosłownie przetłumaczyć algebraiczną definicję złożenia relacji:
  
   ''r(X, Y) :- p(X, Z), q(Z, Y).''
+
   r(X, Y) :- p(X, Z), q(Z, Y).
  
 
</div></div>
 
</div></div>
 +
 
===Zadanie 5===
 
===Zadanie 5===
 
Mamy relacje P i Q jak w poprzednim zadaniu. Jak zdefiniować ich przecięcie, czyli relację R taką, że xRy wtw xPy i xQy?
 
Mamy relacje P i Q jak w poprzednim zadaniu. Jak zdefiniować ich przecięcie, czyli relację R taką, że xRy wtw xPy i xQy?
Linia 46: Linia 47:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Jeszcze prościej niż w poprzednim zadaniu...
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Jeszcze prościej niż w poprzednim zadaniu...
  
   ''r(X, Y) :- p(X, Y), q(X, Y).''
+
   r(X, Y) :- p(X, Y), q(X, Y).
  
 
</div></div>
 
</div></div>
 +
 
===Zadanie 6===
 
===Zadanie 6===
 
Tym razem mamy jedną relację dwuargumentową P. Jak zdefiniować jej domknięcie zwrotne i przechodnie, czyli relację R taką, że xRy wtw <math>x_0Px_1, x_1Px_2,\ldots , x_{n - 1}Px_n</math> dla pewnych <math>x_0, x_1, \ldots, x_n,</math> gdzie <math>x_0 = x</math> i <math>x_n = y</math>.
 
Tym razem mamy jedną relację dwuargumentową P. Jak zdefiniować jej domknięcie zwrotne i przechodnie, czyli relację R taką, że xRy wtw <math>x_0Px_1, x_1Px_2,\ldots , x_{n - 1}Px_n</math> dla pewnych <math>x_0, x_1, \ldots, x_n,</math> gdzie <math>x_0 = x</math> i <math>x_n = y</math>.
Linia 54: Linia 56:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Klasyczne rozwiązanie jest następujące:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Klasyczne rozwiązanie jest następujące:
  
   ''r(X, X).
+
   r(X, X).
   r(X, Y) :- p(X, Z), r(Z, Y).''
+
   r(X, Y) :- p(X, Z), r(Z, Y).
  
 
</div></div>
 
</div></div>
Linia 74: Linia 76:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Bazę danych można zapisać np. tak:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Bazę danych można zapisać np. tak:
  
   ''produkt(p1, skł(s1, skł(s3, skł(s4, koniec)))).
+
   produkt(p1, skł(s1, skł(s3, skł(s4, koniec)))).
 
   produkt(p2, skł(s2, koniec)).
 
   produkt(p2, skł(s2, koniec)).
 
   produkt(p3, skł(s2, skł(s3, koniec))).
 
   produkt(p3, skł(s2, skł(s3, koniec))).
 
+
 
 
   jest(s1).
 
   jest(s1).
 
   jest(s2).
 
   jest(s2).
   jest(s3).''
+
   jest(s3).
  
 
Funktor skł służy do stworzenia odpowiednika listy, której obiecaliśmy jawnie nie używać... Funktor zeroargumentowy koniec służy do zaznaczenia, że dalszej części listy już nie będzie. Notabene, tego typu konstrukcja listy jest w istocie taka sama jak zwykłe listy prologowe — różnica polega jedynie na zgrabnej obudowie składniowej.
 
Funktor skł służy do stworzenia odpowiednika listy, której obiecaliśmy jawnie nie używać... Funktor zeroargumentowy koniec służy do zaznaczenia, że dalszej części listy już nie będzie. Notabene, tego typu konstrukcja listy jest w istocie taka sama jak zwykłe listy prologowe — różnica polega jedynie na zgrabnej obudowie składniowej.
Linia 86: Linia 88:
 
Relacje możnaprodukować i potrzebuje (wraz z dwiema relacjami pomocniczymi) możemy teraz określić następująco:
 
Relacje możnaprodukować i potrzebuje (wraz z dwiema relacjami pomocniczymi) możemy teraz określić następująco:
  
   ''należy(X, skł(X, _)).
+
   należy(X, skł(X, _)).
 
   należy(X, skł(_, Y)) :- należy(X, Y).
 
   należy(X, skł(_, Y)) :- należy(X, Y).
 
+
 
 
   potrzebuje(X, Y) :- produkt(X, Z), należy(Y, Z).
 
   potrzebuje(X, Y) :- produkt(X, Z), należy(Y, Z).
 
+
 
 
   jestwszystko(koniec).
 
   jestwszystko(koniec).
 
   jestwszystko(skł(X, Y)) :- jest(X), jestwszystko(Y)).
 
   jestwszystko(skł(X, Y)) :- jest(X), jestwszystko(Y)).
 
+
 
   możnaprodukować(X) :- produkt(X, Y), jestwszystko(Y).''
+
   możnaprodukować(X) :- produkt(X, Y), jestwszystko(Y).
  
 
</div></div>
 
</div></div>

Aktualna wersja na dzień 20:03, 25 wrz 2006

Zadanie 1

Rozważmy program prologowy:

 p(X, Y, Y) :- X =< Y.
 p(X, Y, Z) :- X < Z, W is Z − 1, p(X, Y, W).

Co zostanie wypisane po wpisaniu celu p(5, X, 15)?

Wskazówka:

Zadanie 2*

Napisać program obliczający największy wspólny dzielnik dwóch dodatnich liczb całkowitych za pomocą algorytmu Euklidesa z odejmowaniem. Chodzi o taki algorytm:

 function nww(x, y)
   while x ≠ y do
     if x > y then x := x – y
     else y := y – x
   return x
Wskazówka:

Zadanie 3

Program z poprzedniego zadania można zastosować do wyliczenia największego wspólnego dzielnika dwóch liczb lub do sprawdzenia, że dzielnik równa się pewnej liczbie. Co się jednak stanie, jeśli wpiszemy cel postaci nww(X, 28, 4)?

Wskazówka:

Zadanie 4

Załóżmy, że mamy dwie relacje, P oraz Q, wyrażone dwuargumentowymi funktorami p i q. Jak zdefiniować relację R będącą złożeniem relacji P i Q? Chodzi o relację R taką, że xRy wtw xPz i zQy dla pewnego z.

Wskazówka:

Zadanie 5

Mamy relacje P i Q jak w poprzednim zadaniu. Jak zdefiniować ich przecięcie, czyli relację R taką, że xRy wtw xPy i xQy?

Wskazówka:

Zadanie 6

Tym razem mamy jedną relację dwuargumentową P. Jak zdefiniować jej domknięcie zwrotne i przechodnie, czyli relację R taką, że xRy wtw dla pewnych gdzie i .

Wskazówka:

Zadanie 7*

Fabryka produkuje kilka różnych produktów, nazwijmy je p1, p2 i p3. Produkty są produkowane ze składników, które nazwijmy s1, s2, s3 i s4. Zbudować prologową bazę danych, która będzie przechowywała następujące informacje:

  • Opis każdego produktu, wyszczególniający które składniki są potrzebne do jego produkcji (na ogół produkt nie wymaga użycia wszystkich składników).
  • Spis dostępnych w tej chwili składników.

Następnie zdefiniować dwie relacje:

  • możnaprodukować(X) — stwierdzająca, że fabryka posiada wszystkie składniki potrzebne do wyprodukowania produktu X.
  • potrzebuje(X, Y) — stwierdzająca, że produkt X potrzebuje składnika Y.

Całość należy zaprogramować nie używając bezpośrednio list (w tym sęk...).

Wskazówka:

Zadanie 8

Przyjrzyj się funktorowi należy z rozwiązania poprzedniego zadania. Zaobserwuj, co się dzieje, gdy użyjemy go z konkretnym pierwszym argumentem i zmienną w miejscu drugiego, np. należy(abc, X).

Wskazówka: