Zkouška 28.6.2016 - Dvořák, Hric

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: Zkouška 28.6.2016 - Dvořák, Hric

Zkouška 28.6.2016 - Dvořák, Hric

od bombur » 1. 7. 2016 20: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 http://forum.matfyz.info/viewtopic.php?f=169&t=10479

4) 5 bodů, Haskell: Stejné jako úloha č. 1 pro Haskell v http://forum.matfyz.info/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.

Nahoru