Poznanie zaawansowanych pojęć matematyki dyskretnej w aspekcie teoretycznym i algorytmicznym.
Wymagania wstępne
Matematyka dyskretna 1.
Zakres tematyczny
Wykład/ćwiczenia
Wybrane klasy grafów:grafy przedziałów, k-drzewa, cięciwowe, krawędziowe i ich własności.
Różne rodzaje dominowania w grafach.
Digrafy, definicje i oznaczenia.
Digrafy silnie spójne, tranzytywne i acykliczne, ich własności.
Wybrane algorytmy digrafowe.
Definicja matroidu. Przykłady i podstawowe własności.
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
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.
Egzamin.
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.
R. Distel, Graph Theory, Springer-Verlag, New York 1997.
R.J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 1998.
D. J. A. Welsh, Matroid theory, Academic Press, Inc., New York, 2010.
Literatura uzupełniająca
W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 2005.
H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth,Theoretical Computer Science 209 (1998) 1-45.
A. Brandstadt, V.B. Le, J.P.Spinrad, Graph Classes: a survey, SIAM 2004
Uwagi
Przedmiot oferowany również w semestrze IV.
Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 19-05-2022 21:46)
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.
