Matfyz Wiki
Malé příklady
Prolog:
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
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:
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.