Zkouška 28.6.2016 - 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ů.

Zkouška 28.6.2016 - Dvořák, Hric

Příspěvekod bombur » 1. 7. 2016 19:26

Malé příklady: (80 minut)

1) 5 bodů, Prolog: Napište predikát termy(+N, -V), který postupně skrze V vydá všechny možnosti, jak lze z právě N funktorů poskládat smysluplný výraz. Každý funktor je buď binární plus/2 nebo unární minus/1 anebo nulární p/0. Na pořadí možností ve výstupu nezáleží.

Například:
Kód: Vybrat vše

?- termy (4, V).
V = plus(minus(p),p) ;
V = plus(p,minus(p)) ;
V = minus(plus(p,p)) ;
V = minus(minus(minus(p))) .


2) 5 bodů, Prolog: Napište predikát parovani(+G, +H, -P), který bere neorientovaný graf G bez smyček (tj. reflexivních hran) zadaný jako seznam následníků, hranu H v podobě (v1-v2) a vydá co do inkluze maximální párování obsahující zadanou hranu H (pozor: nikoli největší párování, ale pouze maximální co do inkluze).

Například:
Kód: Vybrat vše

?- parovani(graf(a-[b,c,d],b-[a,c],c-[a,b,d],d-[a,c],e-[]),a-d,P).
P = [a-d,b-c].


3) 5 bodů, Haskell: úloha č. 3 v viewtopic.php?f=169&t=10479

4) 5 bodů, Haskell: Stejné jako úloha č. 1 pro Haskell v viewtopic.php?f=169&t=10036.
Pouze místo násobení bylo za úkol řídké polynomy skládat.

Například:
Kód: Vybrat vše

comp [(3,2),(2,1)] [(1,2),(1,0)] = [(3,4),(8,2),(5,0)]



Poznámka k bodování: Bylo třeba získat alespoň 4 body z Haskellu, alespoň 4 body z Prologu a aspoň 12 bodů celkem.

Velký příklad: (90 minut, jazyk buď Haskell anebo Prolog)
Máme seznam dominových kostek a chceme z nich složit dominový kříž (tj. dva klasické dominové řetězce, které se protínají). Musíme použít všechny dominové kostky a každá z "větví" kříže musí být nenulové délky.
Program musí buď ohlásit, že řešení neexistuje anebo vrátit dominový kříž.
Bylo třeba najít polynomiální řešení, ačkoliv exponenciální by pravděpodobně také obstálo (bylo by to ale asi mínus do celkového hodnocení).

Například:
Pro dominové kostky [(1,2),(1,4),(2,2),(4,2),(4,3),(4,5)] máme kříž:
- 1. řetězec: (1,2),(2,2),(2,4),(4,5)
- 2. řetězec: (1,4),(4,3)
- řetězce se protínají v nějakém čísle 4 (je jedno jakém z nich...)

Bylo možné vyřešit navíc bonusovou úlohu: Pokud nelze z dominových kostek kříž vytvořit, nalezněte minimální počet formací, které z dominových kostek vytvořit lze. Formace je buď dominový kříž anebo klasický dominový řetězec. Tato úloha má již řešení vždy (triviální rozklad na formace, avšak ne nutně minimální, je takový, že každá kostka bude tvořit jednu formaci). Opět existuje polynomiální algoritmus.
bombur
 

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

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 3 návštevníků

cron