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

Wygeneruj PDF dla tej strony

Matematyka dyskretna 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

1. Some classes of graphs, their properties and applications.
2. Various dominating sets in graphs.
3. Graph colouring, graph list-colouring, Theorems of Brooks, Szekeres-Wilf, Vizing, and Thomasen
4. Matroids and their properties. Rado-Edmond’s Theorem, Rado’s Theorem.
5. Definition and basic notations of digraphs. Acyclic and transitive digraphs.

CLASSES

1. The properties of intersection graphs, chordal graphs and their applications.
2. The properties of the chromatic number, the choice number, the domination numbers and their applications in tasks and practical issues. The basic graph colouring algorithms.
3. Classes of digraphs and their properties. Basic algorithms for digraphs.
4. Definition of the matroid, examples of matroids. The  greedy algorithm for the

Metody kształcenia

Lecture: problem lecture

Classes: solve of exercises, discussion

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

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

Warunki zaliczenia

Class. The final grade is issued on the points obtained during the classes and activity during the classes.

Lecture. The final grade is issued on the points of the final test.

Final course grade.The final grade consists of the class grade (50%) and the class grade (50%). The condition of passing the subject is a positive grade from both: the class and the lecture.

Literatura podstawowa

 

1. J. Bang-Jensen,  G. Gutin, Digraphs, Theory, Algorithms and Applications, Springer, 2001.
2. R. Diestel, Graph Theory, Springer-Verlag, New York, 1997.
3. D. J. A. Welsh, Matroid Theory, Academic Press, Inc., New York, 2010

 

Literatura uzupełniająca

K.A. Ross, Ch.R.B. Wright, Discrete Mathematic, Pearson Education, New Jersey, 2003

Uwagi

Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 21-11-2020 06:10)