Zkouška 20.6.2022

Přednáška je věnována neprocedurálnímu programování. Většina semestru je věnována programování v jazyku Prolog, ve kterém studenti i ladí zápočtové programy. Informativně se studenti seznámí i s jazykem LISP a neprocedurálními částmi programovacích systémů.
Uživatelský avatar
ERRORCEK
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 20. 6. 2020 00:27
Typ studia: Informatika Bc.

Zkouška 20.6.2022

Příspěvek od ERRORCEK »

  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:

    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]]
    
    1. Sestavte definici predikátu extrakce/2. Budete-li používat pomocné predikáty, popište prosím jejich význam v komentářích.
    2. 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?
    3. 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?

  2. 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,
    2. úseky nenavazují bezprostředně na sebe, tj. navazující úseky jsou vždy spojeny do jedné položky ve vstupním seznamu.
    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:

    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]
    
    1. Sestavte definici predikátu alokace/4. Budete-li používat pomocné predikáty, popište prosím jejich význam v komentářích.
    2. 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íž?
    3. 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 ?
    Odpověď prosím zdůvodněte.
  3. 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):

    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]]
    
    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.
    2. Napište typ funkce vrstvy.
    3. Napište kód funkce vrstvy.
    4. Lze nějak (jednoduše) popsat, v jakém pořadí budou vrcholy uvnitř jednotlivých vrstev?

  4. 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:

    Kód: Vybrat vše

    [(0,0,'a'),(0,0,'n'),(1,1,'a'),(0,0,'_'),(2,2,'a'),(6,3,'$')]
    dělení na úseky, pro ilustraci:
    useky
    useky
    obrázok_2022-06-20_160956382.png (1.43 KiB) Zobrazeno 694 x
    1. Napište typ funkce prekomprese
    2. Napište funkci prekomprese
    3. 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?
Odpovědět

Zpět na „PRG005 Neprocedurální programování“