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.
- e je jednotkový prvek
- pro
Příklad:
Kód: Vybrat vše
?- cyklicka([[e,a,b,c],[a,b,c,e],[b,c,e,a],[c,e,a,b]],G).
G = a ;
G = c ;
false.
(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:
Kód: Vybrat vše
p(Xs,[Y|Ys]) :- append(Ys,[Y], Xs), !.
(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:
Kód: Vybrat vše
p2(Xs,Ys):- p(Ys,Xs).
q2(Xs,Ys):- q(Ys,Xs).
(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
Kód: Vybrat vše
odhadHam vzd graf x
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
Kód: Vybrat vše
match::String -> [Maybe Char] -> Bool
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ě.