Poznanie zaawansowanych pojęć matematyki dyskretnej w aspekcie teoretycznym i algorytmicznym.
Wymagania wstępne
Matematyka dyskretna 1.
Zakres tematyczny
Wykład
Różne rodzaje dominowania w grafach (6 godz.).
Grafy przecięć rodzin zbiorów, krawędziowe, totalne, przedziałowe, łukowe i inne; ich własności i zastosowania (8 godz.).
Digrafy, definicje i oznaczenia, digrafy tranzytywne i acykliczne, ich własności (8 godz.).
Matroidy i ich własności, twierdzenie Rado-Edmondsa, twierdzenie Rado o niezależnych transwersalach (8 godz.).
Ćwiczenia
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ą (6 godz.).
Badanie własności grafów przecięć ze szczególnym zwróceniem uwagi na zastosowania tych grafów (6 godz.).
Macierzowe reprezentacje digrafów w kontekście badania ich własności w szczególności tranzytywności i acykliczności, analiza algorytmów digrafowych (8 godz.).
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 (8 godz.).
Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się
Opis efektu
Symbole efektów
Metody weryfikacji
Forma zajęć
Warunki zaliczenia
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.
Literatura podstawowa
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.
Literatura uzupełniająca
W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 2005.
Uwagi
Przedmiot oferowany również w semestrze VI.
Zmodyfikowane przez dr Robert Dylewski, prof. UZ (ostatnia modyfikacja: 09-04-2017 16:24)
Ta strona używa ciasteczek (cookies), dzięki którym nasz serwis może działać lepiej. Korzystając z niniejszej strony, wyrażasz zgodę na ich używanie. Dowiedz się więcej.