# Zkouška 12.7.2021

<{ForumPost(poster="ERRORCEK", timestamp=2021-07-13 14:00:29)}>
*Disclaimer: na skúške som nebol, len mi bolo preposlané zadanie na to aby som ho tu zavesil*  

1. **Prolog: Izomorfizmus bin. stromů s popisem** (3 podotázky)  
Jsou zadány dva binární (zakořeněné) stromy $S$ a $T$ s ohodnocenými vrcholy, přičemž ohodnocení vrcholů se může opakovat. Definujte predikát **iso/3**, který zjistí, zdali jsou tyto stromy  isomorfní a vydá popis transformace. Volání je **iso(+S,+T, -Popis)**, kde ve třetím argumentu bude popis. Popis je strom stejného tvaru jako $S$ a ve vrcholech má boolovské hodnoty *true* a *false*. Hodnota *true* ve vrcholu znamená, že se děti vrcholu v $S$ mají přehodit, abychom dostali $T$.  
  
Dva binární stromy jsou *isomofní*, pokud lze jeden získat z druhého permutací dětí libovolných vrcholů stromu, tj. vyměněním nebo nevyměněním podstromů vrcholu.  

    1. Navrhněte reprezentaci binárního (zakořeněného) stromu s ohodnocenými vrcholy v jazyce Prolog. Vaši reprezentaci ukažte na příkladě.
    1. Definujte predikát **iso/3**.
    1. Je některý z predikátů, které ve vašem řešení používáte (ať už vámi definovaných či knihovních), *nedeterministický*? Je predikát **iso/3** *nedeterministický*? Lze ho zdeterminičtit (a jak?), pokud nám stačí nejvýš jedno řešení?{: style="list-style-type:lower-alpha"}

*Příklad:*

      S= d                 T= d                Popis= t
       /---\                /---\                   /---\
      b     e              e     b                 f     t
     / \   / \            / \   / \               / \   / \
    a   c f   g          g   f a   c             f   f f   f
    

*v S sú **d**, **e** a v Popis **t** červenou farbou*
1.  **Prolog: Koncepty**  
Jeden objekt je zadán uspořádaným seznamem dvojic *klíč-hodnota*. Na vstupu máte seznam objektů. Napište proceduru **koncept/2**, která vyrobí *nejmenší *koncept zahrnující všechny vstupní objekty. Koncept je seznam dvojic *klíč-seznam_hodnot*. Koncept zahrnuje objekt, pokud koncept má všechny klíče objektu a v seznamu hodnot příslušného klíče u konceptu je obsažena hodnota klíče u objektu. Pokud objekt nějaký klíč konceptu nemá, bude v seznamu hodnot konceptu hodnota *nedef*.  
*Příklad:*

    ?- koncept([[barva-modra, motor-diesel, pocet_kol-6],  % TIR
    
                [barva-bila, motor-plyn, pocet_mist-40],   % bus
    
                [motor-elektro, pocet_mist-5] ],  Koncept). % osobni
    
    Koncept = [barva-[modra,bila,nedef], motor-[diesel,plyn,elektro], pocet_kol-[6,nedef], pocet_mist-[40,5,nedef]]
    

1.  **Haskell: Otočení v orientované sekvenci**  
Na vstupu je daný seznam ***S*** obsahující dvojice (položka, orientace), kde položky jsou obecné informace nějakého typu (například geny v chromozomu), a orientace je typu *Bool *(pro sousměrně a protisměrně). Volání funkce **otoceni *S*** má vydat seznam všech výsledků **\[Vs** jako seznam seznamů dvojic stejného typu, kde jeden výsledek vznikne otočením nějaké souvislé části **S**, přičemž v otočené části změníte informaci o směru. Délka otočené části je od 1 do délky S, tj. otáčenou spojitou část vybíráte všemi možnými způsoby.  

    1. Napište (obecný) typ funkce **otoceni**
    1. Napište funkci **otoceni**
    1. Pracovala by Vaše implementace funkce **otoceni **na *nekonečném *vstupním seznamu? Šla by napsat správná implementace pro nekonečný seznam? (Stačí myšlenka: proč ano nebo proč ne.){: style="list-style-type:lower-alpha"}

*Příklad:*

    > otočení [('a',True),('b',True),('c',False)]
    
    [[('a',False),('b',True),('c',False)],[('a',True),('b',False),('c',False)],[('b',False),('a',False),('c',False)],[('a',True),('b',True),('c',True)],[('a',True),('c',True),('b',False)],[('c',True),('b',False),('a',False)]]
    

1.  **Haskell: Doplnění hypergrafu** (3 podotázky)  
  
*Hypergraf *je zadán množinou vrcholů a množinou hyperhran, což jsou alespoň dvouprvkové podmnožiny množiny vrcholů. Naší cílem je definovat funkci doplnění, která doplní do hypergrafu H všechny dvouprvkové (hyper)hrany pro ty dvojice vrcholů, které nejsou společně obsaženy v žádné hyperhraně vstupního hypergrafu H. Funkce tedy např. z hypergrafu

    *  s vrcholy {1,2,3,4,5} a hyperhranani {1,3,5} a {2,3,4}
    *  vytvoří hypergraf se stejnými vrcholy a hyperhranami {1,3,5},{2,3,4},{1,2},{1,4},{5,2} a {5,4}

    1.  Definujte datový typ pro reprezentaci hypergrafu. Pokuste se o co nejobecnější definici (vrcholy mohou být reprezentovány nejen čísly, ale i znaky, řetězci apod.)
    1.  Specifikujte typovou signaturu funkce

    doplneni ::

    1.  Funkci definujte.{: style="list-style-type:lower-alpha"}{: style="list-style-type:decimal"}

<{/ForumPost}>