Selected Topics in matroid Theory - course description

General information

Course name	Selected Topics in matroid Theory
Course ID	11.1-WK-MATD-WZTM-Ć-S14_pNadGenRUX8L
Faculty	Faculty of Mathematics, Computer Science and Econometrics
Field of study	Mathematics
Education profile	academic
Level of studies	Second-cycle studies leading to MS degree
Beginning semester	winter term 2020/2021

Course information

Semester	3
ECTS credits to win	7
Available in specialities	Mathematical Informatics
Course type	optional
Teaching language	polish
Author of syllabus	prof. dr hab. Mieczysław Borowiecki dr hab. Elżbieta Sidorowicz, prof. UZ

Classes forms

The class form	Hours per semester (full-time)	Hours per week (full-time)	Hours per semester (part-time)	Hours per week (part-time)	Form of assignment
Class	30	2	-	-	Credit with grade
Lecture	30	2	-	-	Exam

Aim of the course

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.

Prerequisites

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

Scope

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.

Teaching methods

Wykład: konwencjonalny.

Ćwiczenia: klasyczna metoda problemowa.

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

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

Notes

Modified by dr Alina Szelecka (last modification: 05-06-2020 12:21)

Generate PDF for this page