zkouška 12.9.2012
Napsal: 12. 9. 2012 23:50
Dnešní zadání:
1 Prolog :máme neorientovaný graf zadaný seznamem hran,hrana je zadaná pouze jednou(a-b).Napište funkci,která dostane seznam hran a vrátí vrcholy s jejich stupni.(nebo nejak tak).
%stupne(+Hrany,-Stupne)
2 Prolog obdelníky a okna,taky už to tu někde je.Máme zadáno okno o(X,Y,X2,Y2),kde X,Y označuje souřadnice levého dolního rohu,a X2 Y2 pravého horního.Napište funkci,která dostane seznam obdelníků definovaných stejně jako okno,pak okno,a vrátí seznam obdelníků nebo částí obdelníků co jsou vidět,tzn průnik každého obdelníku s oknem,a je li nulový,nevracet ho vůbec.
3 Haskell Máte seznam xs a a seznam dvojic a,napište funkci perm,která vrátí všechny permutace seznamu xs takové,že je v nich první prvek každé dvojice dříve než ten druhý(resp někde to tu je srozumetelněji).Zároveň napište typ funkce perm: (Eq a)=>[a]->[(a,a)]->[[a]]
4 Haskell Napi3te funkci fold pro stromy BTree a = Void | Node (Btree a) a (BTree a) takovou,aby byl její předpis a->(a->b->a->a)->BTree a->a,a zároveň pomocí ní definujte funkci hloubka a listy,které vrátí počet listů stromu a hloubku stromu.
fold :: a->(a->b->a->a)->BTree a->a
fold x f Void = x
fold x f (Node l v p)=f (fold x f l) v (fold x f p)
hloubka tree = fold 0 (\a b c -> (max a b)+1) tree
listy tree=fold 0 (\a b c->max a+b 1)
Velky: máme hypergraf-graf,kde jeho hrany mohou protínat více vrcholů,lépe se to predstavuje kruznici kolem grafu na obrazku,kde uvnitr jsou vrcholy co na hrane lezi,který má být lineární-každé dvě jeho hrany se protínají v nejvýše jednom vrcholu,a každá má alespoň 2 vrcholy.Na vstupu dostaneme libovolně zadaný hypergraf,ověřte jestli je lineární,a pokud ano,pokuste se ho obarvin n barvami,kde n je počet vrcholů.Údajně je nějaká hypotéza že to jde vždy.Můj postup byl reprezentovat si hrany seznamem vrcholů již se hrana dotýká,a nejdříve ověřit linearitu,pak si seřadit hrany podle jejich velikosti od největší(Hric říkal že by vhodnější bylo je řadit podle dotyků s ostatními hranami,ale to je o dost pracnější),a pak dávat postupně hrany do seznamů,reprezentující barvy.Nakonec spočítat počet vrcholů,a počet barev,a pokud mám barev víc,zkusit to obarvit jinak.Používal jsem prolog,a přišlo mi že spoustu věcí mám zadarmo.
Pokud by se něco co jsem napsal nedalo pochopit,ozvěte se,pokusím se dovysvětlit.
1 Prolog :máme neorientovaný graf zadaný seznamem hran,hrana je zadaná pouze jednou(a-b).Napište funkci,která dostane seznam hran a vrátí vrcholy s jejich stupni.(nebo nejak tak).
%stupne(+Hrany,-Stupne)
2 Prolog obdelníky a okna,taky už to tu někde je.Máme zadáno okno o(X,Y,X2,Y2),kde X,Y označuje souřadnice levého dolního rohu,a X2 Y2 pravého horního.Napište funkci,která dostane seznam obdelníků definovaných stejně jako okno,pak okno,a vrátí seznam obdelníků nebo částí obdelníků co jsou vidět,tzn průnik každého obdelníku s oknem,a je li nulový,nevracet ho vůbec.
3 Haskell Máte seznam xs a a seznam dvojic a,napište funkci perm,která vrátí všechny permutace seznamu xs takové,že je v nich první prvek každé dvojice dříve než ten druhý(resp někde to tu je srozumetelněji).Zároveň napište typ funkce perm: (Eq a)=>[a]->[(a,a)]->[[a]]
4 Haskell Napi3te funkci fold pro stromy BTree a = Void | Node (Btree a) a (BTree a) takovou,aby byl její předpis a->(a->b->a->a)->BTree a->a,a zároveň pomocí ní definujte funkci hloubka a listy,které vrátí počet listů stromu a hloubku stromu.
fold :: a->(a->b->a->a)->BTree a->a
fold x f Void = x
fold x f (Node l v p)=f (fold x f l) v (fold x f p)
hloubka tree = fold 0 (\a b c -> (max a b)+1) tree
listy tree=fold 0 (\a b c->max a+b 1)
Velky: máme hypergraf-graf,kde jeho hrany mohou protínat více vrcholů,lépe se to predstavuje kruznici kolem grafu na obrazku,kde uvnitr jsou vrcholy co na hrane lezi,který má být lineární-každé dvě jeho hrany se protínají v nejvýše jednom vrcholu,a každá má alespoň 2 vrcholy.Na vstupu dostaneme libovolně zadaný hypergraf,ověřte jestli je lineární,a pokud ano,pokuste se ho obarvin n barvami,kde n je počet vrcholů.Údajně je nějaká hypotéza že to jde vždy.Můj postup byl reprezentovat si hrany seznamem vrcholů již se hrana dotýká,a nejdříve ověřit linearitu,pak si seřadit hrany podle jejich velikosti od největší(Hric říkal že by vhodnější bylo je řadit podle dotyků s ostatními hranami,ale to je o dost pracnější),a pak dávat postupně hrany do seznamů,reprezentující barvy.Nakonec spočítat počet vrcholů,a počet barev,a pokud mám barev víc,zkusit to obarvit jinak.Používal jsem prolog,a přišlo mi že spoustu věcí mám zadarmo.
Pokud by se něco co jsem napsal nedalo pochopit,ozvěte se,pokusím se dovysvětlit.