# Zkouska 17.2.

<{ForumPost(poster="Anonymous", timestamp=2006-02-17 13:16:36)}>
Ahoj! Tady je zadani vcerejsich malych prikladu:  
Prolog

    Vytvorte seznam vsech rostoucich posloupnosti prirozenych cisel s danym souctem (bez pouziti setof/bagof).

    Projdete graf pomoci DFS a ke kazdemu vrcholu pridejte cas posledni pruchodu.

Haskell

    Definujte binarni strom s daty pouze v listech. Vytvorte fci, ktera pro dany strom rozlozi listy do trid podle poctu skoku doprava pri ceste od korene k danemu listu.

    Hladovym algoritmem najdete minimalni vrcholove pokryti (kazda hrana musi mit v pokryti alespon jeden vrchol).


<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2006-02-17 13:18:47)}>
Ted se divam, ze jsem tam napsal spatne datum. Tohle je zkouska ze 16.2. I kdyz to je stejne jedno...
<{/ForumPost}>

<{ForumPost(poster="zapo", timestamp=2006-02-18 16:42:40)}>
To DFS bolo z 1 vrcholu, takze sa to nemuselo robit pre cely graf. Ak by nahodou niekomu mohlo pomoct riesenie, tak:

    % DFS z vrcholu
    % g(V,E), V=[a,b,...] E=[e(a,b),...]
    
    % prejdi(+ES,+E,+Vrchol,+KdeBol,-KdeBOlOut,+TIn,-TOut,-Zoz)
    prejdi([],_,_,KB,KB,T,T,[]).
    prejdi([e(A,B)|ES],E,Vrchol,KdeBol,KdeBolOut,TIn,TOut,Zoz):-
        (   A \= Vrchol;
            ( A=Vrchol, member(B,KdeBol) )
        ),
        prejdi(ES,E,Vrchol,KdeBol,KdeBolOut,TIn,TOut,Zoz).
    prejdi([e(A,B)|ES],E,Vrchol,KdeBol,KdeBolOut,TIn,TOut,Zoz):-
        TIn1 is TIn + 1,
        A = Vrchol,
        not(member(B,KdeBol)),
        prejdi(E,E,B,[B|KdeBol],KBO,TIn1,TOut1,Zoz1),
        TOut2 is TOut1 + 1,
        prejdi(ES,E,Vrchol,KBO,KdeBolOut,TOut2,TOut,Zoz2),
        append(Zoz1,Zoz2,Zoz3),
        Zoz = [B-(TIn1,TOut2)|Zoz3].
    
    % dfs(+g(V,E),-Zoznam)
    dfs(g([],_),[]).
    dfs(g([A|_],E),Zoznam):-
        prejdi(E,E,A,[A],_,0,T,Zoz),
        T2 is T + 1,
        Zoznam = [A-(0,T2)|Zoz].

Je to trocha upravene, a vypise to nie len cas vystupu ale aj cas vstupu. Zacina z 1. vrcholu.  
  
Ako velky priklad bolo priblizne nieco taketo:

 > Distribuovany tvar polynomu viac premennych je dany zoznamom, obsahujucich absolutny clen a zoznam mocnin premennych pre dany clen.  
 > Ulohou bolo dostat na vstupe zoznam premennych a polynom (s operaciamy plus, minus, krat a mocnina na prirodzene cislo), ktory trebalo previest na distribuovany tvar.

Na zaciatku sa mi to zdalo ako nieco nepochopitelne ale ked som sa nad tym zamyslel a Hric ukazal aj priklad, tak sa to celkom dalo a k mojmu riesenie v podstate ani nemal ziadne vyhrady :)  
  
Ked tak este ten priklad, co ukazal:

    premenne: [x, y, z]
    polynom: ((x+3)*(y*z)^5)
    dist. tvar: (abs - x, y, z)
         1 - 1, 5, 5
         3 - 0, 5, 5


<{/ForumPost}>