- 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ů.
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
Kód: Vybrat vše
?- 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]]
- Sestavte definici predikátu extrakce/2. Budete-li používat pomocné predikáty, popište prosím jejich význam v komentářích.
- 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?
- 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?
- 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.
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.
Kód: Vybrat vše
?- alokace([100,10,50], [0-60, 100-50, 250-70], Umisteni, NoveObsazeno). Umisteni = [100-150,10-60,50-320], NoveObsazeno = [0-70, 100-270]
- Sestavte definici predikátu alokace/4. Budete-li používat pomocné predikáty, popište prosím jejich význam v komentářích.
- 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íž?
- 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
- jak volání +X, -Y
- tak -X, +Y ?
- POVINNÁ (Haskell) : Vrstvy stromu
Na vstupu je zadán strom, tj. druh grafu (= neorientovaný souvislý acyklický graf). Funkcí vrstvy rozdělte strom na vrstvy, od listů. V první vrstvě jsou listy stromu . 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):
Kód: Vybrat vše
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]]
- 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.
- Napište typ funkce vrstvy.
- Napište kód funkce vrstvy.
- Lze nějak (jednoduše) popsat, v jakém pořadí budou vrcholy uvnitř jednotlivých vrstev?
- 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.
Příklad:
vstup: "anna_a_anna$"
výstup:dělení na úseky, pro ilustraci:Kód: Vybrat vše
[(0,0,'a'),(0,0,'n'),(1,1,'a'),(0,0,'_'),(2,2,'a'),(6,3,'$')]
- Napište typ funkce prekomprese
- Napište funkci prekomprese
- 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?
Zkouška 20.6.2022
- ERRORCEK
- Matfyz(ák|ačka) level I
- Příspěvky: 11
- Registrován: 20. 6. 2020 00:27
- Typ studia: Informatika Bc.