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$ .

?- 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.

?- 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.

?- 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.

?- 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

type Graf = [ (String, [String]) ]

+get/+ea291f81-4c28-43ab-9889-a61e83bb1e60/NPRG005/Zkouška%20Dvořák%2C%20Hric%2025.05.%202026/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 -> 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.

> 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.