Zkouška 14.5.2007

PROLOG

1. Permutaci prvku od 1 do n muzeme reprezentovat bud jako "vektor obrazu"
   napr. pro n=7 termem v(7, [3,2,4,1,6,5,7])
   nebo jako seznam netrivialnich cyklu prislusneho zobrazeni
   c(7, [ [1,3,4], [5,6] ] ) (cykly [2] a [7] jsme vynechali).
   Soucin permutaci P1 a P2 je permutace P3, ktera vznikne slozenim zobrazeni P1 P2, tj. P3(x)=P1(P2(x)).
   Sestavte predikaty, ktere realizuji nasobeni a umocnovani permutaci reprezentovanych pomoci cyklu.

2)Mate k dispozici predikat modry/1, ktery uspeje, pokud argument je modry. Sestavte predikat
natretiny(+Seznam, -Prvni, -Druhy, -Treti),
ktery rozdeli efektivnim zpusobem vstupni seznam na tri seznamy obsahujici priblizne stejne modrych prvku (Zretezeni seznamu Prvni, Druhy a Treti je seznam Seznam, pocty modrych prvku v seznamech Prvni, Druhy a Treti se mohou lisit nejvyse o 1). Pri jeho konstrukci nesmite pouzit zadnou aritmetiku (ani predikat length).

HASKELL

3. Ridka matice je reprezentovana jako trojice (m,n,s), kde m je pocet radek, n je pocet sloupcu a s je seznam trojic (i,j,aij) {kde i je cislo radky, j je cislo sloupce a aij je nenulova hodnota} usporadany vzestupne podle i a uvnitr radek podle j.
   Naprogramujte funkce, ktere v teto reprezentaci realizuji
   a) transpozici matic
   b) nasobeni matic
   c) umocnovani matic (dobrovolne
   Nejedna se tedy o pole v Haskellu

4. Definujte prirozenou reprezentaci binarniho stromu, v jehoz uzlech je ulozena informace nejakeho typu (podtridy Ord).
   Naprogramujte funkci, ktera ze zadaneho binarniho vyhledavaciho stromu vypusti vsechny uzly, ktere obsahuji hodnotu klice, na kterem zadana funkce krit vrati hodnotu True.

Ak mate riesenia, sem s nimi. Najzaujimavejsie asi bude riesenie toho prveho.

% natretiny(+,-,-,-)

natretiny(Seznam,Prvni,Druhy,Treti):-
prvni_tretina(Seznam,Prvni,Zbytek),napoloviny(Zbytek,Druhy,Treti).


% prvni_tretina(+,-,-)

prvni_tretina(Seznam,Prvni,Zbytek):-
tretina2(Seznam,Seznam,Prvni,Zbytek).

% tretina2(+,+,-,-)

tretina2(L1,L2,P,Zb):-
odeber3modre(L1,L1Zb),!,odeber1modry(L2,PZb,P,L2Zb),tretina2(L1Zb,L2Zb,PZb,Zb).

tretina2(_,L2,[],L2).

% odeber1modry(+,+,-,-)

odeber1modry([H|L],PZb,[H|L2],Zb):-
modry(H),!,L2=PZb,Zb=L;odeber1modry(L,PZb,L2,Zb).

% odeber2modre(+,-)

odeber2modre([H|L],Zb):-
modry(H),!,odeber1modry(L,_,_,Zb);odeber2modre(L,Zb).

% odeber3modre(+,-)

odeber3modre([H|L],Zb):-
modry(H),!,odeber2modre(L,Zb);odeber3modre(L,Zb).


% napoloviny(+,-,-)

napoloviny(L,L1,L2):-polovina2(L,L,L1,L2).

% polovina2(+,+,-,-)

polovina2(L1,L2,P,Zb):-
odeber2modre(L1,L1Zb),!,odeber1modry(L2,PZb,P,L2Zb),polovina2(L1Zb,L2Zb,PZb,Zb).

polovina2(_,L2,[],L2).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% TEST

:-op(100,xfy,->).

modry(m).

s([m,m,a,m,m,b,m,m]).
s([a,m,b,m,c,m,d,m,e,m,f]).
s([a,b,c,m,m,d,e,f,m,g,h,i,m,j,k,l]).

test:-s(X),natretiny(X,L1,L2,L3),write(X->L1+L2+L3),nl,fail.

data Tree a = Nil | ND (Tree a) a (Tree a)

vypust::(a->Bool)->Tree a->Tree a

vypust _ Nil = Nil

vypust krit ND l v p| not krit v = lt v pt| lt == Nil = pt| pt == Nil = lt| otherwise ND ltBEZmax maxlt pt
    wherelt = vypust krit lpt = vypust krit p(ltBEZmax,maxlt)=bezMAX lt


bezMAX::Tree a->(Tree a,a)

bezMAX ND l v p| p == Nil = (l,v)| otherwise = (ND l v pt, maxpt)
    where(pt,maxpt)=bezMAX p