zkouska 1.2

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)

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.

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