Karta Przedmiotu
| Politechnika Białostocka | Wydział Informatyki | ||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Kierunek studiów | Data Science |
Poziom i forma studiów |
pierwszego stopnia stacjonarne |
||||||||||||||||||||||||
| Grupa przedmiotów / specjalność |
Profil kształcenia | ogólnoakademicki | |||||||||||||||||||||||||
| Nazwa przedmiotu | Matematyka dyskretna | E | Kod przedmiotu | DS1S2MDY | |||||||||||||||||||||||
| Rodzaj zajęć | obowiązkowy | ||||||||||||||||||||||||||
| Formy zajęć i liczba godzin | W | Ć | L | P | Ps | T | S | Semestr | 2 | ||||||||||||||||||
| 30 | 30 | Punkty ECTS | 4 | ||||||||||||||||||||||||
| Program obowiązuje od | 2025/2026 | ||||||||||||||||||||||||||
| Przedmioty wprowadzające | Algebra liniowa 1 (DS1S1AL1), Analiza matematyczna 1 (DS1S1AM1), Logika matematyczna (DS1S1LMA), | ||||||||||||||||||||||||||
| Cele przedmiotu | Zapoznanie studentów z podstawowymi pojęciami, twierdzeniami i metodami kombinatoryki i teorii grafów stanowiącymi podstawę modeli matematycznych i algorytmów służących rozwiązywaniu realnych zagadnień, które leżą w obszarze zainteresowania informatyki. | ||||||||||||||||||||||||||
| Ramowe treści programowe | Indukcja matematyczna i rekurencja. Arytmetyka liczb całkowitych i arytmetyka modularna. Podstawowe obiekty kombinatoryczne, techniki ich zliczania. Funkcje tworzące. Asymptotyka funkcji. Podstawowe pojęcia i twierdzenia teorii grafów, w szczególności charakterystyki typowych rodzajów grafów. | ||||||||||||||||||||||||||
| Inne informacje o przedmiocie | przedmiot ma związek z prowadzoną na Uczelni działalnością naukową | ||||||||||||||||||||||||||
| Wyliczenie: | Nakład pracy studenta związany z: | Godzin ogółem |
W tym kontaktowych |
W tym praktycznych |
|||||||||||||||||||||||
| udziałem w wykładach | 30 | 30 | |||||||||||||||||||||||||
| udziałem w innych formach zajęć | 30 | 30 | 30 | ||||||||||||||||||||||||
| indywidualnym wsparciem merytorycznym procesu uczenia się, udziałem w egzaminie i zaliczeniach organizowanych poza planem zajęć | 4 | 4 | 4 | ||||||||||||||||||||||||
| przygotowaniem do egzaminu | 15 | ||||||||||||||||||||||||||
| przygotowaniem do zaliczenia ćwiczeń audytoryjnych | 15 | 15 | |||||||||||||||||||||||||
| przygotowaniem do bieżących zajęć | 6 | 6 | |||||||||||||||||||||||||
| Razem godzin: | 100 | 64 | 55 | ||||||||||||||||||||||||
| Razem punktów ECTS: | 4 | 2.6 | 2.2 | ||||||||||||||||||||||||
| Zakładane kierunkowe efekty uczenia się | Wiedza | Umiejętności | Kompetencje społeczne |
||||||||||||||||||||||||
| DS1_W01 | DS1_U01 | DS1_K01 | |||||||||||||||||||||||||
| DS1_U03 | |||||||||||||||||||||||||||
| DS1_U19 | |||||||||||||||||||||||||||
| Cele i treści ramowe sformułował(a) | dr hab. Dorota Mozyrska, dr hab. Małgorzata Wyrwas | Data: | 29/05/2025 | ||||||||||||||||||||||||
| Realizacja w roku akademickim | 2025/2026 | ||||||||||||||||||||||||||
| Treści programowe | |||||||||||||||||||||||||||
| Wykład | |||||||||||||||||||||||||||
| 1. | Indukcja matematyczna i rekurencja | ||||||||||||||||||||||||||
| 2. | Arytmetyka liczb całkowitych, w tym systemy pozycyjne i arytmetyka modularna. Wzmianka o RSA | ||||||||||||||||||||||||||
| 3. | Funkcje tworzące i ich wykorzystanie do rozwiązywania rekurencji | ||||||||||||||||||||||||||
| 4. | Podstawowe pojęcia kombinatoryczne i związki między nimi | ||||||||||||||||||||||||||
| 5. | Podstawowe pojęcia kombinatoryczne i związki między nimi | ||||||||||||||||||||||||||
| 6. | Liczby Stirlinga drugiego rodzaju i ich własności | ||||||||||||||||||||||||||
| 7. | Liczby Stirlinga pierwszego rodzaju i ich własności | ||||||||||||||||||||||||||
| 8. | Podstawowe pojęcia teorii grafów. Podstawowe typy grafów. Izomorfizm grafów | ||||||||||||||||||||||||||
| 9. | Charakteryzacja grafów spójnych i wielospójnych | ||||||||||||||||||||||||||
| 10. | Charakteryzacje grafów acyklicznych. Drzewa rozpinające graf | ||||||||||||||||||||||||||
| 11. | Grafy Eulera i ich charakteryzacje. Grafy Hamiltona i ich charakteryzacje | ||||||||||||||||||||||||||
| 12. | Grafy planarne i ich charakteryzacje | ||||||||||||||||||||||||||
| 13. | O kolorowaniu wierzchołków grafów. Liczba chromatyczna grafu | ||||||||||||||||||||||||||
| 14. | O kolorowaniu krawędzi grafów. Indeks chromatyczny grafu | ||||||||||||||||||||||||||
| 15. | Kolorowanie map | ||||||||||||||||||||||||||
| Ćwiczenia | |||||||||||||||||||||||||||
| 1. | Techniki dowodów indukcyjnych i rozwiązywania rekurencji | ||||||||||||||||||||||||||
| 2. | Liczby pierwsze i złożone, systemy pozycyjne. Wykorzystanie twierdzeń Eulera i Małego Twierdzenia Fermata | ||||||||||||||||||||||||||
| 3. | Wyznaczanie funkcji tworzących i ich wykorzystywanie do rozwiązywania rekurencji | ||||||||||||||||||||||||||
| 4. | Wariacje, wariacje z powtórzeniami, kombinacje i kombinacje z powtórzeniami. Charakteryzacje liczbowe | ||||||||||||||||||||||||||
| 5. | Funkcje, iniekcje, suriekcje na zbiorach skończonych. Własności permutacji | ||||||||||||||||||||||||||
| 6. | Opis własności liczb Stirlinga drugiego rodzaju | ||||||||||||||||||||||||||
| 7. | Opis własności liczb Stirlinga pierwszego rodzaju | ||||||||||||||||||||||||||
| 8. | Rozpoznawanie podstawowych liczbowych charakteryzacji grafów. Rozpoznawanie istnienia izomorfizmu między grafami | ||||||||||||||||||||||||||
| 9. | Rozpoznawania spójności, niespójności grafów | ||||||||||||||||||||||||||
| 10. | Zliczanie drzew o określonej własności. Zliczanie drzew rozpinających graf | ||||||||||||||||||||||||||
| 11. | Rozpoznawanie grafów Eulera i Hamiltona. Charakteryzacje liczbowe tych grafów | ||||||||||||||||||||||||||
| 12. | Rozpoznawanie planarności grafów | ||||||||||||||||||||||||||
| 13. | Wyznaczanie liczby chromatycznej grafu. Wyznaczanie indeksu chromatycznego grafu | ||||||||||||||||||||||||||
| 14. | Związki kolorowania wierzchołków z kolorowaniem map | ||||||||||||||||||||||||||
| 15. | Zaliczenie przedmiotu | ||||||||||||||||||||||||||
| Metody dydaktyczne (realizacja stacjonarna) |
|||||||||||||||||||||||||||
| W | wykład problemowy; wykład konwersatoryjny; wykład z prezentacją multimedialną | ||||||||||||||||||||||||||
| Ć | ćwiczenia przedmiotowe; klasyczna metoda problemowa | ||||||||||||||||||||||||||
| Metody dydaktyczne (realizacja zdalna) |
|||||||||||||||||||||||||||
| W | wykład problemowy; wykład konwersatoryjny; wykład z prezentacją multimedialną | ||||||||||||||||||||||||||
| - | |||||||||||||||||||||||||||
| Forma zaliczenia | |||||||||||||||||||||||||||
| W | egzamin pisemny z pytaniami otwartymi | ||||||||||||||||||||||||||
| Ć | kolokwia | ||||||||||||||||||||||||||
| Warunki zaliczenia | |||||||||||||||||||||||||||
| W | Uzyskanie min. 30% z każdego E1-E2, a po spełnieniu tego warunku ostateczna ocena wynika z sumy uzyskanych punktów. Kryteria oceny: [ 0 – 50]% punktów – 2.0 (50 – 60]% punktów – 3.0 (60 – 70]% punktów – 3.5 (70 – 80]% punktów – 4.0 (80 – 90]% punktów – 4.5 (90 – 100]% punktów – 5.0 |
||||||||||||||||||||||||||
| Ć | Uzyskanie min. 30% z każdego E3-E6, a po spełnieniu tego warunku ostateczna ocena wynika z sumy uzyskanych punktów w trakcie zajęć. Kryteria oceny: [0 – 50)% punktów – 2.0 [50 – 60)% punktów – 3.0 [60 – 70)% punktów – 3.5 [70 – 80)% punktów – 4.0 [80 – 90)% punktów – 4.5 [90 – 100]% punktów – 5.0 |
||||||||||||||||||||||||||
| Symbol efektu | Zakładane efekty uczenia się | Odniesienie do efektów uczenia się zdefiniowanych dla kierunku studiów | |||||||||||||||||||||||||
| Wiedza | Umiejętności | Kompetencje społeczne |
|||||||||||||||||||||||||
| Wiedza: student zna i rozumie | |||||||||||||||||||||||||||
| E1 | podstawowe pojęcia i twierdzenia matematyki dyskretnej oraz ich zastosowania | ||||||||||||||||||||||||||
| E2 | teoretyczne aspekty matematyki dyskretnej | ||||||||||||||||||||||||||
| Umiejętności: student potrafi | |||||||||||||||||||||||||||
| E3 | definiować pojęcia z kombinatoryki i teorii grafów, opisywać ich własności oraz interpretować i wyjaśniać zależności między nimi | ||||||||||||||||||||||||||
| E4 | interpretować poznane pojęcia w zastosowaniach do opisu realnych zagadnień z zakresu struktury danych i algorytmiki | ||||||||||||||||||||||||||
| Kompetencje społeczne: student jest gotów do | |||||||||||||||||||||||||||
| E5 | krytycznej oceny posiadanej wiedzy z matematyki dyskretnej oraz uznawania poznanej wiedzy w rozwiązywaniu problemów poznawczych i praktycznych | ||||||||||||||||||||||||||
| Symbol efektu | Sposób weryfikacji efektu uczenia się | Forma zajęć na której zachodzi weryfikacja | |||||||||||||||||||||||||
| E1 | egzamin pisemny | W | |||||||||||||||||||||||||
| E2 | egzamin pisemny | W | |||||||||||||||||||||||||
| E3 | kolokwium | Ć | |||||||||||||||||||||||||
| E4 | kolokwium | Ć | |||||||||||||||||||||||||
| E5 | kolokwium | Ć | |||||||||||||||||||||||||
| Literatura podstawowa | |||||||||||||||||||||||||||
| 1. | V. Bryant, Aspekty kombinatoryki, Wydawnictwo Naukowo-Techniczne, Warszawa, 1997 | ||||||||||||||||||||||||||
| 2. | R. L. Graham, D. E. Knuth, O. Patashnik, Matematyka konkretna, Wydawnictwo Naukowe PWN, Warszawa, 1998 | ||||||||||||||||||||||||||
| 3. | K. A. Ross, Ch.R.B. Wright, Matematyka dyskretna, Wydawnictwo Naukowe PWN, Warszawa, 2001 | ||||||||||||||||||||||||||
| 4. | W. Lipski, Kombinatoryka dla programistów, Wydawnictwo Naukowo-Techniczne, Warszawa, 2004 | ||||||||||||||||||||||||||
| 5. | B. Bogdańska, A. Neugebauer, Kombinatoryka, Wydawnictwo szkolne OMEGA, Kraków 2018 | ||||||||||||||||||||||||||
| Literatura uzupełniająca | |||||||||||||||||||||||||||
| 1. | D. E. Knuth, Sztuka programowania, t. 1-4, Wydawnictwo Naukowo-Techniczne, Warszawa, 2020 | ||||||||||||||||||||||||||
| 2. | R. J. Wilson, Wstęp do teorii grafów, Wydawnictwo Naukowe PWN, Warszawa, 1998 | ||||||||||||||||||||||||||
| 3. | H. Lewis, R. Zax, Matematyka dyskretna, Niezbędnik dla informatyków. Wydawnictwo Naukowe PWN, Warszawa, 2021 | ||||||||||||||||||||||||||
| Koordynator przedmiotu: | dr hab. Czesław Bagiński, dr inż. Anna Borowska, dr inż. Krzysztof Ostrowski | Data: | 30/05/2025 | ||||||||||||||||||||||||