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 1

Wygeneruj PDF dla tej strony

Matematyka dyskretna 1 - opis przedmiotu

Cel przedmiotu

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

Wymagania wstępne

Zapisz zmiany

Linear Algebra 1

Zakres tematyczny

LECTURES

1. Fundamental counting rules, Inclusion-Exclusion Principle,  Pigeonhole Principle.
2. Recursion.
3. Basic notions of  graph theory: neighbourhood, adjacency, isomorphism, paths, cycles, n-connectivity, subgraphs.
4. Some classes of graphs. Union, join and complement graph operations.
5. Trees, binary trees.
6. BFS and DFS algorithms.
7. Vector spaces of  the graph.
8. n-connectivity of graphs.
9. Eulerian graphs. Hamiltonian Graphs.
10. Planar  graphs, the characterization of planar graphs .
11. Covers, independence and domination.
12. System of distinct representatives, Hall’s Theorem, the perfect maching  of  the bipartite graph.

CLASSES

1. Application of fundamental counting rules in exercises.
2. Application of Inclusion-Exclusion principle in exercises.
3. Proving combinatorial identities.
4. Solving recurrence relations by   characteristic equations or by induction.
5. Basic graph theory notation. Graph matrices and other kinds of graph representations. Basic graph operations.
6. Properties of trees, counting labelled trees. BFS, DFS-algorithm, fundamental circuits and fundamental bonds.
7. Connectivity of graphs.
8. Algorithms for determining Eulerian and Hamiltonian cycles. Properties of Eulerian and Hamiltonian graphs.
9. Euler’s Theorem and Kuratowski’s Theorem for planar graphs.
10. Independence number, covering number, domination number in graphs
11. Applications of Hall’s Thorem.

Metody kształcenia

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. V. Bryant, Aspects of Combinatorics, Cambridge University Press, 2000.
2. K.A. Ross, Ch.R.B. Wright, Discrete Mathematic, Pearson Education, New Jersey, 2003.
3. R. J. Wilson, Introduction to Graph Theory, Pearson Education Limited, United Kingdom, 2010.

 

Literatura uzupełniająca

Uwagi

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