Zadania (Prolog)

  1. Długość listy można w Prologu zdefiniować następująco. 
      length(0, []).
  length(N, [_|L]) :- length(M, L), N is M+1.
    Proszę zdefiniować predykaty fib/2 oraz nwd/3.

  2. Niech będzie dana baza danych zawierająca predykaty parent/2, female/1 i male/1.
    Proszę zdefiniować predykaty child/2, mother/2, sister/2, has_a_child/1, grandparent/2 oraz predecessor/2.

  3. Niech będą dane następujące predykaty. 
     q1(X,Y) :- p(X,Y).                q2(X,Y) :- p(X,Z), q2(Z,Y).
 q1(X,Y) :- p(X,Z), q1(Z,Y).       q2(X,Y) :- p(X,Y).  

 q3(X,Y) :- p(X,Y).                q4(X,Y) :- q4(X,Z), p(Z,Y).  
 q3(X,Y) :- q3(X,Z), p(Z,Y).       q4(X,Y) :- p(X,Y).
    oraz baza danych dla predykat p: 
     p(pam,bob).       
 p(tom,bob).
 p(tom,liz).
 p(bob,ann).      
 p(bob,pat).     
 p(pat,jim).
    Przy użyciu "drzew odpowiedzi" proszę ilustrować, jak Prolog odpowiada na pytania qi(tom,pat). oraz qi(liz,jim).

  4. Niech będzie dany następujący program. 
     f(1,one).
 f(s(1),two).
 f(s(s(1)),three).
 f(s(s(s(X))),N) :- f(X,N).
    Jak odpowiada Prolog na pytanie
    1. f(s(1),A)?
    2. f(s(s(1)),two)?
    3. f(s(s(s(s(s(s(1)))))),C)?
    4. f(D,three)?
    5. f(s(s(s(s(s(s(X)))))),E)?

  5. Proszę zdefiniować następujące predykaty dla list.

    1. delete(X,L1,L2), który jest spełniony, jeżeli L2 równa się L1 bez elementu X.
    2. delete(L1,L2), który jest spełniony, jeżeli L2 równa się L1 bez ostatnich trzech elemnetów.
    3. p(X,L,Y,Z), który jest spełniony, jeżeli Y jest poprzednikiem elementu X w liście L a Z następcą elementu X w liście L.
      Przykład: 
       ?- p(3, [1,2,3,4,5], Y, Z).
 Y = 2, Z = 4
    4. q(X,L1,L2), który jest spełniony, jeżeli L2 równa się początku listy L1 do podwójnego wystąpienia elementu X.
      Przykład: 
       ?- q(3, [1,2,3,3,1,2,4], Z).
 Z = [1,2,3,3]
    5. evenlength(L) oraz oddlength(L), które są spełnione, jeżeli długość listy L jest parzysta oraz nieparzysta.
    6. shift(L1,L2), który jest spełniony, jeżeli L2 równa się L1 po jednej rotacji do lewej.
      Przykład: 
       ?- shift([1,2,3,4,5], L).
 L = [2,3,4,5,1]
    7. palindrom(L), który jest spełniony, jeżeli lista L zawiera palindrom.
      Przykłady: 
       ?- palindrom([a,b,c]).
 no
 ?- palindrom([a,b,c,d,c,b,a]).
 yes
  6. Proszę zdefiniować następujące predykaty dla list.

    1. flatten(L1,L2), który jest spełniony, jeżeli lista L2 jest wersją płaską listy L1.
    2. ordered(L), który jest spełniony, jeżeli lista L jest posortowana.
    3. mergesort(L1,L2), który jest spełniony, jeżeli lista L2 jest wersją posortowaną listy L1. Predykat ma simulowac algorytm quicksort.

  7. Niech będą dane następująca defincja predykatu append. 
      append([X|L1], L2, [X|L3]) :- append(L1, L2, L3).
  append([], L, L).
    Przy użyciu drzewa wykonywania proszę ilustrować, jak Prolog odpowiada na pytanie 
     ?- append(X, [3,4], [2,3,4]).
  8. Proszę zdefiniować predykat permutation(L,P), który jest spełniony, jeżeli lista P jest permutacją listy L.
    Przy użyciu ";" powiennien być możliwe wyliczać wszystkie permutacje listy L.

  9. Proszę zdefiniować następujące predykaty

    1. nth(N,L,X), który jest spełniony, jeżeli X jest N-tym elementem listy L.
    2. sorted(L), który jest spełniony, jeżeli lista L jest posortowana.
    3. zrealizujący algorytm mergesort.
      Jak można zdefiniować predykat permutation z zadania 10. używając mergesort?

  10. Proszę zdefiniować predykat number(Z), który znajduje wszystkie trzy-cyfrowe liczby, które można podzielić prez 5 i 6 oraz mają resztę 3, jeżeli zostają podzielone przez 9.

  11. Proszę zdefiniować następujące predykaty

    1. sum(D,X), który jest spełniony, jeżeli X jest sumą wszystkich elementów w drzewie D.
    2. search(X,D), który znajduje element X w drzewie D.
    3. post(D,L), który jest spełniony, jeżeli lista L zawiera wszystkie elementy drzewa D w porządu postfiksowym.

  12. Używając dzrewa wykonania proszę pokazać jak Prolog odpowiada na następujące pytania. 

    1.  p(1).
 p(2) :- !.
 p(3).

 ?- p(x).         ?- p(x), p(y).      ?- p(x), !, p(y). 
    2.  p(x) :- a(x).
 p(x) :- b(x), c(x), !, d(x).
 p(x) :- f(x).                       
 a(1).     b(1).     c(1).
 b(2).     c(2).     d(2).
 f(3).

 ?- p(x).
  13. Niech będzie dana następująca definicja.
     max(X,Y,X) :- X >= Y, !.
 max(X,Y,Y).
    Na kolejne pytanie Prolog odpowiada "błędnie": 
     ?- max(5,2,2).
 yes
    Dlaczego Prolog tak odpowiada i jak można to zreperować (bez zmian cut'u i drugiej reguły)?

  14. Proszę zdefiniować predykat difference(A, B, C), który jest spełniony, jeżeli C = A \ B .