Matematické Fórum

Zde jsou dva ukoly pro lehce chytrejsi jedince...:)
1) Nech? p je permutace na množině X. Značením rozumíme funkci, která
vznikne k-násobným složením p samy se sebou (rozmyslete si, že to bude
opět permutace). Řád permutace je nejmenší k takové, že , kde
id označuje identickou permutaci, která každý prvek zobrazí sám na sebe.
Určete řád permutace (2 3 1 5 4 7 8 9 6).

2) Vymyslete algoritmus (naprogramovatelný např. v Pascalu), který načte řád-
kově zadanou permutaci n prvků, a určí její řád. Analyzujte jeho časovou a
pamě?ovou složitost. Algoritmus podrobně popište a zdůvodněte, že pracuje
správně. řešení v čase O(n),