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 hanoi(N), który pisze na ekran rozwiązanie problemu Wieże Hanoi.
   
   
5. Proszę zdefiniować predykat rzym/2, który transformuje rzymskie liczby do liczb dziesiętnich.
   
   
6. 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. Proszę zdefiniować predykat connection(Miasto1, Miasto2, Odjazd, L), który znajduje połączenia pociągowe między Miasto1 a Miasto2.
   Podstawowe informacje o pociągach znajdują się w predykacie train(Miasto1, Miasto2, Odjazd, Przyjazd, Numer), n.p.
   oznacza train(gdańsk, malbork, 8.03, 9.15, 813), że pociąg numer 813 odjeżdża z Gdańska o 8.03 i będzie w Malborku o 9.15.
   Lista L zawiera trasę podróży od Miasto1 do Miasto2.
   Przykład:

    ?- connection(gdańsk, warszawa, 8.00, L).
    L = [(813, malbork), (813, toruń), (733, płock), (750, warszawa)] 

8. 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)?
   
   
9. 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 q_i(tom,pat). oraz q_i(liz,jim).
   
   
10. 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.
    
    
11. 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
    
    
12. 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ą.
    
    
13. 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?
    
    
14. Proszę zrealizować algorytm mergesort.
    
    
15. Proszę obliczyć mgu 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'))
    
    
16. 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ą.
    
    
17. 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). 

18. Niech będzie dana następująja definicja.

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

    Proszę podać rezolucję SLD dla pytania ?- append(X,[3,4],[2,3,4]).. Jaką rezolucję wykonuje Prolog?
    
    
19. Proszę zdefiniować predykat fibonacci(N,F), który jest spełniony, jeżeli F jest N-tą liczbą Fibonacci'ego.
    
    
20. 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.
    
    
21. 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). 

22. Proszę zoptimalizować następucący program.

     class(Number, positive) :- Number > 0.
     class(0,zero).
     class(Number, negative) :- Number < 0. 

23. Proszę zdefinoiwać predykat max(L,N), który jest spełniony, jeżeli N jest maksimum w liście L.
    
    
24. Proszę zdefiniować predykat split(L1, L2, L3), który podzieli listę L1 tak, że w L2 są wszystkie elementy z L1 mniejsze od zera, a w L3 wszystkie większe albo równy do zera.
    
    
25. Zbiory można reprezentować jako listy. Dla takiej reprezentacji proszę zrealizaować operacje A ⊆ B, A ∪ B oraz A \ B.
    
    
26. 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)?
    
    
27. Proszę zdefiniować predykat flatten(L1, L2), który jest spełniony, jeżeli lista L2 jest wersją płaską listy L1. Przykład:

     ?- flatten([1,2,[3,4,[5,6],7],8,[9],10], L).
     L = [1,2,3,4,5,6,7,8,9,10]
    

28. Proszę zdefiniować predykat iscopylist(L1, L2), który jest spełniony, jeżeli lista L2 jest kopią listy L1.
    
    
29. Proszę zdefiniować predykat variables(T, L), który jest spełniony, jeżeli L jest listą zmiennich w termie T.
    
    
30. 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
    

31. 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,2,3],4]).
     false
    

32. Proszę zdefiniować predykat powerset(L1, L2) używając funktor bagof.
    
    
33. 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.
    
    
34. 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
    

35. Dla bazy rodziń z wykładu proszę pisać pytania, żeby znaleść
    
    
    1. nazwiska rodziń bez dzieci.
    2. pracujące dzieci.
    3. nazwiska rodziń z pracującą żoną i nie pracującym mężem.
    4. dzieci, których rodzicy mają conajmniej 15 lat różnicy we wieku.
    
    Dla bazy rodziń z wykładu proszę zdefiniować relację
    
    
    1. twins(Child1,Child2).
    2. n-th-child(N,Family,Child).
    
    
36. Proszę zdefiniować predykat palindrom(L) raz konwencjonalnie a raz używając odpowiednego automatu.
    
    
37. Proszę zdefiniować predykat queens/1, który rozwiązuje problem 8 hetmanów.
    
    
38. Proszę zdefiniować predykat eval(Formula,List,Value), który ewaluuje formuły z logiki staniowej używając wartości z listy List dla zmiennych.
    
    
39. 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.