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, ževstup 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"}
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žúseky jsou v seznamu uspořádány vzestupně dle počáteční adresy,
ú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.
POVINNÁ (Haskell) : Vrstvy stromu
Na vstupu je zadán strom, tj. druh grafu (= neorientovaný souvislý acyklický graf). Funkcí vrstvy rozdělte strom {: alt="S" type="image/"} na vrstvy, od listů. V první vrstvě jsou listy stromu {: alt="S" type="image/"}. 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"}
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 jevzdá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: