# zkouska 1.2

<{ForumPost(poster="Fistandantilus", timestamp=2008-02-01 13:08:28)}>
prolog  
1) mame n-arni strom a cislo k. uzly jsou cislovany lokalne od 0 vratte listy takove ze soucet cisel predchudcu je roven k

                  a 0
                / | \
            b0   c1    d2
          /  \    |     | \ 
        e0  f1   g0   h0 i1
    
    pro k = 3 tedy vratime list i 
    pro k = 2 vratime listy h
    

2) zjistete zda je graf bipartitni, v pripade ze ano vratte dotvrzujici mnoziny vrcholu (vite co myslim)  
  
haskell  
3) seznam vektoru vratte vektory, ktere nejsou dominovany zadnym vektorem  
4) seznam dvojic (cena,objem) a objem batohu, vratte nejcenejsi predmety, ktere se do batohu vejdou  
  
Velky priklad  
presne si nepamatuju  
  
  
(priklady 1 - 4 jsou presneji popsany v ve zkouskach z roku 2005)
<{/ForumPost}>

<{ForumPost(poster="Triebenekl", timestamp=2008-02-01 15:23:00)}>
Pokud si to dobře pamatuji, velký příklad byl:  
  
Řídíte letiště.  
Máte časy příletu a odletu letadel (každé letadlo právě jednou přiletí a odletí).  
Dále máte ke každému letadlu výčet bran, ke kterým ho můžete přistavit (bude tam stát dokud neodlétne).  
Pokud se některé letadlo při příletu nevejde k žádné své bráně, dáte ho na odstavnou plochu (tam zůstane do odletu).  
  
Úkolem je naimplementovat heuristický algoritmus, který rozvrhne plán přistavování letadel tak, aby se jich co nejvíc podařilo přistavit k branám.
<{/ForumPost}>

<{ForumPost(poster="elgriton", timestamp=2008-02-07 20:41:23)}>
Prvni priklad s n-arnimi stromy. Cislovani bylo myslim trochu jine. Ohodnoceni se dedi z otce na prvorozeneho syna, pricita se u jeho bratru. Tady je nejaky kod, co jsem zplodil potom doma. Za spravnost nerucim.  

    % N-arni strom
    % 
    % Zadani:
    % Mejme n-arni strom a dane cislo M. Deti jednoho vrcholu jsou cislovany zleva od nuly. Cesta z korene do vrcholu je ohodnocena jako soucet cislovani jednotlivych vrcholu na ceste. Ukolem je vypsat vsechny vrcholy, jejichz cesta ma ohodnoceni prave M.
    % --------------------
    % Reprezentace dat:
    % Vstup:	tree(Value,[Children])
    % ---------------
    
    % like a DFS with some cutting, if found somewhere
    
    % level(+T,+M,-L)
    level(T,M,L):-level(T,0,M,[],L).	% wrapper
    
    % check nodes alone
    level(t(_,Ch),N,M,In,Out):-	% not yet here, continue deeperN<M, level(Ch,N,M,In,Out).
    
    level(t(V,Ch),M,M,In,[V|Out]):-	% found,level(Ch,M,M,In,Out).	% and try its first child, if any
    
    % check lists of node's children
    level([],_,_,In,In).	% return accumulator
    
    % inside a list
    level([Head|Tail],N,M,In,Out):-	% not yet here,N<M, N1 is N+1,level(Head,N,M,In,Out1),	% continue among first's childrenlevel(Tail,N1,M,Out1,Out). % continue among this' brothers
    
    % found in a list
    level([t(V,Ch)|_],M,M,In,[V|Out]):-	% foundlevel(Ch,M,M,In,Out).	% search among children
    


<{/ForumPost}>