Wierk - Wydział Informatyki, Elektroniczne Ramy Kwalifikacji

Wydział Informatyki
Kierunek studiów	Informatyka i ekonometria							Poziom i forma studiów	pierwszego stopnia inżynierskie stacjonarne
Specjalność / Ścieżka dyplomowania	---							Profil kształcenia	praktyczny
Nazwa przedmiotu	Matematyka dyskretna							Kod przedmiotu	IE1MDY
								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	Analiza matematyczna (IE1AMA), Logika dla informatyków (IE1LDI),
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. Wstępne przygotowanie studentów do oceny złożoności obliczeniowej rozważanego problemu (i nawyku przeprowadzania takiej oceny).
Treści programowe	Wykłady: Indukcja matematyczna i rekurencja oraz wybrane metody jej rozwiązywania. Podstawy arytmetyki liczb całkowitych i arytmetyka modularna. Podstawowe obiekty kombinatoryczne, ich własności i techniki zliczania, w szczególności Szufladkowa Zasada Dirichleta i Zasada Włączeń-Wyłączeń. Funkcje tworzące. Asymptotyka funkcji. Podstawowe pojęcia i twierdzenia teorii grafów, w szczególności charakterystyka grafów eulerowskich i hamiltonowskich, własności grafów spójnych, planarnych i drzew, zliczanie drzew rozpinających graf, opis zagadnienia kolorowania grafów. Ćwiczenia: Indukcja matematyczna i rekurencja oraz wybrane metody jej rozwiązywania. Podstawy arytmetyki liczb całkowitych i arytmetyka modularna. Podstawowe obiekty kombinatoryczne, ich własności i techniki zliczania, w szczególności Szufladkowa Zasada Dirichleta i Zasada Włączeń-Wyłączeń. Funkcje tworzące. Asymptotyka funkcji. Podstawowe pojęcia i twierdzenia teorii grafów, w szczególności charakterystyka grafów eulerowskich i hamiltonowskich, własności grafów spójnych, planarnych i drzew, zliczanie drzew rozpinających graf, opis zagadnienia kolorowania grafów.
Metody dydaktyczne	wykład problemowy, wykład informacyjny, ćwiczenia przedmiotowe,
Forma zaliczenia	Wykład - egzamin pisemny. Ćwiczenia - dwa sprawdziany pisemne oraz aktywność na zajęciach.
Symbol efektu uczenia się	Zakładane efekty uczenia się								Odniesienie do kierunkowych efektów uczenia się
EU1	zna najważniejsze obiekty kombinatoryczne i ich własności								K_W01
EU2	zna najważniejsze rodzaje grafów oraz ich charakteryzacje								K_W01
EU3	zna i rozumie treści najważniejszych twierdzeń i metod zliczania								K_W01
EU4	umie stosować schemat indukcji i rozwiązywać podstawowe rekurencje								K_U01
EU5	potrafi stosować funkcje tworzące i szacować rodzaje asymptotyki								K_U01 K_U03
EU6	umie rozpoznawać typy obiektów kombinatorycznych i rodzaje grafów oraz potrafi stosować techniki ich zliczania								K_U01
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	egzamin pisemny								W
EU4	kolokwium								Ć
EU5	kolokwium								Ć
EU6	kolokwium								Ć
Bilans nakładu pracy studenta (w godzinach)									Liczba godz.
Wyliczenie
	1 - Udział w wykładach								30
	2 - Udział w ćwiczeniach audytoryjnych								30
	3 - Przygotowanie do ćwiczeń audytoryjnych								15
	4 - Udział w konsultacjach								5
	5 - Przygotowanie do egzaminu								13
	6 - Obecność na egzaminie								2
	7 - Przygotowanie do zaliczenia ćwiczeń								5
RAZEM:									100
Wskaźniki ilościowe									GODZINY	ECTS
Nakład pracy studenta związany z zajęciami wymagającymi bezpośredniego udziału nauczyciela									67 (4)+(1)+(2)+(6)	2.7
Nakład pracy studenta związany z zajęciami o charakterze praktycznym									50 (3)+(2)+(7)	2.0
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 2021. 3. K. A. Ross, Ch.R.B. Wright, Matematyka dyskretna, Wydawnictwo Naukowe PWN, Warszawa 2012. 4. W. Lipski, Kombinatoryka dla programistów, Wydawnictwo Naukowo-Techniczne, Warszawa 2007.
Literatura uzupełniająca	1. D. E. Knuth, Sztuka programowania, t. 1-3, Wydawnictwo Naukowo-Techniczne, Warszawa 2003. 2. R. J. Wilson, Wstęp do teorii grafów, Wydawnictwo Naukowe PWN, Warszawa 1998. 3. A. Neugebauer, B. Bogdańska, Matematyka olimpijska. Kombinatoryka, Wydawnictwo Omega, Warszawa 2020.
Jednostka realizująca	Katedra Matematyki								Data opracowania programu
Program opracował(a)	dr hab. Czesław Bagiński								2021.04.28