- Prolog: Izomorfizmus bin. stromů s popisem (3 podotázky)
Jsou zadány dva binární (zakořeněné) stromy a 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 a ve vrcholech má boolovské hodnoty true a false. Hodnota true ve vrcholu znamená, že se děti vrcholu v mají přehodit, abychom dostali .
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.
- 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ě.
- Definujte predikát iso/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í?
v S sú d, e a v Popis t červenou farbouKó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
- 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]]
- 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.)
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)]]
- 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}
- 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.)
- Specifikujte typovou signaturu funkce
Kód: Vybrat vše
doplneni ::
- Funkci definujte.
Zkouška 12.7.2021
- 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
Disclaimer: na skúške som nebol, len mi bolo preposlané zadanie na to aby som ho tu zavesil