Wierk - Wydział Informatyki, Elektroniczne Ramy Kwalifikacji

Wydział Informatyki
Kierunek studiów	Matematyka Stosowana							Poziom i forma studiów	pierwszego stopnia inżynierskie stacjonarne
Specjalność / Ścieżka dyplomowania	Przedmiot wspólny							Profil kształcenia	praktyczny
Nazwa przedmiotu	Matematyka dyskretna							Kod przedmiotu	MAT1MDY
								Rodzaj przedmiotu	obowiązkowy
Forma zajęć i liczba godzin	W	Ć	L	P	Ps	T	S	Semestr	2
	30	30						Punkty ECTS	5
Przedmioty wprowadzające	Algebra liniowa z geometrią analityczną 1 (MAT1AL1), Analiza matematyczna 1 (MAT1AM1), Logika i teoria mnogości (MAT1LTM),
Cele przedmiotu	Wprowadzenie aparatu matematycznego niezbędnego do konstruowania i analizy algorytmów. Zapoznanie studentów z zasadą indukcji matematycznej, podstawowymi pojęciami, twierdzeniami i metodami teorii liczb, kombinatoryki, teorii grafów. Zapoznanie z metodami rozwiązywania rekurencji ze szczególnym uwzględnieniem teorii funkcji tworzących..
Treści programowe	Wykład: Indukcja matematyczna i rekurencje. Liniowe równania rekurencyjne. Funkcje tworzące. Kombinatoryka: moce zbiorów, rozmieszczenia, dwumianowy symbol Newtona, techniki zliczania obiektów kombinatorycznych, szufladkowa zasada Dirichleta, zasada włączeń i wyłączeń, liczby Stirlinga pierwszego i drugiego rodzaju, elementy asymptotyki. Algorytmy generowania obiektów kombinatorycznych. Teoria grafów: komputerowa reprezentacja grafu. drzewa, ich charakteryzacja i zliczanie drzew rozpinających graf, algorytmy przeszukiwania drzew, twierdzenie Cayley'a, grafy Eulera, Hamiltona i ich charakteryzacje, grafy planarne, grafy dwudzielne, twierdzenie Halla o małżeństwach, kolorowania. Ćwiczenia: Indukcja matematyczna i rekurencje. Liniowe równania rekurencyjne. Funkcje tworzące. Kombinatoryka: moce zbiorów, rozmieszczenia, dwumianowy symbol Newtona, techniki zliczania obiektów kombinatorycznych, szufladkowa zasada Dirichleta, zasada włączeń i wyłączeń, liczby Stirlinga pierwszego i drugiego rodzaju, elementy asymptotyki. Algorytmy generowania obiektów kombinatorycznych. Teoria grafów: komputerowa reprezentacja grafu. drzewa, ich charakteryzacja i zliczanie drzew rozpinających graf, algorytmy przeszukiwania drzew, twierdzenie Cayley'a, grafy Eulera, Hamiltona i ich charakteryzacje, grafy planarne, grafy dwudzielne, twierdzenie Halla o małżeństwach, kolorowania.
Metody dydaktyczne	wykład problemowy, wykład informacyjny, ćwiczenia przedmiotowe,
Forma zaliczenia	Wykład - egzamin pisemny. Ćwiczenia - dwa sprawdziany 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 pojęcia kombinatoryki i teorii grafów oraz ich własności								K_W01 K_W03 K_W04
EU2	zna i rozumie treść i znaczenie większości twierdzeń								K_W01 K_W03
EU3	potrafi przeprowadzić dowody wybranych twierdzeń								K_U01 K_U03
EU4	potrafi opisać własności obiektów kombinatorycznych i teorii grafów, wyjaśnić zależności między nimi wykorzystując poznane twierdzenia, metody i techniki								K_U03 K_U12 K_U19
EU5	dostrzega obecność i rolę pojęć matematyki dyskretnej w zastosowaniach, zwłaszcza informatycznych; demonstruje przykłady praktycznego wykorzystania tych pojęć								K_U02 K_U03
Symbol efektu uczenia się	Sposób weryfikacji efektu uczenia się								Forma zajęć na której zachodzi weryfikacja
EU1	egzamin								W
EU2	egzamin								W
EU3	sprawdziany, ocena aktywności na ćwiczeniach								Ć
EU4	sprawdziany, ocena aktywności na ćwiczeniach								Ć
EU5	sprawdziany, ocena aktywności na ćwiczeniach								Ć
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								20
	4 - Udział w konsultacjach								5
	5 - Przygotowanie do egzaminu								20
	6 - Przygotowanie do zaliczenia ćwiczeń								18
	7 - Obecność na egzaminie								2
RAZEM:									125
Wskaźniki ilościowe									GODZINY	ECTS
Nakład pracy studenta związany z zajęciami wymagającymi bezpośredniego udziału nauczyciela									67 (1)+(2)+(7)+(4)	2.7
Nakład pracy studenta związany z zajęciami o charakterze praktycznym									68 (2)+(6)+(3)	2.7
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 2006. 3. W. Lipski, Kombinatoryka dla programistów, Wydawnictwo Naukowo-Techniczne, Warszawa 1982. 4. K.A. Ross, C.R.B. Wright, Matematyka dyskretna, Wydawnictwo Naukowe PWN, Warszawa 2005. 5. R.J. Wilson, Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, Warszawa 2012
Literatura uzupełniająca	1. M. Aigner, Gunter M. Ziegler, Dowody z Księgi, Wydawnictwo Naukowe PWN, Warszawa 2004. 2. T. Gerstenkorn, Tadeusz Śródka, Kombinatoryka i rachunek prawdopodobieństwa, PWN, Warszawa 1974. 3. R.P. Grimaldi, Discrete and combinatorial mathematics - An applied introduction, Addison-Wesley Publishing Company, 1993 4. L. Jeśmianowicz, Jerzy Łoś, Zbiór zadań z algebry, Państwowe Wydawnictwo Naukowe, Warszawa 1976.
Jednostka realizująca	Katedra Informatyki Teoretycznej								Data opracowania programu
Program opracował(a)	prof. dr hab. Piotr Grzeszczuk								2021.04.20