Matematyka dyskretna Field of study: Applied Computer Science
Programme code: W4-S1IS19.2.2019

Module name: Matematyka dyskretna
Module code: 03-IS-14-MD
Programme code: W4-S1IS19.2.2019
Semester:
  • winter semester 2023/2024
  • winter semester 2022/2023
  • winter semester 2021/2022
  • winter semester 2020/2021
Language of instruction: Polish
Form of verification: exam
ECTS credits: 4
Description:
1. Elementy teorii liczb: liczby pierwsze, jednoznaczność rozkładu, NWD, algorytm Euklidesa, równania diofantyczne; kongruencje, arytmetyka modularna, ciała skończone, małe twierdzenie Fermata i twierdzenie Eulera; sito Eratostenesa, testy pierwszości, algorytm Rabina, rozkład liczby na czynniki, algorytm Fermata. Algorytm szyfrujący RSA i warunki jego bezpieczeństwa. 2. Kombinatoryka: wariacje, permutacje, kombinacje; symbole dwumianowe Newtona i ich własności. Algorytmy generujące proste obiekty kombinatoryczne: permutacje, wariacje, podzbiory zbioru; generowanie losowych obiektów kombinatorycznych; złożoność obliczeniowa i przykłady zastosowań takich algorytmów. 3. Metody zliczania obiektów: metoda bijektywna; reguła włączania i wyłączania; rekurencja i funkcje tworzące, liczby Fibonacciego. 4. Elementy teorii grafów: podstawowe pojęcia; minimalne drzewo rozpinające; problem minimalnych odległości; grafy Eulera i Hamiltona, problem komiwojażera.
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]
rozumie znaczenie zastosowań matematyki dyskretnej w informatyce [MD_1]
 KIN_W01 [5/5]
zna podstawowe pojęcia i metody obliczeniowe elementarnej teorii liczb [MD_2]
 K_W01 [5/5] KIN_W01 [5/5]
zna elementarne pojęcia kombinatoryki i podstawowe algorytmy kombinatoryczne [MD_3]
 K_W01 [5/5] KIN_W01 [5/5]
zna podstawowe pojęcia teorii grafów [MD_4]
 K_W01 [5/5] KIN_W01 [5/5]
potrafi zastosować algorytm Euklidesa do rozwiązywania równań diofantycznych liniowych i układów równań kongruencyjnych, potrafi zastosować poznane metody testowania liczb pierwszych i rozkładu liczb na czynniki pierwsze, [MD_5]
 KIN_U01 [5/5] KIN_U02 [5/5]
potrafi zastosować właściwe schematy kombinatoryczne do rozwiązywania problemów informatycznych i przeprowadzić konieczne obliczenia przy pomocy poznanych metod i algorytmów. [MD_6]
 KIN_U01 [5/5] KIN_U02 [5/5] KIN_U03 [5/5]
potrafi zastosować terminologię i algorytmy teorii grafów do rozwiązywania problemów informatycznych [MD_7]
 KIN_U01 [5/5] KIN_U02 [5/5] KIN_U03 [5/5]
potrafi w sposób zrozumiały, w mowie i piśmie przedstawić poznaną wiedzę [MD_8]
 KIN_U01 [2/5]
Type Description Codes of the learning outcomes of the module to which assessment is related
kolokwium [MD_w_1]
kolokwium pisemne
 MD_5 MD_6 MD_7 MD_8
aktywność na zajęciach ( ocena ciągła) [MD_w_2]
rozwiązywanie zadań - odpowiedź ustna; udział w dyskusji;
 MD_1 MD_5 MD_6 MD_7 MD_8
egzamin pisemny i/ lub ustny [MD_w_3]
wszystkie zagadnienia omawiane na wykładach;
 MD_1 MD_2 MD_3 MD_4 MD_8
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]
wykład wybranych zagadnień z wykorzystaniem pomocy audiowizualnych;
20
praca z podręcznikiem; lektura uzupełniająca
 10 kolokwium [MD_w_1] aktywność na zajęciach ( ocena ciągła) [MD_w_2] egzamin pisemny i/ lub ustny [MD_w_3]
discussion classes [MD_fs_2]
rozwiązywanie zadań rachunkowych, analiza, wybór metody, przeprowadzenie obliczeń i dyskusja wyników; wyprowadzenie niektórych wzorów i omówienie wybranych przykładów zasygnalizowanych na wykładach, dyskusja; możliwość wykorzystania komputerów
30
przyswojenie wiedzy z wykładów; praca z podręcznikiem i zbiorami zadań; rozwiązywanie zadań
 50 aktywność na zajęciach ( ocena ciągła) [MD_w_2] egzamin pisemny i/ lub ustny [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)