# Zkouska 6.9.

<{ForumPost(poster="marion", timestamp=2010-09-10 11:14:59)}>
**Malé příklady**  
  
Prolog:  
  
1) Na vstupu dostanete 2 seznamy, každý obsahuje nejvýše 1 hvězdičku, kterou lze nahradit libovolným počtem libovolných prvků (mohli jsme si vybrat, jestli povolíme i nahrazení ničím). Výstupem měla být odpověď, jestli je možné oba seznamy doplnit tak, aby se shodovaly. Např.  
  
\[*,5,7,7] a \[1,2,*,7] vrátí true  
  
\[3,*,5,7,7] a \[1,2,*,7] vrátí false  
  
2) Dostaneme graf reprezentovaný seznamy sousedů a množinu M. Máme zjistit, jestli je graf bipartitní s jednou partitou M. Pokud ano, vrátit i druhou partitu.  
  
Haskell:  
  
1) Definujte funkci, 

    rozdel :: (a->Bool) -> [a] -> [[a]]

která má za úkol rozdělit zadaný seznam na co nejdelší úseky, které splňují podmínku. Opět příklad:  
  
rozdel odd  \[1,3,5,2,4,6,7,9]  vrátí \[\[1,3,5],\[2,4,6],\[7,9]]  
  
2] 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. Naším úkolem bylo definovat funkci (<).  
  
**Velký příklad**  
  
Každé zařízení je identifikováno n-bitovým číslem, celkem máme 2<sup>n</sup> zařízení. 2 zařízení jsou v přímém spojení, pokud se liší právě v jednom bitu. Dostaneme monžinu O a A, |O| = |A| což představuje odesilatele a adresáty. Odesilatelé posílají zpravů adresátům. Jedno zařízení může zprávu poslat pouze těm zařízením, se kterými má příme spojení. Jakmile zpráva doputuje k nějakému adresátovi, již se dál neposílá. Naším úkolem je heuristicky najít takovou disjunktní množinu cest, že přes každé zařízení projde zpráva právě jednou.
<{/ForumPost}>