Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Matematyka dyskretna
Tok studiów:
2018/2019
Kod:
JIS-1-109-s
Wydział:
Fizyki i Informatyki Stosowanej
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka Stosowana
Semestr:
1
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Osoba odpowiedzialna:
dr hab. inż. Gawroński Przemysław (gawron@newton.ftj.agh.edu.pl)
Osoby prowadzące:
dr hab. inż. Gawroński Przemysław (gawron@newton.ftj.agh.edu.pl)
dr inż. Joanna Świebocka-Więk (jsw@agh.edu.pl)
Krótka charakterystyka modułu

Konstrukcja aparatu pojęciowego, którego celem jest przeprowadzenie dowodów poprawności kryptosystemu RSA oraz twierdzenia o rekurencji uniwersalnej.

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W009 Student zna podstawowe twierdzenia teorii liczb i na ich podstawie potrafi przeprowadzić kodowanie w kryptosystemie RSA. IS1A_W03, IS1A_W02 Aktywność na zajęciach,
Wykonanie ćwiczeń
M_W010 Student zna i rozumie idee rekurencji oraz indukcji, potrafi wykorzystać reguły wnioskowania przeprowadzania prostych dowodów. IS1A_W03, IS1A_W02 Aktywność na zajęciach,
Udział w dyskusji,
Wykonanie ćwiczeń
Umiejętności
M_U009 Student potrafi wykonywać obliczenia w arytmetyce modularnej. IS1A_U06, IS1A_U05, IS1A_U01, IS1A_U04 Aktywność na zajęciach,
Udział w dyskusji,
Wykonanie ćwiczeń
M_U010 Student potrafi rozwiązywać równania rekurencyjne. IS1A_U06, IS1A_U05, IS1A_U04 Aktywność na zajęciach,
Udział w dyskusji,
Wykonanie ćwiczeń
Kompetencje społeczne
M_K005 Student rozumie znaczenie bezpieczeństwa informacji. IS1A_K02 Aktywność na zajęciach,
Wykonanie ćwiczeń,
Udział w dyskusji
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W009 Student zna podstawowe twierdzenia teorii liczb i na ich podstawie potrafi przeprowadzić kodowanie w kryptosystemie RSA. + + - - - - - - - - -
M_W010 Student zna i rozumie idee rekurencji oraz indukcji, potrafi wykorzystać reguły wnioskowania przeprowadzania prostych dowodów. + - - - - - - - - - -
Umiejętności
M_U009 Student potrafi wykonywać obliczenia w arytmetyce modularnej. + + - - - - - - - - -
M_U010 Student potrafi rozwiązywać równania rekurencyjne. + + - - - - - - - - -
Kompetencje społeczne
M_K005 Student rozumie znaczenie bezpieczeństwa informacji. - + - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:
  1. Przeliczanie

    Podstawowe prawa przeliczania, zbiory, równoliczność zbiorów, k-elementowe permutacje zbiorów, podzbiory, permutacje, właściwości symbolu Newtona, dwumian Newtona, trójkąt Paskala

  2. Kryptografia z teorią liczb

    Wprowadzenie do kryptografii, kryptografia z kluczem prywatnym, kryptografia z kluczem publicznym, arytmetyka modulo, największy wspólny dzielnik, algorytm Euklidesa, rozszerzony algorytm Euklidesa, kongruencje, odwrotność multiplikatywna, potęgowanie modularne, małe twierdzenie Fermata, chińskie twierdzenie o resztach, algorytm RSA – konstrukcja oraz podstawy teoretyczne.

  3. Elementy logiki i dowodzenia

    Równoważność zdań, tabele prawdy, prawa DeMorgana, zmienne i kwantyfikatory, tautologie rachunku zdań, reguły wnioskowania, dowody wprost, dowody nie wprost.

  4. Indukcja i rekurencja

    Silna i słaba zasada indukcji matematycznej, rekurencja, wieże Hanoi, równania rekurencyjne, iterowanie równań rekurencyjnych, drzewa rekursji, twierdzenie o rekurencji uniwersalnej

  5. Wstęp do teorii grafów

    Podstawowe własności grafów, drzewa, minimalne drzewo rozpinające, grafy eulerowskie, grafy hermitowskie – problem komiwojażera, grafy planarne, kolorowanie wierzchołkowe i krawędziowe grafów, skojarzenia w grafach i grafach dwudzielnych, grafy skierowane, przepływy w grafach.

  6. Konstrukcja aparatu pojęciowego, którego celem jest przeprowadzenie dowodów poprawności kryptosystemu RSA oraz twierdzenia o rekurencji uniwersalnej.

Ćwiczenia audytoryjne:
  1. Przeliczanie

    - student potrafi określić krotność wykonywanych pętli z wartownikiem, z licznikiem i ogólnych,
    - student potrafi określić czy dane zbiory są równoliczne,
    - student potrafi wyznaczyć ilość podzbiorów danego zbioru spełniających zadany warunek,

  2. Kryptografia z teorią liczb

    - student potrafi wykorzystać rozszerzony algorytm Euklidesa do wyznaczenia liczb całkowitych spełniających równanie: a*p+b*q=NWD,
    - student potrafi wykonywać działania w zadanej arytmetyce modulo,
    - student potrafi rozwiązać równanie i układ równań kongruencyjnych,
    - student potrafi wykorzystać małe twierdzenie Fermata do wykonania obliczeń w arytmetyce modulo,
    - student potrafi zakodować i rozkodować wiadomość korzystając z algorytmu RSA

  3. Elementy logiki i dowodzenia

    - student potrafi wykazać, że dane wyrażeni jest tautologią,
    - student potrafi wykorzystać regułę wnioskowania,
    - student potrafi stwierdzić poprawność tautologii rachunku kwantyfikatorów,
    - student zna ideę dowodu nie wprost i potrafi go przeprowadzić w podstawowych przypadkach.

  4. Indukcja i rekurencja

    - student potrafi przeprowadzić dowód indukcyjny,
    - student potrafi użyć notacji asymptotycznej do określenia złożoności obliczeniowej algorytmów iteracyjnych i rekurencyjnych,
    - student potrafi stworzyć drzewo rekursji dla wywołań algorytmu rekurencyjnego,
    - student potrafi zastosować twierdzenie o rekurencji uniwersalnej do określenia czasowej złożoności obliczeniowej algorytmu rekurencyjnego.

  5. Wstęp do teorii grafów

    - student potrafi utworzyć macierzową i listową reprezentację grafu skierowanego i niekierowanego,
    - student potrafi stwierdzić czy dany graf jest eulerowski, czy jest hamiltonowski,
    - student potrafi znaleźć w grafie cykl eulerowski i hamiltonowski,
    - student potrafi dla danego grafu utworzyć minimalne drzewo rozpinające.

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 120 godz
Punkty ECTS za moduł 4 ECTS
Udział w wykładach 30 godz
Samodzielne studiowanie tematyki zajęć 24 godz
Udział w ćwiczeniach audytoryjnych 30 godz
Przygotowanie do zajęć 36 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

Ocena końcowa z przedmiotu to ocena z ćwiczeń audytoryjnych.

W semestrze przewidziane są 3 kolokwia.
Ocena końcowa z ćwiczeń obliczana jest według wzoru:
OC = 0.6*kolokwia + 0.4* aktywność.

Aktywność: Za każdą pozytywną odpowiedź przy tablicy student otrzymuje 1 punkt. W semestrze należy zdobyć 10 punktów.

Ocena z ćwiczeń rachunkowych ustalana będzie zgodnie ze skalą ocen obowiązującą w regulaminie AGH, przyporządkowującą procent opanowania materiału konkretnej ocenie.

Wymagania wstępne i dodatkowe:

Nie podano wymagań wstępnych lub dodatkowych.

Zalecana literatura i pomoce naukowe:
  1. Clifford Stein, Robert L. Drysdale, Kenneth Bogart, Discrete Mathematics for Computer Science
  2. Kenneth A. Ross, Charles R.B. Wright, Matematyka dyskretna
Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:
  • P. Gawroński, M. J. Krawczyk, K. Kułakowski, Emerging communities in networks -
    a flow of ties, Acta Phys. Pol. B, 46, (2015), 911
  • A. Jarynowski, P. Gawroński, K. Kułakowski, How the competitive altruism leads to
    bistable homogeneous states of cooperation or defection, Lecture Notes in Computer
    Science, 7204 (2012) 543
  • K. Kułakowski, P. Gawroński, To cooperate or to defect? Altruism and reputation,
    Phys. A, 388, (2009), 3581
Informacje dodatkowe:

Sposób i tryb wyrównania zaległości powstałych wskutek nieobecności studenta na zajęciach:
ćwiczenia audytoryjnych: Nieobecność na jednych ćwiczeniach zajęciach wymaga od studenta samodzielnego opanowania przerabianego na tych zajęciach materiału. Nieobecność na więcej niż jednych ćwiczeniach wymaga od studenta samodzielnego opanowania przerabianego na tych zajęciach materiału i jego zaliczenia w formie pisemnej w wyznaczonym przez prowadzącego terminie lecz nie później jak w ostatnim tygodniu trwania zajęć. Student który bez usprawiedliwienia opuścił więcej niż dwa ćwiczenia i jego cząstkowe wyniki w nauce były negatywne może zostać pozbawiony, przez prowadzącego zajęcia, możliwości wyrównania zaległości.
Obecność na wykładzie: zgodnie z Regulaminem Studiów AGH.

Zasady zaliczania zajęć:
ćwiczenia audytoryjne: Podstawowym terminem uzyskania zaliczenia jest koniec zajęć w danym semestrze. Student może dwukrotnie przystąpić do poprawkowego zaliczania.
Student który bez usprawiedliwienia opuścił więcej niż dwa zajęcia i jego cząstkowe wyniki w nauce były negatywne może zostać pozbawiony, przez prowadzącego zajęcia, możliwości poprawkowego zaliczania zajęć. Od takiej decyzji prowadzącego zajęcia student może się odwołać do prowadzącego przedmiot (moduł) lub Dziekana.