Zkouška 31. 5. 2022

Přednáška je věnována neprocedurálnímu programování. Většina semestru je věnována programování v jazyku Prolog, ve kterém studenti i ladí zápočtové programy. Informativně se studenti seznámí i s jazykem LISP a neprocedurálními částmi programovacích systémů.
MájaH
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 30. 1. 2020 20:14
Typ studia: Informatika Bc.

Zkouška 31. 5. 2022

Příspěvek od MájaH »

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:


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

Kód: Vybrat vše

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:

Kód: Vybrat vše

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

Kód: Vybrat vše

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

Kód: Vybrat vše

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ě.
Odpovědět

Zpět na „PRG005 Neprocedurální programování“