Wybrane zagadnienia z matematyki dyskretnej 1 - opis przedmiotu

Informacje ogólne

Nazwa przedmiotu	Wybrane zagadnienia z matematyki dyskretnej 1
Kod przedmiotu	11.1-WK-MATD-WZMD1-S21
Wydział	Wydział Matematyki, Informatyki i Ekonometrii
Kierunek	Matematyka
Profil	ogólnoakademicki
Rodzaj studiów	drugiego stopnia z tyt. magistra
Semestr rozpoczęcia	semestr zimowy 2021/2022

Informacje o przedmiocie

Semestr	4
Liczba punktów ECTS do zdobycia	7
Typ przedmiotu	obieralny
Język nauczania	polski
Sylabus opracował	dr hab. Elżbieta Sidorowicz, prof. UZ

Formy zajęć

Forma zajęć	Liczba godzin w semestrze (stacjonarne)	Liczba godzin w tygodniu (stacjonarne)	Liczba godzin w semestrze (niestacjonarne)	Liczba godzin w tygodniu (niestacjonarne)	Forma zaliczenia
Ćwiczenia	30	2	-	-	Zaliczenie na ocenę
Wykład	30	2	-	-	Egzamin

Cel przedmiotu

Poznanie zaawansowanych pojęć matematyki dyskretnej w aspekcie teoretycznym i algorytmicznym.

Matematyka dyskretna 1, Algebra liniowa

Wykład/ćwiczenia

Wybrane klasy grafów i ich własności.
Wybrane klasy digrafów i ich własności.
Algorytmy digrafowe.
Algebry Boole’a. Funkcje boolowskie.
Formuły boolowskie, minimalizacja.
Zastosowania formuł boolowskich w teorii grafów i złożoności obliczeniowej problemów.

Wykład: konwencjonalny, konwersatoryjny.

Ćwiczenia: klasyczna metoda problemowa.

Opis efektu	Symbole efektów	Metody weryfikacji	Forma zajęć

Ocena końcowa przedmiotu: średnia pozytywnych ocen z ćwiczeń i z egzaminu.

Warunkiem zaliczenia ćwiczeń jest uzyskanie pozytywnej oceny ze sprawdzianów pisemnych, aktywności na ćwiczeniach oraz przygotowanego referatu.

Warunkiem zaliczenia sprawdzianu pisemnego jest uzyskanie ustalonej dla danego sprawdzianu minimalnej liczby punktów.

Warunkiem przystąpienia do egzaminu jest uzyskanie pozytywnej z ćwiczeń.

J. Bang-Jensen, G.Gutin, Digraphs, Theory and Algorithms, 2001.
R. Distel, Graph Theory, Springer-Verlag, New York 1997.
M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics 57, Elsevier, 2004.
T. Fujisawa, T. Kasami, Theory of discrete structures, Tokyo, 1984.
K. A. Ross, Ch. R. B. Wright, Matematyka dyskretna, PWN, 2010.

H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science 209 (1998) 1-45.
A. Brandstadt, V.B. Le, J.P. Spinrad, Graph Classes: a survey, SIAM 2004.
Ch. H. Papadimitriou, Złożoność obliczeniowa, Helion, 2012.

Zmodyfikowane przez dr Ewa Sylwestrzak-Maślanka (ostatnia modyfikacja: 09-05-2021 10:02)