1. Prolog (10 bodů): Vrstvy binárního stromu
V této úloze budeme pracovat s kořenovými binárními stromy, které jsou reprezentovány stejně jako na přednášce, tj.
termem b(LevýPodstrom, Kořen, PravýPodstrom) či atomem nil (je-li strom prázdný).
Naším cílem je definovat predikát vrstvy(BinStrom, SeznamVrstev), který uspěje, pokud
BinStrom je binární strom a SeznamVrstev je seznam, jehož i-tým prvkem je seznam všech vrcholů, které leží ve vzdálenosti i-1 od kořene, v pořadí zleva doprava, první seznam tedy obsahuje pouze kořen, druhý děti kořene, atd.
Predikát budeme definovat ve dvou variantách, které se liší směrem výpočtu.
(a) Sestavte definici predikátu vrstvy1(+BinStrom, ?SeznamVrstev),
který obdrží zadaný binární strom BinStrom a vrátí odpovídající seznam vrstev (je-li SeznamVrstev zadán jako volná proměnná) nebo ověří, zdali je druhý argument skutečně seznamem jeho vrstev (je-li SeznamVrstev zadán jako seznam seznamů).
Příklad:
?- vrstvy1(b(a, b(b, b(d, nil, nil), nil), b(c, b(e, nil, nil), nil)), Vrstvy).
Vrstvy = [[a], [b, c], [d, e]].
(b) Sestavte definici predikátu vrstvy2(?BinStrom, +SeznamVrstev),
který obdrží seznam seznamů SeznamVrstev a vrátí v argumentu BinStrom postupně všechny odpovídající binární stromy (je-li BinStrom zadán jako volná proměnná) nebo ověří, zdali první argument skutečně reprezentuje odpovídající binární strom (je-li BinStrom konkretizován).
Příklad: (středníky zadává uživatel)
?- vrstvy2(Strom, [[a],[b,c],[d,e]]).
Strom = b(a, b(b, nil, nil), b(c, b(d, nil, nil), b(e, nil, nil))) ;
Strom = b(a, b(b, nil, b(d, nil, nil)), b(c, nil, b(e, nil, nil))) ;
Strom = b(a, b(b, nil, b(d, nil, nil)), b(c, b(e, nil, nil), nil)) ;
Strom = b(a, b(b, b(d, nil, nil), nil), b(c, nil, b(e, nil, nil))) ;
Strom = b(a, b(b, b(d, nil, nil), nil), b(c, b(e, nil, nil), nil)) ;
Strom = b(a, b(b, b(d, nil, nil), b(e, nil, nil)), b(c, nil, nil)) ;
false.
Poznámka: Pozor na to, že zde pracujeme se seznamy seznamů, což přináší stejná úskalí, jako práce s maticemi (viz čtvrtá přednáška).
(c) Je některý z predikátů, které jste sestavili v části (a) či (b), koncově rekurzivní? Pokud ano, který to je? Pokud ne, měla by koncově rekurzivní definice u některého z nich smysl?
(d) Využili jste v (a) či (b) nějaký predikát vyššího řádu (tj. predikát, jehož argumentem je jiný predikát)? Pokud ano, který to je? Pokud ne, nedal by se zde nějaký smysluplně využít?
2. Haskell (10 bodů): Cesta přesné délky v orientovaném grafu
V této úloze budeme pracovat se orientovanými grafy, jejichž vrcholy jsou reprezentovány (navzájem různými) řetězci. Takové grafy lze v jazyce Haskell reprezentovat prostřednictvím typového synonyma
type Graf = [ (String, [String]) ]
graf.png
Graf g na obrázku bude tedy reprezentován následovně:
g :: Graf
g = [("a", ["b","c","f"]),
("b", ["d"]),
("c", ["b","e",]),
("d", ["c"]),
("e", ["d"]),
("f", ["c","e"]) ]
Cesta v orientovaném grafu je posloupnost vrcholů grafu, v niž se žádný vrchol neopakuje, a z každého vrcholu cesty vyjma posledního vede orientované hrana do vrcholu následujícího.
Cílem našeho problému je definovat funkci
cesta :: Graf -> String -> String -> Int -> [[String]]
která obdrží orientovaný graf, dva jeho vrcholy a délku hledané cesty, nalezne všechny cesty mezi zadanými vrcholy o zadané délce (přičemž délka cesty se měří počtem hran na cestě) a vrátí seznam nalezených cest, přičemž každá cesta je reprezentována seznamem svých vrcholů.
Pokud žádná cesta zadané délky mezi zadanými vrcholy neexistuje, vrácený seznam bude prázdný.
cesta g "a" "d" 3
[["a","c","b","d"], ["a","c","e","d"], ["a","f","e","d"]]
cesta g "a" "d" 5
[]
Poznámka: Algoritmus pracující v polynomiálním čase pro tento problém není znám, takže se očekává, že vaše funkce bude hledat řešení hrubou silou a bude tedy pracovat - měřeno nejhorším případem - v exponenciálním čase.
Nezapomeňta dávat pozor na zacyklení !
(a) Sestavte definici funkce cesta. Budete-li potřebovat nějaké pomocné funkce, u každé prosím v poznámce popište význam parametrů a návratovou hodnotu.
(b) Využili jste v (a) notaci stručných seznamů (list comprehension)? Pokud ne, našlo by se tam pro ně nějaké smysluplné využití?
(c) Zobecněte definici typového synonyma Graf tak, aby vrcholy grafu mohly být reprezentovány i jinak než jen řetězci. Současně upravte typovou signaturu funkce cesta tak, aby odpovídala této obecnější verzi typového synonyma Graf. Bude-li třeba, použijte typová omezení na vhodné typové třídy.
(d) Půjde s takto pozměněnou typovou signaturou použít váš původní kód, nebo budou potřebné nějaké další změny? Odpověď prosím zdůvodněte.
3. Haskell (10 bodů): Řídké polynomy
Následující typová třída reprezentuje polynomy s koeficienty typu a:
class TPol q where
koef :: q a -> Int -> Maybe a
soucin :: Num a => q a -> q a -> q a
-- dalsi metody nemusíme uvazovat
Funkce koef k zadanému polynomu a přirozenému číslu i vrátí
koeficient členu stupně i, opatřený konstruktorem Just (pokud takový existuje) nebo hodnotu Nothing (jinak)
Příklad:
koef 3x6+2x3+1 3
Just 2
koef 3x6+2x3+1 5
Nothing
Funkce soucin dva zadané polynomy vynásobí.
(a) Definujte nový datový typ RPol pro reprezentaci řídkých polynomů s koeficienty typu a:
data RPol a = ...
Řídký polynom má většinu svých prvků rovných nule. Vaše reprezentace
by měla obsahovat nenulové prvky polynomu, prostorová složitost by tedy měla být lineární v počtu nenulových prvků, pokud budete u nenulových prvků předpokládat nějaké uspořádání, uveďte to prosím do poznámky.
Nezapomeňte na reprezentaci nulového polynomu.
(b) Učiňte typ RPol instancí typové třídy TPol
instance TPol RPol where
koef ...
soucin ...
včetně implementace funkcí koef a soucin.
(c) Učiňte typ RPol instancí typové třídy Show (za předpokladu, že typ jeho koeficientů je instancí třídy Show)
instance Show a => Show (RPol a) where
show ...
včetně implementace funkce show. Tu implementujte nějakým rozumným způsobem tak, aby z výstupu byl patrný skutečný tvar polynomu.
Poznámka: Funkce show pouze převede polynom z interní reprezentace (navržené v (a)) na řetězec. Jde jen o práci s řetězci (a volání funkce show na koeficienty polynomu), nejsou k tomu třeba žádné V/V funkce.
(d) Využijte typ RPol pro definici nekonečného polynomu
1+x3+x6+x9+…
(e) Co se stane, když na nekonečný polynom z (d) aplikujeme funkci koef ? Obdržíme vždy správný výsledek? Pokud ne, bylo by možné definice funkce koef opravit tak, aby pracovala korektně i nad tímto nekonečným vstupem?
Svoji odpověď prosím stručně zdůvodněte!
**BONUS Prolog (jen 5 bodů) : Problém žárlivých manželů **
Problém žárlivých manželů je klasická logická hádanka, v níž vystupují 3 manželské páry, které se potřebují přepravit na druhou stranu řeky. K dispozici je jen jedna loďka pro dvě osoby. Veslovat umějí všichni, problém spočívá v tom, že pokud v nějakém okamžiku zůstane na jednom břehu manželka bez manžela v přítomnosti jiného muže, její žárlivý manžel neprodleně podává žádost o rozvod. Lze naplánovat převoz přes řeku tak, aby žádná manželská krize nevznikla a štěstí všech párů zůstalo zachováno?
Jde o analogii Problému farmáře, který jsme řešili na přednášce prohledáváním stavového prostoru. Cílem této úlohy je zobecnit Problém žárlivých manželů na m ≥ 2 manželských párů a r ≥ 1 řek:
pzm.png
Na začátku je všech m párů na nejpravějším břehu. Kromě toho je na pravém břehu každé z r řek k dispozici loďka pro dvě osoby. V jednom kroku řešení se přemístí jedna z loděk s jednou či dvěma osobami z jednoho břehu "svojí" řeky na druhý. Lze přepravit všechny páry na nejlevější břeh tak, aby během přesunu nedošlo k žádné manželské krizi?
Naším cílem je popsat řešení této úlohy v jazyce Prolog metodou prohledávání stavového prostoru.
(a) Popište prologovský term, kterým budete reprezentovat stav. Nezapomeňte na to, že kromě rozmístění všech osob na r+1 březích potřebujeme znát i pozice všech r loděk.
Snažte se reprezentaci navrhnout tak, aby umožnila co nejjednodušší řešení části (c).
(b) Popište, jak bude ve vaší reprezentaci vypadat počáteční a koncový stav.
(c) Sestavte predikát prejezd(+Stav1, ?Stav2), který uspěje, pokud Stav2 obdržíme ze Stavu1
jedním přejezdem jedné z loděk z jednoho břehu na druhý s jednou nebo dvěma osobami.
Pro zadaný Stav1 by měl predikát prejezd/2 postupně vrátit všechny možné hodnoty pro Stav2, každou právě jednou.
(d) Sestavte predikát bezpecny(+Stav), který uspěje, pokud zadaný Stav nepovede k manželské krizi, jak je popsáno výše.
Poznámka: Pro r = 1 má problém řešení pouze v případě m ≤ 3. Pokud vás zajímá, jak to dopadne pro r > 1 , sestavte výsledný predikát, který hádanku vyřeší pro obecné m a r.
Sem ale jeho definici uvádět nemusíte, jde o analogii řešení Problému farmáře z přednášky.
Attachments: