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

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 2017/18" (zakończony)

Okres: 2018-02-26 - 2018-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 20 godzin więcej informacji
Wykład, 20 godzin więcej informacji
Koordynatorzy: Gniewomir Sarbicki
Prowadzący grup: Grzegorz Pestka, 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 2018/19" (zakończony)

Okres: 2019-02-25 - 2019-09-30
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 20 godzin więcej informacji
Wykład, 20 godzin więcej informacji
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 2019/20" (zakończony)

Okres: 2020-02-29 - 2020-09-20
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 20 godzin więcej informacji
Wykład, 20 godzin więcej informacji
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 2020/21" (w trakcie)

Okres: 2021-02-22 - 2021-09-20
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 20 godzin więcej informacji
Wykład, 20 godzin więcej informacji
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
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.