Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Permutace
Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
1/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Motivace Permutace jsou d˚ uleˇzitou ˇc´ast´ı matematiky viz pouˇzit´ı v pravdˇepodobnosti, algebˇre (napˇr. determinanty) a mnoho dalˇs´ıch. Jsou z´asadn´ı tak´e pro kryptografii viz napˇr. monoalfabetick´e a polyalfabetick´e ˇsifry, enigma. Pomoc´ı permutac´ı lze vydˇelat pen´ıze viz pan Samuel Loyd. Samuel Loyd a jeho hlavolam “15-ka” 1000$ tomu, kdo najde ˇreˇsen´ı: 1 5 9 13
2 6 10 15
3 7 11 14
4 8 12
Rostislav Horˇ c´ık: Y01DMA
→
1 5 9 13
2 6 10 14
3 7 11 15
11. kvˇ etna 2010: Permutace
4 8 12
2/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Definice Necht’ n = {1, 2, 3, . . . , n} a Sn je mnoˇzina vˇsech bijekc´ı z n do n. Pak Sn tvoˇr´ı grupu (Sn , ·, −1 , id) s operac´ı skl´ad´an´ı funkc´ı · a neutr´aln´ım prvkem id. Grupa Sn se naz´yv´a grupa permutac´ı (nebo tak´e symetrick´a grupa). Konvence Permutace budeme skl´adat zleva do prava, tj. f · g = g ◦ f . Obraz prvku x permutac´ı f znaˇc´ıme xf , tj. xf = f (x). Permutaci f ∈ Sn zapisujeme takto: 1 2 ··· n 1f 2f · · · nf
Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
3/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Pˇr´ıklad Mˇejme f , g ∈ S4 definovan´e: 1 2 3 4 f = , 2 4 1 3 Pak
1 2 3 f ·g = 2 1 3 2 4 −1 f = 1 2
1 2 3 4 g= 3 2 4 1
4 1 2 3 4 6= g · f = 4 1 4 3 2 1 3 1 2 3 4 = 3 4 3 1 4 2
Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
4/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Definice Mˇejme r r˚ uzn´ych prvk˚ u x1 , . . . , xr ∈ n. Pak r -cyklus (x1 x2 · · · xr ) je permutace z Sn , kter´a zobrazuje x1 7→ x2 , x2 7→ x3 , . . . , xr −1 7→ xr , xr 7→ x1 a fixuje ostatn´ı prvky z n. 2-cykly se tak´e naz´yvaj´ı transpozice. Pˇr´ıklad Uvaˇzujme permutaˇcn´ı grupu S5 . Pak napˇr. 3-cyklus (1 5 2) je n´asleduj´ıc´ı permutace z S5 : 1 2 3 4 5 5 1 3 4 2 Kaˇzd´y 1-cyklus je identick´a permutace id. Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
5/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Definice Dva r -cykly (x1 x2 · · · xr ) a (y1 y2 · · · yr ) se naz´yvaj´ı disjunktn´ı, pokud {x1 , x2 , . . . , xr } ∩ {y1 , y2 , . . . , yr } = ∅ . Vˇeta Kaˇzd´a permutace se d´a vyj´adˇrit jako souˇcin disjunktn´ıch cykl˚ u. Pˇr´ıklad 1 2 3 4 5 6 7 8 = (1 2 4 5) · (3) · (6) · (7 8) = 2 4 3 5 1 6 8 7 = (1 2 4 5) · (7 8)
Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
6/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Pˇr´ıklad Stejn´a metoda funguje i na v´ypoˇcet souˇcinu cykl˚ u. (1 4 5) · (4 6) · (6 4 7) · (3 7) = (1 4 5) · (3 7 6) Tvrzen´ı Mˇejme r -cyklus (x1 x2 · · · xr ). Pak (x1 x2 · · · xr )−1 = (xr xr −1 · · · x1 ). Pˇr´ıklad ((1 2 4 5) · (7 8) · (3 6))−1 = (3 6)−1 · (7 8)−1 · (1 2 4 5)−1 = (6 3) · (8 7) · (5 4 2 1) = (3 6) · (7 8) · (1 5 4 2) Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
7/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Tvrzen´ı Disjuntn´ı cykly komutuj´ı, tj. f · g = g · f pro disjunktn´ı cykly f , g . Tvrzen´ı ˇad r -cyklu (x1 x2 · · · xr ) je r . R´ Pˇr´ıklad Napˇr. (1 4 5)3 = (1 4 5) · (1 4 5) · (1 4 5) = id. Vˇeta Necht’ f je permutace a f = f1 · f2 · · · fk je jej´ı rozklad na souˇcin disjunktn´ıch cykl˚ u. Pak ˇr´ad f je nejmenˇs´ı spoleˇcn´y n´asobek ˇr´ad˚ u f1 aˇz fk .
Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
8/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Pˇr´ıklad 1 2 3 4 5 6 7 8 Spoˇctˇete ˇr´ad f = ∈ S8 . 2 4 6 5 1 3 8 7 ˇ ad f je tedy lcm(4, 2, 2) = 4. M´ame f = (1 2 4 5) · (7 8) · (3 6). R´
Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
9/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Vˇeta Kaˇzd´a permutace lze vyj´adˇrit jako souˇcin transpozic. D˚ ukaz Cyklus (x1 x2 · · · xr ) lze vyj´adˇrit jako (x1 x2 ) · (x1 x3 ) · (x1 x4 ) · · · (x1 xr ). Pˇr´ıklad f = (1 2 4 5) · (7 8) · (3 6) = (1 2) · (1 4) · (1 5) · (7 8) · (3 6).
Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
10/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Definice Transpozici tvaru (i i + 1) budeme naz´yvat sousedn´ı transpozice. Vˇeta Kaˇzdou permutaci lze vyj´adˇrit jako souˇcin sousedn´ıch transpozic. D˚ ukaz Pro i < j plat´ı (i j) = σ · (j − 1 j) · σ −1 , kde σ = (i i + 1) · (i + 1 i + 2) · · · (j − 2 j − 1). Pˇr´ıklad Vyj´adˇrete transpozici (3 7) ∈ S8 jako souˇcin sousedn´ıch transpozic. M´ame σ = (3 4) · (4 5) · (5 6). Pak (3 7) = (3 4) · (4 5) · (5 6) · (6 7) · (5 6) · (4 5) · (3 4) . Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
11/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Definice Permutaci f nazveme lichou (sudou), pokud lze vyj´adˇrit jako souˇcin lich´eho (sud´eho) poˇctu transpozic. Lemma Identick´a permutace id je sud´a (a ne lich´a). Vˇeta Kaˇzd´a permutace je bud’ lich´a nebo sud´a (nikdy ne oboj´ı). Tj. lich´e permutace jdou vyj´adˇrit pouze jako souˇcin lich´eho poˇctu transpozic a sud´e permutace sud´eho poˇctu.
Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
12/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Definice Definujme zobrazen´ı s : Sn → Z2 vztahem: ( 0 pokud je f sud´a, s(f ) = 1 pokud je f lich´a. Vˇeta Necht’ f , g ∈ Sn . Pak s(f · g ) = s(f ) + s(g ), tj. s je homomorfismus grup.
Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
13/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
15-ka 1 5 9 13
2 6 10 15
3 7 11 14
4 8 12
→
1 5 9 13
2 6 10 14
3 7 11 15
4 8 12
Zadan´y stav se liˇs´ı o jednu transpozici. K ˇreˇsen´ı je tedy potˇreba lich´a permutace. Naopak na to aby se pr´azdn´e pol´ıˇcko vr´atilo zpˇet na svoji pozici je potˇreba sud´a permutace. Pan Loyd prodal mnoho sv´ych 15-tek, aniˇz by musel nˇekomu vyplatit sl´ıbenou odmˇenu, protoˇze ˇreˇsen´ı prostˇe neexistuje.
Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
14/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Enigma Enigma je ˇsifrovac´ı pˇr´ıstroj pouˇz´ıvaj´ıc´ı symetrickou polyalfabetickou ˇsifru. Chod pˇr´ıstroje je urˇcen: 3 rotory — permutace %1 , %2 , %3 , poˇc´ateˇcn´ı nastaven´ı a nastaven´ı zar´aˇzek, Plug board — souˇcin disjunktn´ıch transpozic τ , Reflektor — souˇcin disjunktn´ıch transpozic %, Pak j-t´e p´ısmeno zpr´avy je ˇsifrov´ano permutac´ı: j = τ · (σ i1 · %1 · σ −i1 ) · (σ i2 · %2 · σ −i2 ) · (σ i3 · %3 · σ −i3 )· −i3 −i2 −i1 · % · (σ i3 · %−1 ) · (σ i2 · %−1 ) · (σ i1 · %−1 )·τ, 3 ·σ 2 ·σ 1 ·σ
kde σ = (ABCD · · · Z ) a i1 , i2 , i3 z´avis´ı na j a nastaven´ı rotor˚ u. Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
15/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
16/17
Permutaˇ cn´ı grupy Cykly a transpozice Aplikace
ˇ ´I! UPOZORNEN Ofici´aln´ı str´anky pˇredmˇetu: http://cs.cas.cz/∼horcik 1
Poˇzadavky na z´apoˇcet
2
Pr˚ ubˇeh zkouˇsek
3
Studijn´ı materi´aly (skripta a errata skript, sb´ırka pˇr´ıklad˚ ua jej´ı errata)
4
Vzorky test˚ u a p´ısemn´e zkouˇsky
5
Handouts z pˇredn´aˇsek
Rostislav Horˇ c´ık: Y01DMA
11. kvˇ etna 2010: Permutace
17/17
