SylabUZ
Course name | Discrete Mathematics 2 |
Course ID | 11.1-WK-IiEP-MD2-W-S14_pNadGenR7E9T |
Faculty | Faculty of Mathematics, Computer Science and Econometrics |
Field of study | Informatics and Econometrics |
Education profile | academic |
Level of studies | First-cycle studies leading to Bachelor's degree |
Beginning semester | winter term 2018/2019 |
Semester | 6 |
ECTS credits to win | 4 |
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 |
Class | 30 | 2 | - | - | Credit with grade |
Lecture | 30 | 2 | - | - | Credit with grade |
Poznanie zaawansowanych pojęć matematyki dyskretnej w aspekcie teoretycznym i algorytmicznym.
Matematyka dyskretna 1.
Wykład
1. Grafy przecięć rodzin zbiorów, krawędziowe, totalne, przedziałowe, łukowe i inne; ich własności i zastosowania (6 godz.).
2. Różne rodzaje dominowania w grafach (4 godz.).
3. Kolorowanie grafów (klasyczne, z listy), twierdzenia Brooksa, Szekeres-Wilf, Vizinga, Thomassena (8 godz.).
4. Matroidy i ich własności, twierdzenie Rado-Edmondsa, twierdzenie Rado o niezależnych transwersalach (6 godz.).
5. Digrafy, definicje i oznaczenia, digrafy tranzytywne i acykliczne, ich własności (6 godz.).
Ćwiczenia
1. Rozpoznawanie w zadaniach z treścią problemów grafowych związanych z kolorowaniem i dominowaniem. Teoretyczne i algorytmiczne rozwiązywanie tego typu problemów, w szczególności znajdowanie liczby chromatycznej i liczb dominujących grafu. Dowodzenie prostych faktów teoretycznych związanych z tą tematyką (8 godz.).
2. Badanie własności grafów przecięć ze szczególnym zwróceniem uwagi na zastosowania tych grafów (6 godz.).
3. Macierzowe reprezentacje digrafów w kontekście badania ich własności w szczególności tranzytywności i acykliczności, analiza algorytmów digrafowych (6 godz.).
4. Zapoznanie się z pojęciem matroidu z uwzględnieniem matroidu grafowego, kografowego, wektorowego i jednorodnego. Badanie własności matroidu poprzez dowodzenie prostych faktów związanych z tym pojęciem. Poznanie znaczenia tej struktury w kontekście algorytmu zachłannego (8 godz.).
Kolokwium zaliczeniowe (2 godz.).
Wykład konwersatoryjny, wykład tradycyjny, ćwiczenia dyskusyjne.
Outcome description | Outcome symbols | Methods of verification | The class form |
Warunki zaliczenia poszczególnych zajęć:
1. Sprawdzanie stopnia przygotowania studentów oraz ich aktywności w trakcie ćwiczeń.
2. Kolokwium z zadaniami o zróżnicowanym stopniu trudności, pozwalające na ocenę czy i w jakim stopniu, student osiągnął wymienione efekty kształcenia głównie w zakresie umiejętności i kompetencji.
3. Konwersacja podczas wykładu w celu weryfikacji wyższych poziomów efektów kształcenia w zakresie wiedzy i umiejętności.
4. Praca pisemna weryfikująca efekty kształcenia w zakresie wiedzy i kompetencji zdobyte podczas wykładu.
Na ocenę z przedmiotu składa się ocena z ćwiczeń (50%) i ocena z wykładu (50%). Warunkiem zaliczenia przedmiotu jest uzyskanie pozytywnych ocen zaliczających ćwiczenia i wykład.
1. J. Bang-Jensen, G.Gutin, Digraphs, Theory and Algorithms, 2001.
2. K. A. Ross, Ch. R. B. Wright, Matematyka dyskretna, PWN, Warszawa, 1996.
3. R. J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa 1998.
1. W. Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 2005.
2. N. Abbas, Graph clustering: Complexity, sequential and parallel algorithms, Ph.D. Thesis, University of Alberta, Edmonton, Canada, 1995.
3. M. Faber, Characterizations of strongly chordal graphs, Discrete Math. 43 (1983) 173–189.
Modified by dr Robert Dylewski, prof. UZ (last modification: 04-05-2018 19:24)