Cel kształcenia i wykaz literatury

Główny cel kształcenia: dostarczyć studentom zaawansowanych pojęć i twierdzeń matematycznych z zakresu teorii grup i teorii liczb, i pokazać ich duże znaczenie w Informatyce

Ogólne informacje o zajęciach: Tematyka tego modułu kształcenia została podzielona na dwie odrębne, ale niezupełnie niezależne, części. Pierwsza część ma na celu rozszerzenie i pogłębienie wiedzy na temat struktur algebraicznych takich jak grupy permutacji, a następnie ich uogólnienie i rozszerzenie na pierścień i ciało. W drugiej części wykładów zostanie przedstawiona teoria liczb całkowitych, która stanowi podstawowe narzędzie projektowania systemów komputerowych oraz zapewnienia bezpieczeństwa komputerów i sieci komputerowych. W ramach tego modułu zostaną również przedstawione wybrane algorytmy związane z teorią liczb.

Materiały dydaktyczne: http://www.pei.prz.edu.pl/dydaktyka.html po zalogowaniu

Inne: http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1 i 2

Wykaz literatury, wymaganej do zaliczenia zajęć

Literatura wykorzystywana podczas zajęć wykładowych

1	Ross K., Wright C.	Matematyka dyskretna	Wydawnictwo PWN, Warszawa.	2012
2	Song Y. Yan	Teoria liczb w informatyce	Wydawnictwo naukowe PWN, Warszawa.	2006
3	Marek Libura, Jarosław Sikorski	Wykłady z matematyki dyskretnej, Cz I.: Kombinatoryka	Zakład Poligraficzny Jerzy Kosiński, Warszawa.	2003

Literatura wykorzystywana podczas zajęć ćwiczeniowych/laboratoryjnych/innych

1	Antoni Szczepański	Instrukcja do ćwiczenia z teorii grup permutacji i instrukcja do ćwiczenia z teorii liczb.	.	2020
2	Antoni Szczepański	Biblioteka kombinatoryczno-grafowa procedur i funkcji dla programu Maxima.	.	2020
3	Antoni Szczepański	Biblioteka teorio-liczbowa procedur i funkcji dla programu Maxima.	.	2020

Literatura do samodzielnego studiowania

1

Sysło M.

Algorytmy

WSiP, Warszawa.

1997

Wymagania wstępne w kategorii wiedzy/umiejętności/kompetencji społecznych

Wymagania formalne: rejestracja na 1. semestr studiów magisterskich

Wymagania wstępne w kategorii Wiedzy: ma podstawową wiedzę na temat struktur danych, programowania komputerów i komputerowych technik obliczeniowych

Wymagania wstępne w kategorii Umiejętności: ma dobrze rozwinięty zmysł matematyczny, potrafi myśleć abstrakcyjnie, potrafi wykonywać zadania określone w sposób algorytmiczny

Wymagania wstępne w kategorii Kompetencji społecznych: gotowość do systematycznej pracy, wytrwałość w rozwiązywaniu trudnych zadań, umiejętność pracy w małym zespole

Efekty kształcenia dla zajęć

MEK	Student, który zaliczył zajęcia	Formy zajęć/metody dydaktyczne prowadzące do osiągnięcia danego efektu kształcenia	Metody weryfikacji każdego z wymienionych efektów kształcenia	Związki z KEK	Związki z PRK
01	zna różne właściwości permutacji i potrafi wykonywać obliczenia z nimi związane	wykład, laboratorium, ćwiczenia rachunkowe	sprawdzian pisemny, egzamin cz. pisemna	K_W01++ K_U05++	P7S_UW P7S_WG
02	potrafi stosować teorię grup permutacji do zliczania istotnie różnych konfiguracji (np. kolorowań)	wykład, laboratorium, ćwiczenia rachunkowe	sprawdzian pisemny, egzamin cz. pisemna	K_W01++ K_U05++	P7S_UW P7S_WG
03	zna podstawowe pojęcia i twierdzenia teorii liczb, i potrafi je praktycznie stosować	wykład, laboratorium, ćwiczenia rachunkowe	sprawdzian pisemny, egzamin cz. pisemna	K_W01++ K_U05++	P7S_UW P7S_WG
04	potrafi rozwiązywać liniowe równania diofantyczne oraz kongruencje liniowe	wykład, laboratorium, ćwiczenia rachunkowe	sprawdzian pisemny, egzamin cz. pisemna	K_W01++ K_U05++	P7S_UW P7S_WG
05	zna algorytmy potęgowania modularnego i potrafi je praktycznie stosować	wykład, laboratorium, ćwiczenia rachunkowe	sprawdzian pisemny, egzamin cz. pisemna	K_W01++ K_U05++	P7S_UW P7S_WG

Uwaga: W zależności od sytuacji epidemicznej, jeżeli nie będzie możliwości weryfikacji osiągniętych efektów uczenia się określonych w programie studiów w sposób stacjonarny w szczególności zaliczenia i egzaminy kończące określone zajęcia będą mogły się odbywać przy użyciu środków komunikacji elektronicznej (w sposób zdalny).

Treści kształcenia dla zajęć

Sem.	TK	Treści kształcenia	Realizowane na	MEK
1	TK01	Definicja permutacji. Permutacja odwrotna. Zapis cyklowy permutacji (cykle rozłączne, punkty stałe). Składanie permutacji w zapisie cyklowym. Grupa permutacji. Grupa symetryczna Sn. Tabela Cayleya mnożenia grupy. Podgrupa. Grupa generowana przez pojedynczą permutację. Potęgowanie permutacji. Rząd permutacji. Działania grup na zbiorach. Grupa automorfizmów grafu i grupa indukowana w zbiorze krawędzi. Orbity działania grupy. Wyznaczanie liczby orbit.	W01, W02, C01, L01	MEK01 MEK02
1	TK02	Grupa obrotów sześcianu. Grupa izometrii płaskich foremnych figur geometrycznych (grupa dwuścianu). Twierdzenie Polyi oraz Frobeniusa-Burnside'a. Zastosowanie teorii grup do zliczania kolorowań różnych obiektów kombinatorycznych: wierzchołków grafu, krawędzi grafu, podobszarów figury płaskiej. Zliczanie istotnie różnych kolorowań wierzchołków, krawędzi i ścian figur płaskich oraz brył. Wielomian cyklowy grupy permutacji. Zliczanie kolorowań co najwyżej k kolorami i dokładnie k kolorami. Kolorowanie określoną liczbą i rodzajem kolorów. Zliczanie grafów skierowanych i nieskierowanych. Zliczanie kolorowań naszyjników.	W03, W04, W05, C02, L02	MEK02
1	TK03	Podstawowe oznaczenia stosowane w teorii liczb. Wiadomości wstępne z algebry. Rozszerzenie pojęcia grupy: grupa multiplikatywna i addytywna. Inne struktury algebraiczne: pierścień i ciało. Teoria podzielności liczb całkowitych. Twierdzenie o dzieleniu z resztą. Liczby pierwsze i złożone. Sito Eratostenesa. Zasadnicze twierdzenie arytmetyki - rozkład kanoniczny liczby naturalnej. NWD i NWW oraz tw. z tym związane. Liczby względnie pierwsze. Liczby Mersenne'a i Fermata. Zwyczajny i rozszerzony algorytm Euklidesa. Liniowe równania diofantyczne i twierdzenie o jego rozwiązaniach.	W06, W07, C03, L03	MEK03 MEK04
1	TK04	Funkcje arytmetyczne (Eulera, Carmichaela, Mobiusa). Teoria kongruencji. Przystawanie modulo. Pełny i zredukowany układ reszt modulo. Arytmetyka modularna. Mulitplikatywna odwrotność. Kongruencje liniowe i twierdzenie o ich rozwiązywaniu. Małe twierdzenie Fermata. Twierdzenie Wilsona. Zastosowanie twierdzenia Eulera do wyznaczania odwrotności modulo i rozwiązywania kongruencji liniowych. Chińskie twierdzenie o resztach. Szybkie potęgowanie modularne. Zastosowanie teorii liczb w kryptografii - kryptosystem RSA. Deterministyczne i probabilistyczne testy pierwszości liczb naturalnych.	W08, W09, W10, C04, C05, L04, L05	MEK05

Nakład pracy studenta

Forma zajęć	Praca przed zajęciami	Udział w zajęciach	Praca po zajęciach
Wykład (sem. 1)		Godziny kontaktowe: 20.00 godz./sem.	Uzupełnienie/studiowanie notatek: 10.00 godz./sem. Studiowanie zalecanej literatury: 20.00 godz./sem.
Laboratorium (sem. 1)	Przygotowanie do laboratorium: 5.00 godz./sem. Przygotowanie do kolokwium: 5.00 godz./sem. Inne: 5.00 godz./sem.	Godziny kontaktowe: 10.00 godz./sem.	Dokończenia/wykonanie sprawozdania: 30.00 godz./sem. Inne: 10.00 godz./sem.
Konsultacje (sem. 1)		Udział w konsultacjach: 1.00 godz./sem.
Egzamin (sem. 1)	Przygotowanie do egzaminu: 15.00 godz./sem.	Egzamin pisemny: 2.00 godz./sem. Inne: 2.00 godz./sem.

Sposób wystawiania ocen składowych zajęć i oceny końcowej

Forma zajęć	Sposób wystawiania oceny podsumowującej
Wykład	na podstawie egzaminu pisemnego
Laboratorium	w oparciu o wyniki kolokwiów oraz za sprawozdania
Ocena końcowa	zależy od wyników egzaminu pisemnego, obecności na wykładach, oceny końcowej z ćwiczeń oraz oceny końcowej z laboratoriów; warunkiem zaliczenia przedmiotu jest zaliczenie każdej jego formy, a więc ćwiczeń, laboratoriów i egzaminu na ocenę minimum 3,0.

Przykładowe zadania

Wymagane podczas egzaminu/zaliczenia
(-)

Realizowane podczas zajęć ćwiczeniowych/laboratoryjnych/projektowych
(-)

Inne
(-)

Czy podczas egzaminu/zaliczenia student ma możliwość korzystania z materiałów pomocniczych : tak

Dostępne materiały : Można posiadać notatki z wykładów, ćwiczeń tablicowych lub laboratoriów komputerowych, książki w wersji papierowej. Nie można korzystać ze smartfona ani innego komputera z dostępem do Internetu.

Treści zajęć powiazane są z prowadzonymi badaniami naukowymi: nie