Disclaimer: na skúške som nebol, len mi bolo preposlané zadanie na to aby som ho tu zavesil
Prolog: Izomorfizmus bin. stromů s popisem (3 podotázky)
Jsou zadány dva binární (zakořeněné) stromy {: alt="S" type="image/"} a {: alt="T" type="image/"} 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 {: alt="S" type="image/"} a ve vrcholech má boolovské hodnoty true a false. Hodnota true ve vrcholu znamená, že se děti vrcholu v {: alt="S" type="image/"} mají přehodit, abychom dostali {: alt="T" type="image/"}.
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ě.
1. Definujte predikát **iso/3**.
1. 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í?{: style="list-style-type:lower-alpha"}
Příklad:
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
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:?- koncept([[barva-modra, motor-diesel, pocet_kol-6], % TIR
[barva-bila, motor-plyn, pocet_mist-40], % bus [motor-elektro, pocet_mist-5] ], Koncept). % osobniKoncept = [barva-[modra,bila,nedef], motor-[diesel,plyn,elektro], pocet_kol-[6,nedef], pocet_mist-[40,5,nedef]]
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.Napište (obecný) typ funkce otoceni
Napište funkci otoceni
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.){: style="list-style-type:lower-alpha"}
Příklad:
> 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)]]
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.)
1. Specifikujte typovou signaturu funkce
doplneni ::
1. Funkci definujte.{: style="list-style-type:lower-alpha"}{: style="list-style-type:decimal"}