Stránka 1 z 1

Zkouška 10.6.2019 (Dvořák + Hric)

Napsal: 12. 6. 2019 01:00
od Kikinka00711
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:

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]]
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:

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]
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.

Kód: Vybrat vše

soucty :: Num a => [a] → (Int, Int, a)
Pokuste se o nějakou optimalizaci, tj. nepočítejte součty hrubou silou (zcela samostatně).
Příklad: (indexováno od 0)

Kód: Vybrat vše

soucty [-1,1,2,3,-4]
 (1,3,6)
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á
  • 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
Řádky jsou ukončeny znakem '\n'. Slovo je každý maximální podřetězec textu neobsahující mezeru ' ', tabulátor '\t' či konec řádku '\n'.
(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í.