# Zkouška 22.6.

<{ForumPost(poster="Viki.n", timestamp=2017-06-23 17:05:25)}>
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](http://forum.matfyz.info/viewtopic.php?f=169&t=11052) 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)

    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)

    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)

    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)

    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 
    
    


<{/ForumPost}>

<{ForumPost(poster="knezi", timestamp=2018-05-30 13:34:12)}>
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 :).
<{/ForumPost}>