Fórum studentů MFF UK

Ještě doplním kolegu
na test bylo 2 hodiny.

body:
1) 14 b
2) 12 b
3) 12 b
4) 16 b
5) 16 b
6) 20 b
+ 10b za kvízy které zadával průběžně na svoje stránky
hodnocení 55-67-80
[line][/line]

Celkově mi na test přišlo poměrně málo času, není to na nějaké velké vymejšlení/zasekávání.

1) Mějme [latex]f, g, h, m \in Q[x][/latex], kde [latex]m, h[/latex] jsou nesoudělné. Dokažte, že pokud je [latex]fh \equiv gh[/latex] mod [latex]m[/latex] implikuje [latex]f \equiv g[/latex] mod [latex]m[/latex]. Napište obor integrity, kdo tato implikace neplatí.

2)
a) Platí v [latex]Z_7[x][/latex] Bezoutka? Formulace/protipříklad
b) Najděte všechny polynomy [latex]f \in Z_7[x][/latex], pro které platí [latex]x f \equiv 2[/latex] mod [latex]x^3 + x + 1[/latex]

3) Najděte rozklad polynomu [latex]\alpha x^2 + x + (\alpha + 1)[/latex] v [latex]F_9[x][/latex]. Kde [latex]F_9 = Z_3\[\alpha\]/(\alpha^2 + 1)[/latex].

4)
a) Reed-Salomonovy kódy. Co to je, jak a proč.
b) Dekódujte a odhalte chybu.

5)
a) Existuje šedesátiprvková grupa s prvek řádu 20? Nez něj? Důkaz/protipříklad.
b) Buď G grupa, platí [latex]\langle a, b \rangle_G = {a^k, b^k, k \in Z}[/latex]? Důkaz/protipříklad.

6) Působení [latex]G = A_5[/latex] na [latex]X = \{1, 2, 3, 4, 5\}^2[/latex] uspořádaných dvojic, kde [latex]\pi((x, y)) = (\pi(x), \pi(y))[/latex].
Kolik je orbit? Jaké mají prvky?
Co je [latex]G_{(1, 2)}[/latex] ? A co je [latex]X_{(1 2 3)}[/latex]?
Napište a dokažte lemma o vztahu stabilizátoru a orbity.

===================

Odpovědi/nástřely:

1)
[latex]Q[x][/latex] je Gaussovský, takže jednoznačné rozklady. Implikace platí z rozkladů prvků [latex]h(f-g)[/latex], [latex](f-g)[/latex] a [latex]h[/latex].
Neplatí v OI [latex]Z[\sqrt(5)][/latex], který nemá jednoznačné rozklady -> [latex]2 | (\sqrt(5) + 1)(\sqrt(5) - 1)[/latex], ale nedělí ani jeden z těch dvou.

2)
a) [latex]Z_7[/latex] je těleso, [latex]Z_7[x][/latex] je tedy euklidovský a tedy platí v něm Bezoutka. V euklidově algoritmu jenom musím počítat s normou.
b) [latex]f = 5x^2 + 5 + k(x^3 + x + 1)[/latex]pro [latex]k \in Z_7[x][/latex]

3)
Polynom je irreducibilní prvek.
Žádný z 9-ti prvků Z [latex]F_9[/latex] není jeho kořen, tudíž nelze rozložit.

4)
a) Samopravné kódy fungující na interpolaci polynomů.
b) Stačí si tipnout funkci, která prochází všemi body až na jeden.

5)
a) Existují obě. Grupa [latex]G = Z_{60}[/latex] má prvek řádu 20, Grupa [latex]G = Z_2 \times Z_2 \times Z_3 \times Z_5[/latex] ho nemá.
b) Neplatí, [latex]\langle a, b \rangle_G[/latex] musí obsahovat a (a taky b), ale to není obsaženo v [latex]{a^k, b^k, k \in Z}[/latex].

6)
Dvě orbity - pět prvků (a, a) a dvacet prvků (a, b). (a, a) se nezobrazí na nic jiného než jiné (b, b), zatímco pro libovolné a, b, c umím najít permutaci takovou, abych z (a, b) vygeneroval (a, c) nebo (c, b).
[latex]G_{(1, 2)}[/latex] jsou identita a trojcykly neobsahujíci 1 nebo 2.
[latex]X_{(1 2 3)}[/latex] jsou dvojice neobsahující 1, 2 nebo 3.