# Zk. 29. 05. 2012

<{ForumPost(poster="jans", timestamp=2012-05-29 18:05:04)}>
Zdravím,  
  
dnešní zadání zkoušky bylo takovéto:  
**Prolog 1**: Definovat predikát, který obdrží ohodnocení výrokových proměnných, tj. asociativní seznam a vrátí všechna ohodnocení těchto proměnných, která se liší alespoň ve dvou hodnotách.  
Nástin řešení: vytáhnout si z předaného ohodnocení názvy proměnných, vygenerovat si všechna možná ohodnocení a z nich vyházet ta, která se od zadaného ohodnocení buď neliší nebo se liší právě v hodnotě jedné proměnné.  
  
**Prolog 2**: Na vstupu máme orientovaný graf bez smyček a multihran. Graf je zadán jako seznam ve tvaru vrchol-hrany, kde hrany je seznam sousedů vrcholu. Dále máme zadán seznam ekvivalentních vrcholů a máme provést kontrakci těchto vrcholů do jednoho, tj. hrana povede z tohoto vrcholu do nějakého vrcholu mimo tento seznam pouze pokud vedla alespoň z jednoho vrcholu v tomto seznamu a naopak. Je třeba dát pozor, aby nevznikly smyčky a multihrany, případně je poté odstranit.  
  
**Haskell 3**: Máme zadaný datový typ (Bag a = Item a | Items \[a]) a typ funkce fold, která má tuto strukturu procházet. Máme definovat tuto funkci a poté ještě funkci listy, která vrátí seznam všech položek v Item a v této datové struktuře.  
  
**Haskell 4**: Dostaneme číslo n a máme vygenerovat nekonečný seznam posloupností délky n, které jsou uspořádány maximo-lexikograficky, někde to tu již na fóru je, nicméně přikládám řešení těchto posledních dvou příkladů.  

    -- Zkouskovy priklad cislo 3:
    data Bag a = Item a | Items [Bag a]
    
    -- a) Definovat funkci fold pro obecny pruchod datovou strukturou.
    fold :: (a -> b) -> ([b] -> b) -> Bag a -> b
    fold func listFunc (Item x) = func x
    fold func listFunc (Items xs) = listFunc [fold func listFunc bag | bag <- xs]
    
    -- b) Definovat funkci listy, ktera vrati seznam polozek s datovymi konstruktory Item.
    listy :: Bag a -> [a]
    listy bag = fold makeList joinLists bag
    
    makeList :: a -> [a]
    makeList x = [x]
    
    joinLists :: [[a]] -> [a]
    joinLists [] = []
    joinLists (x:xs) = x ++ joinLists xs
    
    -- > listy (Items [Item 1, Item 2, Items [Item 3, Item 4], Item 5])
    -- [1,2,3,4,5]
    
    -------------------------------------------------------------------
    
    -- Zkouskovy priklad cislo 4 - vygenerovat nekonecny seznam posloupnosti
    -- delky n usporadanych v maximolexikografickem usporadani.
    gen :: Int -> [[Int]]
    gen n = genWithMax n 1
    
    genWithMax :: Int -> Int -> [[Int]]
    genWithMax n max = [xs | xs <- var n max, max `elem` xs] ++ genWithMax n (max + 1)
    
    var :: Int -> Int -> [[Int]]
    var 0 _ = [[]]
    var k n = [x:xs | x <- [1..n], xs <- var (k - 1) n]
    
    -- > take 10 (gen 2)
    -- [[1,1],[1,2],[2,1],[2,2],[1,3],[2,3],[3,1],[3,2],[3,3],[1,4]]
    


<{/ForumPost}>

<{ForumPost(poster="kolage", timestamp=2012-06-06 20:22:51)}>
Nevíte, jestli letos nebudou velké úlohy nebo je to jen výjimečnost 1. termínu?
<{/ForumPost}>

<{ForumPost(poster="Shigi", timestamp=2012-06-06 22:04:49)}>

 > kolage wrote:Nevíte, jestli letos nebudou velké úlohy nebo je to jen výjimečnost 1. termínu?

Budú aj veľké úlohy.  
  
Viď [http://ksvi.mff.cuni.cz/~dvorak/vyuka/NPRG005/](http://ksvi.mff.cuni.cz/~dvorak/vyuka/NPRG005/)
<{/ForumPost}>

<{ForumPost(poster="jans", timestamp=2012-06-10 13:09:33)}>

 > kolage wrote:Nevíte, jestli letos nebudou velké úlohy nebo je to jen výjimečnost 1. termínu?

Velká úloha byla samozřejmě i na prvním termínu, pouze jsem to sem zapomněl napsat - měli jsme najít ve slovníku se vzorky slov slovo, které nejvíce odpovídá zadanému vzorku. Vzdálenost slov se určovala pomocí metriky, kterou nám zadali, je to tu již někde popsáno v jiném vlákně.
<{/ForumPost}>