Zkouška 21.5.13 (Dvořák+Hric)

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

Zkouška 21.5.13 (Dvořák+Hric)

Příspěvek od petrbel »

dnešní zkouška

4 malé úlohy ~ 80min
Prolog (pouze std predikáty z přednášky, bez použití assert, findall a dalších užitečných)
1) Rotace seznamu v konstantním časem (pomocí rozdílových seznamů)

2) dostanete graf a vrchol - máte najít každou nezávislou množinu vrcholů obsahující zadaný vrchol co největší do inkluze (může jich být víc! pozor na definici "co do inkluze")
Reprezentace grafu je následující graf(Vrcholy, Hrany), kde Vrcholy=[Int]; Hrany=[v->[u, w, z], x->[y,z]]

Haskell (papír s fcemi dostanete, když použijete jiné, musíte je na ústním naprogramovat)
3) Reprezentujte dlouhá a neomezeně přesná čísla seznamem číslic a pozicí desetiné čárky; naimplementujte násobení těchto čísel

4) zipWith na obecných stromech (hodnoty ve všech listech) - dostanete funkci, dva stromy a defaultní hodnotu a máte vrátit strom. Je potřeba rekurzivně se volat na syny a když v jednom stromu syn chybí a ve druhém je (nebo nopak) do prvního si "přimyslet" nový vrchol s defaultní hodnotou

1 velká úloha ~ 90 min, jazyk je na vás (prolog byl vhodnější, jazyk bez omezení na funkce/predikáty, reprezentace dat a další věci jsou na vás)
Zobecnění hamiltonovské kružnice
Dostanete (ohodnocený, orientovaný) graf a jeho 2 disjunktní podmnožiny vrcholů A, B takové, že |A|=|B|=N. Vašim úkolem je vypsat N (hranově i vrcholově) disjunktních cest vedoucích z A do B (tedy z každého vrcholu v A povede jedna; do každého vrcholu v B povede jedna). Navíc cesty musí projít projít všemi vrcholy. Navíc pokud je možných řešení jak cesty vést více, vyberte to, jehož hrany mají nejmenší součet délek. Pokud je i tak řešení více, vyberte takové, které má nejdelší cestu nejkratší možnou. Navíc se pokuste o vhodnou heuristiku (problém je překvapivě NP-úplný)

Heuristika nebyla na plný počet vyžadována, ale pokud jste prohledávali do šířky, vyplatilo se jít nejkratší možnou cestou a potom další výpočty chytře ořezávat už na začátku, ale jak říkám - nebylo to podstatné.

Na ústním jsem byl asi 25min, prošli jsme všechny malé příklady (diskuze řešení, další nápady atd.) a pak hlavně tu velkou úlohu.

Kdyby to někoho zajímalo, tak tady jsou moje úkoly přes semestr a nějaké drobné přípravy na zkoušku https://github.com/petrbel/NPRG005-non- ... rogramming - give me star :)
Odpovědět

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