Algebra abstrakcyjna i kodowanie - I rok informatyki, WPPT

Tematy wykładów 2007/2008

1. Wykład 27 lutego 2008

• działanie algebraiczne, grupa, jednoznaczność elementu neutralnego i odwrotnego,

prawo skracania,

• terminologia multyplikatywna i addytywna,

• podgrupa, warunki konieczne i dostateczne,

• dodawanie i mnożenie modulo n.

2. Wykład 29 lutego 2008

• łączność dodawania modulo n, element przeciwny, grupa Z

n

,

• potęga elementu grupy, grupa cykliczna, generator grupy cyklicznej,

• rząd elementu, rząd grupy, grupa cykliczna generowana przez element skończonego

rzędu,

• przykłady rzędów elementów w Z

∗

n

,

3. Wykład 5 marca 2008

• warstwa lewostronna i prawostronna, twierdzenie o warstwach (rozłączność lub

równość warstw),

• indeks podgrupy H w grupie G, twierdzenie Lagrange’a,

• twierdzenie o grupie, której rząd jest liczbą pierwszą,

• dzielnik normalny.

4. Wykłady 12 i 14 marca 2008

• działania na warstwach - poprawność definicji, grupa ilorazowa,

• twierdzenie charakteryzujące dzielnik normalny (zob. tez listy zadań),

• homomorfizm i izomorfizm grup, jądro i obraz homomorfizmu,

• podstawowe własność homomorfizmu,

• twierdzenie o izomorfizmie grup cyklicznych generownych przez elementy tego sa-

mego rzędu,

• rząd elementu - druga definicja, twierdzenie o grupie cyklicznej generowanej przez

element skończonego rzędu,

• grupa permutacji, cykl, rząd grupy cyklicznej generowanej przez daną permutację,

• homomorfizm grupy addytywnej liczb całkowitych Z z grupą Z

n

z dodawaniem

modulo n.

5. Wykład 19 marca

• rząd elementu grupy izomorficznej z daną grupą,

• twierdzenie Cayleya,

• pierścień, ciało.

1

6. Wykład 26 marca 2008

• podstawowe własności pierścieni - mnożenie przez zero pierścienia,...

• pierścien Z

n

, warunki konieczne i dostateczne na istnienie elementu odwrotnego ze

względu na mnożenie modulo n, twierdzenie Euklidesa,

• dzielenie liczb całkowitych - iloraz, reszta,

• równanie diofantyczne, twierdzenie charakteryzujące liczby pierwsze i twierdzenie

o rozwiązaniach równania diofantycznego (dowody będą podane na następnym
wykładzie),

• definicja największego wspólnego dzielnika liczb całkowitych, algorytm Euklidesa

wyznaczania największego wspólnego dzielnika liczb całkowitych,

7. Wykład 2 kwietnia 2008

• dowody twierdzeń o równaniach diofantycznych: ax + by = NWD(a, b), ax + by = c,

• rozszerzony algorytm Euklidesa,

• zastosowanie rozszerzonego algorytmu Euklidesa do obliczania odwrotności modulo

n i do rozwiązywania równań diofantycznych,

• zasadnicze twierdzenie arytmetyki (bez dowodu).

8. Wykłady 9 i 11 kwietnia 2008

• przystawanie modulo n, kongruencje,

• zastosowanie przystawania modulo n do wyznaczania ostatniej cyfry liczby całko-

witej wyrażonej jako potęga liczby 10,

• rozwiązywanie kongruencji ax ≡ b (mod m) za pomocą algorytmu Euklidesa,

• małe twierdzenie Fermata (dowód indukcyjny) i jego zastosowanie do obliczania

odwrotności w ciele Z

p

,

• twierdzenie Eulera-Fermata (dowód korzystający z twierdzenia Lagrange’a i wła-

sności mnożenia modulo n),

• drugi dowód małego twierdzenia Fermata, wynikający z twierdzenia Eulera-Fermata,

• funkcja Eulera, obliczanie odwrotności w Z

∗

n

,

• algorytm szybkiego potęgowania,

• sformułowanie chińskiego twierdzenia o resztach (bez dowodu).

Uwaga

. Na kolokwium w dniu 23 kwietnia obowiązuje materiał aż do wykładu z dnia

11 kwietnia włącznie, bez chińskiego twierdzenia o resztach.

9. Wykład 18 kwietnia 2008

• algorytm Gaussa rozwiązywania chińskiego twierdzenia o resztach,

• algorytm rozwiązywania układu dwóch kongruencji z chińskiego twierdzenia o resz-

tach,

• zastosowanie chińskiego twierdzenia o resztach do wykonywania działań na dużych

liczbach

• wielomiany - przypomnienie

10. Wykład 23 kwietnia 2008

2

• pierścień wielomianów nad dowolnym pierścieniem

• dzielenie wielomianów z resztą

• funkcja wielomianowa, pierwiastek wielomianu

• wielomian nierozkładalny, przykłady wielomianów nierozkładalnych nad ciałem Z

2

• ideał, dodawanie i mnożenie warstw względem ideału

• pierścień ilorazowy wielomianów

11. Wykład 25 kwietnia 2008

• przykłady ideałów w pierścieniu wielomianów i przykłady pierścieni ilorazowych

wielomianów

• twierdzenie o tym, że jeśli wielomian w(x) ∈ Z

p

jest nierozkładalny nad ciałem Z

p

,

to pierścień ilorazowy wielomianów Z

p

[x]/w(x)Z

p

[x] jest ciałem

• obliczanie warstwy odwrotnej

• wzmianka o największym wspólnym dzielniku wielomianów i rozszerzonym algo-

rytmie Euklidesa dla wielomianów

12. Wykłady 30 kwietnia i 7 maja - dr P. Kubiak

13. Wykład 9 maja

• grupy cykliczne, lemat o podgrupach grupy liczb całkowitych

• własności grup cyklicznych, twierdzenia o obrazie homomorficznym grupy cyklicz-

nej i podgrupie grupy cyklicznej

• własności rzędu elementu, tw. o rzędzie elementu ψ(a), gdzie ψ jest homomorfi-

zmem grup

• twierdzenie charakteryzujące skończone grupy cykliczne (dla każdego dzielnika d

rzędu grupy istnieje ϕ(d) elementów rzędu d, gdzie ϕ jest funkcją Eulera)

• iloczyn (suma) prosty grup,

• tw. o izomorfiźmie grupy Z

mn

z sumą prostą grup Z

m

i Z

n

(NWD (m, n) = 1)

• tw. o izomorfiźmie grupy Z

∗

kl

z sumą prostą grup Z

k

i Z

l

(NWD (k, l) = 1)

• rozkład grupy Z

n

na sumę odpowiednich grup Z

k

• skończone grupy abelowe, tw. o rozkładzie skończonej grupy abelowej na sumę

prostą grup cyklicznych, których rzędy są potęgami liczb pierwszych

• klasyfikacja skończonych grup abelowych.

Uwaga

. Na kolokwium w dniu 28 maja obowiązuje materiał z moich wykładów do

wykładu z dnia 9 maja włącznie (listy 6,7,8). Kodów korekcyjnych na kolokwium nie
będzie (będą na egzaminie).

14. Wykład 23 maja 2008 – powtórka

• kody korekcyjne, minimalna odległość Hamminga, minimalna waga Hamminga,

kod liniowy,

• wykrywanie i korygowanie błędów - twierdzenie chrakteryzujące kody wykrywające

błędy o wadze t, twierdzenie charakteryzujące kody korygujące błędy po wadze t,

• kontrolna macierz parzystości, macierz generująca kod liniowy, standardowa postać

macierzy generującej kod liniowy i jego kontrolnej macierzy parzystości.

3

15. Wykład 28 maja 2008

• Kody wielomianowe i cykliczne

16. Wykłady 4 i 6 czerwca - dr Kubiak

Krystyna Ziętak

4