Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowaniaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Podstawy algebry, wybrane zagadnienia algorytmiczne

Informacje ogólne

Kod przedmiotu: 1000-I1PAL Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji
Nazwa przedmiotu: Podstawy algebry, wybrane zagadnienia algorytmiczne
Jednostka: Wydział Matematyki i Informatyki
Grupy: Inf., I st., stacjonarne, 2 rok, przedmioty do wyboru
Inf., I st., stacjonarne, 3 rok, przedmioty do wyboru
Inf., II st, stacjonarne, przedmioty do wyboru
Mat. I st., stacjonarne, przedmioty do wyboru (podstawowe)
Wszystkie przedmioty z WMiI
Punkty ECTS i inne: 6.00
Język prowadzenia: polski
Wymagania wstępne:

Student powinien posiadać wiedzę z zakresu przedmiotu "Algebra liniowa z geometrią analityczną" (kursy I1ALAz i I1ALAl lub ich odpowiedniki na studiach matematycznych).

Rodzaj przedmiotu:

przedmiot fakultatywny

Całkowity nakład pracy studenta:

30 godz. wykład

30 godz. ćwiczenia

50 godz. praca własna - bieżące przygotowanie do zajęć, studiowanie literatury

35 godz. praca własna - przygotowanie do egzaminu.

5 godz. zaliczenie ćwiczeń, egzamin


RAZEM: 150 godz


6 pkt. ECTS

Efekty uczenia się - wiedza:

Po ukończeniu kursu 1000-I1PAL student osiąga następujące efekty (kody odnoszą się do efektów dla studiów 1 stopnia na kierunku informatyka - studia licencjackie i inżynierskie, s1):


W1 - definiuje podstawowe wybrane pojęcia algebry m.in. takie jak grupa, grupa cykliczna i abelowa, dzielnik normalny, grupa ilorazowa, działanie grupy na zbiorze, prezentacja grupy, suma prosta podgrup grupy abelowej, pierścień wielomianów, element odwracalny, rozkład elementu na iloczyn nierozkładalnych, ideał w pierścieniu wielomianów (K_W01, s1),


W2 - formułuje najważniejsze wybrane twierdzenia algebry, ilustruje je odpowiednimi przykładami (K_W01, s1),


W3 - dostrzega analogie i związki pomiędzy różnymi pojęciami oraz zagadnieniami algebraicznymi, wyrażające się w podobieństwie stosowanych pomysłów i algorytmicznych metod rozwiązań (K_W01 , s1).



Na kierunku matematyka (s1) efekty powiązane są z: K_W05.


Efekty uczenia się - umiejętności:

Po ukończeniu kursu 1000-I1PAL student osiąga następujące efekty (kody odnoszą się do efektów dla studiów 1 stopnia na kierunku informatyka - studia licencjackie i inżynierskie, s1):



U1 - wykonuje działania w grupach ilorazowych, w poszczególnych przypadkach wyznacza strukturę podobiektów i zadaje homomorfizmy z ilorazów (K_U01, s1),


U2 - reprezentuje najprostsze grupy w terminach grup permutacji oraz za pomocą generatorów i relacji, w przypadku skończenie generowanych grup abelowych (K_U01, s1),


U3 - stosuje algorytm sprowadzania macierzy całkowitoliczbowych do postaci diagonalnej do rozwiązywania układów równań liniowych nad liczbami całkowitymi i rozkładania skończonych grup abelowych na sumę prostą podgrup nierozkładalnych (K_U01, s1),


U4 - wyznacza postać Jordana macierzy endomorfizmu liniowego i macierzy kwadratowej w prostych możliwych do opanowania przypadkach (K_U01, s1),


U5 - znajduje największy wspólny dzielnik przy użyciu algorytmu Euklidesa oraz przeprowadza efektywne obliczenia w pierścieniu wielomianów k[x] (K_U01, s1),


U6 - znajduje postać Smitha macierzy całkowitoliczbowych i wielomianowych oraz stosuje je do rozstrzygania relacji równoważności macierzy i relacji podobieństwa macierzy kwadratowych (K_U01, s1).



Na kierunku matematyka (s1) efekty powiązane są z: KU_01 oraz KU_14 - K_U18.


Efekty uczenia się - kompetencje społeczne:

Po ukończeniu kursu 1000-I1PAL student osiąga następujące efekty (kody odnoszą się do efektów dla studiów 1 stopnia na kierunku informatyka - studia licencjackie i inżynierskie, s1):


K1 - sumienność i dokładność: jest nastawiony na jak najlepsze wykonanie zadania; dba o szczegół; jest systematyczny (K_K04, s1),


K2 - komunikatywność: skutecznie przekazuje innym swoje myśli w zrozumiały sposób; właściwie posługuje się terminologią fachową; potrafi nawiązać kontakt w obrębie swojej dziedziny i z osobą reprezentującą inną dziedzinę (K_K02, s1).



Na kierunku matematyka (s1) efekty powiązane są z: K_K04 oraz K_K03.

Metody dydaktyczne podające:

- wykład informacyjny (konwencjonalny)

Metody dydaktyczne poszukujące:

- ćwiczeniowa
- referatu

Skrócony opis:

Celem zajęć jest zaznajomienie uczestników z wybranymi podstawowymi pojęciami algebry oraz problemami ich dotyczącymi, ze szczególnym uwzględnieniem aspektów algorytmicznych w ich rozwiązaniach i przygotowania do wykorzystywania systemów komputerowego wspomagania algebry.

Przedmiot przeznaczony jest głównie dla studentów informatyki. Mogą w nim również uczestniczyć studenci matematyki.

Pełny opis:

1. Grupy - podstawowe definicje:

grupa, grupa abelowa, rząd grupy, podgrupa, operacje na podgrupach, grupa generowana przez zbiór, grupy cykliczne, warstwy względem podgrupy, indeks podgrupy, twierdzenie Lagrange’a, homomorfizmy grup, obraz i jądro.

2. Grupy ilorazowe:

podgrupa normalna, domknięcie normalne, normalizator, warstwy względem podgrupy normalnej, grupa ilorazowa, podgrupy grupy ilorazowej, zadawanie homomorfizmów z grupy ilorazowej, twierdzenia o izomorfizmie, opis grup cyklicznych.

3. Działanie grup na zbiorach i zastosowania:

grupy przekształceń, grupy permutacji, twierdzenie Cayley’a - realizacja grupy abstrakcyjnej, ”komputeryzowalność” teorii grup skończonych, działanie grupy na zbiorze, orbita i stabilizator, przykłady, algorytmy dla grup permutacji, zastosowania techniki działań do opisu własności centrum grupy, w szczególności dla p-grupy.

4. Rozkład skończenie generowanej grupy abelowej:

produkt grup, produkt a suma prosta podgrup grupy abelowej, rozkład skończonej grupy cyklicznej na sumę prosta podgrup typu Z_{p^n}, grupy Z^n i homomorfizmy pomiędzy nimi, prezentacja skończenie generowanej grupy abelowej poprzez macierz, algorytm diagonalizacji macierzy całkowitoliczbowej, twierdzenie strukturalne o rozkładzie skończenie generowanej grupy abelowej na sumę prostą podgrup nierozkładalnych typu Z i Z_{p^n} wraz z algorytmem rozkładu, przypadek grup skończonych, przykłady i zastosowania.

5. Elementy algebry liniowej nad Z:

rozwiązywania układów równań liniowych nad Z przy pomocy algorytmu diagonalizacji macierzy całkowitoliczbowej, znajdowanie jądra i obrazu homomorfizmów pomiędzy grupami Z^n, wyznaczanie klas abstrakcji relacji równoważności dla całkowitoliczbowych macierzy - postać Smitha i niezmienniki elementarne stowarzyszone z macierzą.

6. Postać normalna macierzy kwadratowych nad ciałem, podobieństwo macierzy:

wartości i wektory własne endomorfizmu liniowego, macierz charakterystyczna i wielomian charakterystyczny macierzy kwadratowej, nilpotentne i odwracalne klatki Jordana, postać normalna endomorfizmu przestrzeni linowej - twierdzenie Jordana, relacja podobieństwa macierzy kwadratowych i jej rozstrzyganie - kwestia algorytmiczności znajdowanie postaci normalnej.

7. Macierze nad pierścieniem wielomianów jednej zmiennej nad ciałem:

podstawowe informacje o pierścieniu wielomianów jednej zmiennej nad ciałem, znaczenie algorytmu Euklidesa, macierze wielomianowe i relacja równoważności pomiędzy nimi, rozstrzyganie równoważność macierzy przy pomocy algorytmu wyznaczania ich postaci Smitha oraz poprzez niezmienniki elementarne, podobieństwo macierzy kwadratowych nad ciałem a równoważność ich macierzy charakterystycznych.

8. Informacja o modułach Kroneckera.

Literatura:

Literatura podstawowa

1. M.A. Armstrong, Groups and symmetries.

2. A. Białynicki-Birula, Zarys algebry PWN, Warszawa 1987.

3. M. Mignotte, Mathematics for computer algebra.

Literatura uzupełniająca

4. J. Browkin, Teoria ciał, PWN Warszawa 1977.

5. F. R. Gantmacher, Matrix Theory, Chelsea, New York, 1959.

6. M. Gelfand, Wykłady z algebry liniowej, PWN, Warszawa (wiele wydań).

7. T. Kaczorek, Zastosowanie macierzy wielomianowych i wymiernych w teorii układów dynamicznych, Wydawnictwo PB, 2004.

Zbiory zadań:

1. M. Bryński, J. Jurkiewicz, Zbiór zadań z algebry, PWN 1978.

2. J. Rutkowski, Algebra abstrakcyjna w zadaniach, PWN, Warszawa, 2000.

3 K. Szymiczek, Zbiór zadań z teorii grup, PWN, Warszawa, 1989.

4. Zbiór zadań z algebry, pod red. A.I. Kostrykina, PWN, Warszawa, 2005.

Metody i kryteria oceniania:

Zaliczenie wykładu - egzamin pisemny. Egzamin składa się z pytań teoretycznych i zadań. Studenta obowiązuje materiał prezentowany w czasie wykładu; weryfikacja efektów: W1,W2, W3, K1, K2.

Zaliczenie ćwiczeń na ocenę - odbywa się na podstawie aktywności, udziału w zajęciach i prac domowych oraz referatów; weryfikacja efektów: U1 - U6, K1, K2.

Zajęcia w cyklu "Semestr zimowy 2017/18" (zakończony)

Okres: 2017-10-01 - 2018-02-25
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Piotr Dowbor
Prowadzący grup: Piotr Dowbor
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin
Skrócony opis:

Celem zajęć jest zaznajomienie uczestników z podstawowymi pojęciami algebry oraz problemami ich dotyczącymi, ze szczególnym uwzględnieniem aspektów algorytmicznych w ich rozwiązaniach i przygotowania do wykorzystywania systemów komputerowego wspomagania algebry.

Pełny opis:

I. GRUPY.

1. Podstawowe definicje:

grupa, grupa abelowa, rząd grupy, podgrupa, operacje na podgrupach, grupa generowana przez zbiór, grupy cykliczne, warstwy względem podgrupy, indeks podgrupy, twierdzenie Lagrange’a, homomorfizmy grup, obraz i jądro.

2. Grupy ilorazowe:

podgrupa normalna, domknięcie normalne, normalizator, warstwy względem podgrupy normalnej, grupa ilorazowa, podgrupy grupy ilorazowej, zadawanie homomorfizmów z grupy ilorazowej, twierdzenia o izomorfizmie, opis grup cyklicznych.

3. Działanie grup na zbiorach i zastosowania:

grupy przekształceń, grupy permutacji, twierdzenie Cayley’a - realizacja grupy abstrakcyjnej, ”komputeryzowalność” teorii grup skończonych, działanie grupy na zbiorze, orbita i stabilizator, przykłady, algorytmy dla grup permutacji.

4. Prezentacje grup za pomocą generatorów i relacji:

słowa w alfabecie, relacja skracania, słowa nieskracalne, grupa wolna zadana przez zbiór (alfabet), zadawanie homomorfizmu z grupy wolnej, grupa jako obraz homomorficzny grupy wolnej, relacje w grupie wolnej a relacje pomiędzy generatorami w grupie, relacje generujące, prezentacje grupy, grupa zadana przez generatory i relacje, przykłady i zastosowania, grupy skończenie przedstawialne jako obiekt kombinatoryczny, algorytmiczne podejście do przedstawienia grupy skończonej, prezentacja skończenie generowanej grupy abelowej.

5. Rozkład skończenie generowanej grupy abelowej i elementy algebry liniowej nad Z:

produkt grup, produkt a suma prosta podgrup grupy abelowej, rozkład skończonej grupy cyklicznej na sumę prosta podgrup typu Z_{p^n}, grupy abelowe postaci Z_n, zadawanie skończenie generowanej grupy abelowej przez macierz, algorytm diagonalizacji macierzy całkowitoliczbowej, zastosowanie do rozwiązywania układów równań liniowych nad Z, twierdzenie strukturalne o rozkładzie skończenie generowanej grupy abelowej na sume prosta podgrup nierozkładalnych typu Z i Z_{p^n} wraz z algorytmem rozkładu, przypadek grup skończonych, przykłady i zastosowania.

II. PIERŚCIENIE.

6. Podstawowe definicje i fakty:

pierścień przemienny, podpierścień, elementy odwracalne, dzielniki zera i elementy nierozkładalne, grupa addytywna i multyplikatywna pierścienia, dziedzina całkowitości, homomorfizmy pierścieni, obraz i jądro homomorfizmu, ideał w pierścieniu, pierścień ilorazowy, podpierścienie i ideały w pierścieniu ilorazowym, zadawanie homomorfizmu z pierścienia ilorazowego, twierdzenia o izomorfizmie dla pierścieni.

7. Ideały:

operacje na ideałach, ideał generowany przez zbiór elementów, ideał główny, pierścień ideałów głównych, ideały pierwsze i maksymalne, charakteryzacja w terminach pierścienia ilorazowego, elementy nierozkładalne a opis ideałów pierwszych i maksymalnych w dziedzinach ideałów głównych, ”Chinskie twierdzenie o resztach” - algorytm realizujący tezę, konsekwencje dla rozkładu grup multyplikatywnych Z^n, relacja podzielności i stowarzyszenia w dziedzinach całkowitości, podzielność a ideały, największy wspólny dzielnik, interpretacja w klasycznych przykładach.

8. Pierścienie ideałów głównych:

definicja pierścienia wielomianów jednej zmiennej o współczynnikach w ustalonym pierścieniu, stopień wielomianu i jego własności, algorytm dzielenia dla wielomianów, pierwiastki wielomianu, twierdzenie Bezout i jego zastosowania, wielomiany nierozkładalne nad C i nad R, cykliczność skończonych podgrup grupy multyplikatywnej ciała, pierścienie Euklidesa - definicja i klasyczne przykłady, ideały (maksymalne i pierwsze) w pierścieniu Euklidesa, algorytm na szukanie największego wspólnego dzielnika, pierścienie ilorazowe pierścieni Euklidesa - struktura i algorytm obliczania elementów odwrotnych.

9. Pierścienie wielomianów wielu zmiennych:

definicja bezpośrednia, równoważność z definicja indukcyjną, stopień wielomianu, różne porządki na jednomianach, pierścień wielomianów jako przykład dziedziny całkowitości niebędącej pierścieniem ideałów głównych, funkcje wielomianowe a wielomiany - przypadek ciała nieskończonego i skończonego (na przykładzie Z_p).

10. Rozkłady elementów pierścienia na iloczyn czynników nierozkładalnych:

definicja pierścienia z jednoznacznością rozkładu i klasyczne przykłady, twierdzenie o dziedzinach ideałów głównych, twierdzenie o pierścieniu wielomianów nad pierścieniem z jednoznacznością rozkładu, wnioski dla pierścieni wielomianów wielu zmiennych o współczynnikach w ciałach i pierścieniu liczb całkowitych, wybrane algorytmy rozkładu wielomianu na czynniki nierozkładalne w pierścieniach wielomianów jednej zmiennej (m.in. algorytmy Kroneckera, Berlekampa).

Literatura:

Literatura podstawowa

1. M.A. Armstrong, Groups and symmetries.

2. A. Białynicki-Birula, Zarys algebry PWN, Warszawa 1987.

3. M. Mignotte, Mathematics for computer algebra.

Literatura uzupełniąjaca

4. J. Browkin, Teoria ciał, PWN Warszawa 1977.

5. M. Gelfand, Wykłady z algebry liniowej, PWN, Warszawa (wiele wydań).

6. S. Lang, Algebra, PWN, Warszawa 1973.

Zbiory zadań:

1. M. Bryński, J. Jurkiewicz, Zbiór zadań z algebry, PWN 1978.

2. J. Rutkowski, Algebra abstrakcyjna w zadaniach, PWN, Warszawa, 2000.

3 K. Szymiczek, Zbiór zadań z teorii grup, PWN, Warszawa, 1989.

4. Zbiór zadań z algebry, pod red. A.I. Kostrykina, PWN, Warszawa, 2005.

Zajęcia w cyklu "Semestr zimowy 2018/19" (zakończony)

Okres: 2018-10-01 - 2019-02-24
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Piotr Dowbor
Prowadzący grup: Piotr Dowbor
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr zimowy 2019/20" (zakończony)

Okres: 2019-10-01 - 2020-02-28
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Piotr Dowbor
Prowadzący grup: Piotr Dowbor
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr zimowy 2020/21" (zakończony)

Okres: 2020-10-01 - 2021-02-21
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Piotr Dowbor
Prowadzący grup: Piotr Dowbor
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin
Uwagi:

Wykład i ćwiczenia będą się odbywały zdalnie z wykorzystaniem platformy MS Teams.

Egzamin odbędzie się w sposób tradycyjny lub zdalny (platforma MOODLE) w zależności od sytuacji epidemicznej.

Zajęcia w cyklu "Semestr zimowy 2021/22" (w trakcie)

Okres: 2021-10-01 - 2022-02-20
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin, 30 miejsc więcej informacji
Wykład, 30 godzin, 30 miejsc więcej informacji
Koordynatorzy: Piotr Dowbor
Prowadzący grup: Piotr Dowbor
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Wykład - Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.