1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2022/2023
4. WMIiE - oferta ERASMUS - Program Erasmus
5. Discrete Mathematics and Mathematical Foundations of Computer Science

Wygeneruj PDF dla tej strony

Discrete Mathematics and Mathematical Foundations of Computer Science - opis przedmiotu

Cel przedmiotu

Differing and counting combinatorial objects. Using these capabilities, in order to estimate the size of the data and resources needed to solve the problem and study its complexity.

Wymagania wstępne

Zapisz zmiany

Completed vocational mathematical or technical studies.

Zakres tematyczny

Lecture
1. Elements of combinatorics: counting methods for labeled and unlabeled combinatorial objects, Polya’s Enumeration Theorem, extremal set theory (16 h).
2. Elements of graph theory: connectivity, matchings, Hall’s Theorem, Theorem, Ramsey’s Theorem (6 h).
3. The probabilistic method of Erdös (6 h).
4. Elements of counting theory: transition functions, automata, Turing machines, formal languages. (2 h).
 

Class
1. Elements of combinatorics:
a. combinatorial object recognition in the practical problems, the concept of functions operating on finite sets, which are free, injective, "on", decreasing, non-increasing, the usage of well-known formulas to count the identified objects (6 h),
b. application of Inclusion-Exclusion Principle and Pigeonhole Principle, double counting of labeled combinatorial objects (6 h),
c. application of Polya’s Enumeration Theorem in order to count unlabeled combinatorial objects (6 h).

2. Elements of graph theory:
a. recognition of notions of graph theory in practical tasks, application of well-known algorithms to solve these tasks (2 h),
b. estimation of small Ramsey numbers, proving theorems on Ramsey graphs and numbers by usage of the classical techniques presented during the lectures (2 h).
3. The probabilistic method of Erdös: prooving the facts on the combinatorial structures by usage of the naive method, the expected value method and Local Lovás Lemma (4 h).
4. Elements of the theory of computation: constructing programs for Turing machines, computability test function (2 h).
5. Test completion (2h).

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 lectures 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 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 exercises. The prerequisite to obtain a positive evaluation of the module is the positive evaluation of the exercise and the exam.

Literatura podstawowa

1. Diesel, Grach Theory, Springer-Verlag, Heidelberg, Gradule Test In Mathematics, Vol. 173.

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

3. C.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (seria Klasyka Informatyki).
 

Literatura uzupełniająca

1. Z. Palka, A. Ruciński, Wykłady z kombinatoryki, cz. I, WNT, Warszawa, 1998.
2. W. Lipski, Kombinatoryka dla programistów, WNT, 2005.
3. K.A. Ross, Ch.R.B. Wright, Discrete mathematics, 1996.
4. J.M. Aldous, R.J. Wilson, Graphs and applications, Springer, 2000..

Uwagi

Zmodyfikowane przez dr hab. Ewa Drgas-Burchardt, prof. UZ (ostatnia modyfikacja: 26-04-2022 15:03)