Metody numeryczne w kryptologii

stacjonarne

jednolite magisterskie

obowiązkowy

realizowane formy zajęć: W – wykład, C –- ćwiczenia audytoryjne, L – ćwiczenia laboratoryjne, P – ćwiczenia projektowe, S – seminarium;

rygor: x – egzamin, + – zaliczenie na ocenę, z – zaliczenie ogólne

Studia stacjonarne: W 20 /x; C 0 /-; L 24 /+; razem: 44 godziny, 5 punktów ECTS

Matematyka ze studiów pierwszego stopnia, jak w poniższym przykładzie.

Matematyka 1. / Student powinien znać: symbole i elementarne pojęcia logiki i teorii mnogości; funkcje elementarne; liczby rzeczywiste i zespolone; podstawowe pojęcia, określenia i twierdzenia algebry liniowej i geometrii analitycznej; rachunek wektorowy i macierzowy, przestrzenie wektorowe, układy liniowych równań algebraicznych i metody ich rozwiązywania; analityczne konstrukcje prostych i płaszczyzn; krzywe i powierzchnie drugiego stopnia.

Matematyka 2. / Student powinien znać: symbole, określenia, twierdzenia i przykłady dotyczące ciągów i szeregów liczbowych, rachunku różniczkowego i całkowego funkcji jednej zmiennej rzeczywistej oraz rachunku różniczkowego funkcji wielu zmiennych. Student powinien umieć obliczać granice ciągów i funkcji jednej zmiennej, znajdować pochodne i całki oznaczone i nieoznaczone oraz znajdować pochodne cząstkowe.

Analiza matematyczna. / Student powinien znać: symbole, określenia, twierdzenia i przykłady dotyczące rachunku różniczkowego i całkowego funkcji wielu zmiennych oraz równań różniczkowych zwyczajnych. Student powinien umieć obliczać całki wielokrotne i rozwiązywać proste równania różniczkowe zwyczajne.

semestr studiów / kierunek studiów / specjalność

dziewiąty semestr / kryptologia i cyberbezpieczeństwo / systemy kryptograficzne

dr hab. Marek Kojdecki

aktywność / obciążenie studenta w godzinach

studia stacjonarne

1. Udział w wykładach / 20

2. Udział w ćwiczeniach rachunkowych / 0

3. Udział w ćwiczeniach laboratoryjnych / 24

4. Udział w ćwiczeniach projektowych / 0

5. Udział w seminariach / 0

6. Samodzielne studiowanie tematyki wykładów / 48

7. Samodzielne przygotowanie do ćwiczeń / 0

8. Samodzielne przygotowanie do laboratoriów / 48

9. Realizacja projektu / 0

10. Samodzielne przygotowanie do seminarium / 0

11. Udział w konsultacjach / 6

12. Przygotowanie do egzaminu / 2

13. Przygotowanie do zaliczenia / 0

14. Udział w egzaminie / 2

Sumaryczne obciążenie pracą studenta: 150 godzin / 5 punktów ECTS

Zajęcia:

– z udziałem nauczycieli (1+2+3+4+5+11+14): 44 godziny / 1,5 punktu ECTS

– powiązane z działalnością naukową (1 do 10): 140 godzin / 5 punktów ECTS

– o charakterze praktycznym (2+3+4+7+8+9): 72 godzin / 2,5 punktów ECTS

Przedmiot służy do wykształcenia wiedzy i umiejętności potrzebnych do rozwiązywania układów liniowych równań algebraicznych i liniowych zadań najmniejszych kwadratów z oceną dokładności rozwiązań i z wykorzystaniem przekształceń macierzowych.

Wykład / metody dydaktyczne

Tematy kolejnych wykładów (po dwie godziny lekcyjne):

1. Podstawowe pojęcia analizy numerycznej. Wektory, macierze i normy.

2. Podstawowe pojęcia analizy numerycznej. Błędy zaokrągleń w obliczeniach komputerowych; arytmetyki zmiennoprzecinkowe; uwarunkowanie zadania obliczeniowego; algorytmy numerycznie poprawne; arytmetyki stałoprzecinkowe.

3. Bezpośrednie metody rozwiązywania układów liniowych równań algebraicznych. Uwarunkowanie zadania; algorytmy numerycznie poprawne; zadania źle uwarunkowane.

4. Bezpośrednie metody rozwiązywania układów liniowych równań algebraicznych. Metoda Gaussa z pełnym oraz z częściowym wyborem elementu głównego; metoda Cholesky'go-Banachiewicza; wpływ błędów zaokrągleń na wynik.

5. Bezpośrednie metody rozwiązywania układów liniowych równań algebraicznych. Faktoryzacja macierzy; metoda Gaussa; metoda Householdera, wpływ błędów zaokrągleń na wynik.

6. Liniowe zadanie najmniejszych kwadratów w postaci algebraicznej. Rozkład macierzy według wartości własnych; rozkład macierzy według wartości szczególnych.

7. Liniowe zadanie najmniejszych kwadratów w postaci algebraicznej. Postawienie zagadnienia; uogólniona macierz odwrotna i uogólnione rozwiązanie układu liniowych równań algebraicznych.

8. Liniowe zadanie najmniejszych kwadratów w postaci algebraicznej. Zadanie regularne; algorytm rozwiązywania z równaniem normalnym; uwarunkowanie zadania regularnego; algorytm z przekształceniem Householdera.

9. Liniowe zadanie najmniejszych kwadratów w postaci algebraicznej. Zadania nieregularne i źle uwarunkowane; regularyzacja.

10. Iteracyjne rozwiązywanie układów liniowych równań algebraicznych. Metody iteracji prostych; metody Gaussa-Seidela i Jacobiego; charakterystyki zbieżności.

/ wykład z możliwym wykorzystaniem technik audiowizualnych; podanie zadań do samodzielnego rozwiązania i tematów do studiowania

Ćwiczenia / metody dydaktyczne

Są włączone w ćwiczenia laboratoryjne

/ ćwiczenia rachunkowe ułatwiające opanowanie, zrozumienie i usystematyzowanie wiedzy wyniesionej z wykładów i własnych studiów studentów oraz nabycie umiejętności rachunkowych; podanie zadań do samodzielnego rozwiązania i tematów do studiowania; pisemna praca kontrolna

Laboratoria / metody dydaktyczne

Tematy kolejnych zajęć (po dwie godziny lekcyjne):

1. Normy wektorów i macierzy. Przestrzenie wektorowe i przekształcenia liniowe; wektory, macierze i normy; obliczenia za pomocą programów narzędziowych.

2. Arytmetyki zmiennoprzecinkowe. Błędy zaokrągleń w obliczeniach komputerowych; arytmetyki zmiennoprzecinkowe; uwarunkowanie zadania obliczeniowego; przykłady, w tym sumowanie szeregów potęgowych.

3. Rozwiązywanie układów liniowych równań algebraicznych. Metoda Gaussa z pełnym oraz z częściowym wyborem elementu głównego; wpływ błędów zaokrągleń na wynik.

4. Faktoryzacja trójkątno-trójkątna macierzy. Rozkład metodą Gaussa; rozkład Cholesky'go-Banachiewicza; zastosowania do układów liniowych równań algebraicznych.

5. Faktoryzacja ortogonalno-trójkątna macierzy. Rozkład Householdera; rozkład Givensa; zastosowania do równań macierzowych i do układów liniowych równań algebraicznych.

6. Rozkład macierzy według wartości własnych. Faktoryzacja macierzy według wartości własnych; potęgowanie macierzy, funkcje macierzowe; zastosowania do układów liniowych równań algebraicznych.

7. Formy kwadratowe. Postacie kanoniczne form kwadratowych; wykorzystanie wartości własnych; metoda Lagrange'a.

8. Rozkład macierzy według wartości szczególnych. Faktoryzacja macierzy według wartości szczególnych; regularne liniowe zadanie najmniejszych kwadratów; uogólniona macierz odwrotna; przykłady.

9. Liniowe zadanie najmniejszych kwadratów w postaci algebraicznej. Zadanie regularne; algorytm rozwiązywania z równaniem normalnym; uwarunkowanie zadania; wpływ błędów zaokrągleń na wynik.

10. Liniowe zadanie najmniejszych kwadratów w postaci algebraicznej. Zadanie nieregularne; regularyzacja, algorytm rozwiązywania z równaniem normalnym; wpływ błędów zaokrągleń na wynik.

11. Liniowe zadanie najmniejszych kwadratów w postaci algebraicznej. Zadanie regularne; algorytm z przekształceniem Householdera; zadania nieregularne i źle uwarunkowane; regularyzacja.

12. Iteracyjne rozwiązywanie układów liniowych równań algebraicznych. Metody Gaussa-Seidela i Jacobiego.

/ ćwiczenia laboratoryjne z wykorzystaniem programów uczących i programów narzędziowych (jak Matlab) i ćwiczeniami rachunkowymi, ułatwiające opanowanie, zrozumienie i usystematyzowanie wiedzy wyniesionej z wykładów i własnych studiów studentów oraz nabycie umiejętności rachunkowych; podanie zadań do samodzielnego rozwiązania i tematów do studiowania; pisemna praca kontrolna

podstawowa:

A. Kiełbasiński, H. Schwetlick: Numeryczna algebra liniowa; PWN, Warszawa, 1991.

A. Maćkiewicz : Algorytmy algebry liniowej. Metody bezpośrednie; Wydawnictwo Politechniki Poznańskiej, Poznań 2002.

M.A. Kojdecki: Elementy analizy numerycznej; WAT, Warszawa, 2011 (skrypt w postaci elektronicznej).

uzupełniająca:

G. H. Golub, C. F. Van Loan: Matrix Computations; The John Hopkins University Press, Baltimore and London, 1996.

A. Björck: Numerical Methods in Matrix Computations; Springer, 2015.

J. i M. Jankowscy: Przegląd metod i algorytmów numerycznych. Część 1; WNT, Warszawa, 1981.

M. Dryja, J. i M.Jankowscy: Przegląd metod i algorytmów numerycznych. Część 2; WNT, Warszawa, 1982.

A. Björck, G. Dahlquist: Metody numeryczne; PWN, Warszawa, 1983.

D. Kincaid, W. Cheney: Analiza numeryczna; WNT, Warszawa, 2006.

Z. Fortuna, B. Macukow, J. Wąsowski: Metody numeryczne; WNT, Warszawa, 1982.

symbol / efekt uczenia się / odniesienie do efektów kierunku

Student, który zaliczył przedmiot,

W01 – Zna i rozumie podstawowe metody numerycznego rozwiązywania układów liniowych równań algebraicznych i liniowego zadania najmniejszych kwadratów, także z wykorzystaniem metod faktoryzacji macierzy oraz metody faktoryzacji macierzy i pojęcie uogólnionej macierzy odwrotnej. / K_W02

W02 – Zna i rozumie podstawowe pojęcia analizy numerycznej w tym arytmetyki zmiennoprzecinkowej i arytmetyki stałoprzecinkowej; metodę wstecznej analizy błędów w obliczeniach komputerowych i jej zastosowania do oceny dokładności rozwiązań zadań numerycznej algebry liniowej. / K_W02

U01 –Umie wybrać i zastosować metodę numerycznego rozwiązywania układu liniowych równań algebraicznych oraz liniowego zadania najmniejszych kwadratów. / K_U03

U02 – Umie formułować i rozwiązywać proste problemy z wykorzystaniem układów liniowych równań algebraicznych, liniowego zadania najmniejszych kwadratów i faktoryzacji macierzy. / K_U03

U03 – Potrafi pozyskiwać informacje z literatury, baz danych i innych źródeł (także anglojęzycznych); potrafi interpretować uzyskane informacje i formułować wnioski. / K_U18

K01 – Rozumie potrzebę ciągłego dokształcania się i odświeżania wiedzy, w szczególności związanej ze złożoną strukturą matematyki. / K_K01

Przedmiot zaliczany jest na podstawie egzaminu

sprawdzającego wiedzę (W01, i W02) i umiejętności (U01, U02).

Egzamin przeprowadzany jest w formie pisemnej lub pisemnej i ustnej.

Warunkiem dopuszczenia do egzaminu jest zaliczenie ćwiczeń laboratoryjnych.

Ćwiczenia laboratoryjne zaliczane są na podstawie wyników prac kontrolnych przeprowadzanych pod bezpośrednią kontrolą podczas zajęć (U01, U02, W01, W02) lub w formie zadań do samodzielnego rozwiązania (U01, U02, U03) oraz na podstawie sprawozdań z wybranych ćwiczeń.

Dodatkowo studenci otrzymują wskazówki do samodzielnego studiowana z zachętą do korzystania z różnorodnych źródeł wiedzy (U03 i K01).

Skala ocen: dostatecznie (3) – student zna i rozumie większość wyłożonych zagadnień, umie rozwiązywać najprostsze zadania rachunkowe, rozumie treść najważniejszych twierdzeń; dobrze (4) – student zna i rozumie znaczną większość wyłożonych zagadnień, umie formułować i rozwiązywać najprostsze zadania rachunkowe oraz interpretować ich wyniki za pomocą twierdzeń; bardzo dobrze (5) – student zna i rozumie wszystkie wyłożone zagadnienia, umie formułować i rozwiązywać zadania rachunkowe oraz interpretować ich wyniki za pomocą twierdzeń; dość dobrze (3,5) i ponad dobrze (4,5) – pośrednio między dostatecznie i dobrze oraz między dobrze i bardzo dobrze.