Zkouška 1. termín - MIN401 - jaro 2021 - 17. 6. 2021
Veškeré odpovědi musí být zdůvodněny a výpočty musí být doprovozeny komentářem. (Řešení sestávající pouze z odpovědí budou považována za opsaná a hodnocena 0 body.)
1. (4 body) Rozložte polynom
p(x) = x4 + 2x3 + 2x + 2
na ireducibilní faktory nad Z3.
2. (8 bodů) Uvažme grupy (Z, +), (Zn, +), (Z x Z, +) a grupy permutací (Sn, o), n > 2. (a) Uvažme podmnožinu
M = {a e S5|o-(2) = 2 nebo tr(2) = 5} C §5.
Rozhodněte, zda je M podgrupa v §5. (bl) Určete nejmenší podgrupu H\ v Zig obsahující prvky 6 a 9. (b2) Najděte nějakou netriviální podgrupu H2 v Zig neobsahující prvek 6. (b3) Existuje v Zig netriviální podgrupa, která neobsahuje ani jeden z prvků 6 a 9? (cl) Uvažme zobrazení ip : 1*$ —y §6 takové, že
y?(0)=id   a   ip{k) = (l,2,...,k + 1)
kde k G {1,... 5}. Rozhodněte, zda 99 je homomorpfismus grup. (c2) Uvažme homomorpfismus grup ip : Z —y §g určený podmínkou
^(1) = (1,4,2,6)(2,5,7).
Určete jádro ker^. Dále určete ip(23). (c3) Uvažme homomorpfismus grup ip' : Z x Z —y §10 určený podmínkami
^(1,0) = (3,5)(2,4)   a   ^(0,1) = (1, 7)(6,10, 8, 9).
Určete jádro ker^'. Dále určete ^'(ÍO, 10).
3. (8 bodů) Mějme lineární (6, 3)-kód nad Z2 zadaný maticí
/l   1 0\
1  0 1
o 1 1
10 0'
o 1 o \o o 1/
Tedy délka zprávy před zakódováním je 3 a po zakódování 6. Byla přijata zpráva
(a) 100001,
(b) 110011,
(c) 111001.
Ve všech těchto případech určete syndrom a zprávu dekódujte (tj. určete odeslanou zprávu) za předpokladu, že při přenosu došlo k nejmenšímu možnému počtu chyb. Je dekodódování za tohoto předpokladu vždy možné jednoznačně? Jestliže nikoliv, určete všechny možnosti s minimem chyb.
Řešení a bodování:
1. [4 body] Vyzkoušením 0, 1 a 2 přímo vidíme, že polynom p(x) nemá kořeny nad Z3. Ještě je ale možné, že p(x) je součinem dvou kvadratických faktorů, tj. že
x4 + 2x3 + 2x+ 2 = (x2 + ax + b)(x2 + cx + d) = x4 + (a + c)x3 + (b + ac+ ď)x2 + (ad + bc)x + bd,
kde a, b, c, d G {0,1, 2}. Tedy bd = 2, což dává dvě možnosti: b = 2, d = 1 a přehozené pořadí (které by ale jen znamenalo přehození pořadí kvadratických faktorů). Pro tyto hodnoty b a d dostáváme zbývající rovnice
a + c = 2,    b + ac + d = ac = 0   a   ad + bc = a + 2c = 2. Případ a = 0 nemá řešení a v případš c = 0 dostaneme a = 2, tj.
p(x) = x4 + 2x3 + 2x+ 2 = (x2 + 2x + 2)(x2 + 1).
2. [8 bodů]
(a) Například (125) G M, ale inverze tohoto cyklu do M nepatří, tj. (152) ^ M. Tedy M není podgrupa.
(b) iii je generována největším společným dělitelem 6 a 9, tj. H\ = {0, 3, 6, 9,12,15}. Dále H2 = {0, 9} a podgrupa v (b3) neexistuje - rozmyslete si, jaký by musel být nejmenší nenulový prvek v takové podgrupě.
(cl) ip není homomorpfismus - například ip(l) o (p(5) není identita v §6-(c2) Jelikož uj := (1,4, 2, 6)(2, 5, 7) = (1, 4, 2, 5, 7, 6) je cyklus délky 6, je
ker V' = 6Z = {6k G Z\k G Z}.
Dále V(24) = ícř a tedy tp(23) = uj^1 = (1,6, 7, 5, 2, 4). (c3) Zjevně        0) má řád 2 a "0'(0,1) má řád 4 (řády jsou v §10). Tedy
ker V'' = {(a, b) G Z x Z | 2|a V 4|6}.
Dále V'(10,10) = (6,8)(10,9).
3. [8 bodů] Matice kódu G a matice kontroly parity iř jsou
G =
/l	1	
1	0	1
0	1	1
1	0	0
0	1	0
\o	0	v
'l   0   0   1   1 CP
iř = I o 1 o 1 o 1
,001011,
Platná kódová slova (při přenosu bez chyb) jsou
110100,    101010,    011001,    011110,    101101,    110011,    000000, 000111.
(a) Dostáváme syndrom H ■ (100001)T = (1H)T, přičemž slova s tímto syndromem jsou
010101,    001011,    111000,    111111,    001100,    010010,    100001, 100110.
Minimální počet jsou tedy dvě chyby (jedničky), což nastane u třech slov 001100, 010010 a 100001. Po odečtení slova 100001 dostaneme 101101, 110011 a 000000, tj. původně byla zaslána některá ze zpráv 101, 011 nebo 000. Dekódování tedy není jednoznačné.
(b) Dostáváme syndrom H ■ (110011)T = (000)T, tj. 110011 je platné kódové slovo a poslaná zpráva byla 011.
(c) Dostáváme syndrom H ■ (111001)T = (100)T, přičemž slova s tímto syndromem jsou
001101,    010011,    100000,    100111,    010100,    001010,    111001, 111110.
Minimální počet je tedy jedna chyba (jednička), což nastane u slova 100000. Po odečtení slova 111001 dostaneme 011001, tj. původně byla zaslána zpráva 001.