# Zkouška 20.6.2022

<{ForumPost(poster="ERRORCEK", timestamp=2022-06-20 16:25:40)}>
1. **POVINNÁ (Prolog) : Relační databáze**  
Na vstupu je zadán seznam záznamů, přičemž jeden záznam je reprezentován uspořádaným seznamem dvojic *atribut-hodnota*. Můžete si představit, že  

- vstup reprezentuje tabulku relační databáze,
- záznamy odpovídají jejím řádkům
- a atributy jsou jména sloupců.

Hodnoty některých atributů mohou být v některých záznamech nedefinovány, pak se příslušná dvojice *atribut-hodnota* v příslušném seznamu vůbec nevyskytuje.  
  
Cílem tohoto problému je definovat predikát **extrakce/2**, který obdrží popsaný vstup a na výstupu vrátí asociativní seznam dvojic *atribut-seznam_vsech_ruznych_hodnot* takový, že  

    *  každý atribut ze vstupní tabulky bude ve výstupním seznamu právě jednou
    *  každá hodnota atributu ze vstupní tabulky bude ve výstupním seznamu u příslušného atributu právě jednou
    *  je-li v nějakém záznamu hodnota některého atributu nedefinována, na výstupu bude u příslušného atributu hodnota *nedef*, a to právě jednou

*Příklad:*

    ?- extrakce([[barva-oranzova, motor-plyn, pocet_mist-40],   % autobus
                 [barva-modra, motor-diesel, pocet_kol-6],      % kamion
                 [motor-elektro, pocet_mist-5] ],  Atributy).   % osobni
    
    Atributy = [barva-[modra,oranzova,nedef],
                motor-[plyn,diesel,elektro], 
                pocet_kol-[6,nedef],
                pocet_mist-[40,nedef,5]]
    

    1.  Sestavte definici predikátu **extrakce/2**. Budete-li používat pomocné predikáty, popište prosím jejich význam v komentářích.
    1.  Je-li ve vašem řešení použit **řez** (!) či **negace**, co se stane, když ho (ji) odstraníme? Pokud ne, dal(a) by se někde smysluplně použít?
    1.  Je ve vašem řešení definován nějaký **koncově rekurzivní** predikát? Odpověď prosím zdůvodněte. Pokud ne, dal(a) by se některá z vašich definic přeformulovat tak, aby splňovala podmínky koncové rekurze?{: style="list-style-type:lower-alpha"}

----

1. **VOLITELNÁ (Prolog) : Alokace paměti**  
Na vstupu obdržíme  informaci o úsecích obsazené paměti ve tvaru seznamu dvojic ***zacatek-delka_useku***, přičemž  

    1.  úseky jsou v seznamu uspořádány vzestupně dle počáteční adresy,
    1.  úseky nenavazují bezprostředně na sebe, tj. navazující úseky jsou vždy spojeny do jedné položky ve vstupním seznamu.{: style="list-style-type:decimal"}

Dále obdržíme seznam délek úseků, které potřebujeme obsadit.  
CIlem problému je sestavit predikát **alokace(+Alokovat, +Obsazeno, -Umisteni, -NoveObsazeno)**, který  

    *  pro každý požadavek ze seznamu **Alokovat**
    *  obsadí v paměti první volný úsek, kam se požadovaná velikost vejde (heuristika *First Fit*),
    *  vrátí  v seznamu **Umisteni** polohy alokovaných úseků ve tvaru dvojic ***umisteni-delkaUseku***
    *  a v seznamu **NoveObsazeno** nový seznam obsazených úseků ve tvaru splňujícím podmínky 1 a 2 výše.

*Příklad:*

    ?- alokace([100,10,50], [0-60, 100-50, 250-70], Umisteni, NoveObsazeno).
       Umisteni = [100-150,10-60,50-320],
       NoveObsazeno = [0-70, 100-270]
    

    1.  Sestavte definici predikátu **alokace/4**. Budete-li používat pomocné predikáty, popište prosím jejich význam v komentářích.
    1.  Je některý z predikátů, který jste použili (ať už váš vlastní nebo knihovní), ***nedeterministický*** ? Pokud ano, je zde nedeterminismus užitečný nebo je spíše na obtíž?
    1.  Je některý z predikátů, které jste použili (ať už váš vlastní nebo knihovní), ***invertibilní*** ? Tedy má mezi svými argumenty dvojici argumentů **X** a **Y** takovou, že funguje{: style="list-style-type:lower-alpha"}

    *  jak volání **+X**, **-Y**
    *  tak **-X**, **+Y** ?
Odpověď prosím zdůvodněte.

----

1. **POVINNÁ (Haskell) : Vrstvy stromu**  
Na vstupu je zadán *strom*, tj. druh grafu (= neorientovaný souvislý acyklický graf). Funkcí **vrstvy** rozdělte strom $S$ na vrstvy, od listů. V první vrstvě jsou listy stromu $S$. Jejich odstraněním dostaneme nový strom S', který se (např. rekurzivně) rozdělí na druhou a další vrstvy. Výstup je seznam vrstev, tj. seznam seznamů vrcholů S, kde každý vrchol je v právě jedné vrstvě.  
  
*Příklad (pseudokód):*  

    vstup: [(a,c),(b,c),(c,d),(c,e),(d,f),(f,g),(f,h),(h,i)]
    výstup: [[a,b,e,g,i],[c,h],[d,f]]
    

    1.  Navrhněte reprezentaci grafu, kterou budete používat. Umožněte variabilní typ vrcholů (čísla, řetězce, ...). Vaše reprezentace nemusí odpovídat příkladu.
    1.  Napište typ funkce vrstvy.
    1.  Napište kód funkce vrstvy.
    1.  Lze nějak (jednoduše) popsat, v jakém pořadí budou vrcholy uvnitř jednotlivých vrstev?{: style="list-style-type:lower-alpha"}

----

1. **VOLITELNÁ (Haskell) : Prekomprese**  
Dostanete **String *s***. Ten budete dělit postupně zleva na úseky popsané trojicemi *(ix,d,z)*. Pro zatím nekomprimovanou (pravou) část s najdete *nejdelší* prefix *p*, který se nachází v už komprimované (levé) části. Popisující trojice úseku je  

    *  vzdálenost ix začátku nalezeného prefixu v levé části od konce levé části,
    *  délka d nalezeného prefixu, tj. *d =|p|*,
    *  jeden znak z v pravé části za nalezeným prefixem.

Poté úsek délky *d+1* považujeme za zpracovaný a přesuneme ho z pravé části do levé. Na začátku je levá část prázdná, na konci je pravá část prázdná. Předpokládejte, že vstup končí znakem '$', který se jinde nevyskytuje.  
  
*Příklad:*  
vstup: "anna_a_anna$"  
výstup:

    [(0,0,'a'),(0,0,'n'),(1,1,'a'),(0,0,'_'),(2,2,'a'),(6,3,'$')]

dělení na úseky, pro ilustraci:

obrázok_2022-06-20_160956382.png

    1.  Napište typ funkce **prekomprese**
    1.  Napište funkci **prekomprese**
    1.  Využili jste nějakou vlastní a nějakou vestavěnou ***funkci vyššího řádu***? Šla by použít nějaká vestavěná funkce vyššího řádu a kde?{: style="list-style-type:lower-alpha"}{: style="list-style-type:decimal"}


*Attachments:*

![obrázok_2022-06-20_160956382.png](/NPRG005/Zkou%C5%A1ka%202022-06-20/pic.jpg)

<{/ForumPost}>