Zkouška 6. 6. 2016 (Dvořák, Hric)
Napsal: 11. 6. 2016 23:02
Jako obvykle: rozdelene na 2 casti:
1. Cast: (80 minut)
Je treba ziskat alespon 4 body z Prologu (ulohy 1 a 2), 4 body z Haskellu (ulohy 3 a 4) a celkove alespon 12 bodu. Celkove je mozno ziskat 20 bodu.
Prolog:
1) (5 bodu) ( viz: http://forum.matfyz.info/viewtopic.php?f=169&t=10536 - uloha 1) Naprogramujte predikat splay(+Hodnota, +BinarniVyhledavaciStrom, -Vysledek), ktery provede funkci splay (protahnout dany vrchol az do korene pomoci rotaci) na Hodnotu. Pokud Hodnota ve strome neni, pak se splay provede na bezprostredniho predchudce/naslednika.
2) (5 bodu) Na vstupu mame seznam po castech konstantnich funkci [Funkce], kde kazda Funkce je ve tvaru [Hodnota-DelkaUseku]. Vsechny funkce zacinaji v 0 a po konci posledniho useku pokracuji hodnotou 0. Mame vytvorit nejmensi novou funkci takovu, ze v kazdem bode je vetsi rovna vsem zadanym funkcim.
Priklad: [ [2-5, 2-3], [3-4] ]
Dve funkce: prvni ma v intervalu [0, 2) hodnotu 5, v intervalu [2, 4) hodnotu 3 a v intervalu [4, inf) hodnotu 0. Druha ma v intervalu [0, 3) hodnotu 4 a v intervalu [3, inf) hodnotu 0.
Vysledkem je fce [2-5, 1-4, 1-3]
Haskell:
3) (5 bodu) (viz: http://forum.matfyz.info/viewtopic.php?f=169&t=10536 - uloha 3) Mame zadanou matici (jako seznam seznamu). Nasim cilem je vypsat seznam vsech dvojic (x, y) takovych, ze podmatice (1, 1) (x, y) bude obsahovat pouze kladne hodnoty. Dvojice (x, y) musi byt vzdy nejvyssi mozne (t. j. nelze ani v jedne souradnici zvetsit)
4) (5 bodu)
a) Napiste fold pro binarni stromy Tree a = Leaf a | T (Tree a) (Tree a).
fold :: (a -> b) -> (b -> b -> b) -> Tree a -> b
b) Napiste one-liner funkci, ktera vypise minimum a maximum z celeho stromu pomoci vami napsaneho foldu.
c) Napiste hlavicku funkce z b)
2. Cast: (90 minut) (Jazyk dle vlastniho vyberu)
Na vstupu mame seznam spotrebicu, jak dlouho musi bezet (bez preruseni), od kdy do kdy je muzeme pustit a jak velky vyzaduji prikon. Ukolem je naplanovat spusteni jednotlivych spotrebicu tak, aby nejvyssi prikon v libovolnem case byl co nejnizsi (aby jsme mohli instalovat co nejmensi pojistky).
1. Cast: (80 minut)
Je treba ziskat alespon 4 body z Prologu (ulohy 1 a 2), 4 body z Haskellu (ulohy 3 a 4) a celkove alespon 12 bodu. Celkove je mozno ziskat 20 bodu.
Prolog:
1) (5 bodu) ( viz: http://forum.matfyz.info/viewtopic.php?f=169&t=10536 - uloha 1) Naprogramujte predikat splay(+Hodnota, +BinarniVyhledavaciStrom, -Vysledek), ktery provede funkci splay (protahnout dany vrchol az do korene pomoci rotaci) na Hodnotu. Pokud Hodnota ve strome neni, pak se splay provede na bezprostredniho predchudce/naslednika.
2) (5 bodu) Na vstupu mame seznam po castech konstantnich funkci [Funkce], kde kazda Funkce je ve tvaru [Hodnota-DelkaUseku]. Vsechny funkce zacinaji v 0 a po konci posledniho useku pokracuji hodnotou 0. Mame vytvorit nejmensi novou funkci takovu, ze v kazdem bode je vetsi rovna vsem zadanym funkcim.
Priklad: [ [2-5, 2-3], [3-4] ]
Dve funkce: prvni ma v intervalu [0, 2) hodnotu 5, v intervalu [2, 4) hodnotu 3 a v intervalu [4, inf) hodnotu 0. Druha ma v intervalu [0, 3) hodnotu 4 a v intervalu [3, inf) hodnotu 0.
Vysledkem je fce [2-5, 1-4, 1-3]
Haskell:
3) (5 bodu) (viz: http://forum.matfyz.info/viewtopic.php?f=169&t=10536 - uloha 3) Mame zadanou matici (jako seznam seznamu). Nasim cilem je vypsat seznam vsech dvojic (x, y) takovych, ze podmatice (1, 1) (x, y) bude obsahovat pouze kladne hodnoty. Dvojice (x, y) musi byt vzdy nejvyssi mozne (t. j. nelze ani v jedne souradnici zvetsit)
4) (5 bodu)
a) Napiste fold pro binarni stromy Tree a = Leaf a | T (Tree a) (Tree a).
fold :: (a -> b) -> (b -> b -> b) -> Tree a -> b
b) Napiste one-liner funkci, ktera vypise minimum a maximum z celeho stromu pomoci vami napsaneho foldu.
c) Napiste hlavicku funkce z b)
2. Cast: (90 minut) (Jazyk dle vlastniho vyberu)
Na vstupu mame seznam spotrebicu, jak dlouho musi bezet (bez preruseni), od kdy do kdy je muzeme pustit a jak velky vyzaduji prikon. Ukolem je naplanovat spusteni jednotlivych spotrebicu tak, aby nejvyssi prikon v libovolnem case byl co nejnizsi (aby jsme mohli instalovat co nejmensi pojistky).