1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2023/2024
4. Computer science and econometrics - pierwszego stopnia z tyt. licencjata
5. Discrete Mathematics 2

Wygeneruj PDF dla tej strony

Discrete Mathematics 2 - opis przedmiotu

Cel przedmiotu

The course introduces advance notions and ideas of discrete mathematics in theoretic and algorithmic aspects.

Wymagania wstępne

Zapisz zmiany

Discrete Mathematics 1

Zakres tematyczny

LECTURE/CLASSES
1. Selected classes of graphs: interval graphs, chordal graphs, edge graphs, k-trees, their properties, and applications.
2. Various types of domination in graphs.
3. Graph coloring (classic, from a list), theorems by Brooks, Szekeres-Wilf, Vizing, Thomassen.
4. Digraphs, definitions, and notations.
5. Strongly connected digraphs, transitive, acyclic, their properties.
6. Selected digraph algorithms.

Metody kształcenia

Traditional lecture; auditory exercises where students solve problems.

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu	Symbole efektów	Metody weryfikacji	Forma zajęć

Warunki zaliczenia

Conditions for passing classes and lectures:

1. Checking students' level of preparedness and their activity during exercises.
2. A test with tasks of varying difficulty levels, allowing assessment of whether and to what extent a student has achieved the mentioned learning outcomes, mainly in terms of skills and competencies.
3. Conversation during the lecture to verify higher levels of learning outcomes in terms of knowledge and skills.
4. A written test verifying learning outcomes in terms of knowledge and competencies acquired during the lecture.

The final grade for the course consists of the exercise grade (50%) and the lecture grade (50%). The condition for passing the course is obtaining positive passing grades for both exercises and the lecture.

Literatura podstawowa

1. J. Bang-Jensen, G. Gutin, Digraphs, Theory and Algorithms, 2001. 
2. R. Distel, Graph Theory, Springer-Verlag, New York 2017. 
3. V.B. Brandstadt, J.P. Le, Spinrad, Graph Classes: a survey, SIAM 2004.

Literatura uzupełniająca

H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth,Theoretical Computer Science 209 (1998) 1-45.

Uwagi

Zmodyfikowane przez dr Ewa Synówka (ostatnia modyfikacja: 10-04-2024 20:25)