1. SylabUZ
2. Wydział Nauk Ścisłych i Przyrodniczych
3. semestr zimowy 2024/2025
4. WMIiE - oferta ERASMUS - Program Erasmus
5. Discrete Mathematics 1

Wygeneruj PDF dla tej strony

Discrete Mathematics 1 - opis przedmiotu

Cel przedmiotu

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

Wymagania wstępne

Zapisz zmiany

Introduction to mathematics, Linear algebra 1.

Zakres tematyczny

Lecture
1. Basic notions of the graph theory: neighbourhood, adjacency, isomorphism, paths, cycles, connectivity, subgraphs (2 h).
2. Graph matrixes (2 h).
3. Some classes of graphs (2 h).
4. Union, join and complement graph operations (2 h).
5. Trees and their properties (4 h).
6. BFS and DFS algorithms (2 h).
7. Vector spaces of the graph (2 h).
8. n-connectivity (2 h).
9. Eulerian graphs. Hamiltonian Graphs (3 h).
10. Planar graphs, Kuratowski’s Theorem, Harary’s Theorem (3 h).
11. Covers and independence (2 h).
12. Vertex colouring of graphs, list colouring of graphs, Brooks’s Theorem, the Szekeres-Wilf Theorem, Vizing’s Theorem, Thomassen’s Theorem (4 h).

Class
1. Reading information on a graph from its matrixes, adjacency lists, sets of pairs. Interpretation of operations on graph matrixes. Matrixes of graph operations (4 h).
2. Investigation of basic tree’s features. Counting labeled trees, using known algorithms to find a spanning tree of a graph, its sets of fundamental cycles and elementary cut. Generating of cycle and cut spaces of a graph. Construction of a modular decomposition tree of a graph (8 h).
3. Analysis of graph connectivity (2 h).
4. Investigation of Eulerian and Hamiltonian graphs and dependence of these properties on other features of graphs. Using known algorithms to recognize an Euler tour and a Hamilton cycle in a graph (4 h).
5. Recognition of problems associated with graph planarity, independence and covers numbers of a graph in practical exercises. Application of theoretical knowledge in practical problems on this topic (4 h).
6. Recognition of coloring problems in practice. Theoretical and algorithmic approach (6 h).
7. Test completion (2 h).

 

Metody kształcenia

Conversation lecture, traditional lecture, discussion exercises.

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

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

Warunki zaliczenia

Methods: D - participation in the discussions during the course P1 - essay P2 - written exam PU2 - oral exam S - self-esteem
Assessment of individual classes:
1. Checking of preparedness of students and their activity during exercise (D, S).
2. Colloquium with the tasks of different difficulty, allowing to evaluate whether the students have achieved specified learning outcomes in terms of skills and competencies (P1).
3. Conversation during the lecture in order to verify the effects of higher levels of education in terms of knowledge and skills (D, S).
4. Written exam to verify the learning outcomes in terms of knowledge and skills (P2).
5. Oral exam, which allows to complete student’s written [removed]PU2).
The grade of the module consists of the assessment exercise (50%), exam grade (P2 + PU2) (50%). The condition of the exam is to get a positive assessment of the exercise. The prerequisite to obtain a positive evaluation of the module is the positive evaluation of the exercise and the exam.

Literatura podstawowa

1. J.M. Aldous, R. Wilson, Graphs and applications, Springer, 2000.

2.  D. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River, 2001.

3. R. J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa, 1998.
 

Literatura uzupełniająca

1. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa, 1989.

Uwagi

Zmodyfikowane przez dr Dorota Głazowska (ostatnia modyfikacja: 18-04-2024 13:08)