Algebra abstrakcyjna i kodowanie, I rok inf. WPPT

Egzamin poprawkowy 27 czerwca 2008 - zestaw A

Zadanie 1

(a) (3 pkt) Znajdź wszystkie rozwiązania następującej kongruencji 6x ≡ 3 (mod 9).

(1 pkt) Dlaczego ta kongruencja ma rozwiązanie?

(b) (3 pkt) Niech a ∈ Z

m

. Co trzeba założyć o a, żeby istniał element odwrotny

c = a

−

1

ze względu na mnożenie modulo m? Jak można go obliczyć za pomocą

twierdzenia Fermata-Eulera? Jak brzmi to twierdzenie?

(c) (3 pkt) Niech a spełnia założenia z poprzedniego punktu i niech c = a

−

1

będzie

elementem odwrotnym do a ze względu na mnożenie modulo m. Wykaż, że jeśli
liczba całkowita b ∈ Z jest przystająca do a modulo m, to liczba bc jest przystająca
do 1 modulo m, czyli że prawdziwa jest następująca implikacja:

b ≡ a (mod m) =⇒ bc ≡ 1 (mod m).

Zadanie 2

(a) (4 pkt) Niech I = (x

2

+1)Z

3

[x]. Wykaż, że pierścień ilorazowy Z

3

[x]/I jest dziewię-

cioelementowym ciałem. Oblicz iloczyn jakiś dwóch różnych elementów tego ciała.
Zauważ, że wielomiany mają współczynniki z ciała Z

3

.

(b) Niech G

n

będzie grupą macierzy nieosobliwych rzeczywistych stopnia n (działaniem

jest mnożenie).

• (2 pkt) Dlaczego podzbiór H

n

macierzy rzeczywistych stopnia n o wyznacz-

niku równym 1 jest podgrupą grupy G

n

?

• (2 pkt) Opisz warstwy grupy G

n

względem podgrupy H

n

.

(1 pkt) Niech n = 3. Podaj przykład jakiejś warstwy względem H

3

i przykład

macierzy, która do tej warstwy należy.

Zadanie 3

(a) (3 pkt) Albo odpowiedz na pytania:

Co to znaczy, że kod koryguje wszystkie błędy o ustalonej wadze Hamminga

t? Na

czym to polega i kiedy jest to wykonalne?
albo na pytania:
Czy wielomian

g(x) = 1 + x

2

+ x

3

generuje kod cykliczny o długości

n = 7?

Dlaczego? Podaj dwa słowa kodowe należące do kodu wielomianowego generowanego
przez wielomian

g(x).

(b) (3 pkt) Napisz kontrolną macierz parzystości kodu Hamminga o długości n = 7.

(3 pkt) Podaj jakieś niezerowe słowo z tego kodu i słowo, które do kodu nie należy.
Pamiętaj, że kod Hamminga jest doskonały dla błędów z wagą Hamminga 1. Co
to znaczy?
(3 pkt) Czy ten kod ma 2

4

słów? Dlaczego?

Algebra abstrakcyjna i kodowanie, I rok inf. WPPT

Egzamin poprawkowy 27 czerwca 2008 - zestaw B

Zadanie 1

(a) (2 pkt) Rozwiąż następującą kongruencję 7x ≡ 31 (mod 29).

(2 pkt) Dlaczego ta kongruencja ma rozwiązanie? Czy jest ono tylko jedno? Dla-
czego?

(b) (3 pkt) Niech a ∈ Z

m

. Co trzeba założyć o a, żeby istniał element odwrotny

c = a

−

1

ze względu na mnożenie modulo m? Kiedy można go obliczyć za pomocą

twierdzenia Fermata? Jak brzmi to twierdzenie?

(c) (3 pkt) Niech a spełnia założenia z poprzedniego punktu i niech c = a

−

1

będzie

elementem odwrotnym do a ze względu na mnożenie modulo m. Wykaż, że jeśli
liczba całkowita b ∈ Z jest przystająca do a modulo m, to liczba bc jest przystająca
do 1 modulo m, czyli że prawdziwa jest następująca implikacja:

b ≡ a (mod m) =⇒ bc ≡ 1 (mod m).

Zadanie 2

(a) (4 pkt) Niech I = (x

2

+ x + 1)Z

2

[x]. Wykaż, że pierścień ilorazowy Z

2

[x]/I jest

czteroelementowym ciałem. Podaj wszystkie elementy tego ciała i oblicz iloczyn
jakiś dwóch różnych elementów tego ciała.

(b) Niech G

n

będzie grupą macierzy nieosobliwych rzeczywistych stopnia n (działaniem

jest mnożenie).

• (2 pkt) Dlaczego podzbiór H

n

wszystkich macierzy stopnia n o elementach

całkowitych i wyznaczniku równym 1 jest podgrupą grupy G

n

?

• (2 pkt) Opisz warstwy grupy G

n

względem podgrupy H

n

.

(1 pkt) Niech n = 3. Podaj przykład jakiejś warstwy względem H

3

i przykład

macierzy, która do tej warstwy należy.

Zadanie 3

(a) (3 pkt) Albo odpowiedz na pytania:

Co to znaczy, że kod koryguje wszystkie błędy o ustalonej wadze Hamminga

t? Na

czym to polega i kiedy jest to wykonalne?
albo na pytania:
Czy wielomian

g(x) = 1+x+x

2

generuje kod cykliczny o długości

n = 6? Dlaczego?

Podaj dwa słowa kodowe należące do kodu wielomianowego generowanego przez
wielomian

g(x).

(b) (3 pkt) Napisz kontrolną macierz parzystosci kodu Hamminga o długości n = 7.

(3 pkt) Podaj jakieś niezerowe słowo z tego kodu i słowo, które do kodu nie należy.
Pamiętaj, że kod Hamminga jest doskonały dla błędów z wagą Hamminga 1. Co
to znaczy?
(3 pkt) Czy ten kod ma 2

4

słów? Dlaczego?

2