Informacje dla kandydatów

Algebra abstrakcyjna i kodowanie

Stacks Image 374
Wykład rozpocznie się od wprowadzenie trzech podstawowych struktur algebraicznych: grup, pierścieni i ciał. Poznasz wiele przykładów tych stuktur. Zrozumiesz piękne twierdzenie Lagrange`a:

$$\mbox{\(H\) jest podgrupą grupy \(G\)} \rightarrow card(H)\,|\, card(G)$$

które ma wiele fajnych konsekwencji. Poznasz pierwsze wyniki o klasyfikacji grup skończonych. Nauczyć się liczyć w grupach cyklicznych \(C_n\), pierścieniach \(Z_n\), ciałach \(Z_p\), grupach \((Z_n)^*\) oraz w pierścieniach wielomianów.
Stacks Image 707
Następnie omówione zostaną podstawowe pojęcia i fakty z Teorii Liczb. Nauczysz się rozwiązywać równania diofantyczne, poznasz małe twierdzenie Fermata, zapoznasz się z własnościami funkcji Eulera, poznasz chińskie twierdzenie o resztach i jego zastosowania.

Następnie zajmiesz się serią zagadnień z teorii kodów. Poznasz pojęcie kodów korekcyjnych, odległości Hamminga, wykrywaniem i korekcją błędów, kodów liniowych kodów Hamminga, Golaya. Poznasz pojęcie elementu pierwotnego, wielomianu nierozkładalnego, algebraicznego rozszerzenie ciała, ciała Galoisa, wielomianu minimalnego, kod BCH

Wykład zakończy się omówieniem struktury i konstrukcji skończonych ciał algebraicznych. Dowiesz się, że dla każdej liczby pierwszej \(p\) oraz dodatniej liczby naturalnej \(n\) istnieje dokładnie jedno ciało liczbowe, które ma \(p^n\) elementów.

Algebra abstrakcyjna jest ważnym narzędziem współczesnej informatyki. Podstawowe dzisiaj techniki kryptograficzne, takie jak algorytm RSA i algorytm ElGamala opierają się na własnościach algebraicznych omawianych na tym wykładzie struktur. Bardzo wiele protokołów wykorzystuje pierścień \(\{0, 1\}^n\), skończona płaszczyzna \((Z_n)^2\) jest wykorzystywana do predystrybucji kluczy. Przykładów można by podać tu znacznie więcej.

Większość omawianych na tym wykładzie zagadnień może być dla Ciebie zupełnie nowa. Ale szybko polubisz abstrakcyjne struktury algebraiczne. Ze zdziwieniem zorientujesz się, że umiesz liczyć w dowolnych ciałach (bo umiesz już liczyć w liczbach rzeczywistych i zespolonych, a pojęcie ciała algebraicznego jest uogólnieniem tych dwóch konkretnych ciał).

Dodatkowe materiały

Katedra Informatyki
Politechnika Wrocławska
Wydział Podstawowych Problemów Techniki