Wierk - Wydział Informatyki, Elektroniczne Ramy Kwalifikacji

Wydział Informatyki
Kierunek studiów	Data Science							Poziom i forma studiów	pierwszego stopnia inżynierskie stacjonarne
Specjalność / Ścieżka dyplomowania	---							Profil kształcenia	ogólnoakademicki
Nazwa przedmiotu	Matematyka dyskretna							Kod przedmiotu	DS1S2MDY
								Rodzaj przedmiotu	obowiązkowy
Forma zajęć i liczba godzin	W	Ć	L	P	Ps	T	S	Semestr	2
	30	30						Punkty ECTS	4
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.
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. 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 audytoryjne: 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	ćwiczenia przedmiotowe, klasyczna metoda problemowa, wykład konwersatoryjny, wykład problemowy, wykład z prezentacją multimedialną,
Forma zaliczenia	Wykład (W) - egzamin pisemny z pytaniami otwartymi Ćwiczenia (Ć) - kolokwia
Symbol efektu uczenia się	Zakładane efekty uczenia się								Odniesienie do kierunkowych efektów uczenia się
EU1	podstawowe pojęcia i twierdzenia matematyki dyskretnej oraz ich zastosowania								DS1_W01
EU2	teoretyczne aspekty matematyki dyskretnej								DS1_W01
EU3	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								DS1_U01 DS1_U03 DS1_U19
EU4	interpretować poznane pojęcia w zastosowaniach do opisu realnych zagadnień z zakresu struktury danych i algorytmiki								DS1_U01 DS1_U03 DS1_U19
EU5	krytycznej oceny posiadanej wiedzy z matematyki dyskretnej oraz uznawania poznanej wiedzy w rozwiązywaniu problemów poznawczych i praktycznych								DS1_K01
Symbol efektu uczenia się	Sposób weryfikacji efektu uczenia się								Forma zajęć na której zachodzi weryfikacja
EU1	egzamin pisemny								W
EU2	egzamin pisemny								W
EU3	kolokwium								Ć
EU4	kolokwium								Ć
EU5	kolokwium								Ć
Bilans nakładu pracy studenta (w godzinach)									Liczba godz.
Wyliczenie
	1 - udziałem w wykładach								30
	2 - udziałem w innych formach zajęć								30
	3 - indywidualnym wsparciem merytorycznym procesu uczenia się, udziałem w egzaminie i zaliczeniach organizowanych poza planem zajęć								4
	4 - przygotowaniem do egzaminu								15
	5 - przygotowaniem do zaliczenia ćwiczeń audytoryjnych								15
	6 - przygotowaniem do bieżących zajęć								6
RAZEM:									100
Wskaźniki ilościowe									GODZINY	ECTS
Nakład pracy studenta związany z zajęciami wymagającymi bezpośredniego udziału nauczyciela									64 (1)+(2)+(3)	2.6
Nakład pracy studenta związany z zajęciami o charakterze praktycznym									55 (2)+(3)+(5)+(6)	2.2
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
Jednostka realizująca	Katedra Matematyki								Data opracowania programu
Program opracował(a)	dr hab. Czesław Bagiński,dr inż. Anna Borowska,dr inż. Krzysztof Ostrowski								2025.05.30