SylabUZ

Wygeneruj PDF dla tej strony

Wybrane zagadnienia z matematyki dyskretnej - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Wybrane zagadnienia z matematyki dyskretnej
Kod przedmiotu 11.1-WK-IiED-WZMD-Ć-S14_pNadGenODAI5
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Informatyka i ekonometria
Profil ogólnoakademicki
Rodzaj studiów drugiego stopnia z tyt. magistra
Semestr rozpoczęcia semestr zimowy 2019/2020
Informacje o przedmiocie
Semestr 4
Liczba punktów ECTS do zdobycia 7
Typ przedmiotu obieralny
Język nauczania polski
Sylabus opracował
  • dr hab. Elżbieta Sidorowicz, prof. UZ
Formy zajęć
Forma zajęć Liczba godzin w semestrze (stacjonarne) Liczba godzin w tygodniu (stacjonarne) Liczba godzin w semestrze (niestacjonarne) Liczba godzin w tygodniu (niestacjonarne) Forma zaliczenia
Wykład 30 2 - - Egzamin
Ćwiczenia 30 2 - - Zaliczenie na ocenę

Cel przedmiotu

Poznanie zaawansowanych pojęć matematyki dyskretnej w aspekcie teoretycznym i algorytmicznym

Wymagania wstępne

Matematyka dyskretna 1.

Zakres tematyczny

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.

Metody kształcenia

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

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu Symbole efektów Metody weryfikacji Forma zajęć

Warunki zaliczenia

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ń.

Literatura podstawowa

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.

Literatura uzupełniająca

1. A. Brandstadt, V.B. Le, J.P. Spinrad, Graph Classes: a survey, SIAM 2004

Uwagi


Zmodyfikowane przez dr Robert Dylewski, prof. UZ (ostatnia modyfikacja: 17-09-2019 12:34)