wyklady abstract 78, PPT
[ Pobierz całość w formacie PDF ]
Algebraabstrakcyjnaikodowanie -Irokinformatyki,WPPT
Tematywykładów2007/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ądelementu,rządgrupy,grupacyklicznagenerowanaprzezelementskoń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,
•
grupapermutacji,cykl,rządgrupycyklicznejgenerowanejprzezdaną 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
,warunkikonieczneidostatecznenaistnienieelementuodwrotnegoze
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,
•
zastosowanierozszerzonegoalgorytmuEuklidesadoobliczaniaodwrotnościmodulo
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 EuleraFermata (dowód korzystający z twierdzenia Lagrange’a i wła
sności mnożenia modulo
n
),
•
drugidowódmałegotwierdzeniaFermata,wynikającyztwierdzeniaEuleraFermata,
•
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,
•
algorytmrozwiązywaniaukładudwóchkongruencjizchińskiegotwierdzeniaoresz
tach,
•
zastosowaniechińskiegotwierdzeniaoresztachdowykonywaniadziałańnaduż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
•
wielomiannierozkładalny,przykładywielomianównierozkładalnychnadciał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
•
twierdzenieotym,żejeśliwielomian
w
(
x
)
2
Z
p
jestnierozkładalnynadciał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,
•
wykrywanieikorygowaniebłędówtwierdzeniechrakteryzującekodywykrywające
błędy o wadze
t
, twierdzenie charakteryzujące kody korygujące błędy po wadze
t
,
•
kontrolnamacierzparzystości,macierzgenerującakodliniowy,standardowapostać
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
KrystynaZiętak
4
[ Pobierz całość w formacie PDF ]