1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2022/2023
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/ćwiczenia

1. Wybrane klasy grafów: grafy przedziałów,  cięciwowe, krawędziowe, k-drzewa,  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. Digrafy, definicje i oznaczenia.
5. Digrafy silnie spójne, tranzytywne, acykliczne, ich własności.
6. Wybrane algorytmy digrafowe.

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

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. R. Distel, Graph Theory, Springer-Verlag, New York 1997
3. R. J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 1998.

Literatura uzupełniająca

1. W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 2005.
2. H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth,Theoretical Computer Science 209 (1998) 1-45.
3. V.B. Brandstadt, J.P. Le, Spinrad, Graph Classes: a survey, SIAM 2004.

Uwagi

Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 19-05-2022 21:47)