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-MATD-WZMD-W-S14_pNadGenEX6NW
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Matematyka
Profil ogólnoakademicki
Rodzaj studiów drugiego stopnia z tyt. magistra
Semestr rozpoczęcia semestr zimowy 2019/2020
Informacje o przedmiocie
Semestr 2
Liczba punktów ECTS do zdobycia 7
Występuje w specjalnościach Informatyka matematyczna
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 miedzy 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. Brandstadt, V.B. Le, J.P. Spinrad, Graph Classes: a survey, SIAM 2004

Uwagi

Przedmiot oferowany również w semestrze IV.


Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 14-03-2020 09:10)