Řešení Zkoušky 1. termín - MIN401 - jaro 2022 - 21.6.2022 Příklad 1: [4 body] Uvažme permutace 123456789 347219865 123456789 521438769 123456789 M~'~ 1 46 3 75 9 2/' (i) Rozložte permutaci s na součin nezávislých cyklů. (ii) Rozložte permutaci s na součin transpozic a určete její paritu. (iii) Spočtěte t~ľ a u211. (iv) Spočtěte (s120 o r3)17 o u23. Řešení: (i) s = (1378695)(24). (ii) s = (13)(37)(78)(86)(69)(95). Permutace je sudá, protože počet transpozic v rozkladu je sudý. (iii) Pro výpočet inverze stačí prohodit řádky a nový horní řádek seřadit: ,_i íl 2 3 4 5 6 7 8 9N 1 \3 254 1 8769,/' Máme rozklad u = (1892)(34675). Číslo 211 dává zbytek 3, resp. 1 po dělení 4, resp. 5. Takže u211 = (1298)(34675). (iv) Platí t~ľ = (153)(68). Tedy r~3 = (68). Stejně jako v předchozí části získáme u23 = (1298)(37456) a s120 = (1378695). Tedy s120 of3 = (895137). Takže (s120 of3)17 = (873159). Celkem tedy (s120 o r3)17 o u23 = (873159)(1298)(37456) = (12856)(497). Příklad 2: [2 body] Ukažte, že množina {a + by/3 | a, b E Q, a2 + 62 > 0} je podgrupa grupy (K\{0},-). Řešení: Označme množinu ze zadání M. Zřejmě 1 = 1 + 0\/3 G M. Nechť a + by/3 E M. Potom 1 a — &V3 a — 6y3 a — 6 a- ;V3 G M. a + &V3 (a + 6^/3)(a-6^/3) a2 - 362 a2 - 362 a2 - 3b2 Všimněme si, že a2 — 3b2 ý 0? protože y/3 je iracionální. Navíc nemůže nastat, že by oba zlomky byli nulové, protože nemohou být a, b zároveň obě nulové. Nyní, nechť a + by/3 E M a c + dy/3 E M. Potom (a + by/3)(c + dy/3) = (ac + 3bd) + (bc + ad)\/3 E M. Vskutku, pro spor nechť ac + 3bd = 6c + ad = 0. Víme, že c ^ 0 nebo d 7^ 0. Nechť d ^ 0, tedy — + 36 (Z5, +), /([a]3, [%) = [&H]5 pro a, 6 G Z. (ii) (Zis,+) -> (Z5,+) x (Z3,+), #([a]15) = ([a]5, Ns) pro a G Z. Řešení: (i) Není to ani zobrazení, protože například [21]5 ý [24]s- (ii) Jedná se o zobrazení, protože g([a+15k]15) = ([a+15k]5, [a+15k]3) = ([a] 5, [a]3) = (?([a]i5) pro všechna a, k E Z. Dokonce se jedná i o homomorfismus, protože #(M15 +[&] 15) = g([a+b]15) = ([a+b]5, [a+6]3) = ([a]5, [a]3) + ([6]5, [6]3) = g([a]15)+g([b]15). Jádro je zřejmě {[0]i5J a obraz je (Z5,+) x (Z3,+). Je to tedy injektivní i surjektivní homomorfismus. Příklad 4: [2 body] Určete všechny a G Q takové, že polynom f = x5 — ax2 — ax + 1 G Q[x] má dvojnásobný kořen —1. Řešení: Derivace zadaného polynomu je 5x4 — 2ax — a. Dosazením X — 1 cl položením derivace rovno nule zjistíme, že 5 + 2a — a = 0, tedy a = —5. Jediné možné a G Q splňující zadání je tedy a = —5, a opravdu dosazením —1 do x5 + 5x2 + 5x + 1 a 5x4 + 10rr + 5 zjistíme, že x = — 1 je vskutku kořen těchto dvou polynomů. Tedy hledané a G Q je právě a = —5. Příklad 5: [4 body] Určete všechny ireducibilní polynomy nad Z2 stupně menšího než 5. Řešení: Jsou to právě polynomy X, x + 1, x2 + x + 1, x3 + x + 1, x3 + x2 + 1, x4, +x + 1, + + 1, + + x2 + X + 1. Vskutku, u polynomů stupně menšího než 4 můžeme o ireducibilitě rozhodnout podle toho jestli mají kořen (V Z2 stačí vyzkoušet dva potenciální kořeny [0)2, [l^)- U polynomů stupně 4 můžeme rozhodnout pomocí existence kořenů a vyloučením všech součinů dvojic kvadratických ireducibilních polynomů, takový polynom je ovšem pouze jeden, tedy jediný takový polynom, který vyloučíme, je {x2 + x + l)2 = x4 + x2 + 1. Příklad 6: [2 body] Nakreslete Hasseho diagram svazu kladných dělitelů čísla 120. Řešení: (Obrázek převzat ze stackexchange vlákna.) 120 / I \ 24 40 €0 8 12 20 30 XIX XI \ 4 6 10 15 \IX XI 2 3 5 \ IX 1 Příklad 7: [4 body] Uvažme lineární (ll,7)-kód generovaný polynomem 1 + x3 + x4. (i) Určete generující matici a matici kontroly parity. (ii) Dekódujte slovo 00000100100 za předpokladu, že došlo k nejmenšímu množství chyb. Řešení: (i) Pomocí algoritmu ze cvičení najdeme generující matici g = (1 1 1 1 0 1 o\ 0 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 v> 0 0 0 0 0 v Z tohoto ihned vidíme i matici kontroly parity h = /l 0 0 0 1 1 1 1 0 1 o\ 0 1 0 0 0 1 1 1 1 0 1 0 0 1 0 0 0 1 1 1 1 0 \o 0 0 1 1 1 1 0 1 0 v (ii) Vypočteme G • (0100100)T = (10100100100)T. Chyba je 10100000000. Přičtením kombinací alespoň dvou sloupců bychom určitě stále měli chybu alespoň s dvěma jedničkama. Zmenšit chybu lze tedy pouze potenciálně pomocí přičtení nějakého sloupce. Je ihned vidět, že jediný sloupec, který zmenší chybu je šestý sloupec, a přičtením tohoto sloupce dostaneme chybu 00000000010. Poslaná zpráva byla tedy 00000100110, a informační část této zprávy je 0100110.