Zkouska 18.06.2012
Napsal: 18. 6. 2012 21:42
Prolog:
1) Mate dva seznamy a v kazdem maximalne 1 hvezdicku. Ukolem je zjistit zda jsou seznamy ekvivalentni. Hacek je v tom, ze hvezdicku lze nahradit za libovolnou posloupnost cisel.
[1,2,*,7,5] a [1,2,*,7,7,5] jsou ekvivalentni
2) Mate seznam prvku [X->Y] napr [a->b,a->c,e->f] pricemz toto dava nejake nelinearni usporadani. Mate najit vsechny neporovnatelne dvojice. V predchozim prikladu je to napr [a-e,a-f,b-c,b-e,b-f] idea je snad jasna, pozor na pohlidani tranzitivity.
Haskell:
3)Multimnožina (prvky se mohou opakovat) je definována
type Multim = [(Int,a)]
například [(2,'c'),(1,'d')] odpovídá množině ['c','c','d']
Řekneme, že M1<M2, pokud v M2 existuje prvek, který není v M1 a je větší než všechny prvky v M1, které nejsou v M2 (pismena josu klasicky usporadana a<b<...). Naším úkolem bylo definovat funkci (<).
4) Prevest obecny strom na binarni.
Velka uloha:
Mate reklamni bloky b1,..,bn a kazdy ma urcitou delku. Dale mame nejake zakazniky z1,...,zm a ti maji nejake nabidky. Nabizeji napr ze by chteli blok b7 a z neho by chteli 3 minuty a jsou ochotni zaplatit 200 000 Kc. Zaroven kazdy zakaznik ma omezeny kapital a nechce ho prekrocit (ale muze chtit napr reklamy za 2 000 000 Kc pricemz ma jen 700 000 Kc, to je na nas nabidnout mu bloky abychom neprekrocili jeho kapital). Ukolem je vytvorit pro dane bloky jake zakazniky chceme v blocich obsluhovat, pricemz musime vyhovet podminkam (neprekrocit kapital, logicky nenaplanovat 12 min na 10 min blok).
Prijatelne reseni je bud nejaka heuristika (nemusi byt chytra, staci hladove obsazovat intervaly) nebo presne reseni (tadyu asi mysli generovani vsech permutaci). Hodnoti se zda dokazeme napsat vetsi program v Haskellu/Prologu nez zda umime algoritmy.
1) Mate dva seznamy a v kazdem maximalne 1 hvezdicku. Ukolem je zjistit zda jsou seznamy ekvivalentni. Hacek je v tom, ze hvezdicku lze nahradit za libovolnou posloupnost cisel.
[1,2,*,7,5] a [1,2,*,7,7,5] jsou ekvivalentni
2) Mate seznam prvku [X->Y] napr [a->b,a->c,e->f] pricemz toto dava nejake nelinearni usporadani. Mate najit vsechny neporovnatelne dvojice. V predchozim prikladu je to napr [a-e,a-f,b-c,b-e,b-f] idea je snad jasna, pozor na pohlidani tranzitivity.
Haskell:
3)Multimnožina (prvky se mohou opakovat) je definována
type Multim = [(Int,a)]
například [(2,'c'),(1,'d')] odpovídá množině ['c','c','d']
Řekneme, že M1<M2, pokud v M2 existuje prvek, který není v M1 a je větší než všechny prvky v M1, které nejsou v M2 (pismena josu klasicky usporadana a<b<...). Naším úkolem bylo definovat funkci (<).
4) Prevest obecny strom na binarni.
Velka uloha:
Mate reklamni bloky b1,..,bn a kazdy ma urcitou delku. Dale mame nejake zakazniky z1,...,zm a ti maji nejake nabidky. Nabizeji napr ze by chteli blok b7 a z neho by chteli 3 minuty a jsou ochotni zaplatit 200 000 Kc. Zaroven kazdy zakaznik ma omezeny kapital a nechce ho prekrocit (ale muze chtit napr reklamy za 2 000 000 Kc pricemz ma jen 700 000 Kc, to je na nas nabidnout mu bloky abychom neprekrocili jeho kapital). Ukolem je vytvorit pro dane bloky jake zakazniky chceme v blocich obsluhovat, pricemz musime vyhovet podminkam (neprekrocit kapital, logicky nenaplanovat 12 min na 10 min blok).
Prijatelne reseni je bud nejaka heuristika (nemusi byt chytra, staci hladove obsazovat intervaly) nebo presne reseni (tadyu asi mysli generovani vsech permutaci). Hodnoti se zda dokazeme napsat vetsi program v Haskellu/Prologu nez zda umime algoritmy.