1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2019/2020
4. Informatyka i ekonometria - pierwszego stopnia z tyt. licencjata
5. Matematyka dyskretna 2

Wygeneruj PDF dla tej strony

Matematyka dyskretna 2 - opis przedmiotu

Cel przedmiotu

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

Wymagania wstępne

Zapisz zmiany

Matematyka dyskretna 1.

Zakres tematyczny

Wykład

1. Grafy przecięć rodzin zbiorów, krawędziowe, totalne, przedziałowe i cięciwowe; ich własności i zastosowania.
2.  Różne rodzaje dominowania w grafach.
3. Kolorowanie grafów (klasyczne, z listy), twierdzenia Brooksa, Szekeres-Wilf, Vizinga, Thomassena.
4. Matroidy i ich własności, twierdzenie Rado-Edmondsa, twierdzenie Rado o niezależnych transwersalach.
5. Digrafy, definicje i oznaczenia, digrafy tranzytywne i acykliczne, ich własności.

Ćwiczenia

1. Badanie własności grafów przecięć i cięciwowych ze szczególnym zwróceniem uwagi na zastosowania tych grafów.
2. Rozpoznawanie w zadaniach z treścią problemów grafowych związanych z kolorowaniem i dominowaniem. Teoretyczne i algorytmiczne rozwiązywanie tego typu problemów, w szczególności znajdowanie liczby chromatycznej i liczb dominujących grafu. Dowodzenie prostych faktów teoretycznych związanych z tą tematyką.
3. Klasy digrafów i ich własności.  Algorytmy digrafowe.
4. 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.

Metody kształcenia

Wykład konwersatoryjny, wykład tradycyjny, ćwiczenia dyskusyjne.

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ęć:

1.      Sprawdzanie stopnia przygotowania studentów oraz ich aktywności w trakcie ćwiczeń.

2.      Kolokwium z zadaniami o zróżnicowanym stopniu trudności, pozwalające na ocenę czy i w jakim stopniu, student osiągnął wymienione efekty kształcenia głównie w zakresie umiejętności i kompetencji.

3.      Konwersacja podczas wykładu w celu weryfikacji wyższych poziomów efektów kształcenia w zakresie wiedzy i umiejętności.

4.      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 wykładu (50%). Warunkiem zaliczenia przedmiotu jest uzyskanie pozytywnych ocen zaliczających ćwiczenia i wykład.

Literatura podstawowa

1. J. Bang-Jensen, G. Gutin, Digraphs, Theory and Algorithms, 2001.
2. K. A. Ross, Ch. R. B. Wright, Matematyka dyskretna, PWN, Warszawa, 1996.
3. R. J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 1998.
4. D. J. A. Welsh, Matroid theory, Academic Press, Inc., New York, 2010.

Literatura uzupełniająca

1. W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 2005.
2. N. Abbas, Graph clustering: Complexity, sequential and parallel algorithms, Ph.D. Thesis, University of Alberta, Edmonton, Canada, 1995.
3. M. Faber, Characterizations of strongly chordal graphs, Discrete Math. 43 (1983) 173–189.

Uwagi

Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 13-05-2021 12:03)