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

Wygeneruj PDF dla tej strony

Topics in Discrete Mathematics 2 - opis przedmiotu

Cel przedmiotu

Acquiring advanced concepts of discrete mathematics in both theoretical and algorithmic aspects.

Wymagania wstępne

Zapisz zmiany

Discrete Mathematics 1. Linear Algebra.

Zakres tematyczny

Lecture/classes

1. Hypergraphs, basic properties, and representations.
2. Cycles in hypergraphs.
3. Conformal hypergraphs, the Helly property.
4. Coloring hypergraphs and its computational complexity.
5. Matchings, coverings, and transversals.
6. Definition of a matroid.
7. Examples and basic properties of matroids.
8. Dual matroids. Submatroids.
9. Transversals, Hall's theorem. Transversal matroids. Rado's theorem on independent transversals.
10. Greedy algorithm, Rado-Edmonds theorem. Kruskal's theorem.

Metody kształcenia

Lecture: conventional, conversational.

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

Final grade for the course: the average of positive grades from classes and the exam.

To pass the classes, students need to obtain a positive grade from written tests, participate actively in classes, and prepare a presentation.

To pass a written test, students need to achieve a minimum number of points set for that particular test.

To be eligible for the exam, students must receive a positive overall grade from the classes.

Literatura podstawowa

1. C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.
2. D. J. A. Welsh, Matroid theory, Academic Press, Inc., New York, 2010.
3. R.J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 1998.

Literatura uzupełniająca

1. J. Oxley, Matroid Theory, Oxford University Press, 2006

Uwagi

Zmodyfikowane przez dr hab. Elżbieta Sidorowicz, prof. UZ (ostatnia modyfikacja: 12-01-2024 19:11)