1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2021/2022
4. Matematyka - drugiego stopnia z tyt. magistra
5. Wybrane zagadnienia z matematyki dyskretnej 2

Wygeneruj PDF dla tej strony

Wybrane zagadnienia z matematyki dyskretnej 2 - opis przedmiotu

Cel przedmiotu

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

Wymagania wstępne

Zapisz zmiany

Matematyka dyskretna 1, Algebra liniowa 1

Zakres tematyczny

Wykład/ćwiczenia

1. Hipergrafy, podstawowe własności i sposoby reprezentacji.
2. Cykle w hipergrafie.
3. Hipergrafy konformalne, własność Helly.
4. Kolorowanie hipergrafów i jego złożoność obliczeniowa.
5. Skojarzenia, pokrycie i transwersale.
6. Definicja matroidu. Przykłady i podstawowe własności matroidu.
7. Matroidy dualne. Podmatroidy.
8. Transwersale, twierdzenie Halla. Matroidy transwersalne. Twierdzenie Rado o niezależnych transwersalach.
9. Algorytm zachłanny, twierdzenie Rado-Edmondsa. Twierdzenie Kruskala.

Metody kształcenia

Wykład: konwencjonalny, konwersatoryjny.

Ćwiczenia: klasyczna metoda problemowa.

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

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

Warunki zaliczenia

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ń.

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: 08-05-2021 14:25)