Matematyka dyskretna Field of study: Computer Science
Programme code: 08-S1INI12.2019

Module name: Matematyka dyskretna
Module code: 08-IO1S-13-MD
Programme code: 08-S1INI12.2019
Semester:
  • summer semester 2021/2022
  • summer semester 2020/2021
Language of instruction: Polish
Form of verification: exam
ECTS credits: 4
Description:
Celem zajęć w tym module jest dostarczenie studentom niezbędnego aparatu matematycznego wykorzystywanego w różnych działach informatyki a odbiegającego treściami od treści klasycznie wykładanych na kierunkach technicznych. W szczególności celem jest zapoznanie studentów z prostymi obiektami kombinatorycznymi, metodami ich zliczania a także sposobem ich generowania, metodami rozwiązywania problemów rekurencyjnych; z elementami teorii liczb wykorzystywanych w kryptografii a także elementami teorii grafów.
Prerequisites:
(no information given)
Key reading:
(no information given)
Learning outcome of the module Codes of the learning outcomes of the programme to which the learning outcome of the module is related [level of competence: scale 1-5]
Potrafi pracować w kilkuosobowej grupie. [MD_U_5]
 K_K01 [1/5] K_K05 [1/5]
Ma podstawową wiedzę z zakresu teorii grafów: drzewa i cykle; minimalne drzewo spinające graf; cykle Eulera i Hamiltona; grafy dwudzielne, problem komiwojażera. Potrafi zastosować algorytmy przeszukiwania grafów w głąb i wszerz; algorytm Dijkstry; algorytm Kruskala. [MD_W_1]
 K_W01 [2/5] K_W02 [2/5] K_W04 [1/5] K_W09 [1/5] K_U08 [2/5]
Ma podstawową wiedzę z zakresu kombinatoryki skończonej: wariacje z powtórzeniami i bez, kombinacje, permutacje. Potrafi zastosować algorytmy generujące obiekty kombinatoryczne ( podzbiory k-elementowe, ciągi ustalonej długości, permutacje). [MD_W_2]
 K_W01 [2/5] K_W02 [2/5] K_W04 [1/5] K_W09 [1/5] K_U08 [2/5]
Ma podstawową wiedzę z zakresu teorii liczb: liczby pierwsze, jednoznaczność rozkładu liczb naturalnych, algorytm Euklidesa; liniowe równania diofantyczne, kongruencje, arytmetyka modularna i ciała skończone, chińskie twierdzenie o resztach, twierdzenie Eulera. Potrafi zastosować kilka znanych przez siebie, prostych testów pierwszości : sito Erastotenesa, test Fermata. Zna pojęcie liczby pseudopierwszej i liczby Carmichaela. Potrafi wytłumaczyć, na jakiej zasadzie działa kryptosystem RSA, w jaki sposób odbywa się szyfrowanie, jak można użyć systemu do podpisu cyfrowego. [MD_W_3]
 K_W01 [2/5] K_W02 [2/5] K_W04 [1/5] K_W09 [1/5] K_W12 [1/5] K_U01 [1/5] K_U04 [1/5] K_U05 [1/5] K_U08 [1/5]
Posiada podstawową wiedzę z zakresu funkcji tworzących i operacji na nich. Potrafi znajdować postać zwartą ciągów zadanych warunkiem rekurencyjnym, przy wykorzystaniu funkcji tworzących. [MD_W_4]
 K_W02 [2/5] K_U01 [1/5] K_U04 [1/5] K_U05 [1/5] K_U08 [1/5]
Type Description Codes of the learning outcomes of the module to which assessment is related
Aktywność na zajęciach [MD_w_1]
Weryfikacja znajomości treści wykładów na podstawie pytań zadawanych przez prowadzącego konwersatorium na zajęciach, prezentacja zadań domowych, dyskusja w grupie.
 MD_W_1 MD_W_2 MD_W_3 MD_W_4
Egzamin [MD_w_2]
Egzamin pisemny, składający się z dwóch części: pierwsza część teoretyczna, druga część praktyczna: rozwiązywanie zadań.
 MD_W_1 MD_W_2 MD_W_3 MD_W_4
Prace kontrolne [MD_w_3]
Kolokwia po każdym temacie zamkniętym na ćwiczeniach.
 MD_U_5 MD_W_1 MD_W_2 MD_W_3 MD_W_4
Form of teaching Student's own work Assessment of the learning outcomes
Type Description (including teaching methods) Number of hours Description Number of hours
lecture [MD_fs_1]
Podanie treści kształcenia w formie prezentacji , częściowo z wykorzystaniem tablicy. Przedstawienie szczegółowych dowodów twierdzeń co ma pomóc w ich zrozumieniu.
 20
Zapoznanie się z tematyką wykładu.
 30 Aktywność na zajęciach [MD_w_1] Egzamin [MD_w_2]
practical classes [MD_fs_2]
Szczegółowe przygotowanie studentów do rozwiązywania zadań ze wskazaniem na metodologię postępowania, wskazaniem kolejności wykonywanych czynności.
 30
Rozwiązywanie zadań z zestawów zadań dostarczonych przez prowadzącego.
 40 Aktywność na zajęciach [MD_w_1] Prace kontrolne [MD_w_3]
Attachments
Module description (PDF)
Information concerning module syllabuses might be changed during studies.
Syllabuses (USOSweb)
Semester Module Language of instruction
(no information given)