Teorie matroidů - NDMX065

• Anglický název: Matroid Theory
• Zajišťuje: Studijní oddělení (32-STUD)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: letní
• E-Kredity: 6
• Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Je zajišťováno předmětem: NDMI065
• Další informace: http://kam.mff.cuni.cz/~pangrac/vyuka/matroid.html
• Garant: RNDr. Ondřej Pangrác, Ph.D.
• Třída: DS, diskrétní modely a algoritmy; Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika
• Prerekvizity : {NXXX007, NXXX008, NXXX009}
• Neslučitelnost : NDMI065
• Záměnnost : NDMI065

Anotace

čeština

Poslední úprava: T_KAM (18.04.2010)

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

angličtina

Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (14.01.2005)

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.

Podmínky zakončení předmětu

Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (26.02.2019)

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.

Literatura

čeština

Poslední úprava: PANGRAC/MFF.CUNI.CZ (10.04.2010)

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

Oxley:Matroid theory

Truemper: Matroid decomposition

angličtina

Poslední úprava: IUUK (05.05.2014)

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

Oxley: Matroid theory.

Truemper: Matroid decomposition.

Požadavky ke zkoušce

Poslední úprava: RNDr. Ondřej Pangrác, Ph.D. (14.02.2019)

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.

Sylabus

čeština

Poslední úprava: PANGRAC/MFF.CUNI.CZ (10.04.2010)

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

angličtina

Poslední úprava: PANGRAC/MFF.CUNI.CZ (10.04.2010)

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.