Stránka 1 z 1

Zkouška 22.6.

Napsal: 23. 6. 2017 17:05
od Viki.n
1) Prolog: Máme daný orientovaný graf reprezentovaný jako [vrchol-[seznam sousedů]|...], zjistěte, zda v něm je orientovaná kružnice, a pokud ano, vraťte vrcholy nějaké takové kružnice v tom pořadí, jak jsou na kružnici. Chce se polynomiální řešení.

2) Prolog: Máme daný BVS klastickým způsobem, tj např. t(t(nil,0,nil)1,nil) a číslo, máme vrátit strom stromovými rotacemi upravený tak, aby dané číslo, nachází-li se ve stromě, nebo nejblíže vyšší nebo nižší bylo v kořeni

3) Haskell: Tetris: Máme obdélníkovou tabulku uloženou po řádcích jako seznam seznamů Intů. Vymažte z ní všechny sloupce, které neobsahují žádnou nulu.

4) Haskell: Očíslování stromu jako čtvrtý příklad tady akorátže preorder, pozor na to, že strom je obecný (=ne binární).

Velký příklad: Odtamtéž, co 4., až na to, že komodity nemají určený cílový objem a cílem je maximalizovat součet toků. Řekli nám, že se jedná nejen o NP-úplnou úlohu, ale že i její bruteforce řešení je obtížné, proto není potřeba najít optimum, ale stačí nějaký tok, který nepůjde triviálně zlepšit. Tzn. například najít optimum pro jednu komoditu, zafixovat ji tak a hledat optimum pro druhou a tak dále je přijatelné řešení. Nevadilo jim exponenciální hledání zlepšujících cest, ikdyž to jde dělat lineárně.

Řešení
1)

Kód: Vybrat vše

removeVertex(_,[],[]).
removeVertex(X,[X-_|T],T1):-removeVertex(X,T,T1).
removeVertex(X,[X1-S|T],[X1-S1|T1]):-delete(X,S,S1),removeVertex(X,T,T1).

cutTo(A,[A|_],[A]). %Vezme část seznamu až do prvního výskytu prvku A.
cutTo(A,[B|Z],[B|Z1]:-A/=B,cutTo(A,Z,Z1).

circle(G,C):-member(X-[],G),removeVertex(X,G,G1),!,circle(G1,C). %Odstraním z grafu všechny vrcholy s outdegree 0
circle([V-E|G],C):-circle_([V-E|G],[V],C). %V grafu bez vrcholů s outdegree 0 najdu kružnici na první pokus DFSkem
circle_(G,[V|A],C):-member(V-E,G),member(V1,E),member(V1,[V|A]),!,cutTo(V1,[V|A],B),reverse(B,C).
circle_(G,[V|A],C):-member(V-E,G),member(V1,E), circle_(G,[V1,V,|A],C).
2)

Kód: Vybrat vše

splay(P,t(L,P,R),t(L,P,R)).
splay(P,t(L,P1,nil),t(L,P1,nil)):-P>P1,!.
splay(P,t(nil,P1,R),t(nil,P1,R)):-P<P1,!.
splay(P,t(L,P1,R),T):-P<P1,splay(P,L,L1),rotRight(t(L1,P1,R),T).
splay(P,t(L,P1,R),T):-P>P1,splay(P,R,R1),rotLeft(t(L,P1,R1),T).

rotRight(t(t(A,B,C),D,E),t(A,B,t(C,D,E))).
rotLeft(A,B):-rotRight(B,A).
3)

Kód: Vybrat vše

filtrovatPodle::[a]->[Bool]->[a]
filtrovatPodle _ [] = []
filtrovatPodle [] _ = []
filtrovatPodle (a:as) (b:bs) |b         =  (a:(filtrovatPodle as bs))
                             |otherwise = filtrovatPodle as bs

vymazat::[[Int]]->[[Int]]
vymazat (a:as) = map (\x -> filtrovatPodle x mask) (a:as)
             where mask = foldl (zipWith (||)) (map (=0) a) (map (map (=0)) as)
4)

Kód: Vybrat vše

ocisluj::NT a->NT (a,Int)
ocisluj x = y
        where (y,_)=ocislujSeZacatkem 1 x

ocislujSeZacatkem :: Int -> NT a -> (NT (a,Int),Int)
ocislujSeZacatkem x (N a p) = ((N (a,x) p1),n)
                        where (p1,n) = ocislujPole (x+1) p

ocislujpole :: Int -> [NT a] -> ([NT (a,Int)],Int)
ocislujpole x [] = ([],x)
ocislujpole x (a:as) =((b:bs),z)
                 where (b,x1) = ocislujSeZacatkem x a
                       (bs,z) = ocislujpole x1 as 


Re: Zkouška 22.6.

Napsal: 30. 5. 2018 13:34
od knezi
Jen ke dvojce prologu. Dle kódu si můžete vybrat, jestli ten element bude největší nižší nebo nejnižší vyšší. Nemusíte hledat ten s nejmenším rozdílem oproti hledanému. Ušetří to dost práce :).