SylabUZ
Course name | Topics in Discrete Mathematics |
Course ID | 11.1-WK-IiED-WZMD-Ć-S14_pNadGenODAI5 |
Faculty | Faculty of Mathematics, Computer Science and Econometrics |
Field of study | Informatics and Econometrics |
Education profile | academic |
Level of studies | Second-cycle studies leading to MS degree |
Beginning semester | winter term 2020/2021 |
Semester | 4 |
ECTS credits to win | 7 |
Course type | optional |
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 |
Lecture | 30 | 2 | - | - | Exam |
Class | 30 | 2 | - | - | Credit with grade |
Poznanie zaawansowanych pojęć matematyki dyskretnej w aspekcie teoretycznym i algorytmicznym
Matematyka dyskretna 1.
Wykład/ćwiczenia
1. Hipergrafy, podstawowe własności i sposoby reprezentacji.
2. Cykle w hipergrafie.
3. Hipergrafy konformalne, własność Helly
4. Grafy przecięć krawędzi hipergrafu, grafy średnie, własności algorytmiczne i ich zastosowania między innymi w relacyjnych bazach danych.
5. Grafy przedziałów, cięciwowe, k-drzewa.
6. Kolorowanie hipergrafów i jego złożoność obliczeniowa.
7. Skojarzenia, pokrycie i transwersale.
8. Prezentacja nierozwiązanych problemów hipergrafowych.
Wykład konwencjonalny; wykład konwersatoryjny; wykład problemowy.
Ćwiczenia – rozwiązywanie typowych zadań ilustrujących tematykę przedmiotu, ćwiczenia na zastosowanie teorii, rozwiązywanie zadań problemowych, przygotowanie przez studenta referatu na wybrany temat
Outcome description | Outcome symbols | Methods of verification | The class form |
Ocena końcowa przedmiotu: średnia pozytywnych ocen z ćwiczeń i z egzaminu.
Warunkiem zaliczenia ćwiczeń jest uzyskanie pozytywnej oceny ze sprawdzianów pisemnych, aktywności na ćwiczeniach oraz przygotowanego referatu.
Warunkiem zaliczenia sprawdzianu pisemnego jest uzyskanie ustalonej dla danego sprawdzianu minimalnej liczby punktów.
Warunkiem przystąpienia do egzaminu jest uzyskanie pozytywnej z ćwiczeń.
1. C. Berge, Graphs and Hypergraphs, North-Holland, Amsterdam, 1973.
2. M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics 57, Elsevier, 2004.
1. A. Brandstadt, V.B. Le, J.P. Spinrad, Graph Classes: a survey, SIAM 2004
Modified by dr Alina Szelecka (last modification: 05-06-2020 12:23)