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

<{ForumPost(poster="Kikinka00711", timestamp=2019-06-12 01:00:02)}>
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:

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

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

    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)

    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í.
<{/ForumPost}>