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