Zadania (Prolog)

  1. Konkatenacja list można w Prologu zdefiniować następująco.
      append([], L, L).
      append([X|L1], L2, [X|L3]) :- append(L1, L2, L3).
        
    Proszę zdefiniować predykaty member/2 oraz last/2.

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

  4. Proszę zdefiniować predykat rzym/2, który transformuje rzymskie liczby do liczb dziesiętnich.

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

  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 "grafu odpowiedzi" proszę ilustrować, jak Prolog odpowiada na pytanie
     ?- append(X, [3,4], [2,3,4]).
    
  8. 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 "grafy odpowiedzi" proszę ilustrować, jak Prolog odpowiada na pytania qi(tom,pat). oraz qi(liz,jim).

  9. Proszę zdefiniować predykat permutation(L1,L2), który jest spełniony, jeżeli lista L2 jest permutacją listy L1.
    Przy użyciu ";" powiennien być możliwe wyliczać wszystkie permutacje listy L1.

  10. Proszę zdefiniować predykat accept(State,String), który simuluje zaakceptowania Stringu przez niedeterministyczny autmat końcowy z krokami ε.

  11. 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(Plac1,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 Place1-Place2: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-londom:sr806:16:10, london-edinburgh:ba4822:18:40].
         
  12. Proszę zdefiniować predykat eight, który rozwiązuje problem 8 hetmanów.

  13. Proszę zdefiniować predykat palindrom(L) raz "konwencjonalnie" a raz używając odpowiednego automatu.

  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 ≡ (¬q → (p ∧ r))
    B ≡ r → (¬p ∧ ¬q)
    C ≡ (r ∨ w) → ¬(w → ¬q).

    Używając rezolucję proszę pokazać, że (A ∧ B) → C jest tautologią.

  16. Proszę zdefiniować predykat sorted(L), który jest spełniony jeżeli lista L jest posortowana. Jak można zdefiniować predykat permutation z zadania 10. używając sorted?

  17. Proszę zrealizować algorytm mergesort.

  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ć pełne 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).                             ?- q(Z).
    3.  p(X,Z) :- q(X,Y), p(Y,Z).
       p(X,X).
       q(a,b).                                      ?- p(X,b). 
  21. Niech będą dane następująje definicje.
     append1([],L,L).
     append1([H|L],L2,[H|L3]) :- append1(L1,L2,L3).
    
     append2([H|L1],L2,[H|L3]) :- append2(L1,L2,L3).
     append2([],L,L).
    
    Proszę podać drzewa SLD dla pytań ?- append1(X,[3,4],[2,3,4]). i ?- append2(X,[3,4],[2,3,4]).. Jakie rezolucje wykonuje Prolog?

  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. Proszę zoptimalizować następucący program.
     class(Number, positive) :- Number > 0.
     class(0,zero).
     class(Number, negative) :- Number < 0. 
  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 tak jest i jak można to zreperować (bez zmian cut'u i drugiej reguły)?

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

  26. Proszę zdefiniować predykat variables(T, L), który jest spełniony, jeżeli L jest listą zmiennich w termie T.

  27. Proszę zdefiniować predykat iscopylist(L1, L2), który jest spełniony, jeżeli lista L2 jest kopią listy L1.

  28. Proszę zdefiniować predykat count(A, L, N), który jest spełniony, jeżeli N jest liczbą wystąpienia termu A w termie T. Przykłady:
     ?- count(a, f(a), N).
     N = 1
     ?- count(a, f(a, g(b,a)), N).
     N = 2
     ?- count(a, f(a,X)), N).
     N = 1
    
  29. Proszę zdefiniować predykat sublist(L1, L2), który sprawdza, czy lista L1 jest podlistą na dowolnym pożomie listy L2. Przykłady:
     ?- sublist([1,2],[7,[1,2,3],4]).
     true
     ?- sublist([1,2],[7,[1,4,2,3],4]).
     false
    
  30. Proszę zdefiniować predykat powerset(L1, L2) używając predykat bagof.

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

  32. Proszę zrealizować koncept licznika. Licznik ma nazwę oraz wartość, i można go manipulować z operpacjami init/2, get/2, inc/1, dec/1 oraz del.
    Przykłady:
     ?- init(z,3).
     true
     ?- get(z,V).
     V = 3
     ?- inc(z), dec(z), dec(z).
     true
     ?- get(z,V).
     V = 2
     ?- del(z).
     true
     ?- get(z,V).
     false
    
  33. Na wykł 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 breadth first search.

  34. Proszę zdefiniować predykat ewal(Formuła, Lista, Wartość), któy znajduje wartość 1 lub 2 dla formuły logiki zdanowejFormuła. Lista, to lista wartości zmiennych.
    Przy pomocy ewal proszę zdefiniować predykat taut(Formuła), który sprawdza, czy Formuła jest tautologią.