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 1

Wygeneruj PDF dla tej strony

Discrete Mathematics 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 matching  of  the bipartite graph.

CLASSES

1. Recognizing combinatorial objects in problem statements. Utilizing known formulas for counting these objects.

2. Applying the inclusion-exclusion principle, the partition principle in problem-solving.

3. Proving simple combinatorial identities.

4. Establishing recursive relations. Solving homogeneous recurrence equations using characteristic equations and mathematical induction.

5. Introduction to fundamental concepts in graph theory, examples illustrating these concepts. Discussion of graph representation methods, basic graph classes, and operations on graphs through examples.

6. Exploring fundamental properties of trees. Counting labeled trees, graph traversal using established algorithms involving the construction of sets of fundamental cycles and elementary cuts. Generating cycle spaces and graph cuts.   

7. Connectivity of graphs.

8. Determining Eulerian and Hamiltonian cycles in a graph, using appropriate algorithms. Problems related to properties of Eulerian and Hamiltonian graphs.

9. Graph planarity, problems applying Euler's and Kuratowski's theorems.

10. Finding independence numbers and covers as well as dominations in a graph, applying these concepts in practical problems.

11. Problems applying Hall's theorem.

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

The final grade for the course consists of classes grades (50%) and lecture grades (50%). The condition for obtaining a positive final grade is to receive positive grades for both classes and lectures. The condition for taking the lecture exam is to obtain a positive grade for the classes.

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

R. Diestel, Graph Theory, Springer-Verlag, New York, 2017.

Uwagi

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