Matroid Theory - NDMX065

• Title: Teorie matroidů
• Form of teaching: lecture+practicals
• Guaranteed by: Student Affairs Department (32-STUD)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2022
• Duration in semesters: 1
• Semester: summer
• E-Credits: 6
• Hours per week, examination: summer s.:2/2, C+Ex [HT]
• Capacity: unlimited
• Maximum number of enrolled students: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech
• Teaching methods: full-time
• Is provided by: NDMI065
• Additional information: http://kam.mff.cuni.cz/~pangrac/vyuka/matroid.html
• Repeated enrollment: 2 / 2 / 2 / 2
• Guarantor: RNDr. Ondřej Pangrác, Ph.D.
• Class: DS, diskrétní modely a algoritmy; Informatika Mgr. - Diskrétní modely a algoritmy
• Classification: Informatics > Discrete Mathematics
• Pre-requisite : {NXXX007, NXXX008, NXXX009}
• Incompatibility : NDMI065
• Interchangeability : NDMI065

Annotation

English

Introduction to matroid theory - definitions (independent sets, basis, cycles, rank function), operations on matroids (duality and minors), matroidal connectivity, classes of matroids and their representations.

Last update: Pangrác Ondřej, RNDr., Ph.D. (14.01.2005)

Czech

Úvodní kurz teorie matroidů - definice matroidů (nezávislé množiny, báze, kružnice, ranková funkce), operace na matroidech (dualita a minory), souvislost matroidů, třídy matroidů a jejich reprezentace.

Last update: T_KAM (18.04.2010)

Course completion requirements

Na zápočet je potřeba získat 2/3 bodů z aktivity na cvičení. Body je možné doplnit domácími úkoly.

Zápočet je nutnou podmínkou pro konání zkoušky.

Last update: Pangrác Ondřej, RNDr., Ph.D. (26.02.2019)

Literature

English

D. Kráľ, O. Pangrác: Introduction to Matroid Theory (Lecture Notes), ITI Series 430, 2009.

Oxley: Matroid theory.

Truemper: Matroid decomposition.

Last update: IUUK (05.05.2014)

Czech

D.Král', O.Pangrác: Introduction to Matroid Theory (Lecture Notes), ITI series 430 (2009).

Oxley:Matroid theory

Truemper: Matroid decomposition

Last update: PANGRAC/MFF.CUNI.CZ (10.04.2010)

Course assessment methods and requirements for successful completion, grading scheme

Požadavky ke zkoušce odpovídají sylabu předmětu v rozsahu, v jakém byl pokryt na přednáškách a cvičeních.

Zkouška má obvykle ústní podobu s možností písemné přípravy. Zápočet je podmínkou pro konání zkoušky.

Last update: Pangrác Ondřej, RNDr., Ph.D. (14.02.2019)

Syllabus

English

Definitions and basic examples. Duality and minors. Connectivity of matroids and comparsion with graph connectivity. Matroid intersection theorem and its applications. Representability, representable, binary and regular matroids. Graphic matroids. Algorithmic aspects of matroids.

Last update: PANGRAC/MFF.CUNI.CZ (10.04.2010)

Czech

Definice a základní příklady. Dualita a minory. Souvislost matroidů a vztah ke grafové souvislosti. Matroid intersection theorem a jeho aplikace. Reprezentovatelnost, reprezentovatelné, binární a regulární matroidy. Grafové matroidy. Algoritmické aspekty matroidových problémů.

Last update: PANGRAC/MFF.CUNI.CZ (10.04.2010)