Algebra abstrakcyjna i kodowanie, I rok inf. WPPT
Egzamin II – 29 czerwca 2009 – zestaw A
1.
• Wyznacz wszystkie warstwy grupy multyplikatywnej Z
∗
36
względem podgrupy
H
= {1, 13, 25}.
• Oblicz za pomocą twierdzenia Fermata-Eulera element odwrotny do jakiegoś
elementu k ∈ Z
∗
36
, k 6= 1. Dlaczego można do tego celu zastosować to twierdze-
nie?
2. Niech n > 0 będzie liczbą naturalną. Pokaż, że 10
n
≡ 1 (mod 9). Zastosuj tę własność
do dowodu, że liczba n jest przystająca modulo 9 do sumy swoich cyfr dziesiętnych.
Zastosuj odpowiedni zapis liczby n w systemie dziesiętnym, czyli o podstawie 10.
3. Znajdź minimalną odległość kodu o macierzy generującej
G
=
0 0 1 0 1 1 0 0 0
0 1 0 1 0 0 1 0 0
1 0 1 0 0 0 0 1 0
0 1 1 0 1 0 0 0 1
.
Podaj kontrolną macierz parzystości tego kodu. Omów zdolność wykrywania błędów
i zdolność ich korygowania przez ten kod.
4. Rozwiąż nad ciałem Galoisa GF(4) układ równań
(α + 1)x + y = α,
x
+ (α + 1)y = α + 1,
gdzie α jest pierwiastkiem wielomianu x
2
+ x + 1 definiującego to ciało.
5. Rozwiąż układ trzech (lub dwóch) kongruencji
x
≡ 2(mod 7),
x
≡ 7(mod 9),
x
≡ 3(mod 4).
Uwaga
. Za rozwiązanie układu tylko dwóch kongruencji liczba punktów będzie
mniejsza.
6. =====================
Dodatkowe zadanie
Niech H i K będą podgrupami grupy G. Niech a, b ∈ G. Zbiór HaK
HaK
= {hak : h ∈ H, k ∈ K}
nazywamy warstwą dwustronną podgrup H i K. Udowodnij, że albo HaK = HbK
albo przekrój HaK ∩ HbK jest pusty.
Algebra abstrakcyjna i kodowanie, I rok inf. WPPT
Egzamin II – 29 czerwca 2009 – zestaw B
1.
• Wyznacz wszystkie warstwy grupy G = Z
∗
36
względem podgrupy H = {1, 17, 19, 35}.
• Oblicz za pomocą rozszerzonego algorytmu Euklidesa element odwrotny do ja-
kiegoś elementu k ∈ Z
∗
36
, k 6= 1. Dlaczego do tego celu nie można zastosować
małego twierdzenia Fermata?
2. Wykaż, że kongruencje x ≡ a (mod m) i x ≡ b (mod n) mają wspólne rozwiązanie x
wtedy i tylko wtedy gdy a ≡ b (mod NWD(m, n)).
3. Znajdź minimalną odległość kodu o macierzy generującej
G
=
1 0 0 0 0 0 1 0 1
0 1 0 0 0 1 0 1 0
0 0 1 0 1 0 1 0 0
0 0 0 1 0 1 1 0 1
.
Podaj kontrolną macierz parzystości tego kodu. Omów zdolność wykrywania błędów
i zdolność ich korygowania przez ten kod.
4. Rozwiąż nad ciałem Galoisa GF(4) układ równań
αx
+ (α + 1)y = α + 1,
x
+ αy = 1,
gdzie α jest pierwiastkiem wielomianu x
2
+ x + 1 definiującego to ciało.
5. Rozwiąż układ trzech (lub dwóch) kongruencji
x
≡ 2(mod 3),
x
≡ 3(mod 5),
x
≡ 2(mod 7).
Uwaga
. Za rozwiązanie układu tylko dwóch kongruencji liczba punktów będzie
mniejsza.
6. =====================
Dodatkowe zadanie
Niech H i K będą podgrupami grupy G. Niech a, b ∈ G. Zbiór HaK
HaK
= {hak : h ∈ H, k ∈ K}
nazywamy warstwą dwustronną podgrup H i K. Udowodnij, że albo HaK = HbK
albo przekrój HaK ∩ HbK jest pusty.
2