Zkouška 24.6.2019 (Dvořák, Hric)
Napsal: 24. 6. 2019 14:44
- Prolog: Generování výrokových formulí (5 bodů)
Formule výrokového počtu jsou sestavené z (výrokových) proměnných ve funktoru var/1 a logických spojek negace, konjunkce a disjunkce (bez konstant). Dále máte dány v argumentech predikátu gen/3 číslo k pro velikost formule a seznam jmen proměnných. Generujte backtrackingem všechny logické formule (každou jednou), které obsahují proměnné ze seznamu a ve kterých je počet spojek a výskytů proměnných dohromady právě k.
Definujte predikát gen(+K, +Jmena, -Fle). Na pořadí generovaných formulí nezáleží, ale měli byste vygenerovat každou právě jednou. K řešení není potřeba predikát =../2 (univ).
Příklad:
?- gen(4,[p],F).
F = not(not(not(var(p))));
F = not(and(var(p),var(p)));
F = not(or(var(p),var(p)));
F = and(not(var(p)),var(p));
F = and(var(p),not(var(p)));
F = or(not(var(p)),var(p));
F = or(var(p),not(var(p)));
false. - Prolog: Koncepty (5 bodů)
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:
?- koncept([ [barva-modra, motor-diesel, pocet_kol-6], [barva-bila, motor-plyn, pocet_mist-40], [motor-elektro, pocet_mist-5] ], Koncept).
Koncept = [barva-[modra,bila,nedef], motor-[diesel,plyn,elektro], pocet_kol-[6,nedef], pocet_mist-[40,5,nedef]] - Haskell: Kumulativní součty (5 bodů)
Je dána číselná matice A. Definujte funkci
kumulace :: Num a => [[a]] -> [[a]]
která z matice A vyrobí matici B stejných rozměrů (viz příklad níže)
každý prvek na souřadnicích (i,j) bude roven součtu všech hodnot
v submatici s levým horním rohem (0,0)
a pravým dolním rohem (i,j)
Poznámka: Snažte se vyhnout opakování stejných výpočtů.
Příklad:
> kumulace[[1,1,1],[1,2,1],[0,1,0],[1,1,-4]]
[[1,2,3],[2,5,7],[2,6,8],[3,8,6]] - Haskell: Doplnění hypergrafu (5 bodů)
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}
(b) Specifikujte typovou signaturu funkce
doplneni ::
(c) Funkci definujte.