SylabUZ
| Course name | Discrete Mathematics and Mathematical Foundations of Computer Science |
| Course ID | 11.0-WK-MATD-MDMPI-Ć-S14_pNadGenS3ESS |
| Faculty | Faculty of Mathematics, Computer Science and Econometrics |
| Field of study | Mathematics |
| Education profile | academic |
| Level of studies | Second-cycle studies leading to MS degree |
| Beginning semester | winter term 2019/2020 |
| Semester | 1 |
| ECTS credits to win | 7 |
| Course type | obligatory |
| Teaching language | polish |
| Author of syllabus |
|
| The class form | Hours per semester (full-time) | Hours per week (full-time) | Hours per semester (part-time) | Hours per week (part-time) | Form of assignment |
| Class | 30 | 2 | - | - | Credit with grade |
| Lecture | 30 | 2 | - | - | Exam |
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.
Completed vocational mathematical or technical studies.
Lecture
1. Elements of combinatorics: counting methods for labeled and unlabeled combinatorial objects, Polya’s Enumeration Theorem, extremal set theory (12 h).
2. Elements of graph theory: connectivity, matchings, Hall’s Theorem, Hamiltonian cycles, vertex and edge colorings, planarity, extremal graph theory questions, Turans’s 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, Church's assertions (6 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 (5 h),
b. application of Inclusion-Exclusion Principle and Pigeonhole Principle, double counting of labeled combinatorial objects (5 h),
c. application of Polya’s Enumeration Theorem in order to count unlabeled combinatorial objects (4 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 (6 h).
4. Elements of the theory of computation: constructing programs for Turing machines, computability test function (4 h).
5. Test completion (2h).
Conversation lecture, traditional lecture, discussion exercises.
| Outcome description | Outcome symbols | Methods of verification | The class form |
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.
1. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa, 1989.
2. C.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (seria Klasyka Informatyki).
3. Diesel, Grach Theory, Springer-Verlag, Heidelberg, Gradule Test In Mathematics, Vol. 173.
4. Kościelski, Teoria obliczeń, WUW, Wrocław, 1997.
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, Matematyka dyskretna, PWN, Warszawa, 1996.
4. R.J. Wilson, Wprowadzenie do teorii grafów, PWN, 1998.
Modified by dr Robert Dylewski, prof. UZ (last modification: 20-09-2019 11:20)
