# Zkouška 25. května 2026 ## 1. Prolog (10 bodů) : Magické čtverce Magický čtverec je čtvercová matice řádu $n$, vyplněná čísly $1,2,…,n^2$ tak, že součty na každém řádku, na každém sloupci i na obou diagonálách jsou stejné. Příklad pro $n = 3$: $$ \begin{pmatrix} 2 & 7 & 6 \\ 9 & 5 & 1 \\ 4 & 3 & 8 \end{pmatrix} $$ Cílem této úlohy je sestavit predikát v jazyce Prolog, který obdrží matici, jejíž prvky mohou být jak přirozená čísla, tak volné proměnné. Pokud matice obsahuje jen čísla, predikát zjistí, zdali jde o magický čtverec. Pokud matice obsahuje volné proměnné, predikát na jejich místa dosadí přirozená čísla tak, abychom obdrželi všechny magické čtverce odpovídající zadanému vstupu. **(a)** Sestavte pomocný predikát `gen/2`, který pro zadané přirozené číslo $n$ vrátí seznam čísel $1,2,…,n^2$. ```prolog ?- gen(3, Xs). Xs = [1,2,3,4,5,6,7,8,9]. ``` Snažte se prosím vyhnout predikátům `bagof`, `setof` a `findall`, jejichž použití vede k velmi neefektivnímu řešení. **(b)** Sestavte pomocný predikát `radek(+N,+M,-Xs,-Zbytek)`, který - pro zadané přirozené číslo N a množinu M reprezentovanou seznamem - v seznamu Xs vrátí všechny variace řádu N bez opakování z prvků množiny M - a v seznamu Zbytek vrátí nepoužité prvky z M. ```prolog ?- radek(2, [1,2,3], Xs, Zbytek). Xs = [1,2], Zbytek = [3] ; Xs = [1,3], Zbytek = [2] ; Xs = [2,1], Zbytek = [3] ; Xs = [2,3], Zbytek = [1] ; Xs = [3,1], Zbytek = [2] ; Xs = [3,2], Zbytek = [1]. ``` **(c)** Sestavte pomocný predikát `diag/2`, který obdrží matici a vrátí seznam s prvky na hlavní diagonále. ```prolog ?- diag([[1,2],[3,4]], Diag). Diag = [1,4]. ``` **(d)** Využijte **(a)**-**(c)** k sestavení hlavního predikátu `magicky/1`, který uspěje, je-li jeho argumentem magický čtverec. Podrobněji: - predikát obdrží matici, jejíž prvky jsou přirozená čísla či volné proměnné - pokud obsahuje jen čísla, predikát zjistí, zdali jde o magický čtverec, a vrátí true či false - pokud obsahuje volné proměnné, predikát na jejich místa dosadí přirozená čísla tak, abychom obdrželi všechny magické čtverce odpovídající zadanému vstupu, každý právě jednou. ```prolog ?- Xss =[[2,B,C],[D,E,F],[G,H,I]], magicky(Xss). Xss = [[2,7,6], [9,5,1], [4,3,8]] ; Xss = [[2,9,4], [7,5,3], [6,1,8]] ; false. ``` Můžete k tomu samozřejmě využít i další pomocné predikáty, jak vlastní, tak knihovní, např. `transpose/2` z modulu `clpfd` (naopak další predikáty a operátory z tohoto modulu nemáme v referenční příručce, takže je prosím nepoužívejte). **(e)** Využívá vaše řešení nějaký **predikát vyššího řádu** (vlastní či knihovní)? Pokud ano, který to je? Pokud ne, dal by se takový predikát někde smysluplně využít? ## Haskell (10 bodů): Cesta 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 ```haskell type Graf = [ (String, [String]) ] ``` ![](/NPRG005/Zkouška Dvořák, Hric 25.05. 2026/graf.png) Graf `g` na obrázku bude tedy reprezentován následovně: ```haskell 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 ```haskell cesta :: Graf -> String -> Int -> Maybe [String] ``` - která obdrží orientovaný graf, jeden jeho vrchol v a přirozené číslo d, - zjistí, zdali existuje cesta z vrcholu v délky alespoň d (přičemž délka cesty se měří počtem hran na cestě) - pokud ano, jednu (libovolnou) takovou cestu vrátí ve tvaru seznamu vrcholů, opatřeného konstruktorem Just - jinak vrátí `Nothing`. ```haskell > cesta g "a" 4 Just ["a","f","e","d","c"] > cesta g "b" 4 Nothing ``` **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)** Zobecněte definici typového synonyma `Graf` tak, aby vrcholy grafu mohly být reprezentovány i jinak než jen řetězci. **(c)** 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 : Zobecnění operací nad seznamy na stromy Cílem této úlohy je zobecnit několik operací nad seznamy na binární stromy a poté je smysluplně využít. **(a)** Definujte datový typ pro reprezentaci binárních stromů, které splňují následující podmínky - každý rodič má právě dvě děti - hodnoty jsou uloženy jen ve vnitřních vrcholech, nikoliv v listech - pokuste se o co nejobecnější definici - nezapomeňte na reprezentaci prázdného stromu. **(b)** Definujte funkci `replicateB` takovou, že - `replicateB n` a vrátí binární strom, který obsahuje n kopií hodnoty a - výsledný strom by měl mít minimální možnou hloubku - např. `replicateB 7` vrátí strom hloubky 3 (hloubka kořene je 0) **(c)** Definujte funkci `zipWithB` jako zobecnění funkce `zipWith` tak, že - `zipWithB f b1 b2` sloučí prvky binárních stromů `b1` a `b2` na stejných pozicích pomocí funkce `f` - pokud nemá nějaký prvek z jednoho stromu odpovídající prvek na stejné pozici v druhém stromě, tak se do výsledného stromu nepřidává - např. pro prázdný strom empty by mělo platit - `zipWithB f t empty == empty` - `zipWithB f empty t == empty` **(d)** Pomocí výše definovaných funkcí `replicateB` a `zipWithB` sestavte definici funkce `cutB` tak, že - `cutB n b` odstraní ze stromu `b` všechny vrcholy, jejichž hloubka je ostře větší než `n` **(e)** Umožňuje váš datový typ v **(a)** definovat nekonečný strom? Odpověď prosím zdůvodněte. ## BONUS Prolog (jen 5 bodů) : Problém čtyř hobitů Čtyři hobiti potřebují přejít řeku po úzkém mostu, kteý současně unese pouze dvě osoby. Protože je temná noc, pro přechod mostu je zapotřebí pochodeň a naši hobiti mají pouze jedinou. Frodo přejde most za 1 minutu, Pipin za 2 minuty, Smíšek za 5 minut a Sam za 8 minut. Když dva hobiti přecházejí most současně, pohybují se rychlostí toho pomalejšího z nich. Mohou se všichni dostat přes řeku, když pochodeň vydrží pouze 15 minut? Sestavte program v jazyce Prolog, který nalezne řešení problému prohledáváním stavového prostoru. **(a)** Popište prologovský term, kterým budete reprezentovat stav. Snažte se reprezentaci navrhnout tak, aby umožnila co nejjednodušší řešení části **(b)**. **(b)** Sestavte predikát `prechod(+Stav1, ?Stav2)`, který uspěje, pokud `Stav2` obdržíme ze `Stavu1` - jedním přechodem z jednoho či dvou hobitů - z jedné strany na druhou. Můžete si samozřejmě definovat pomocné predikáty, budou-li potřebné. **(c)** Sestavte predikát `hadanka(-Reseni)`, který - vrátí řešení (stačí jedno) ve tvaru seznamu stavů od počátečního do koncového, pokud takové řešení existuje, - či vrátí false v opačném případě. **(d)** Fungovalo by vaše řešení i pro jiný počet hobitů (se zadanými časy přechodu) a jinou životnost pochodně? Odpověď prosím zdůvodněte.