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. 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.
   
   
3. Proszę zdefiniować predykat rzym/2, który transformuje rzymskie liczby do liczb dziesiętnich.
   Liczby rzymskie można po prostu reprezentować jako listy, n.p. [x,l,v,i,i].
   
   
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. 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.
   
   
6. 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). 

   Proszę zilustrować, jak Prolog odpowiada na pytania ?-q_i(tom,pat). oraz ?-q_i(liz,jim).
   
   
7. Proszę zdefiniować następujące predykaty dla list.
   
   
   1. last(X,L), który jest spełniony, jeżeli X jest ostatnim elementem listy L.
   2. delete(X,L1,L2), który jest spełniony, jeżeli L2 równa się L1 bez elementu X.
   3. delete(L1,L2), który jest spełniony, jeżeli L2 równa się L1 bez ostatnich trzech elementów.
   4. reverse(L1,L2), który jest spełniony, jeżeli L2 jest listą L1 w odwrotnej kolejności.
   5. 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 

   6. 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] 

   7. evenlength(L) oraz oddlength(L), które są spełnione, jeżeli długość listy L jest parzysta oraz nieparzysta.
      
   8. 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] 

   9. 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 

   10. quadrat(L1,L2), który jest spełniony, jeżeli L2 zawiera quadraty elementów listy L1.
       Przykład:

        ?- quadrat([1,2,3,4,5], L).
        L = [1,4,9,16,25] 

   11. combine(L1,L2,L3), który jest spełniony, jeżeli L3 zawiera pary elementów z list L1 i L2.
       Przykład:

        ?- combine([1,2,3,4], [a,b,c,d], L).
        L = [[1,a],[2,b],[3,c],[4,d]] 

8. Niech będą dane następująca defincja predykatu append.

     append([X|L1], L2, [X|L3]) :- append(L1, L2, L3).
     append([], L, L).   

   Proszę zilustrować, jak Prolog odpowiada na pytanie

    ?- append(X, [3,4], [2,3,4]).
   

9. 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 mergesort.
      
      
10. Drzewo binarne D jest albo pusty (repezentowane przez nil) albo zawiera element X i dwa poddrzewa L i P (reprezentowane przez drzewo(X,L,P)).
    Proszę zdefiniować następujące predykaty dla drzew.
    
    
    1. size(D,N), który jest spełniony, jeżeli N jest ilością elementów drzewa D.
    2. max(D,N), który jest spełniony, jeżeli N jest maximum elementów w drzewie D.
    3. times(N,D1,D2), który bierzy wszystkie wartości węzłów drzewa D1 razy N.
    4. preorder(D,L), który jest spełniony, jeżeli lista L zawiera elementy drzewa D w kolejności prefiksowym.
    
    
11. Graf można reprezentować przy użciu predykatu edge(V1,V2), gzie V1 oraz V2 są węzłami.
    
    
    1. Proszę zdefiniować predykat path(V1,V2), który znajduje drogę między V1 i V2.
    2. Proszę zdefiniować predykat path(V1,V2,L), który znajduje drogę między V1 i V2 oraz drogę tą podaje w liście L.
    3. Jak można reprezentować graf z wagami oraz w takim grafie obliczyć koszty drogi między węzłami V1 i V2?
    
    
12. Niech będą macierze kwadratowe zareprezentowane przez podwójne listy, n.p. [[1,2],[3,4]]. Proszę zdefiniować następujące predykaty dla (kwadratowych) macierzy.
    
    
    1. row(N,M,V) oraz column(N,M,V)
    2. transpose(M1,M2)
    3. m_add(M1,M2,M3)
    4. m_mult(M1,M2,M3)
    
    
13. Proszę zdefiniować predykat route(Place1,Place2,Day,Route), który zrealizuje planowanie lotów na podstawie rozkładu jazdy.
    Rozkład jazdy jest podane przez predykat timetable(Place1,Place2,List_of_flights), gdzie List_of_Flights jest listą lotów od Place1 do Place2. Każdy lot jest listą [Departure_time,Arrival_time,Flight_number,List_of_days].
    Przykład:

         timetable( london, edinburgh,
                    [ [ 9:40, 10:50, ba4733, alldays],
                      [19:40, 20:50, ba4833, [mo,tu,we,th,fr]] ]).
         

    Plan lotów Route jest listą lotów PlaceA-PlaceB:Flight_number:Departure_time, taka że
    
    
    1. PlaceA w pierwszym elemencie w liście, to Place1.
    2. PlaceB w ostatnim elemencie w liście, to Place2.
    3. wszystkie loty odbędą się w tym samym dniu.
    4. między lotami jest wystarczający czas na transfer.
    
    Przykład:

         ?- route(ljubljana,edinburgh,th,R).
         R = [ljubljana-zurich:yu322:11:30, zurich-london:sr806:16:10, london-edinburgh:ba4822:18:40].
         

14. Używając rezolucję proszę sprawdzić czy następujące konsekwencje logiczne są poprawne.
    
    a) (p → q) → r |= p → (q → r)
    
    b) p → (q → r) |= (p → q) → r
    
    
15. Niech będą
    
    A ≡ (p → (¬ q ∨ ¬ r)) ∧ ((p ∧ r) ∨ ( q → (q → r)))
    B ≡ (p ∧ (¬ q ∧ r)) ∨ (r ∧ (r → p))
    C ≡ (p ∧ r) ∨ (¬(q → r)).
    
    Używając rezolucję proszę sprawdzić czy {A,B}|= C jest ważna.
    
    
16. Niech będą
    
    A ≡ (¬q → (p ∧ r))
    B ≡ r → (¬p ∧ ¬q)
    C ≡ (r ∨ w) → ¬(w → ¬q)
    
    Używając rezolucję proszę sprawdzić czy (A ∧ B) → C jest tautologią.
    
    
17. Niech będą
    
    A ≡ ∀x∀y∃z p(x,y,z)
    B ≡ ∀u∀v∀w∀x∀y∀z (p(x,y,u) ∧ p(y,z,v)) → (p(x,v,w) ↔ p(u,z,w))
    C ≡ ∃x (∀y p(x,y,y)) ∧ (∀y∃z p(z,y,x))
    
    Proszę transformować A, B oraz C do zbiorów klausuli.
    
    
18. Proszę obliczyć najbardziej ogólny unifikator dla następujących wyrażeń.
    
    a)   f(x,g(b))                         f(a,y)
    b)   f(h(x,b),y)                      f(h(a,y),x)
    c)   f(x,y)                              f(h(x,b),y)
    d)   g(x,h(x,y),h(y,h(x,y)))     g(x,y',h(z,y'))
    e)   g(x,h(x,y),h(y,h(x,y)))     g(x,y',h(y',z))
    f)   f(a,x,h(g(y)))                   f(z,h(z),h(z'))
    
    
19. Używając rezolucję proszę pokazać, że A ≡ (∀x∃y p(x,y) ∧ ∀y∃z q(y,z)) → ∀x∃y∃z (p(x,y) ∧ q(y,z)) jest tautologią.
    
    
20. Proszę dla następujących pytań podać drzewo SLD. Jakie odpowiedzi daje Prolog?
    

    1.  s(X) :- p(X), r(X).
        s(X) :- q(X).
        p(a).   q(a).   r(a).
        p(b).   q(c).   r(b).                        ?- s(X).

    2.  q(X) :- p(X), r(X).
        p(a).
        r(a).
        r(f(Y)) :- r(Y).                             ?- r(Z).  oraz  ?- q(Z).

    3.  p(X,Z) :- q(X,Y), p(Y,Z).
        p(X,X).
        q(a,b).                                      ?- p(X,b). 

21. Proszę dla następujących pytań podać drzewo SLD. Jakie odpowiedzi daje Prolog?
    

    1.  append1([],L,L).
        append1([H|L1],L2,[H|L3]) :- append1(L1,L2,L3).
       
        append2([H|L1],L2,[H|L3]) :- append2(L1,L2,L3).
        append2([],L,L).                                   ?- appendi(X,[3,4],[2,3,4]).
       

    2.  is_list([]).
        is_list([X|L]) :- is_list(L).                      ?- is_list(L).
       

22. Używając dzrewa SLD 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). 

23. Niech będzie dana następująca definicja predykatu memberc(X,L).

    memberc(X,[X|_]) :- !.
    memberc(X,[_|L]) :- memberc(X,L).
    

    Proszę porównać tą definicję z zwykłą definicją member(X,L).
    
    
24. 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)?
    
    
25. Proszę zdefiniować predykat list_to_term(L,T), który jest spełniony, jeżeli L jest niepustą listą liczb naturalnych a T jest termem zbudowany z tych liczb przy pomocy operatora +.
    Przykłady:

     ?- list_to_term([1,2,3,4],T).
     T = 1 + (2 + (3 + 4))
     ?- list_to_term([7],T).
     T = 7
    

26. Proszę zdefiniować predykat fpresent(A,L). A ma być atomem a L listą termów. Predykat ma być spełniony, jeśli istnieje term, który ma A jako główny funktor.
    Przykłady:

     ?- fpresent(father, [ mother(mary,john), father(bill,john) ]).
     yes
     ?- fpresent(father, [ mother(mary,john) ]).
     no
    

27. Niech będzie dana lista właściwości, n.p. [animate, male, canine, feline] oraz klausuly używające te właściwoście, n.p.

     animate(fred).
     animate(alice).
     male(fred).
     canine(alice).
     feline(fred).
    

    Proszę zdefiniować predykat checkprops(A,L), gdzie A jest dowolnym objektem a L listą właściwości. Predykat ma być spełniony, jeśli objekt A posiada wszystkie właściwoście w L, n.p.

     ?- checkprops(fred, [animate, male]).
     yes
     ?- checkprops(alice, [animate, feline]).
     no
    

28. Proszę zdefiniować predykat filter(P,L1,L2), który jest spełniony, jeżeli lista L2 zawiera dokładnie te elementy z listy L1, który spełniają predykat P.
    Przykład:

     pos(X) :- X > 0.
     neg(X) :- X < 0.
    
     ?- filter(pos,[1,2,0,5,-5,-6,8],L).
     L = [1,2,5,8]
     ?- filter(neg,[1,2,0,5,-5,-6,8],L).
     L = [-5,-6]
    

29. Proszę zdefiniować predykat powerset(L1,L2) używając predykat bagof.
    
    
30. Następujący predykat obliczący liczb Fibonacci'ego powtórzy dużą ilość obliczeń.

     fib(0,1).
     fib(1,1).
     fib(N,F) :- N >1, N1 is N-1, N2 is N-2, fib(N1,F1), fib(N2,F2), F is F1+ F2.
    

    Proszę predykat ten ulepszyć raz używając akumulator a raz używając funktor assert.
    
    
31. Proszę zrealizować koncept licznika. Licznik ma nazwę oraz wartość, i można go manipulować z operacjami init/2, getv/2, incr/1, decr/1 oraz del/1.
    Przykłady:

     ?- init(z,3).
     true
     ?- getv(z,V).
     V = 3
     ?- incr(z), decr(z), decr(z).
     true
     ?- getv(z,V).
     V = 2
     ?- del(z).
     true
     ?- get(z,V).
     no
    

32. Na wykład został umówiony predykat solve(State, Solution), któy używa depth first search.
    Proszę zmienić predykat solve taki, że
    
    1. używa depth first search z ograniczeniem globalnym.
       
    2. używa depth first search z iterative deepening.
       
       
33. Jak w Prologu można reprezentować automaty?
    Proszę zdefiniować predykat palindrom(L) raz konwencjonalnie a raz używając odpowiednego automatu.
    
    
34. Proszę zdefiniować predykat queens/1, który rozwiązuje problem 8 hetmanów.
    
    
35. Grafy z kosztami można zareprezentować używając zbiór faktów edge(Vertice1,Vertice2,Cost).
    
    
    1. Proszę zdefiniować predykat path(V1,V2,C), który obliczy koszty drogi C od V1 do V2.
       
    2. Proszę zdefiniować predykat mincost(V1,V2,C), który znajduje koszty minimalne drogi C od V1 do V2.
       
    3. Proszę rozwiązać punkt b) używając raz algorytm depth-first-search a raz algorytm breadth-first-search.
    4. Proszę rozwiązać punkt b) dla drzew and/or.