1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2023/2024
4. Mathematics - drugiego stopnia z tyt. magistra
5. Topics in Discrete Mathematics 1

Wygeneruj PDF dla tej strony

Topics in Discrete Mathematics 1 - opis przedmiotu

Cel przedmiotu

Understanding advanced concepts of discrete mathematics in theoretical and algorithmic aspects.

Wymagania wstępne

Zapisz zmiany

Discrete Mathematics 1, Linear Algebra

Zakres tematyczny

LECTURES/CLASSES

1. Selected classes of graphs and their properties.
2. Selected classes of digraphs and their properties.
3. Digraph algorithms.
4. Boolean algebras. Boolean functions.
5. Boolean formulas, minimization.
6. Applications of Boolean formulas in graph theory and computational problem complexity.

Metody kształcenia

Lecture: conventional lecture, conversational approach.

Exercises: classical problem-solving method.

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

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

Warunki zaliczenia

The final grade for the course is an average of positive grades from classes and the exam.

To pass the classes, students need to achieve a positive grade in written tests, be active during the classes, and present a prepared presentation.

To pass a written test, students need to score a minimum specified for that particular test.

To sit for the final exam, students must have a positive grade from the classes.

Literatura podstawowa

1. J. Bang-Jensen, G.Gutin, Digraphs, Theory and Algorithms, 2001.
2. M. C.  Golumbic, Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics 57, Elsevier, 2004.
3. T. Fujisawa, T. Kasami, Theory of discrete structures, Tokyo, 1984.
4. Ch. H. Papadimitriou, Computational Complexity, Helion, 2012.

Literatura uzupełniająca

1. H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science 209 (1998) 1-45.
2. A. Brandstadt, V.B. Le,  J.P. Spinrad, Graph Classes: a survey, SIAM 2004.
3. K. A. Ross, Ch. R. B. Wright, Discrete Mathematics, PWN, 2010.

Uwagi

The course is also offered in the semester VI.

Zmodyfikowane przez dr Ewa Sylwestrzak-Maślanka (ostatnia modyfikacja: 10-04-2024 16:19)