SylabUZ

Wygeneruj PDF dla tej strony

Matematyka dyskretna 1 - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Matematyka dyskretna 1
Kod przedmiotu 11.1-WK-MATP-MD1-Ć-S14_pNadGenKDJP9
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Mathematics
Profil ogólnoakademicki
Rodzaj studiów pierwszego stopnia z tyt. licencjata
Semestr rozpoczęcia semestr zimowy 2018/2019
Informacje o przedmiocie
Semestr 2
Liczba punktów ECTS do zdobycia 6
Typ przedmiotu obowiązkowy
Język nauczania polski
Sylabus opracował
  • dr hab. Ewa Drgas-Burchardt, prof. UZ
Formy zajęć
Forma zajęć Liczba godzin w semestrze (stacjonarne) Liczba godzin w tygodniu (stacjonarne) Liczba godzin w semestrze (niestacjonarne) Liczba godzin w tygodniu (niestacjonarne) Forma zaliczenia
Ćwiczenia 30 2 - - Zaliczenie na ocenę
Wykład 30 2 - - Egzamin

Cel przedmiotu

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

Wymagania wstępne

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. V. Bryant, Aspekty kombinatoryki, WNT, Warszawa, 1997.
2. W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 2005.
3. K.A. Ross, Ch.R.B. Wright, Matematyka dyskretna, PWN, Warszawa 1996.
4. R. J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa, 1998.
5. D. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River, 2001.

Literatura uzupełniająca

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

Uwagi


Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 07-07-2018 09:14)