Home     Termíny     Cvičení     Projekty     Rezervace termínu

Osnova

• Rozdílové seznamy
• Negace
• Rozebírání struktury
• zpět na stránku jen se zadáním

---

• Rozdílové seznamy
  • rozdílový seznam - dvojice proměnných Zacatek a Konec
  • zápis libovolný, např. Z,K; Z-K; Z\K; a pod.
  • spojení dvou rozdílových seznamů Z1-K1 a Z2-K2: K1=Z2
  • odebrání prvního prvku: Z-K = [H|Z1]-K (nový seznam Z1-K)
  • přidání prvku na konec: Z-K = Z-[H|K1] (nový seznam Z-K1)
  • je rozdílový seznam prázdný?: var(Z) nebo Z==K, záleží na konkrétní implementaci
• Neúplné datové struktury - analogicky
• Příklady programů s využitím rozdílových seznamů:
  1. Spojování seznamů:

     append(X-Y,Y-Z,X-Z).
     

  2. Obracení seznamu:

     reverse(S,T):-rev(S,T-[]).
     
     rev([],T-T).
     rev([H|S],T-A):-rev(S,T-[H|A]).
     

  3. Hanojské věže:

     :-op(400,xfx,'=>').
     
     hanoi(N,A,B,C,R):-hanoi1(N,A,B,C,R-[]).
     
     hanoi1(1,A,B,C,[A=>B|R]-R).
     hanoi1(N,A,B,C,R0-R):-N>1,
                           N1 is N-1,
                           hanoi1(N1,A,C,B,R0-R1),
                           R1=[A=>B|R2],
                           hanoi1(N1,C,B,A,R2-R).
     
     

  4. Procházení stromem: traverse(Tree,Values)

     Uzly stromu Tree jsou reprezentovány termy

     • tree(Left,Value,Right), kde Left a Right jsou opět stromy a Value je ohodnocení uzlu
     • leaf(Value), kde Value je ohodnoceni uzlu

     Seznam Values obsahuje právě ohodnocení všech uzlů stromu Tree, a to v pořadí
     a) preorder
     b) inorder
     c) postorder
     d) po patrech (vznikne prohledáváním do šířky - BFS)
     

     Pro řešení použijte techniky rozdílových seznamů (při prohledávání do hloubky spojování seznamů, při prohledávání do šířky frontu).

     Příklad:
     

     
                         6
                        / \
                       /   \
                      /     \
                     2       8
                    / \     / \
                   1   4   7   9
                      / \
                     3   5
     
     traverse(Tree,PreOrder,InOrder,PostOrder,BFS):-
              traverse(preorder,Tree,PreOrder),
              traverse(inorder,Tree,InOrder),
              traverse(postorder,Tree,PostOrder),
              traverse(bfs,Tree,BFS).
     
     testing_tree(tree(tree(leaf(1),2,tree(leaf(3),4,leaf(5))),
                  6,tree(leaf(7),8,leaf(9)))).
     
     ?-testing_tree(Tree),traverse(Tree,PreOrder,InOrder,PostOrder,BFS).
     
      PreOrder = [6,2,1,4,3,5,8,7,9],
      InOrder = [1,2,3,4,5,6,7,8,9],
      PostOrder = [1,3,5,4,2,7,9,8,6],
      BFS = [6,2,8,1,4,7,9,3,5] ?;
     
     
     no
     
     

     traverse(PreOrder,InOrder,PostOrder,BFS):-
              testing_tree(Tree),
              traverse_pre(Tree,PreOrder),
              traverse_in(Tree,InOrder),
              traverse_post(Tree,PostOrder),
              traverse_bfs(Tree,BFS).
     
     testing_tree(tree(tree(leaf(1),2,tree(leaf(3),4,leaf(5))),
                  6,tree(leaf(7),8,leaf(9)))).
     
     
     traverse_pre(T,Pre):-
             t_pre(T,Pre,[]).
     
     t_pre(leaf(V),[V|S],S).
     t_pre(tree(L,V,R),[V|S],S2):-
             t_pre(L,S,S1),
             t_pre(R,S1,S2).
     
     traverse_in(T,In):-
             t_in(T,In,[]).
     
     t_in(leaf(V),[V|S],S).
     t_in(tree(L,V,R),S,S2):-
             t_in(L,S,[V|S1]),
             t_in(R,S1,S2).
     
     traverse_post(T,Post):-
             t_post(T,Post,[]).
     
     t_post(leaf(V),[V|S],S).
     t_post(tree(L,V,R),S,S2):-
             t_post(L,S,S1),
             t_post(R,S1,[V|S2]).
     
     traverse_bfs(T,BFS):-
             t_bfs([T|K]-K,BFS).
     
     t_bfs(Z-K,[]):-var(Z),!.
     t_bfs([leaf(V)|Z]-K,[V|S]):-
             t_bfs(Z-K,S).
     t_bfs([tree(L,V,R)|Z]-[L,R|K],[V|S]):-
             t_bfs(Z-K,S).
     
     

  5. Napište predikát flatten/2 pro narovnání seznamu (s využitím rozdílových seznamů):

     ?-flatten([[1,2],[3],[],[4,[5,6],7]],S).
     
     S=[1,2,3,4,5,6,7];
     no
     

     flatten(X,Y):-flatten1(X,Y-[]).
     
     flatten1(H,[H|P]-P):-var(H),!.
     flatten1([],P-P):-!.
     flatten1(H,[H|P]-P):-atomic(H),!.
     flatten1([H|S],P0-P):-flatten1(H,P0-P1),flatten1(S,P1-P).
     

  6. Napište predikát quicksort/2 (s využitím rozdílových seznamů).

  7. Pro zopakování jednoduchých seznamů zkuste naprogramovat některé řadící algoritmy (bubblesort, insertsort, selectsort, mergesort, atd.).

• Negace
  

  Mějme následující databázi faktů:

  
  kurak('Petr').
  
  sachista('Petr').
  sachista('Pavel').
  

  1. S využitím negace napište predikát spolubydlici/1, který najde takového spolubydlícího, který je nekuřák a zároveň šachista.

     spolubydlici(X):-sachista(X), \+ kurak(X).
     

     Opačné pořadí cílů nefunguje, protože negovaný cíl neumí najít instance proměnných, pro které by negace platila. Umí pouze otestovat vlastnosti instanciovaných proměnných.

• Rozebírání struktury
  

  Predikát g/1 testuje (kopíruje funkci systémového predikátu ground/1), zda jeho argument je uzavřený term (neobsahuje neinstanciované proměnné).

  varianta I
  - pomocí vestavěného metalogického predikátu univ '=..'/2 a procházení seznamu

  g1(T):-
    nonvar(T),
    T=..[_|Args],
    g1_list(Args).
  
  g1_list([]).
  g1_list([H|T]):-
    g1(H),
    g1_list(T).
  

  varianta II
  - pomocí vestavěných metalogických predikátů functor/3 a arg/3 a aritmetických operací

  g2(T):-
    nonvar(T),
    functor(T,Name,Arity),
    g2(0,Arity,T).
  
  g2(A,A,_).
  g2(C,A,T):-
    C1 is C+1,
    arg(C1,T,Arg),
    g2(Arg),
    g2(C1,A,T).
  

  varianta III
  - nejefektivnejší je ošetřit každý typ struktury zvlášť

  g(T):-
    var(T),!,fail.
  g(T):-
    atomic(T),!.
  g(T):-
    T=[_|_],!,
    g_list(T).
  g(T):-
    T=..[_|Args],
    g_list(Args).
  
  g_list([]).
  g_list([H|T]):-
    g(H),
    g_list(T).
  

  - testy

  | ?-  g(s(1,a,c(x,[X,34]))).
  
  no
  | ?- X=s, g(s(1,a,c(x,[X,34]))).
  
  X = s ? ;
  
  no
  | ?- X=Y,g(s(1,a,c(x,[X,34]))).
  
  no
  | ?- g(1).
  
  yes
  | ?- g(X).  
  
  no
  

  - úkoly
  1. Jak dlouhý bude výpočet v jednotlivých variantách
     a) pro proměnnou, např. ?-g(X).
     b) pro konstantu, např. ?-g(a).
     c) pro seznam, např. ?-g([1,2,3,4]).
     Popište, co se děje v jednotlivých variantách při tomto testu.

---

^