SylabUZ
Nazwa przedmiotu | Teoria matroidów |
Kod przedmiotu | 11.1-WK-MATT-TeoMatr-S17 |
Wydział | Wydział Matematyki, Informatyki i Ekonometrii |
Kierunek | Matematyka |
Profil | ogólnoakademicki |
Rodzaj studiów | doktoranckie |
Semestr rozpoczęcia | semestr zimowy 2017/2018 |
Semestr | 6 |
Liczba punktów ECTS do zdobycia | 1 |
Typ przedmiotu | obowiązkowy |
Język nauczania | polski |
Sylabus opracował |
|
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 |
Zapoznanie z podstawowymi pojęciami, metodami teorii matroidów oraz wyposażenie doktorantów w podstawowe narzędzia matematyczne niezbędne do formułowania i rozwiązywania typowych zadań i problemów z zakresu matematyki dyskretnej z wykorzystaniem matroidów.
Zaliczona na poziomie studiów I stopnia: matematyka dyskretna, algebra liniowa.
Definicja matroidu. Przykłady i podstawowe własności matroidów. Własności baz, cykli, funkcji rangi i domknięcia w matroidach.
Algorytm zachłanny, twierdzenie Rado-Edmondsa. Twierdzenie Kruskala.
Matroidy dualne, hiperpłaszczyzny matroidu, matroid cykli i matroid kocykli grafu. Rodziny matroidalne.
Kraty geometryczne a matroidy proste. Podmatroidy; minory i ich reprezentacja w kracie.
Transwersale, twierdzenie Halla. Matroidy transwersalne. Twierdzenie Rado o niezależnych transwersalach. Suma matroidów i przykłady jej zastosowań.
Reprezentacja wektorowa matroidów. Reprezentacja matroidów grafowych, matroidy binarne.
Systemy niezależności, problem wyznaczania bazy o największej wadze.
Wykład: konwencjonalny.
Opis efektu | Symbole efektów | Metody weryfikacji | Forma zajęć |
Forma zaliczenia przedmiotu – egzamin.
Ocena końcowa przedmiotu: średnia ocena z egzaminu pisemnego i ustnego.
Warunkiem zaliczenia egzaminu jest uzyskanie pozytywnej oceny ostatecznej z egzaminu pisemnego i ustnego.
1. D.J.A. Welsh, Matroid Theory, Academic Press, London 1976.
2. R.J. Wilson, Wprowadzenie do teorii grafów, PWN, 1998.
3. M. Lipski, Kombinatoryka dla programistów, WNT, 2004 (seria Klasyka Informatyki).
4. J. Oxley, Matroid Theory, Oxford University Press, 2011.
1. Wybrane artykuły z podanej tematyki.
Zmodyfikowane przez mgr Natalia Gawłowicz (ostatnia modyfikacja: 01-09-2017 10:17)