SylabUZ

Wygeneruj PDF dla tej strony

Wybrane zagadnienia z teorii matroidów - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Wybrane zagadnienia z teorii matroidów
Kod przedmiotu 11.1-WK-MATD-WZTM-Ć-S14_pNadGenRUX8L
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Matematyka
Profil ogólnoakademicki
Rodzaj studiów drugiego stopnia z tyt. magistra
Semestr rozpoczęcia semestr zimowy 2018/2019
Informacje o przedmiocie
Semestr 3
Liczba punktów ECTS do zdobycia 7
Typ przedmiotu obieralny
Język nauczania polski
Sylabus opracował
  • prof. dr hab. Mieczysław Borowiecki
  • 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
Ćwiczenia 30 2 - - Zaliczenie na ocenę
Wykład 30 2 - - Egzamin

Cel przedmiotu

Zapoznanie z podstawowymi pojęciami, metodami teorii matroidów oraz wyposażenie studentów w podstawowe narzędzia matematyczne niezbędne do formułowania i rozwiązywania typowych, prostych zadań i problemów z zakresu studiowanego kierunku studiów.

Wymagania wstępne

Zaliczona: Matematyka dyskretna 1, Algebra liniowa 1, Algebra ogólna.

Zakres tematyczny

  1. Definicja matroidu. Przykłady i podstawowe własności matroidów. Własności baz, cykli, funkcji rangi i domknięcia w matroidach.
  2. Algorytm zachłanny, twierdzenie Rado-Edmondsa. Twierdzenie Kruskala.
  3. Matroidy dualne, hiperpłaszczyzny matroidu, matroid cykli i matroid kocykli grafu. Rodziny matroidalne.
  4. Kraty geometryczne a matroidy proste. Podmatroidy; minory i ich reprezentacja w kracie.
  5. Transwersale, twierdzenie Halla. Matroidy transwersalne. Twierdzenie Rado o niezależnych transwersalach. Suma matroidów i przykłady jej zastosowań.
  6. Reprezentacja wektorowa matroidów. Reprezentacja matroidów grafowych, matroidy binarne.
  7. Systemy niezależności, problem wyznaczania bazy o największej wadze.

Metody kształcenia

Wykład: konwencjonalny.

Ćwiczenia: klasyczna metoda problemowa.

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 oraz aktywności na ćwiczeniach.

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. D. J. A. Welsh, Matroid Theory, Academic Press, London 1976.
  2. R. J. Wilson, Wprowadzenie do teorii grafów, PWN, 2008.
  3. M. Lipski, Kombinatoryka dla programistów, WNT, 2004 (seria Klasyka Informatyki).

Literatura uzupełniająca

Wybrane artykuły z podanej tematyki.

Uwagi


Zmodyfikowane przez dr Robert Dylewski, prof. UZ (ostatnia modyfikacja: 25-04-2018 20:16)