Teoria matroidów - opis przedmiotu

Informacje ogólne

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

Informacje o przedmiocie

Semestr	2
Liczba punktów ECTS do zdobycia	2
Typ przedmiotu	obowiązkowy
Język nauczania	polski
Sylabus opracował	prof. dr hab. Mieczysław Borowiecki

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

Cel przedmiotu

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.

Wymagania wstępne

Zaliczona na poziomie studiów I stopnia: matematyka dyskretna, algebra liniowa.

Zakres tematyczny

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.

Metody kształcenia

Wykład: konwencjonalny.

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

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

Warunki zaliczenia

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.

Literatura podstawowa

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.

Literatura uzupełniająca

1. Wybrane artykuły z podanej tematyki.

Uwagi

Zmodyfikowane przez mgr Natalia Gawłowicz (ostatnia modyfikacja: 01-09-2017 09:17)