Module also offered within study programmes:
General information:
Name:
Discrete Mathematics
Course of study:
2018/2019
Code:
JIS-1-109-s
Faculty of:
Physics and Applied Computer Science
Study level:
First-cycle studies
Specialty:
-
Field of study:
Applied Computer Science
Semester:
1
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Responsible teacher:
dr hab. inż. Gawroński Przemysław (gawron@newton.ftj.agh.edu.pl)
Academic teachers:
dr hab. inż. Gawroński Przemysław (gawron@newton.ftj.agh.edu.pl)
dr inż. Joanna Świebocka-Więk (jsw@agh.edu.pl)
Module summary

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

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence
M_K005 Student rozumie znaczenie bezpieczeństwa informacji. IS1A_K02 Activity during classes,
Execution of exercises,
Participation in a discussion
Skills
M_U009 Student potrafi wykonywać obliczenia w arytmetyce modularnej. IS1A_U06, IS1A_U05, IS1A_U01, IS1A_U04 Activity during classes,
Participation in a discussion,
Execution of exercises
M_U010 Student potrafi rozwiązywać równania rekurencyjne. IS1A_U06, IS1A_U05, IS1A_U04 Activity during classes,
Participation in a discussion,
Execution of exercises
Knowledge
M_W009 Student zna podstawowe twierdzenia teorii liczb i na ich podstawie potrafi przeprowadzić kodowanie w kryptosystemie RSA. IS1A_W03, IS1A_W02 Activity during classes,
Execution of exercises
M_W010 Student zna i rozumie idee rekurencji oraz indukcji, potrafi wykorzystać reguły wnioskowania przeprowadzania prostych dowodów. IS1A_W03, IS1A_W02 Activity during classes,
Participation in a discussion,
Execution of exercises
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Social competence
M_K005 Student rozumie znaczenie bezpieczeństwa informacji. - + - - - - - - - - -
Skills
M_U009 Student potrafi wykonywać obliczenia w arytmetyce modularnej. + + - - - - - - - - -
M_U010 Student potrafi rozwiązywać równania rekurencyjne. + + - - - - - - - - -
Knowledge
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. + - - - - - - - - - -
Module content
Lectures:
  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.

Auditorium classes:
  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.

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 120 h
Module ECTS credits 4 ECTS
Participation in lectures 30 h
Realization of independently performed tasks 24 h
Participation in auditorium classes 30 h
Preparation for classes 36 h
Additional information
Method of calculating the final grade:

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

Ćwiczenia rozpoczynać się będą kolokwium sprawdzającym umiejętności i wiedzę w zakresie materiału omówionego na poprzednich zajęciach oraz wykładzie, za które można uzyskać 50% punktów.
Za poprawne wykonanie zadań domowych przy tablicy można uzyskać 50% 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.

Prerequisites and additional requirements:

Prerequisites and additional requirements not specified

Recommended literature and teaching resources:
  1. Clifford Stein, Robert L. Drysdale, Kenneth Bogart, Discrete Mathematics for Computer Science
  2. Kenneth A. Ross, Charles R.B. Wright, Matematyka dyskretna
Scientific publications of module course instructors related to the topic of the module:
  • 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
Additional information:

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.