Malé příklady:
1. Prolog: Generování hodnot výrokových proměnných (5 bodů)
Definujte binární predikát aspon2, který
• obdrží seznam výrokových proměnných (reprezentovaných atomy), v němž je každá proměnná ohodnocena hodnotou true nebo false
• vrátí seznam všech takových ohodnocení týchž proměnných, v němž se každé ohodnocení bude od vstupního lišit v hodnotách alespoň 2 proměnných.
Příklad:
Kód: Vybrat vše
?- aspon2([x1-true, x2-false, y-true], V).
V = [ [x1-false, x2-true, y-true],
[x1-false, x2-false, y-false],
[x1-true, x2-true, y-false],
[x1-false, x2-true, y-false] ]
Graf je zadán jako seznam svých vrcholů se seznamy sousedů (viz příklad). Definujte binární predikát
troj(+Graf, -SeznamTrojuhelniku)
který k takovému grafu vrátí seznam všech jeho trojúhelníků. Ve výsledném seznamu by se každý trojúhelník měl vyskytovat právě jednou (t(a,b,c), t(b,c,a) a t(c,a,b) jsou stejné trojúhelníky).
Příklad:
Kód: Vybrat vše
?- troj([a-[b,c,d],b-[a,c],c-[a,b,d],d-[a,c],e-[]], S).
S = [t(a,b,c), t(a,c,d)]
Definujte funkce:
Kód: Vybrat vše
prevod1 cislo puvodni
Kód: Vybrat vše
prevod2 cislo nova
Příklad:
Kód: Vybrat vše
> prevod1 [1,1,1,0] 2 -- převede binární 1110 do desítkové soustavy
14
> prevod2 33 16 -- převede dekadické číslo 33 do hexadecimální soustavy
[2,1]
Kód: Vybrat vše
prevod1 ::
prevod2 ::
(c) Sestavte alternativní definici funkce prevod1 s využitím alespoň jedné z funkcí map, filter, foldr či foldl, ale bez (explicitního) použití rekurze.
(d) Definujte funkci prevod2 s využitím funkce unfold definované následovně:
Kód: Vybrat vše
unfold :: (t -> Bool) -> (t -> (a, t)) -> t -> [a]
unfold done step x = if done x then []
else let (y,ys) = step x
in y: unfold done step ys
Definujte unární funkci rady, která
obdrží multiplikativní tabulku grupy jako matici prvků. První řádek matice obsahuje násobení grupovou jednotkou e a pořadí prvků odpovídající řádkům a sloupcům je stejné.
vydá seznam všech prvků spolu s jejich řády.
Řád prvku p je nejmenší přirozené číslo n takové, že n-tá mocnina p je rovna e.
(a) Definujte typovou signaturu funkce rady.
(b) Funkci rady definujte.
Příklad:
Kód: Vybrat vše
> rady [["e","a","b"], ["a","b","e"], ["b","e","a"]]
[("e",1), ("a",3), ("b",3)]
Zadání: Problém zamčených truhel
V našem problému máme otevřít N zamčených truhel, přičemž máme k dispozici N+1 klíčů.
Každá truhla má nějakou barvu, přitom různé truhly mohou být obarveny stejnou barvou. Klíče jsou také obarveny barvami, přitom různé klíče mohou mít stejnou barvu.
Háček je v tom, že truhlu vždy odemyká jen klíč téže barvy, jakou je truhla obarvena. Po odemčení truhly zůstane klíč vězet v zámku, a nelze ho tedy použít na odemčení jiné truhly téže barvy.
V každé truhle je - kromě části pokladu - uložen také jeden klíč, který lze - po odemčení této truhly - použít na odemčení další truhly příslušné barvy.
Na začátku obdržíte jeden klíč.
Lze odemčít všechny truhly? Pokud ano, tak jak?
Problém: Na vstupu je
- barva klíče, který má hledač na začátku u sebe
- množina truhel, pro každou její barva a barva klíče v ní uloženého
Je možné odemčít všechny truhly?
- pokud ano, vypište pořadí, v jakém je lze odemčít
- existuje-li více řešení, stačí nalézt jedno
Poznámka: Problém má efektivní řešení. Ale Dvořák říkal, že to není zkouška z algoritmů, takže pokud nás efektivní řešení nenapadne, tak to nevadí, a můžeme implementovat brute force řešení s nějakou heuristikou. Dále nám doporučoval začít odshora, prostě napsat nějakou kostru, podle které bude jasné, jakým způsobem to chceme řešit a implementovat kritické sekce.
Postřehy ze zkoušky:
- 11 bodů z malých příkladů stačí na dvojku
- U velkého příkladu toho není třeba implementovat až tak moc, já měla necelých padesát řádků včetně slovních komentářů, přišla jsem na optimální řešení a Dvořák s tím byl spokojen. Při ústní mu stačilo jen popsat jak přesně to funguje a chtěl po mě, abych napsala reprezentaci grafu pomocí Data a Type, což v mém řešení nebylo. Finální známka byla dva, ale nabízel mi i jedničku, s tím, že se mě ještě bude vyptávat.
- Spolužáka se ptal na rozdíly mezi data, type a newtype, generičnost a brute force v Haskellu. A na lazy evaluation a druhy řezů v Prologu.
- Dvořák je u ústní velmi hodný, do ničeho moc nerýpe, je to spíš příjemné povídání si o odevzdaných řešení, převážně o velké úloze, takže doporučuji si ji před ústní projít.
1. Prolog - toto stačilo na dva body - vypisovalo to do jednoho velkého seznamu a ne do seznamu seznamů a byly tam duplicity.
Kód: Vybrat vše
aspon2(L, R) :- length(L, N), generate(L, N, R).
generate(L, 2, R) :- !, swapN(L, 2, [], R).
generate(L, N, R) :- swapN(L, N, [], R1), NN is N -1, generate(L, NN, R2),
append(R1, R2, R).
swapN([], _, A, A).
swapN([H-V|T], N, A, R) :- length([H-V|T], L), L = N, !,
NN is N-1, switch(V, NV), swapN(T, NN, [H-NV|A], R).
swapN([H-V|T], N, A, R) :- NN is N-1, switch(V, NV),
swapN(T, NN, [H-V|A], R1), swapN(T, NN, [H-NV|A], R2), append(R1, R2, R).
switch(false, true).
switch(true, false).
Kód: Vybrat vše
% graf je reprezentovany jako seznam hran: [a-b, a-c, b-c, a-d, c-d]
troj(G, R) :- vertices(G, [], V), comb(V, 3, [], R). %find_triangles(C, G, [], R).
find_triangles([], _, A, A).
find_triangles([H|T], G, A, R) :- is_triangle(H, G), !, find_triangles(T, G, [H|A], R).
find_triangles([_|T], G, A, R) :- find_triangles(T, G, A, R).
comb(_, 0, A, [A]) :-!.
comb([H|T], N, A, [R]) :- length([H|T], L), N = L, !,
append([H|T], A, R).
comb([H|T], N, A, R) :- N1 is N-1, comb(T, N1, [H|A], R1),
comb(T, N, A, R2), append(R1, R2, R).
vertices([], A, A).
vertices([V1-V2|T] ,A, R) :- member(V1, A), member(V2, A), !, vertices(T, A, R).
vertices([V1-V2|T], A, R) :- member(V2, A), !, vertices(T, [V1|A], R).
vertices([V1-V2|T], A, R) :- member(V1, A), !, vertices(T, [V2|A], R).
vertices([V1-V2|T], A, R) :- vertices(T, [V1, V2|A], R).
% tady budou vsechny kombinace
is_triangle((V1, V2, V3), G) :- member(V1-V2, G), member(V2-V3,G), member(V3-V1,G).
Kód: Vybrat vše
rady :: Eq a => [[a]] -> [(a, Int)]
rady ((h:hh):t) = help h hh ((h:hh):t) [(h, 1)]
help _ [] _ r = r
help a (h:t) l r = help a t l (r++ (compute a 1 (h, a) l))
compute e n (a, a1) l
| (e == (eval a a1 l)) = [(a, n)]
| otherwise = compute e (n+1) (a, (eval a a1 l)) l
eval a b (h:t) = evaluate b h (row a (h:t))
evaluate b (h1:t1) (h2:t2)
| (b == h1) = h2
| otherwise = evaluate b t1 t2
row a ((h:hh):t)
| (a == h) = (h:hh)
| otherwise = column a t
Kód: Vybrat vše
-- Ulohu prevedeme na orientovany graf, kde vrcholy budou barvy. Z vrcholu b1 vede hrana do vrcholu b2, pokud v aspon jedne truhlici barvy b1 je klic barvy b2, na hrane b1 - b2 bude seznam takovych truhel.
-- Vsechny truhly je mozne otevrit jen v pripade, ze takto vytvoreny graf je souvisly a vsechny vstupni stupne vrcholu jsou rovny vystupnim stupnu, krome jednoho vrcholu (mame jeden klic navic), v tomto vrcholu vsak nesmime zacinat
-- Reprezentace vstupu: seznam truhel je seznam trojic - cislo truhly, barva truhly, barva klice
-- Ze seznamu truhel chceme vyrobit orientovany graf, graf je reprezentovany jako dvojice - seznam vrcholu a seznam hran, vrchol je jmeno barvy, hrana je trojice - pocatecni vrchol, koncovy vrchol, seznam truhel:
solve s (v, e)
| existSol = findPath s (v, e) []
| otherwise = []
findPath _ ([], _) path = path
findPath s (v, e) path = findPath (newStart (snd (selectEdge s (v, e)))) (fst (selectEdge s (v, e))) (path ++ [snd (selectEdge s (v, e))])
selectEdge s (v, e) = helpSelectEdge s (v, e) (findEdges s e)
-- Zkusim vybrat nejakou hranu, pokud po jejim odebrani ma uloha stale reseni, tak ji odeberu, jinak si vyberu jinou
helpSelectEdge s (v, e) ((from, to, l):t)
| existSol (removeEdge e (from, to) []) = (v, (removeEdge e (from, to)) [], (from, to, l))
| otherwise = helpSelectEdge s (v, e) t
newStart (_, to, _) = to
-- Odebere hranu ze seznamu - zkusi jit prvni truhlou, pokud je to jedina truhla, tak smaze celou hranu. Nasledne to na graf pusti bfs z noveho startovniho vrcholu, aby se zjistilo, zda je graf stale souvisly
removeEdge ((from, to, (h:t)):tt) (f, t) r
| ((from != f) || (to != t)) = removeEdge tt (f, t) (r ++ [(from, to, (h:t))])
| (length t) > 0 = ((r ++ (f, t, t)), (f, t, h))
| otherwise = (r, (f, t, h))
-- Overeni souvislosti udelame pomoci bfs pusteneho ze zdroje
bfs v e = bfs_ e (q e v []) [v]
bfs_ _ [] r = r
bfs_ e ((v1, v2):t) r
| ((member r v1) && (member r v2)) = bfs_ e t r
| (member r v1) = bfs_ e (t ++ (q e v2 [])) (r ++ [v2])
| otherwise = bfs_ e (t ++ (q e v1 [])) (r ++ [v1])
member [] _ = False
member ((h,_):t) e
| (h == e) = True
| otherwise = member t e
q [] _ r = r
q ((v1, v2):t) v r
| ((v == v1) || (v == v2)) = q t v (r ++ [(v1, v2)])
| otherwise = q t v r