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

Přednáška je věnována neprocedurálnímu programování. Většina semestru je věnována programování v jazyku Prolog, ve kterém studenti i ladí zápočtové programy. Informativně se studenti seznámí i s jazykem LISP a neprocedurálními částmi programovacích systémů.

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

Příspěvekod Kikinka00711 » 12. 6. 2019 00: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:
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í.
Kikinka00711
Matfyz(ák|ačka) level I
 
Příspěvky: 1
Registrován: 28. 5. 2018 14:06
Typ studia: Informatika Bc.

Zpět na PRG005 Neprocedurální programování

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 2 návštevníků