OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie z zestawu
W rozwiązaniach należy umieścić kod testujący przygotowane funkcje.
Stworzyć plik permutations.py i zapisać w nim funkcje do działań na permutacjach liczb od 0 do N-1 (N ustalone globalne). Permutacja będzie reprezentowana przez listę, np. a dla permutacji przyporządkującej 0 → a[0], 1 → a[1], 2 → a[2], 3 → a[3] (tutaj N=4). Mnożenie permutacji rozumiemy jak składanie funkcji, czyli dla a*b=c mamy c[i]=a[b[i]] dla każdego i. Permutacja b jest odwrotna do a, jeśli b[a[i]]=i dla każdego i. Napisać kod testujący moduł permutations.
def mul_perm(perm1, perm2): pass # perm1 * perm2 def invert_perm(perm): pass # permutacja odwrotna def is_identity(perm): pass # bool, czy identyczność def find_order(perm): pass # rząd (krotność) permutacji jeden = list(range(N)) # identyczność
(a) Zbadać grupę symetrii planszy sudoku 4x4. Generatory: permutacje wierszy 1-2, 3-4; zamiana wierszy (1,2) z (3,4); permutacje kolumn 1-2, 3-4; zamiana kolumn (1,2) z (3,4); obrót planszy o 90 stopni.
+-------+-------+ | 0 1 | 2 3 | | 4 5 | 6 7 | +-------+-------+ | 8 9 | 10 11 | | 12 13 | 14 15 | +-------+-------+
(b) Zbadać grupę symetrii planszy sudoku 9x9.
(a) Grupa cykliczna C_N (rzędu N) może być wygenerowana z jednego cyklu (0,1,...,N-1). Sprawdzić to dla kilku różnych N.
(b) Jeżeli N nie jest liczbą pierwszą, to grupę cykliczną można otrzymać również z innego generatora lub generatorów. Dla C_6 wystarczy generator z S_5 postaci (0,1,2)(3,4); korzystamy tutaj z faktu, że C_6 = C_3 x C_2. Możemy również wybrać dwa generatory (0,1,2) i (3,4).
(a) Grupa diedralna D_N (rzędu 2*N) może być wygenerowana z dwóch generatorów. Dla N > 2 jest to grupa symetrii graniastosłupa o podstawie wielokąta foremnego (D_3 dla trójkąta, D_4 dla kwadratu, itd.). Wygodnie jest kolejnymi liczbami oznaczyć ściany boczne graniastosłupa. Generatory dla D_3 to (0,1,2) i (1,2). Pokazać, że D_3 jest izomorficzna z S_3.
(b) Dla D_4 wybieramy generatory (0,1,2,3) i (1,3).
(c) Dla D_5 wybieramy generatory (0,1,2,3,4) i (1,4)(2,3).
(c) Dla D_6 wybieramy generatory (0,1,2,3,4,5) i (1,5)(2,4).
(d) Dla D_2 (rzędu 4) wybieramy generatory korzystając z tabelki grupowej i twierdzenia Cayley'a. Są to permutacje z grupy S_4 (0,1)(2,3) i (0,2)(1,3).
+----+---------+ Tabelka grupowa D_2 | E | 0 1 2 3 | |C_2x| 1 0 3 2 | |C_2y| 2 3 0 1 | |C_2z| 3 2 1 0 | +----+---------+
Dla D_2 można znaleźć inne przedstawienie za pomocą permutacji, jeżeli skorzystamy ze związku D_2 = C_2 x C_2. Wybieramy dwa generatory (0,1) i (2,3).
Grupa symetryczna S_N (rzędu N!) dla N > 1 może być wygenerowana z N-1 generatorów postaci (0,1), (1,2), ..., (N-2,N-1). Sprawdzić to dla kilku różnych N.
Grupa alternująca A_N (rządu N!/2) dla N > 2 może być wygenerowana z N-2 generatorów postaci (0,1,2), (1,2,3), ..., (N-3,N-2,N-1). Sprawdzić to dla kilku różnych N.
Mamy dane dwa generatory (0,1,2,3,4,5)(6,7,8,9,10,11) i (0,6,3,9)(1,11,4,8)(2,10,5,7). Wygenerować wszystkie permutacje nieabelowej grupy rzędu 12. Stworzyć tabelkę grupową.
Dana jest tabelka mnożenia elementów grupy kwaternionów. Zapisać tabelkę z użyciem liczb od 0 do 7. Zbudować grupę permutacji z S_8 reprezentującą grupę kwaternionów, korzystając z dwóch generatorów, np. dla "i" oraz "j".
+--+--+--+--+--+--+--+--+ | 1| i| j| k|-1|-i|-j|-k| | i|-1| k|-j|-i| 1|-k| j| | j|-k|-1| i|-j| k| 1|-i| | k| j|-i|-1|-k|-j| i| 1| |-1|-i|-j|-k| 1| i| j| k| |-i| 1|-k| j| i|-1| k|-j| |-j| k| 1|-i| j|-k|-1| i| |-k|-j| i| 1| k| j|-i|-1| +--+--+--+--+--+--+--+--+