SylabUZ
Nazwa przedmiotu | Matematyka dyskretna i matematyczne podstawy informatyki |
Kod przedmiotu | 11.0-WK-MATD-MDMPI-Ć-S14_pNadGenS3ESS |
Wydział | Wydział Matematyki, Informatyki i Ekonometrii |
Kierunek | Mathematics |
Profil | ogólnoakademicki |
Rodzaj studiów | drugiego stopnia z tyt. magistra |
Semestr rozpoczęcia | semestr zimowy 2018/2019 |
Semestr | 1 |
Liczba punktów ECTS do zdobycia | 7 |
Typ przedmiotu | obowiązkowy |
Język nauczania | polski |
Sylabus opracował |
|
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 |
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.
Opis efektu | Symbole efektów | Metody weryfikacji | Forma zajęć |
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.
Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 30-06-2018 07:59)