Matematyka dyskretna
Informacje ogólne
Kod przedmiotu: | 0800-MDYS |
Kod Erasmus / ISCED: |
(brak danych)
/
(0541) Matematyka
|
Nazwa przedmiotu: | Matematyka dyskretna |
Jednostka: | Wydział Fizyki, Astronomii i Informatyki Stosowanej |
Grupy: | |
Punkty ECTS i inne: |
4.00
|
Język prowadzenia: | polski |
Wymagania wstępne: | Teoria relacji - relacje równoważności i porządku Arytmetyka liczb całkowitych Faktoryzacja wielomianów metoda indukcji matematycznej |
Rodzaj przedmiotu: | przedmiot obowiązkowy |
Efekty uczenia się - wiedza: | Podstawy teorii liczb i obliczeniowej teorii liczb Minimalne podstawy teorii grup, ciał i pierścieni Podstawy teorii kodów liniowych Krzywe eliptyczne nad ciałami $mathbb{Z}_n$ Podstawy teorii grafów Podstawy kryptografii z kluczem publicznym i podpisu elektronicznego |
Efekty uczenia się - umiejętności: | Umiejętność wykonywania obliczeń w ciałach skończonych Umiejętność implementacji algorytmów teorii liczb Umiejętność implementacji algorytmów kryptograficznych Wzrost umiejętności dowodzenia twierdzeń matematyki dyskretnej |
Efekty uczenia się - kompetencje społeczne: | Brak |
Metody dydaktyczne: | Wykład z elementami programowania |
Metody dydaktyczne podające: | - wykład informacyjny (konwencjonalny) |
Metody dydaktyczne poszukujące: | - ćwiczeniowa |
Skrócony opis: |
Dzielenie całkowitoliczbowe i relacja podzielności Algorytm Euklidesa i rozszerzony algorytm Euklidesa Liczby pierwsze, złożone i wzglednie pierwsze Rozkład na czynniki pierwsze i zasadnicze twierdzenie arytmetyki Gęstość liczb pierwszych Sito Eratostenesa Relacja przystawania, pierścienie reszt liczb całkowitych, elementy odwracalne Pierścienie wielomianów i pierścienie reszt wielomianów, konstrukcja ciał skończonych Kongruencje liniowe, chińskie twierdzenie o resztach Kody korygujące błędy, kodowanie nadmiarowe, kody cykliczne, kody RS Podstawowe pojęcia teorii grup Działanie grupy na zbiorze, działanie podgrupy w grupie, tw. Lagrange'a Klasyfikacja grup skończonych, tw. Sylowa i Cayleya Grupa multiplikatywna pierścienia, logarytm dyskretny Algorytmy faktoryzacji liczb całkowitych Testy pierwszości Algorytmy wyznaczania logarytmu dyskretnego. Kryptosystemy El-Gammal i RSA El-Gammal na krzywych eliptycznych Teoria grafów, drzewa, problemy Eulera i Hamiltona |
Pełny opis: |
Dzielenie całkowitoliczbowe, relacja podzielności Algorytm Euklidesa i poszukiwania wspólnego dzielnika liczb całkowitych, dowód jego poprawności i oszacowanie złożoności czasowej Rozszerzony algorytm Euklidesa Liczby pierwsze, złożone i wzglednie pierwsze Rozkład na czynniki pierwsze i zasadnicze twierdzenie arytmetyki Gęstość liczb pierwszych Sito Eratostenesa Relacja przystawania, pierścienie reszt liczb całkowitych Funkcja Eulera, małe twierdzenie Fermata Pierścienie wielomianów i pierścienie reszt wielomianów, konstrukcja ciał skończonych Kongruencje liniowe, chińskie twierdzenie o resztach Kody korygujące błędy, kodowanie nadmiarowe, odległość Hamminga Ograniczenie Hamminga i Singletona Kody cykliczne Kody Reeda-Solomona Grupy, podgrupy, homomorfizmy grup, jądro i obraz Działanie grupy na zbiorze, orbity i stabilizatory Warstwy, dzielnik normalny, grupa ilorazowa, twierdzenie Lagrange'a Klasyfikacja grup skończonych, twierdzenie Sylowa Twierdzenie Cayleya Grupa multiplikatywna pierścienia, logarytm dyskretny Algorytm Fermata, metoda p-1 Pollarda, metoda szybkiego potęgowania, metoda $rho$ Pollarda Test Leibnitza, test Millera-Rabina, liczby pseudopierwsze i silnie pseudopierwsze, Test Lucasa Metoda Gaussa znajdowania rzędu elementu Metody wyznaczania logarytmu dyskretnego - Shanksa, $rho$ Pollarda, Pohlinga-Hellmana Kryptosystem El-Gammal - szyfrowanie i podpis Kryptosystem RSA - szyfrowanie i podpis Przestrzeń rzutowa, krzywe eliptyczne bez samoprzecięć i ich struktura grupowa. Twierdzenie Hassego Kryptosystem El-Gammal na krzywej eliptycznej Graf prosty i skierowany, izomorfizm grafów i grupa automorfizmów grafu Drzewa Problem Eulera i twierdzenie Eulera, twierdzenie Fleury'ego Grafy Hamiltonowskie, twierdzenie Ore |
Literatura: |
Kenneth A. Ross, Charles R. B. Wright Matematyka Dyskretna PWN 2005 J. Jaworski, Z. Palka, J. Szymański Matematyka Dyskretna dla Informatyków A. Szepietowski Matematyka Dyskretna S. G. Krantz Discrete Mathematics Demystified Kenneth A. Rosen Handbook of discrete and combinatorial mathematics Władysław Narkiewicz Teoria Liczb PWN 2003 Jerzy Rutkowski Algebra abstrakcyjna w zadaniach PWN 2006 A. I. Kostrykin Wstęp do algebry PWN 2005 A. Chrzęszczyk Algorytmy teorii liczb i kryptografii w przykładach Wydawnictwo BTC 2010 N. Koblitz Wykład z teorii liczb i kryptografii WNT Warszawa 2006 N. Koblitz Algebraiczne aspekty kryptografii WNT Warszawa 2000 R.J. Wilson Wprowadzenie do teorii grafów |
Metody i kryteria oceniania: |
Egzamin, 8 pytań, lista pytań upubliczniona przed egzaminem na stronie prowadzącego |
Zajęcia w cyklu "Semestr letni 2021/22" (zakończony)
Okres: | 2022-02-21 - 2022-09-30 |
Przejdź do planu
PN WYK
WT ŚR CW
CZ CW
CW
PT |
Typ zajęć: |
Ćwiczenia, 20 godzin
Wykład, 20 godzin
|
|
Koordynatorzy: | Gniewomir Sarbicki | |
Prowadzący grup: | Miłosz Michalski, Jakub Rydzewski, Gniewomir Sarbicki | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Ćwiczenia - Zaliczenie na ocenę Wykład - Egzamin |
Zajęcia w cyklu "Semestr letni 2022/23" (zakończony)
Okres: | 2023-02-20 - 2023-09-30 |
Przejdź do planu
PN WT ŚR CW
CW
CZ WYK
PT |
Typ zajęć: |
Ćwiczenia, 20 godzin
Wykład, 20 godzin
|
|
Koordynatorzy: | Gniewomir Sarbicki | |
Prowadzący grup: | Miłosz Michalski, Gniewomir Sarbicki | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Ćwiczenia - Zaliczenie na ocenę Wykład - Egzamin |
Zajęcia w cyklu "Semestr letni 2023/24" (w trakcie)
Okres: | 2024-02-20 - 2024-09-30 |
Przejdź do planu
PN WYK
WT ŚR CW
CW
CZ CW
PT |
Typ zajęć: |
Ćwiczenia, 20 godzin
Wykład, 20 godzin
|
|
Koordynatorzy: | Gniewomir Sarbicki | |
Prowadzący grup: | Michał Lemańczyk, Miłosz Michalski, Gniewomir Sarbicki | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Ćwiczenia - Zaliczenie na ocenę Wykład - Egzamin |
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.