Poznanie zaawansowanych pojęć matematyki dyskretnej w aspekcie teoretycznym i algorytmicznym.
Prerequisites
Matematyka dyskretna 1.
Scope
Wykład
Różne rodzaje dominowania w grafach.
Grafy przecięć rodzin zbiorów, krawędziowe, totalne, przedziałowe i cięciwowe; ich własności i zastosowania.
Digrafy, definicje i oznaczenia, digrafy tranzytywne i acykliczne, ich własności.
Matroidy i ich własności, twierdzenie Rado-Edmondsa, twierdzenie Rado o niezależnych transwersalach.
Ćwiczenia
Badanie własności grafów przecięć i cięciwowych ze szczególnym zwróceniem uwagi na zastosowania tych grafów.
Rozpoznawanie w zadaniach z treścią problemów grafowych związanych z dominowaniem. Teoretyczne i algorytmiczne rozwiązywanie tego typu problemów, w szczególności znajdowanie liczb dominujących grafu. Dowodzenie prostych faktów teoretycznych związanych z tą tematyką.
Klasy digrafów i ich własności. Algorytmy digrafowe.
Zapoznanie się z pojęciem matroidu z uwzględnieniem matroidu grafowego, kografowego, wektorowego i jednorodnego. Badanie własności matroidu poprzez dowodzenie prostych faktów związanych z tym pojęciem. Poznanie znaczenia tej struktury w kontekście algorytmu zachłannego.
Learning outcomes and methods of theirs verification
Outcome description
Outcome symbols
Methods of verification
The class form
Assignment conditions
Warunki zaliczenia poszczególnych zajęć:
Sprawdzanie stopnia przygotowania studentów oraz ich aktywności w trakcie ćwiczeń.
Sprawdzian, podczas ćwiczeń, z zadaniami o zróżnicowanym stopniu trudności, pozwalający na ocenę czy i w jakim stopniu, student osiągnął wymienione efekty kształcenia głównie w zakresie umiejętności i kompetencji.
Konwersacja podczas wykładu w celu weryfikacji wyższych poziomów efektów kształcenia w zakresie wiedzy i umiejętności.
Praca pisemna weryfikująca efekty kształcenia w zakresie wiedzy i kompetencji zdobyte podczas wykładu.
Na ocenę z przedmiotu składa się ocena z ćwiczeń (50%) i ocena z egzaminu (50%). Warunkiem przystąpienia do egzaminu jest uzyskanie pozytywnej oceny z ćwiczeń. Warunkiem zaliczenia przedmiotu jest uzyskanie pozytywnych ocen zaliczających ćwiczenia i wykład.
Recommended reading
J. Bang-Jensen, G.Gutin, Digraphs, Theory and Algorithms, 2001.
K. A. Ross, Ch.R.B. Wright, Matematyka dyskretna, PWN, Warszawa, 1996.
R.J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 1998.
D. J. A. Welsh, Matroid theory, Academic Press, Inc., New York, 2010.
Further reading
W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 2005.
N. Abbas, Graph clustering: Complexity, sequential and parallel algorithms, Ph.D. Thesis, University of Alberta, Edmonton, Canada, 1995.
M. Faber, Characterizations of strongly chordal graphs, Discrete Math. 43 (1983) 173–189.
Notes
Przedmiot oferowany również w semestrze IV.
Modified by dr Alina Szelecka (last modification: 19-10-2020 13:24)