# Zkouška 31. 5. 2022

<{ForumPost(poster="MájaH", timestamp=2022-06-06 11:58:25)}>
**1. POVINNÁ (Prolog) : Generátor cyklické grupy**  
  
Cílem této úlohy je definovat predikát **cyklicka/2**, který obdrží multiplikativní tabulku grupy jako matici (seznam seznamů) prvků, kde

* první řádek matice obsahuje násobení grupovou jednotkou e,
* pořadí prvků odpovídající řádkům a sloupcům je stejné,
* zjistí, zdali jde o *cyklickou grupu*,
* v kladném případě vrátí postupně všechny její *generátory*,
* v opačném případě selže.

Grupa $(G, \cdot )$ je *cyklická*, pokud existuje prvek $g \in G$ takový, že $G = \{e, g, g_2, ...,g_{n-1}\}$, $n = |G|$, přičemž

* *e* je jednotkový prvek
* $g_i = g \cdot g_{i-1} = g_{i-1} \cdot g $ pro $i > 1$
* $g_1 = g$

Prvku *g* pak říkáme *generátor* grupy G.  
  
**Příklad:
**

    ?- cyklicka([[e,a,b,c],[a,b,c,e],[b,c,e,a],[c,e,a,b]],G).
       G = a ;
       G = c ;
       false.

(a) Definujte predikát **cyklicka/2**. Budete-li používat pomocné predikáty, u každého prosím v komentáři popište význam jeho argumentů.   
  
(b) Obsahuje vaše řešení nějaký *nedeterministický* predikát ? Pokud ano, je zde nedeterminismus užitečný nebo je spíše na obtíž? 
  
  
(c) Obsahuje vaše řešení nějaký *deterministický* predikát? Pokud ano, je zde determinismus užitečný? 
  
  
(d) Obsahuje vaše řešení *řez* nebo *negaci*? Pokud ano, co se stane, když řez / negaci odstraníme? Pokud ne, dal by se zde řez / negace smysluplně využít?  
  
  
**2. VOLITELNÁ (Prolog): Prologovské variace na jednořádkové téma.**  
  
Procedura **p/2** je v jazyce Prolog popsána takto:  

    p(Xs,[Y|Ys]) :- append(Ys,[Y], Xs), !.

(a) Vysvětlete, jaký bude výsledek volání *p(+Xs,-Ys)*, kde *+Xs* značí zadaný vstup a *-Ys* obdržený výstup. Odpověď zdůvodněte.  
   
(b) Sestavte predikát **q/2** takový, abychom při volání *q(+Xs,-Ys)* obdrželi k zadanému vstupnímu seznamu *+Xs* stejný výstupní seznam *-Ys* jako při volání *p(+Xs,-Ys)*. V definici predikátu **q/2** ale nesmíte použít žádný jiný pomocný predikát (ani knihovní, ani váš vlastní)! Můžete samozřejmě využít rekurzi.  
   
(c) Je vaše definice predikátu **q/2** koncově rekurzivní? Proč ano nebo proč ne? Pokud ne, dala by se upravit, aby podmínky koncové rekurze splňovala?  
   
(d) Vysvětlete, jaký bude výsledek volání *p2(+Xs,-Ys)* a *q2(+Xs,-Ys)*, přičemž procedury **p2/2** a **q2/2** jsou definovány takto:

    p2(Xs,Ys):- p(Ys,Xs).
    q2(Xs,Ys):- q(Ys,Xs).

Chová se takto v jazyce Prolog každý binární predikát?  
  
(e) Sestavte predikát **r/2** takový, abychom při volání *r(+Xs,-Ys)* obdrželi k zadanému vstupnímu seznamu *+Xs* stejný výstupní seznam *-Ys* jako při volání *p2(+Xs,-Ys)*, leč v konstantním čase. Oba seznamy mohou být reprezentovány jako neúplně definované datové struktury.  
(e1) Nejprve popište, jak bude reprezentován seznam *\[1,2,3]* jako neúplně definovaná datová struktura.  
(e2) Definujte predikát **r/2**, který k seznamu, zadanému ve vámi navržené reprezentaci, sestrojí odpovídající výstup v konstantním čase. Řešení lze popsat jedinou klauzulí.  
  
  
**3. POVINNÁ (Haskell): Hamiltonovská cesta**  
  
Na vstupu je úplný graf *G*, který má vrcholy v nějakých bodech v rovině, tj. určených dvojicí souřadnic. Dále je určen jeden vrchol *x* grafu *G* jako počáteční. Délky hran se počítají dynamicky z polohy koncových bodů hrany pomocí předaného funkcionálního parametru **vzd**.   
  
Chcete vytvořit proceduru **odhadHam**, která heuristicky spočítá odhad nejkratší *hamiltonovské cesty* začínající v *x*. Výstup je seznam vrcholů na nalezené cestě. Použitá heuristika je, že najdeme nejbližší dosud nepoužitý vrchol k aktuálnímu konci cesty a přidáme ho k cestě (hamiltonovská cesta prochází všemi vrcholy grafu a v našem případě začíná v *x*.)  
  
a) Navrhněte reprezentaci grafu *G*, ve kterém vrcholy mají jméno a polohu v rovině.  
  
b) Napište typ funkce **odhadHam**, pokud očekávané volání je  

    odhadHam vzd graf x

c) Napište funkci **odhadHam**.  
  
**  
4. VOLITELNÁ (Haskell): Neúplné řetězce**  
  
Máte daný text *T::String* a seznam vzorků *::\[\[Maybe Char]]*. Vzorek přiložíte na text 1:1 a vzorek odpovídá textu ("matchuje"), pokud existujicí znaky ve vzorku se shodují se znaky v textu a *Nothing* ve vzorku odpovídá jednomu libovolnému písmenu. Pro každý vzorek má funkce vzorky najít první odpovídající pozici a celkový počet odpovídajících pozic v textu.  
  
a) Napište funkci 

    match::String -> [Maybe Char] -> Bool

která určí, zda vzorek *\[arg2]* odpovídá počátku řetězce *\[arg1]*.  
  
b) Napište typ funkce **vzorky**.  
  
c) Napište funkci **vzorky**, např. s využitím a)  
  
d) Víte, že text může být dlouhý, případně nekonečný. Popište ideu úpravy funkce **vzorky** a jejího typu na funkci **vzorkyN**, která se dá smysluplně používat v tomto případě.
<{/ForumPost}>