Zkouška 12.7.2021

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 12.7.2021

Příspěvek od ERRORCEK »

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ě.
    2. Definujte predikát iso/3.
    3. 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í?
    Příklad:

    Kód: Vybrat vše

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

    Kód: Vybrat vše

    ?- 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]]
    
  3. 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
    2. Napište funkci otoceni
    3. 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.)
    Příklad:

    Kód: Vybrat vše

    > 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)]]
    
  4. 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.)
    2. Specifikujte typovou signaturu funkce

      Kód: Vybrat vše

      doplneni ::
    3. Funkci definujte.
Odpovědět

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