Zkouška 10.6.2019 (Dvořák + Hric)
Napsal: 12. 6. 2019 01:00
Zadání:
1. Prolog: Překrytí segmentů (5 bodů)
Máte dány dva řetězce, u kterých nevíte jejich vzájemnou orientaci. Najděte a vydejte v seznamu všechna jejich vzájemná neprázdná překrytí.
Příklad:
2. Prolog: Neporovnatelné prvky částečně uspořádané množiny (5 bodů)
Částečně uspořádaná množina je popsána seznamem termů tvaru x -> y s významem x pokrývá y (tj. x > y a současně x ≥ z ≥ y implikuje x = z nebo y = z).
Definujte predikát nepor/2, který k takto zadané množině vrátí seznam všech dvojic vzájemně neporovnatelných prvků (tj. dvojic x,y takových, že neplatí x ≥ y ani x ≤ y).
Příklad:
3. Haskell: Největší součet souvislé podposloupnosti (5 bodů)
Pro zadanou posloupnost čísel najděte spojitý úsek, jehož součet je největší. Vydejte souřadnice začátku a konce úseku a dosažený součet.
Pokuste se o nějakou optimalizaci, tj. nepočítejte součty hrubou silou (zcela samostatně).
Příklad: (indexováno od 0)
4. Haskell: Analýza textu (5 bodů)
Na vstupu je zadán text jako hodnota typu String. Naším cílem je definovat binární funkci stat text n, která
(a) Definujte datovou strukturu pro reprezentaci oboru hodnot funkce stat (pomocí data nebo type).
(b) Definujte typovou signaturu funkce stat s použití datové struktury z (a).
(c) Funkci stat definujte.
Velký příklad:
Kostka domina je rozdělena na 2 pole, na každém z nich je jedno číslo. Obě čísla mohou být i stejná, a libovolná kombinace dvou čísel může být použita na více kostkách.
Kostky domina se obvykle skládají do řetězce, v němž jsou na sousedních polích sousedních kostek identická čísla. Naším cílem je poskládat kostky do kříže, tvořeného dvěma řetězci, které se protínají.
Problém: Na vstupu je posloupnost kostek domina. Zjistěte, zdali lze kostky poskládat do kříže, a v kladném případě jedno řešení vypište
(bonus: není-li to možné, můžete se pokusit najít rozklad na minimální počet křížů/řetězců).
Poznámka: Problém má efektivní řešení.
1. Prolog: Překrytí segmentů (5 bodů)
Máte dány dva řetězce, u kterých nevíte jejich vzájemnou orientaci. Najděte a vydejte v seznamu všechna jejich vzájemná neprázdná překrytí.
Příklad:
Kód: Vybrat vše
?- prekryti([a,t,c,t,c],[c,t,c,c], V).
V = [a,t,c,t,c,t,c,c],[a,t,c,t,c,c],[a,t,c,t,c,c,t,c]]
Částečně uspořádaná množina je popsána seznamem termů tvaru x -> y s významem x pokrývá y (tj. x > y a současně x ≥ z ≥ y implikuje x = z nebo y = z).
Definujte predikát nepor/2, který k takto zadané množině vrátí seznam všech dvojic vzájemně neporovnatelných prvků (tj. dvojic x,y takových, že neplatí x ≥ y ani x ≤ y).
Příklad:
Kód: Vybrat vše
?- nepor([a->b, a->c, b->d, e->f], N).
N = [a-e,a-f,b-c,b-e,b-f,c-d,c-e,c-f,d-e,d-f]
Pro zadanou posloupnost čísel najděte spojitý úsek, jehož součet je největší. Vydejte souřadnice začátku a konce úseku a dosažený součet.
Kód: Vybrat vše
soucty :: Num a => [a] → (Int, Int, a)
Příklad: (indexováno od 0)
Kód: Vybrat vše
soucty [-1,1,2,3,-4]
(1,3,6)
Na vstupu je zadán text jako hodnota typu String. Naším cílem je definovat binární funkci stat text n, která
- obdrží takový text a přirozené číslo n
vrátí všechna slova z tohoto textu o délce alespoň n, setříděná lexikograficky
každé slovo s čísly řádků, kde se slovo vyskytuje
(a) Definujte datovou strukturu pro reprezentaci oboru hodnot funkce stat (pomocí data nebo type).
(b) Definujte typovou signaturu funkce stat s použití datové struktury z (a).
(c) Funkci stat definujte.
Velký příklad:
Kostka domina je rozdělena na 2 pole, na každém z nich je jedno číslo. Obě čísla mohou být i stejná, a libovolná kombinace dvou čísel může být použita na více kostkách.
Kostky domina se obvykle skládají do řetězce, v němž jsou na sousedních polích sousedních kostek identická čísla. Naším cílem je poskládat kostky do kříže, tvořeného dvěma řetězci, které se protínají.
Problém: Na vstupu je posloupnost kostek domina. Zjistěte, zdali lze kostky poskládat do kříže, a v kladném případě jedno řešení vypište
(bonus: není-li to možné, můžete se pokusit najít rozklad na minimální počet křížů/řetězců).
Poznámka: Problém má efektivní řešení.