Zkouška 21.6.

[stinovlas]

Prolog:

1) Problém dvou loupežníků. Úkolem je rozdělit seznam na 2 seznamy se stejným součtem - pokud to nejde, pak vrátit false.

2) Úkolem bylo definovat predikát bin(+Graf,-Obarveni), který pro neorientovaný graf G zadaný jako seznam položek typu V-[sousedi V] našel obarvení 2-ma barvami. Pokud takové obarvení neexistovalo, měl vrátit false. K získání plného počtu bodů byl potřeba běh v polynomiálním čase a spojování seznamů v konstantním čase.

Haskell:

3)
a) definujte typ pro binární stromy Binstrom a
b) definujte funkci

Kód: Vybrat vše

vrcholy :: (Binstrom a) -> [(a, Int)]

Tato funkce vrátí seznam vrcholů, které neodpovídají rozložení vyhledávacího bin. stromu (např. napravo je menší hodnota) spolu s počtem jejich předchůdců, vůči kterým uspořádání porušují.

4) Máme definovát typ

Kód: Vybrat vše

data Kalk a = (a, [(a -> a -> a), a])

Např.

Kód: Vybrat vše

(1+2) * 3 --> (1, [((+), 2), ((*), 3)]

Napište funkci kalk, ktrerá vyhodnotí výraz zadaný tímto způsobem. Plný počet bodů byl za definici pomocí foldl nebo foldr.

5) Napište program pro optimalizaci letového provozu. Máte zadána letadla, jejich přílet, odlet, kapacitu a brány u kterých může stát. Kromě toho může letadlo stát i na odstavné ploše, ale není to dobré, protože se k němu musí lidi dopravovat autobusy. Úkolem je tedy vymyslet pro letadla rozvrh, který bude maximalizovat integrál součtu kapacit letadel stojících u bran podle času.


Musím říct, že Hric byl na ústním velice hodný a i když můj algoritmus na 5) nebyl nějak světoborný, koukal spíš na to, jestli umím psát v Haskellu, než na jeho efektivitu ...

[marion]

Ahoj,
u toho prvního úkolu se myslí rozseknout seznam na vhodném místě, nebo lze prvky i přeskakovat, tj. např. ze seznamu [1,3,2] vyrobím seznamy [1,2] a [3] ?